10. Übungsblatt

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 »

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.

evel
Erstie
Erstie
Beiträge: 19
Registriert: 16. Nov 2007 11:08

Re: 10. Übungsblatt

Beitrag 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!

Commander
Neuling
Neuling
Beiträge: 10
Registriert: 11. Mai 2005 17:37

Re: 10. Übungsblatt

Beitrag 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

Siggi
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 101
Registriert: 15. Okt 2006 12:46

Re: 10. Übungsblatt

Beitrag 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.

Dreamdancer
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 17. Jul 2005 23:17
Wohnort: Frankfurt am Main

Re: 10. Übungsblatt

Beitrag 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:

Benutzeravatar
HeyHey
Windoof-User
Windoof-User
Beiträge: 27
Registriert: 3. Dez 2007 13:02

Re: 10. Übungsblatt

Beitrag 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.

Benutzeravatar
blowfish
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 241
Registriert: 18. Okt 2006 16:00

Re: 10. Übungsblatt

Beitrag 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.
Zuletzt geändert von blowfish am 23. Feb 2009 16:18, insgesamt 1-mal geändert.
Ein Hemd ist Einstellungssache!

jno
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 18. Mai 2007 09:41

Re: 10. Übungsblatt

Beitrag 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}\).

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

Re: 10. Übungsblatt

Beitrag 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\).

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

Re: 10. Übungsblatt

Beitrag 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.

Benutzeravatar
HeyHey
Windoof-User
Windoof-User
Beiträge: 27
Registriert: 3. Dez 2007 13:02

Re: 10. Übungsblatt

Beitrag 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:

Antworten

Zurück zu „Archiv“