10. Übungsblatt
10. Übungsblatt
Ist online
Re: 10. Übungsblatt
Servus. Bei der Aufgabe 2 des 10. Blattes war ja eine Kollision der Hashfunktion gefragt. Es ist auch eine angegeben, allerdings ohne Lösungsweg. Wie kommt man denn auf diese Kollision?
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.
Re: 10. Übungsblatt
Das würde ich auch gerne mal wissen.
Re: 10. Übungsblatt
Nein, ist ja noch nen Monat.
Vermutlich verschieben wir Krypto um 30 Minuten für die EiSE schreiber, so dass genug Zeit für beide Klausuren bleibt. Für ein ausgiebiges Mittagessen mit anschließender Ganzkörpermassage zur Entspannung zwischen den beiden Klausuren wird aber vermutlich keine Zeit mehr bleiben.
Vermutlich verschieben wir Krypto um 30 Minuten für die EiSE schreiber, so dass genug Zeit für beide Klausuren bleibt. Für ein ausgiebiges Mittagessen mit anschließender Ganzkörpermassage zur Entspannung zwischen den beiden Klausuren wird aber vermutlich keine Zeit mehr bleiben.
Re: 10. Übungsblatt
Erstmal danke für die Info. Das war aber sicher die Antwort auf die Frage aus einem anderen Thread, oder?
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.
Re: 10. Übungsblatt
hatte da jemand zu viele tabs/fenster offen?
Re: 10. Übungsblatt
Wie sieht es mit einer Antwort zu der eigentlichen Frage aus?
Re: 10. Übungsblatt
Hallo
Wir basteln noch an einer Lösung.
Wir basteln noch an einer Lösung.
Re: 10. Übungsblatt
Irgendwoher muss die auf dem Lösungsblatt angegebene Kollision ja gekommen sein. Mich interessiert eigentlich nur der Ansatz, wie man darauf kommt. Die Kollision ist ja nicht so, dass man sie sofort erkennt, und Durchprobieren von 10.000 Werten kann ja kaum verlangt worden sein. Da Sie eine solche Kollision auf dem Blatt angegeben haben, müssen Sie ja einen solchen Ansatz (bezogen auf dieses spezifische Problem) kennen. Den hätt' ich gern gewusst, am liebsten noch vor der Klausur.
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.
Re: 10. Übungsblatt
\(\frac{1+\sqrt 5} 2\)ist der goldene Schnitt \(\varphi\), und für die Fibonaccizahlen \(F_n\) gilt \(lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\varphi\), d.h. wenn du \(n\) groß genug wählst gilt \(F_{n+1}\approx\varphi F_n\).
Damit ist \(\varphi F_n\) bis auf einen kleinen, von \(n\) abhängigen Fehler eine ganze Zahl (und ein kleines \(\epsilon\ mod\ 1\) das du nur noch hinter die vierte Stelle nach den Komma drücken mußt). Bei \(F_{20}=6765\) bekommst du die erste Kollision mit \(h(2)=2360=h(2+6765)\).
Die Musterlösung nimmt \(F_{21}=10946\) und \(h(1)=6180=h(1+F_{21})\), alle Fibonaccizahlen über der zwanzigsten funktionieren.
Damit ist \(\varphi F_n\) bis auf einen kleinen, von \(n\) abhängigen Fehler eine ganze Zahl (und ein kleines \(\epsilon\ mod\ 1\) das du nur noch hinter die vierte Stelle nach den Komma drücken mußt). Bei \(F_{20}=6765\) bekommst du die erste Kollision mit \(h(2)=2360=h(2+6765)\).
Die Musterlösung nimmt \(F_{21}=10946\) und \(h(1)=6180=h(1+F_{21})\), alle Fibonaccizahlen über der zwanzigsten funktionieren.
Zuletzt geändert von taufrisch am 6. Feb 2009 02:45, insgesamt 1-mal geändert.
Premature optimization is the root of all evil.
Don't anthropomorphize computers: They hate that.
Don't anthropomorphize computers: They hate that.
Re: 10. Übungsblatt
Cool, danke.
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.
-
- Endlosschleifenbastler
- Beiträge: 169
- Registriert: 10. Nov 2005 19:28
- Wohnort: Darmstadt
Re: 10. Übungsblatt
Hi,
mal 2 kleine Anmerkungen zur G1:
1. In der Aufgabe wird nach der Anzahl der Kollisionen gefragt, in der Lösung stehen aber die Anzahl verschiedener Ausgaben. Das hat doch aber erstmal garnichts mit der Lösung zu tun. Beispiel für die Permutation (1,3,2): Da ist als Anzahl verschiedener Ausgaben 2 angegeben, die Anzahl an Kollisionen beträgt doch eigentlich 24, da eine Kollision im Buch als Paar von 2 ungleichen Strings definiert ist, für die h(x) gleich ist. Wobei ich diese Definition für etwas merkwürdig halte, da in dem genannten Beispiel ja z.B. (000, 011) und (011, 000) schon als 2 Kollisionen zählen würde. Ist dass denn so sinnvoll?
2. Die Funktion in der Aufgabe ist überhaupt keine Kompressionsfkn. da die Länge von x gleich der Länge von h(x) ist.
mal 2 kleine Anmerkungen zur G1:
1. In der Aufgabe wird nach der Anzahl der Kollisionen gefragt, in der Lösung stehen aber die Anzahl verschiedener Ausgaben. Das hat doch aber erstmal garnichts mit der Lösung zu tun. Beispiel für die Permutation (1,3,2): Da ist als Anzahl verschiedener Ausgaben 2 angegeben, die Anzahl an Kollisionen beträgt doch eigentlich 24, da eine Kollision im Buch als Paar von 2 ungleichen Strings definiert ist, für die h(x) gleich ist. Wobei ich diese Definition für etwas merkwürdig halte, da in dem genannten Beispiel ja z.B. (000, 011) und (011, 000) schon als 2 Kollisionen zählen würde. Ist dass denn so sinnvoll?
2. Die Funktion in der Aufgabe ist überhaupt keine Kompressionsfkn. da die Länge von x gleich der Länge von h(x) ist.
Re: 10. Übungsblatt
zu 1.: Wir haben nicht wirklich erklärt wie wir Kollisionen zählen, wenn z. B. die Funktion für 3 Eingabewerte die gleiche Ausgabe liefert. Also sind das dann 2 oder 3 Kollisionen. Um die Lösung klarer formulieren zu können, stehen nur die Anzahl der unterschiedlichen Ausgaben da.
zu 2.: Eigentlich hast du recht.
zu 2.: Eigentlich hast du recht.
Re: 10. Übungsblatt
Hallo,
gruß Ahgugu
Vor dem Problem stand ich auch. Wie würde sowas inder Klausur ausschauen? Eine Bearbeitung analog zur Musterlösung würde ja wohl kaum zur gewünschten Maximalpunktzahl führen. Mein Vorschlag wäre, in der Aufgabe die Zählweise zu definieren.erik.tews hat geschrieben:zu 1.: Wir haben nicht wirklich erklärt wie wir Kollisionen zählen, wenn z. B. die Funktion für 3 Eingabewerte die gleiche Ausgabe liefert. Also sind das dann 2 oder 3 Kollisionen. Um die Lösung klarer formulieren zu können, stehen nur die Anzahl der unterschiedlichen Ausgaben da.
Unsere Tutorin versuchte uns das so zu erklären: Die Permutation gehört als Parameter dazu, sprich die Funktion sollte wohl h(pi, x) lauten. Damit würde es sich doch dann um eine Kompressionsfunktion (wenn auch in etwas anderer Notation) handeln, oder?erik.tews hat geschrieben: zu 2.: Eigentlich hast du recht.
gruß Ahgugu