-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Thu, Aug 03, 2017 at 11:57:43AM +0200, ul@openlilylib.org wrote:
Am 2017-08-02 11:19, schrieb tomas@tuxteam.de:
[...]
- (Abstrakte) Daten und ihre Darstellungen Buchstaben, Strings, Zahlen; Binäre darstellung. Maschinenwort.
Mit "Maschinenwort" meinst du das Problem, dass es haklig wird, wenn ein Datentyp (v.a Integer) die Größe eines (systemabhängigen) Maschinenworts überschreitet? Sprachen wie C produzieren dann einen stummen Überlauf (falsche Zahlen ohne Fehlermeldung), Python regelt das für dich, wird aber dramatisch langsamer. Wenn es das ist: "kann ich", der Rest ist mir auch klar.
Klingt so, ja :-)
- Arithmetik (abstrakt und in Maschinendarstellung).
Arithmetik in Maschinendarstellung? Weiß ich jetzt nicht genau, was du meinst. Manche Sachen sind mir klar wie z.B. Diverses was mit Bit-Shifting zu tun hat, vieles Andere nicht. Keine Ahnung, wie die Maschine Multiplikationen regelt (und keine Ahnung, ab wann ich dieses Wissen brauche).
Im wesentlichen ja. Es gibt einerseits die Arithmetik (natürliche, ganze, rationale und reele Zahlen, Grundrechenarten) und die Kompromisse, die ein Computer so machen muss, um "so zu tun, als ob"). Aus Deinen Bemerkungen schliesse ich, dass Du ein brauchbares "working model" davon hast, das Du bei Bedarf verfeinern kannst.
Grundrechenarten und Modulo. Primzahlen
Bei Modulo und Primzahlen sind mir Grundlagen durchaus bekannt, höhere Dinge aber überhaupt nicht. Dieser Artikel über das Fermatsche Theorem (bestimmte Eigenschaften von Zahlen hoch eine Primzahl) fallen mir sehr schwer. Auch weitergehende Modulo-Regeln (was passiert, wenn ich in welcher Reihenfolge Modulo-Operationen durchführe, und v.a., wie kann ich davon profitieren?) - ziemlich blank ...
Naja, das ist nach oben offen und heisst Zahlentheorie. Die zeichnet sich durch böse Überraschungen aus. Dinge, die sehr leicht zu formulieren sind stellen sich als äusserst schwierig zu beweisen heraus (oder zu widerlegen, whatever). Die Goldbachsche Vermutung[1] ist das eine Paradebeispiel. Wenn sich bei Dir die Grenzen "ausgefranst" anfühlen, dann ist das ein gutes Zeichen :)
Zu Modulo musst Du hier lediglich wissen: das ist der Rest der Division einer Zahl durch eine andere. Meistens (die Konventionen variieren aber!) nimmt man den *positiven* Rest:
5 mod 7 == 5 21 mod 7 == 0 -1 mod 7 == 6 (*)
(*) immer die Doku konsultieren :-)
Die Rechenarten ergeben sich daraus:
(a + b) mod c == (a mod c + b mod c) mod c (a*b) mod c == ( (a mod c) * (b mod c) ) mod c
Es loht sich vielleicht (Verständnis ist oft Vertrautwerden), wenn Du Dir die Exponentiation mal genauer anguckst.
- Hashing
Das Konzept von Hash-Funktionen und Hash-Chains ist mir im Kurs klar geworden. Die Mathematik von guten Hash-Funktionen dagegen nicht.
Das liegt daran, dass nicht genau definiert ist, was eine gute Hashfunktion ist. Im wesentlichen ist eine Hashfunktion eine Funktion, die "grosse Datenklumpen" auf "kleine Datenklumpen" abbildet, meistens, weil letztere leichter zu handhaben sind. Abgesehen davon will man meist, dass zwei unterschiedliche Datenklumpen unterschiedliche Hashwerte besitzen (wenn nicht, nennt sich das eine Kollision: die iist natürlich nicht immer zu vermeiden: gehen wir von z.B. Datenklumpen von 10MB aus und hashen wir sie auf 100 Bit "runter", dann müssen sich im Schnitt 10^5 grosse Klumpen auf einem Hash treffen. Doof.
D.h. wir wollen das "typische", "praktisch vorkommende" Datenklumpen "nicht zu oft" kollidieren. Und da fängt die schwarze Magie an :-)
Abgesehen davon gibt es noch spezialisierte Hashfunktionen, die bestimmte Eigenschaften haben:
- perfect hashing: nie eine Kollision (wie geht das denn?). Das geht dann, wenn die Ausgangsmenge der grossen Klumpen im Voraus bekannt ist. Man knetet die Hashfunktion so lange, bis man eine bekommt, die (für diese Menge) nicht kollidiert. Anwendung findet das z.B. in der Menge der Schlüsselworte einer Sprache. Mach mal "man gperf" :-)
- similarity hashing Man will, dass die Hashes von ähnlichen Klumpen auch ähnlich sind (was auch immer ähnlich sei: z.B. Dokumente mit vielen ähnlichen Wörtern sollen auf Bitwürste abgebildet werden, die sich in wenigen Bits unterscheiden). Gut für Dokumenten- und Bildersuche
- kryptographische Hashes Es soll möglichst schwer sein, aus dem Hash Rückschlüsse auf den Originalklumpen zu ziehen. Nach dem heutigen Stand der Technik. Und wenn man nicht NSA heisst. Weites Thema :)
Und auch wenn ich verstanden habe wie diese polynomische String-Hash-Funktion funktioniert, ist mir überhaupt nicht klar, wie die Dozenten auf die Idee gekommen sind, sie in die entsprechende Python-Funktion zu übertragen. Gleiches gilt für die Idee der vorberechneten Hashes. Ich kann leicht nachvollziehen, dass man einmal einen ganzen String (zeichenweise) hasht und dann für jede weitere Stelle praktisch nur eine Funktion berechnen muss.
OK. Das ist was für ein eigenes Posting. Dass man das stellenweise machen kann liegt an der speziellen Konstruktion des Hashes (ein "rolling hash"[2]. Das wird ausgiebig in Tools wie rsync (und ich glaube auch diff) genutzt. Vermutlich macht diese Eigenschaft einen Hash auch besonders unbrauchbar für einen kryptographischen Hash -- Bauchgefühl, ich habe keinen Beweis für sowas ;-)
Nachzuvollziehen, wie das mit den Summenfunktionen tatsächlich funktioniert, ist schon schwieriger. Und das in eine funktionierende Python-Routine zu übertragen, hätte ich nicht alleine gewusst.
Klar. Musst wahrscheinlich kleiner anfangen und den Turm langsam aufbauen.
Diese Theorie kenne ich auch, ich nehme immer das Bild eines Gleichungssystems, das zu viele Unbekannte hat und in dem man erst dann eine Lösung findet, wenn alle gleichzeitig (zufällig) den richtigen Wert haben.
:-)
Aber das trifft hier glaube ich nur bedingt zu. Ich habe sicher das Grundwerkzeug, Algorithmen zu verstehen und bin mit einigen der relevanten Parameter vertraut (z.B. inzwischen den Implikationen der verwendeten Datenstruktur). Bei den komplexeren mathematischen Bestandteilen fehlt mir aber teilweise tatsächlich ein Grundverständnis (entweder vergessen oder teilweise noch nie wirklich damit beschäftigt).
Da gibt es nicht so komplexe Zusammenhänge, die verkleiden sich nur als solche :)
Ich bin mal gespannt, wie sich das im nächsten Kurs (String-Algorithmen) und im optionalen letzten Modul des Graphen-Kurses (erweiterte Aufgaben und anscheinend 1000x so schnelle Navigations-Algorithmen mit echten Kartendaten) entwickelt.
Klingt ja sehr vergnüglich
[1] https://en.wikipedia.org/wiki/Goldbach_conjecture [2] https://en.wikipedia.org/wiki/Rolling_hash
lg - -- t