10. Übungsblatt

erik.tews
Computerversteher
Computerversteher
Beiträge: 326
Registriert: 5. Jan 2004 20:48

10. Übungsblatt

Beitrag von erik.tews »

Ist online

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: 10. Übungsblatt

Beitrag von bruse »

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.

Benutzeravatar
Tristan
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 22. Okt 2008 20:32

Re: 10. Übungsblatt

Beitrag von Tristan »

Das würde ich auch gerne mal wissen.

erik.tews
Computerversteher
Computerversteher
Beiträge: 326
Registriert: 5. Jan 2004 20:48

Re: 10. Übungsblatt

Beitrag von erik.tews »

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.

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: 10. Übungsblatt

Beitrag von bruse »

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.

Hyst
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 5. Mai 2007 22:20

Re: 10. Übungsblatt

Beitrag von Hyst »

hatte da jemand zu viele tabs/fenster offen?

Benutzeravatar
Tristan
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 22. Okt 2008 20:32

Re: 10. Übungsblatt

Beitrag von Tristan »

Wie sieht es mit einer Antwort zu der eigentlichen Frage aus?

erik.tews
Computerversteher
Computerversteher
Beiträge: 326
Registriert: 5. Jan 2004 20:48

Re: 10. Übungsblatt

Beitrag von erik.tews »

Hallo

Wir basteln noch an einer Lösung.

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: 10. Übungsblatt

Beitrag von bruse »

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.

Benutzeravatar
taufrisch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 107
Registriert: 30. Sep 2007 02:42
Wohnort: 127.0.0.1

Re: 10. Übungsblatt

Beitrag von taufrisch »

\(\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.
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.

Benutzeravatar
\Hannes
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 18. Nov 2005 17:24

Re: 10. Übungsblatt

Beitrag von \Hannes »

Wicked :twisted:
Schwabbeldiwapp hier kommt die Grütze.

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: 10. Übungsblatt

Beitrag von bruse »

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.

The One and Only Markus
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 169
Registriert: 10. Nov 2005 19:28
Wohnort: Darmstadt

Re: 10. Übungsblatt

Beitrag von The One and Only Markus »

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.

erik.tews
Computerversteher
Computerversteher
Beiträge: 326
Registriert: 5. Jan 2004 20:48

Re: 10. Übungsblatt

Beitrag von erik.tews »

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.

AhGuGu
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 8. Dez 2005 13:21

Re: 10. Übungsblatt

Beitrag von AhGuGu »

Hallo,
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.
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 2.: Eigentlich hast du recht.
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?

gruß Ahgugu

Antworten

Zurück zu „Archiv“