Seite 2 von 2

Re: 10. Übungsblatt

Verfasst: 17. Feb 2009 09:02
von The One and Only Markus
Also ich finde im Buch wird das recht eindeutig definiert. Demnach ist eine Kollision "ein Paar (x, x') aus D² von Strings, für die x ungleich x' und h(x) = h(x') gilt." Fasse ich jetzt diese Tupel alle in einer Menge zusammen habe ich alle Kollisionen und die Mächtigkeit der Menge ist dann eben die Anzahl der Kollisionen.

Re: 10. Übungsblatt

Verfasst: 17. Feb 2009 14:24
von evel
könnte vielleicht noch mal jemand das finden der kollision aus der G2 ausführlicher erläutern. ich verstehe noch nicht so genau was mir der zusammenhang mit den fibonacci-zahlen bringt.
danke!

Re: 10. Übungsblatt

Verfasst: 17. Feb 2009 17:46
von Commander
Vielleicht könnte nochmal jemand kurz überhaupt erkären, wie ihr da auf eine Kollision kommt. Wenn ich das mit den beiden werten (1, 10947) ausprobiere, kommt irgendwie nicht h(1)=h(10947) raus...danke

Re: 10. Übungsblatt

Verfasst: 19. Feb 2009 10:28
von Siggi
Commander hat geschrieben:Vielleicht könnte nochmal jemand kurz überhaupt erkären, wie ihr da auf eine Kollision kommt. Wenn ich das mit den beiden werten (1, 10947) ausprobiere, kommt irgendwie nicht h(1)=h(10947) raus...danke
Also das ist nicht schwer, wenn man das einfach in die Formel einsetzt:
\(\frac{1+\sqrt 5} 2\) für 1 ist \(a=1.6180333\) . Nun ist \(a mod 1 = a - \lfloor a \rfloor = 1.6180333 - 1 = 0.6180333 = b\) und
\(\lfloor 10000*b\rfloor = \lfloor 6180.333 \rfloor = 6180\).

Nun das gleiche für 10947:
\(10947*\frac{1+\sqrt 5} 2=17712.61807=a\) . Nun ist \(a mod 1 = a - \lfloor a \rfloor = 17712.61807 - 17712 = 0.61807 = b\) und
\(\lfloor 10000*b\rfloor = \lfloor 6180.7 \rfloor = 6180\).

Aber wie kommt man auf die Werte, wenn man das mit der Fibonaccizahl und dem Goldenen Schnitt nicht kennt? Unser Tutor meinte einfach ausprobieren, was in der Klausur ein bisschen blöd sein wird.

Re: 10. Übungsblatt

Verfasst: 21. Feb 2009 17:25
von Dreamdancer
Zu der Kompressionsfunktion: Im Buch auf S.194 wird auch von der Länge n auf die Länge n abgebildet, wenn man den Schlüssel nicht mitrechnet. Also muss man den Schlüssel wohl mitrechnen, sonst wäre es keine Kompressionsfunktion. Ergo muss man auf dem Aufgabenblatt die Permutation wohl auch mitrechnen, also ist es auch hier eine Kompressionsfunktion.

Ich glaube, um die Aufgabe zu lösen, muss man sich ein Kleines Programm schreiben. Wahrscheinlich wurde die Aufgabe auch so erstellt :shock:

Re: 10. Übungsblatt

Verfasst: 23. Feb 2009 15:48
von HeyHey
Hallo,
ich hab mal ne Frage zum Geburtstagsangriff. In der Vorlesung und in der Übung wurde die Formel mit log(2) benutzt. In meinem Buch (3. Ausgabe) steht sie allerdings mit ln(2) drin. Was ist denn jetzt richtig?
Übrigens stimmt dann der Wert in der Musterlösung nicht. Mit log(2) kommt 78 als Lösung raus, 118 bekommt man nur, wenn man mit dem ln(2) rechnet.

Re: 10. Übungsblatt

Verfasst: 23. Feb 2009 16:15
von blowfish
auch im buch ist der ln gemeint. fände es auch besser, wenn das tatsächlich da stehen würde. allerdings kann man sich das auch überlegen, wenn man einen blick in die herleitung wirft. dort taucht häufiger das e auf und keine einzige 10.

Re: 10. Übungsblatt

Verfasst: 23. Feb 2009 16:17
von jno
Die Notationen log und ln meinen eigentlich auch das Gleiche, nämlich den natürlichen Logarithmus. Vielleicht dachtest du ja "log" würde den Logarithmus zur Basis 10 bezeichnen, aber ich glaube der wird, wenn überhaupt, dann mit lg abgekürzt, am besten jedoch einfach \(\log_{10}\).

Re: 10. Übungsblatt

Verfasst: 23. Feb 2009 18:38
von Tristan
\(\log\) ist definiert als die Umkehrfunktion zu \(\exp\). Da alle Logarithmen bereits durch einen Logarithmus bestimmt sind, reicht der Eine auch - deswegen heißt der einfach \(\log\).

Re: 10. Übungsblatt

Verfasst: 23. Feb 2009 21:01
von Hyst
richtig... und um die Klugscheisserei fortzusetzen:
bei log ist wichtig, das man jetzt den Exponenten ausrechnen will. es ist dabei im Grunde wurscht welche Basis zugrunde liegt.

klar, wenn man einen bestimmten wert explizit ausrechnen möchte, muss man wissen über welchen Logarithmus man spricht, damit man den genauen wert bekommt. allerdings geht es meistens nur um den Logarithmus als abstraktes Konstrukt. Quasi der IDEE des Logarithmierens.

außerdem gilt für (fast) alle zahlen a und b:
\(\log_a(x) = \frac{1}{\log_b(a)}\cdot \log_b(x) = c \cdot \log_b(x)\)
somit unterscheiden sich zwei Logarithmen nur um einen konstanten Faktor. insofern ist es wirklich wurscht welcher benutzt wird. denn multipliziert man mit der richtigen Konstante, dann kommt schon das richtige raus ;)

im Zweifelsfall gilt: in beweisen ist immer der Logarithmus gemeint, bei dem der Beweis klappt! völlig egal ob dort: log, ln oder lg steht.

Re: 10. Übungsblatt

Verfasst: 24. Feb 2009 23:20
von HeyHey
Naja, mit der richtigen Konstante multipliziert kriegt man in den meisten Fällen das richtige Ergebnis raus, egal was man vorher hat :)
Ich bin wirklich davon ausgegangen, dass es der Logarithmus zur Basis 10 ist.
Danke für die Antworten und viel Erfolg morgen! :wink: