[Mathe/Informatik] Habe Fragen zu Algorithmen

[Wouzhuo]

Hallo Selfler!

Es gibt da ja diese vielen tollen Möglichkeiten in der Mathematik. Da kann man z.B. eine Funktion schreiben, die gewisse Daten auf gewisse Weise auf andere Daten abbildet. Ich hab in diesem Zusammenhang z.B. "bijektiv" und "surjektiv" oder so gehört. Nun frage ich mich z.B: angenommen ich habe 10 zufällige natürliche Zahlen und möchte eine Funktion schreiben, die jede dieser 10 Zahlen auf zwei andere zufällige natürliche Zahlen im Bereich von X bis Y abbildet.

Wie geht das? Wie kann man soetwas lernen, bzw. hat dieses "Gebiet" vielleicht sogar einen eigenen Namen?
Wäre toll, wenn sich jemand damit auskennt und mir weiterhelfen könnte. Ich bin einfach neugierig, wie man soetwas anstellt.

Viele Grüße.

[Vinzenz Mai]

Hallo,

Nun frage ich mich z.B: angenommen ich habe 10 zufällige natürliche Zahlen

unterschiedliche oder dürfen sie auch gleich sein?

und möchte eine Funktion schreiben, die jede dieser 10 Zahlen auf zwei andere zufällige natürliche Zahlen im Bereich von X bis Y abbildet.

unterschiedliche oder dürfen sie auch gleich sein?

Wie geht das?

das hängt von der Aufgabenstellung ab :-)
Deine skizzierte ist noch nicht präzise genug.

Wie kann man soetwas lernen, bzw. hat dieses "Gebiet" vielleicht sogar einen eigenen Namen?

im Prinzip gehören solche Fragestellungen zur Kombinatorik.

Freundliche Grüße

Vinzenz

[Wouzhuo]

Hallo,

Nun frage ich mich z.B: angenommen ich habe 10 zufällige natürliche Zahlen

unterschiedliche oder dürfen sie auch gleich sein?

Das war zwar nur ein Beispiel, damit ihr versteht, was ich gerne wissen möchte, aber ich kann das Beispiel natürlich konkretisieren:

10 unterschiedliche Zahlen zwischen 40 und 300.

und möchte eine Funktion schreiben, die jede dieser 10 Zahlen auf zwei andere zufällige natürliche Zahlen im Bereich von X bis Y abbildet.

unterschiedliche oder dürfen sie auch gleich sein?

Müssen unterschiedlich sein. Die gebildete Zahl muss auf die ursprüngliche zurückzuführen sein.

Wie kann man soetwas lernen, bzw. hat dieses "Gebiet" vielleicht sogar einen eigenen Namen?

im Prinzip gehören solche Fragestellungen zur Kombinatorik.

Naja, aber wie geht man an so eine Aufgabenstellung heran?

[steckl]

Hi,

Es gibt da ja diese vielen tollen Möglichkeiten in der Mathematik. Da kann man z.B. eine Funktion schreiben, die gewisse Daten auf gewisse Weise auf andere Daten abbildet. Ich hab in diesem Zusammenhang z.B. "bijektiv" und "surjektiv" oder so gehört. Nun frage ich mich z.B: angenommen ich habe 10 zufällige natürliche Zahlen und möchte eine Funktion schreiben, die jede dieser 10 Zahlen auf zwei andere zufällige natürliche Zahlen im Bereich von X bis Y abbildet.

Kann es sein, dass du lineare Abbildung meinst?
Dabei werden Vektoren aus einem Vektrorraum in einen anderen abgebildet. In deinem Beispiel wäre es vom R^1 nach R^2 (eindimensional nach zweidimensional). Wobei ich nicht weiß, was der von dir angegebene Bereich X bis Y sein soll.

Wie geht das? Wie kann man soetwas lernen, bzw. hat dieses "Gebiet" vielleicht sogar einen eigenen Namen?

Suche nach linearer Abbildung.
Also ich habe das mal in einer Mathe-Vorlesung gelernt, aber so wie es bei Wikipedia erklärt ist kann ich es nicht nachvollziehen. Also würde ich mir lieber irgendwo anders eine Anleitung anschauen.

mfG,
steckl

[Wouzhuo]

Hi,

Es gibt da ja diese vielen tollen Möglichkeiten in der Mathematik. Da kann man z.B. eine Funktion schreiben, die gewisse Daten auf gewisse Weise auf andere Daten abbildet. Ich hab in diesem Zusammenhang z.B. "bijektiv" und "surjektiv" oder so gehört. Nun frage ich mich z.B: angenommen ich habe 10 zufällige natürliche Zahlen und möchte eine Funktion schreiben, die jede dieser 10 Zahlen auf zwei andere zufällige natürliche Zahlen im Bereich von X bis Y abbildet.

Kann es sein, dass du lineare Abbildung meinst?

Naja, vermutlich meine ich generell "Abbildungen" und wie man sie nach eigenen Wünschen "baut".

Dabei werden Vektoren aus einem Vektrorraum in einen anderen abgebildet. In deinem Beispiel wäre es vom R^1 nach R^2 (eindimensional nach zweidimensional). Wobei ich nicht weiß, was der von dir angegebene Bereich X bis Y sein soll.

Beispiel: du hast die Zahlen 13, 17, 38 und sollst jede dieser Zahlen mittels einer Funktion auf eine Zahl im Bereich 100 bis 115 abbilden. Ich bezweifel dabei aber, dass man aus der neuen Zahl durch eine "Umkehrung" der Funktion die ursprüngliche Zahl erhalten kann, weil ja ein großer Zahlenraum (13-38) auf einen kleinen (100-115) abgebildet wird. Das wird wohl kaum ohne Informationsverlust gehen. Aber angenommen man hätte nicht 100 bis 115 sondern 100 bis 215, wie würde eine solche Funktion aussehen?

Wie geht das? Wie kann man soetwas lernen, bzw. hat dieses "Gebiet" vielleicht sogar einen eigenen Namen?

Suche nach linearer Abbildung.

Danke, ich werde mal ein bisschen Googeln.

[Vinzenz Mai]

Hallo,

Beispiel: du hast die Zahlen 13, 17, 38 und sollst jede dieser Zahlen mittels einer Funktion auf eine Zahl im Bereich 100 bis 115 abbilden. Ich bezweifel dabei aber, dass man aus der neuen Zahl durch eine "Umkehrung" der Funktion die ursprüngliche Zahl erhalten kann, weil ja ein großer Zahlenraum (13-38) auf einen kleinen (100-115) abgebildet wird.

wenn Dein Ziel die Umkehrbarkeit der Abbildung ist, benötigst Du eine bijektive Abbildung.

Freundliche Grüße

Vinzenz

[Gunnar Bittersmann]

@@Wouzhuo:

nuqneH

Beispiel: du hast die Zahlen 13, 17, 38 und sollst jede dieser Zahlen mittels einer Funktion auf eine Zahl im Bereich 100 bis 115 abbilden.

OK, das tut die Funktion f = {(13, 111), (17, 103), (38, 115)}

Oder auch die Funktion g = {(13, 107), (17, 107), (38, 112)}

Ich bezweifel dabei aber, dass man aus der neuen Zahl durch eine "Umkehrung" der Funktion die ursprüngliche Zahl erhalten kann

f ist umkehrbar: f⁻¹ = {(111, 13), (103, 17), (115, 38)}

g ist allerdings nicht umkehrbar: g⁻¹ = {(107, 13), (107, 17), (112, 38)} ist keine Funktion, da der 107 zwei Werte zugeordnet sind.

Durchaus möglich, dass ich aus deiner Beschreibung nicht schlau werde, was du eigentlich wissen willst.

Qapla'

[Wouzhuo]

@@Wouzhuo:

nuqneH

Beispiel: du hast die Zahlen 13, 17, 38 und sollst jede dieser Zahlen mittels einer Funktion auf eine Zahl im Bereich 100 bis 115 abbilden.

OK, das tut die Funktion f = {(13, 111), (17, 103), (38, 115)}

Oder auch die Funktion g = {(13, 107), (17, 107), (38, 112)}

Jep. Kannst du diese Funktion auch so erweitern, dass ich dynamisch aus dem Zahlenbereich zwischen 13 und 38 noch 5 weitere Zahlen geben kann, die sie immer auf 5 weitere bestimmte Zahlen (also ohne Zufall) abbildet?

Also ich sag dir z.B. noch 14 (du wusstest aber nicht, dass ich wählen würde; hätte auch 36 sein können) und deine Funktion soll diese Zahl nach irgendwelchen Regeln z.B. auf 113 abbilden. Und zwar immer wenn ich der Funktion die Zahl 14 gebe. Und außerdem soll eine weitere Funktion aus der 113 die 14 bestimmen.

Wie gelingt es mir eine solche Funktion zu schreiben? Was ist, wenn ich z.B. _nicht_ möchte, dass aus der neuen Zahl auf die alte geschlossen werden kann? Was ist, wenn ich möchte, dass die erste Funktion f eine Zahl erhält, mit dieser Zahl etwas macht, sodass ich entweder Zahl X _oder_ Zahl Y erhalte (Zufall), dass man aber nur durch X wieder auf die ursprüngliche Zahl kommt (mit einer anderen Funktion), nicht aber durch Y.
Wie geht man an solche Aufgaben ran? Wie schreibt man solche Funktionen? Das muss doch irgendein mathematisches Gebiet sein, wozu es Informationen gibt.

Durchaus möglich, dass ich aus deiner Beschreibung nicht schlau werde, was du eigentlich wissen willst.

Ich möchte mit dem Beispiel nur zeigen, was ich generell gerne lernen möchte.

[Gunnar Bittersmann]

@@Wouzhuo:

nuqneH

Das muss doch irgendein mathematisches Gebiet sein, wozu es Informationen gibt.

Kryptographie

Qapla'

[steckl]

Hi,

Ein Beispiel:
Wertebereich: 0-10
Zielbereich: 200-300
Abbildungsfunktion f(x):= x*10+200
Damit kannst du jede Zahl x eindeutig abbilden.
Die Umkehrfunktion wäre dann:
f⁻¹(x) := (x-200)/10
Damit kommst du wieder auf die ursprüngliche Zahl.

Es gibt aber beliebig viele Abbildungsfunktionen, die du verwenden könntest.

Wie gelingt es mir eine solche Funktion zu schreiben? Was ist, wenn ich z.B. _nicht_ möchte, dass aus der neuen Zahl auf die alte geschlossen werden kann?

Das hört sich nach hashing an. Dabei kannst du beliebig große Mengen auf eine kleine abbilden.
Ein sehr einfaches Beispiel wäre die Quersumme:
Die Zahlen 13,22,31 haben alle die Quersumme 4. Also kannst du von der 4 nicht mehr auf die ursprüngliche Zahl schließen.

Was ist, wenn ich möchte, dass die erste Funktion f eine Zahl erhält, mit dieser Zahl etwas macht, sodass ich entweder Zahl X _oder_ Zahl Y erhalte (Zufall), dass man aber nur durch X wieder auf die ursprüngliche Zahl kommt (mit einer anderen Funktion), nicht aber durch Y.

Du könntest einfach 2 Zahlen erzeugen und dann mit einem Zufallsgenerator entscheiden welche der beiden du verwendest. Dafür würde mir aber kein praktischer Anwendungsfall einfallen. Vor allem weiß du ja dann am Schluss auch nicht, ob du dann X oder Y als Ergebnis erhalten hast.

mfG,
steckl

[Wouzhuo]

Hi,

Ein Beispiel:
Wertebereich: 0-10
Zielbereich: 200-300
Abbildungsfunktion f(x):= x*10+200
Damit kannst du jede Zahl x eindeutig abbilden.
Die Umkehrfunktion wäre dann:
f⁻¹(x) := (x-200)/10
Damit kommst du wieder auf die ursprüngliche Zahl.

Ah, ich habe etwas wichtiges vergessen (was ich ausversehen einfach so vorausgesetzt habe): das ganze soll möglichst "zufällig" sein. Soll heißen, wenn ich die ersten 5 Zahlen abgebildet habe, dann soll jemand, der die Funktion nicht kennt, nicht (oder nicht ohne weiteres) voraussagen können, auf welche Zahl die 6 abgebildet wird.

Es gibt aber beliebig viele Abbildungsfunktionen, die du verwenden könntest.

Wie gelingt es mir eine solche Funktion zu schreiben? Was ist, wenn ich z.B. _nicht_ möchte, dass aus der neuen Zahl auf die alte geschlossen werden kann?

Das hört sich nach hashing an. Dabei kannst du beliebig große Mengen auf eine kleine abbilden.
Ein sehr einfaches Beispiel wäre die Quersumme:
Die Zahlen 13,22,31 haben alle die Quersumme 4. Also kannst du von der 4 nicht mehr auf die ursprüngliche Zahl schließen.

Soetwas geht als _ausschließlich_ unter Informationsverlust oder? Wobei, was ist mit unendlichen Reihen? Angenommen ich möchte eine x-beliebige natürrliche Zahl (sagen wir 42) auf eine andere x-beliebige Zahl (sagen wir 23) abbilden. Kann man eine Funktion dafür schreiben, die _nicht_ "reversibel" ist, _obwohl_ es sozusagen für jede Zahl auch nur eine feste neue Zahl gibt?

Was ist, wenn ich möchte, dass die erste Funktion f eine Zahl erhält, mit dieser Zahl etwas macht, sodass ich entweder Zahl X _oder_ Zahl Y erhalte (Zufall), dass man aber nur durch X wieder auf die ursprüngliche Zahl kommt (mit einer anderen Funktion), nicht aber durch Y.

Du könntest einfach 2 Zahlen erzeugen und dann mit einem Zufallsgenerator entscheiden welche der beiden du verwendest.

Hm, ich muss erstmal nach darüber nachdenken.

Dafür würde mir aber kein praktischer Anwendungsfall einfallen. Vor allem weiß du ja dann am Schluss auch nicht, ob du dann X oder Y als Ergebnis erhalten hast.

Ja, das wäre dann unklar. Es ging mir mehr ums akademische, nicht um einen praktischen Nutzen. Ich will nur wissen, wie man solche Algorithmen entwirft.

Grüße.

[Der Martin]

Hallo,

Ah, ich habe etwas wichtiges vergessen (was ich ausversehen einfach so vorausgesetzt habe): das ganze soll möglichst "zufällig" sein. Soll heißen, wenn ich die ersten 5 Zahlen abgebildet habe, dann soll jemand, der die Funktion nicht kennt, nicht (oder nicht ohne weiteres) voraussagen können, auf welche Zahl die 6 abgebildet wird.

für mich sieht das langsam so aus, als suchtest du keine Funktion im Sinne einer mathematischen Abbildung, sondern eine schlichte Zuordnungstabelle. Und da die Zuordnung umkehrbar sein soll, dürfen weder in der linken, noch in der rechten Spalte Werte mehrfach vorkommen.

Soetwas geht als _ausschließlich_ unter Informationsverlust oder?

Nein. Solange du mathematische oder logische Operationen verwendest, die umkehrbar eindeutig sind (Additionen, Multiplikationen, bitweise XOR, ...), geht's ohne Informationsverlust.

Wobei, was ist mit unendlichen Reihen? Angenommen ich möchte eine x-beliebige natürrliche Zahl (sagen wir 42) auf eine andere x-beliebige Zahl (sagen wir 23) abbilden. Kann man eine Funktion dafür schreiben, die _nicht_ "reversibel" ist, _obwohl_ es sozusagen für jede Zahl auch nur eine feste neue Zahl gibt?

Ich sehe das Problem so: Sobald du deine Abbildung über eine mathematische Vorschrift machst, ganz gleich wie aufwendig die Formel sein mag, kann der Algorithmus -zumindest mit beliebig vielen gegebenen x/y-Paaren- "erraten" werden. Und dann sind mit hinreichend großer Wahrscheinlichkeit auch neue, bislang unbekannte Funktionswerte zu erraten.

Ciao,
 Martin

[Wouzhuo]

Hallo,

Ah, ich habe etwas wichtiges vergessen (was ich ausversehen einfach so vorausgesetzt habe): das ganze soll möglichst "zufällig" sein. Soll heißen, wenn ich die ersten 5 Zahlen abgebildet habe, dann soll jemand, der die Funktion nicht kennt, nicht (oder nicht ohne weiteres) voraussagen können, auf welche Zahl die 6 abgebildet wird.

für mich sieht das langsam so aus, als suchtest du keine Funktion im Sinne einer mathematischen Abbildung, sondern eine schlichte Zuordnungstabelle.

Nein, dort müsste ich ja selbst die Werte eintragen. Genau das möchte ich nicht.

Soetwas geht als _ausschließlich_ unter Informationsverlust oder?

Nein. Solange du mathematische oder logische Operationen verwendest, die umkehrbar eindeutig sind (Additionen, Multiplikationen, bitweise XOR, ...), geht's ohne Informationsverlust.

Ich meinte: eine Funktion ist nur dann nicht umkehrbar, wenn die Ausgangswertebereich kleiner als der Eingangswertebereich ist.

Wobei, was ist mit unendlichen Reihen? Angenommen ich möchte eine x-beliebige natürrliche Zahl (sagen wir 42) auf eine andere x-beliebige Zahl (sagen wir 23) abbilden. Kann man eine Funktion dafür schreiben, die _nicht_ "reversibel" ist, _obwohl_ es sozusagen für jede Zahl auch nur eine feste neue Zahl gibt?

Ich sehe das Problem so: Sobald du deine Abbildung über eine mathematische Vorschrift machst, ganz gleich wie aufwendig die Formel sein mag, kann der Algorithmus -zumindest mit beliebig vielen gegebenen x/y-Paaren- "erraten" werden.

Und dann sind mit hinreichend großer Wahrscheinlichkeit auch neue, bislang unbekannte Funktionswerte zu erraten.

Jeder gute Verschlüsselungsalgorithmus versucht doch aber zu erreichen, dass man trotz eines Klartexts + Geheimtext nicht auf den Schlüssel kommt.

[Gunnar Bittersmann]

@@Wouzhuo:

nuqneH

für mich sieht das langsam so aus, als suchtest du keine Funktion im Sinne einer mathematischen Abbildung, sondern eine schlichte Zuordnungstabelle.

Eine Zuordnungstabelle _ist_ eine Funktion im Sinne einer mathematischen Abbildung, sofern sie eindeutig ist.

Ausgangswertebereich

AKA Wertebereich.

Eingangswertebereich

Der heißt üblicherweise Definitionsbereich.

Qapla'

[Christian Kruse]

你好 Wouzhuo,

Jeder gute Verschlüsselungsalgorithmus versucht doch aber zu erreichen, dass man trotz eines Klartexts + Geheimtext nicht auf den Schlüssel kommt.

Naja, das kriegen symmetrische Algorithmen aber auch nur durch die Einbindung von Zufall hin, und das auch nur mäßig. Lies mal Dave the Laser Unicorn, das ist eine recht interessante Darlegung zu dem Thema.

再见,
 克里斯蒂安

[Gunnar Bittersmann]

@@Wouzhuo:

nuqneH

Ich bezweifel dabei aber, dass man aus der neuen Zahl durch eine "Umkehrung" der Funktion die ursprüngliche Zahl erhalten kann, weil ja ein großer Zahlenraum (13-38) auf einen kleinen (100-115) abgebildet wird.

In beiden Intervalle gibt es unendlich viele Zahlen. Woher also deine Zweifel?

Ein tiefer Blick in die Glaskugel: Meinst du mit „Zahlen“ ausschließlich ganze Zahlen? (Die Mathematik hat in den letzten Jahrhunderten einige Fortschritte gemacht. ;-))

Aber angenommen man hätte nicht 100 bis 115 sondern 100 bis 215, wie würde eine solche Funktion aussehen?

Die Möglichkeiten sind unbegrenzt.

Noch ein tiefer Blick in die Glaskugel: Meinst du mit „Funktion“ eine lineare Funktion (eine solche, die als Graphen eine Gerade hat)?

Qapla'

[Wouzhuo]

@@Wouzhuo:

nuqneH

Ich bezweifel dabei aber, dass man aus der neuen Zahl durch eine "Umkehrung" der Funktion die ursprüngliche Zahl erhalten kann, weil ja ein großer Zahlenraum (13-38) auf einen kleinen (100-115) abgebildet wird.

In beiden Intervalle gibt es unendlich viele Zahlen. Woher also deine Zweifel?

Ich sprach von natürlichen Zahlen. Ansonsten hättest du natürlich ;) Recht.

[Gunnar Bittersmann]

@@Wouzhuo:

nuqneH

Ich sprach von natürlichen Zahlen.

Echt? Nochmal nachgeschaut … Tatsächlich, das tatest du. Wer lesen kann, ist klar im Vorteil.

Wenn der Wertebereich kleiner ist als der Definitionsbereich, dann ist die Funktion natürlich nicht umkehrbar.

Qapla'

[Christian Kruse]

你好 Gunnar,

(Die Mathematik hat in den letzten Jahrhunderten einige Fortschritte gemacht. ;-))

Hehe, naja, irrationale Zahlen sind seit Jahrtausenden bekannt, rationale Zahlen sogar noch länger. Die alten Ägypter kannten z. B. [latex]\sqrt{2}[/latex] schon auf 5 Stellen hinter dem Komma, während die Griechen bereits etwa 500 AC den Beweis angetreten haben, dass [latex]\sqrt{2}[/latex] irrational ist. So richtig viel Fortschritt war in den letzten Jahrhunderten also nicht nötig, um den Zahlenraum zu vervollständigen ;)

再见,
 克里斯蒂安

[Andreas Pflug]

Hehe, naja, irrationale Zahlen sind seit Jahrtausenden bekannt, rationale Zahlen sogar noch länger [...]

Naja, wenn man in Gruppen wie de.sci.mathematik guckt, scheinen das
einige bis heute noch nicht mitbekommen zu haben ;-)

(SCNR)

Andreas