|
Logik in der Informatik
Prof. Dr. Nicole Schweikardt |
|
Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden des Theorieteils, Tipps zum Weiterlesen und gelegentlich ergänzende Bemerkungen.
Start des Kapitels "Page-Rank: Markov-Ketten als Grundlage für Suchmaschinen im Internet". Heute: die Architektur von Suchmaschinen; der Page-Rank einer Webseite; die Page-Rank-Eigenschaft; der Zufalls-Surfer; die Page-Rank-Matrix; Formulierung und Beweis eines Satzes, der den Zusammenhang zwischen der Page-Rank-Eigenschaft und linken Eigenvektoren zum Eigenwert 1 zusammenfasst
Material:
Skript zum Thema
Page-Rank: Teil 1,
Literaturverzeichnis.
Weitere Lektüre:
Viele weitere Informationen und Literaturhinweise zum
Thema Suchmaschinen finden sich in Prof. Georg Schnitgers Skript
zur Vorlesung Internet Algorithmen an der Goethe-Universität
Frankfurt am Main sowie
auf der Webseite von Martin Sauerhoffs Vorlesung
Internet Algorithmen an der TU Dortmund; siehe
http://ls2-www.cs.uni-dortmund.de/lehre/winter200911/IntAlg/.
Ein kurzer und allgemein verständlicher Überblick über das
Page-Rank Verfahren
wird in dem Spiegel-Online Artikel
Wie
Google mit Milliarden Unbekannten rechnet von Holger Dambeck gegeben.
Weiter mit Kapitel "Page-Rank: Markov-Ketten als Grundlage für Suchmaschinen im Internet". Heute: kurze Wiederholung des Inhalts der letzten Vorlesung; Markov-Ketten und stochastische Matrizen; Nachweis, dass streng positive stochastische Matrizen genau einen linken Eigenvektor zum Eigenwert 1 besitzen (dies impliziert, dass es für jeden Dämpfungsfaktor d<1 genau ein Tupel gibt, das die Page-Rank-Eigenschaft bzgl. d hat); ergodische Markov-Ketten und deren Eigenschaften
Material:
Skript zum Thema
Page-Rank: Teile 1
und 2,
Literaturverzeichnis.
Weiter mit Kapitel "Page-Rank: Markov-Ketten als Grundlage für Suchmaschinen im Internet". Heute: kurze Wiederholung des Inhalts der letzten beiden Vorlesungen; ergodische Markov-Ketten und deren Eigenschaften; Beobachtung, dass ergodische Markov-Ketten genau eine stationäre Verteilung besitzen und dass diese iterativ berechnet werden kann, indem man mit einer beliebigen Verteilung startet und immer wieder die stochastische Matrix P von rechts mit dem bisherigen Zwischenergebnis multipliziert; Formulierung und Beginn des Beweises von "Satz 16", der besagt, dass jede streng positive stochastische Matrix ergodisch ist
Material:
Skript zum Thema
Page-Rank: Teile 1
bis 3,
Literaturverzeichnis.
Abschluss von Kapitel "Page-Rank: Markov-Ketten als Grundlage für Suchmaschinen im Internet". Heute: kurze Wiederholung des Inhalts der letzten drei Vorlesungen; Abschluss des Beweises von "Satz 16", der besagt, dass jede streng positive stochastische Matrix ergodisch ist (heute: Beweis von "Behauptung 3"); Überlegungen zur kompakten Speicherung der Page-Rank-Matrix P; Überlegungen zur Berechnung des für einen einzelnen Iterationsschritt benögigten Vektor-Matrix-Produkts X':= X P mit Hilfe eines Rechnerclusters (insbes.: Map-Reduce)
Material:
Skript zum Thema Page-Rank.
Weitere Lektüre:
"Chapter 5: Link Analysis" des Buchs Mining
of Massive Datasets von J. Leskovec, A. Rajamaran und J. Ullman
Start mit dem Kapitel "Datenströme". Heute: Einführung ins Thema; die Suche nach der fehlenden Zahl (Verfahren und untere Schranke); das Multiset-Equality Problem (untere Schranke unter Verwendung der Kommunikationskomplexität, ein randomisierter Algorithmus zur Lösung des Problems)
Material:
Folien und
handschriftliche Notizen.
Weitere Lektüre:
Eine sehr gelungene Einführung ins Thema "Datenstromalgorithmen" gibt der Artikel Algorithmic
Techniques for Processing Data Streams von Elena Ikonomovska und Mariano
Zelke (aus: Data Exchange, Information, and Streams, Dagstuhl Follow-Ups
Vol. 5, 2013);
viele weitere Informationen finden sich in
"Chapter 4: Mining Data Streams" des Buchs Mining
of Massive Datasets von J. Leskovec, A. Rajamaran und J. Ullman
Heute: Details zum randomisierten Algorithmus zum Lösen des Multiset-Equality Problems (Implementierung als Datenstrom-Algorithmus; detaillierte Analyse)
Material:
handschriftliche Notizen.
Weitere Lektüre:
Details zum randomisierten Algorithmus für's Multiset-Equality Problem finden
sich in der Arbeit Lower bounds for processing data with few
random accesses to external memory von
Martin Grohe, André Hernich und Nicole Schweikardt (Journal of the ACM 56(3),
2009) (eine Vorabversion ist hier erhältlich)
Heute: das Erstellen von Stichproben (Stichproben fester Größe mittels Reservoir Sampling; Stichproben variabler Größe mittels Hash-Funktionen)
Material:
Seite 132 (insbes. Figure 4.1) des Buchs Mining
of Massive Datasets von J. Leskovec, A. Rajamaran und J. Ullman.
handschriftliche Notizen.
Weitere Lektüre:
Abschnitt 3.1 des Artikels Algorithmic
Techniques for Processing Data Streams von Elena Ikonomovska und Mariano
Zelke
(aus: Data
Exchange, Information, and Streams, Dagstuhl Follow-Ups, Vol. 5, 2013).
Kapitel 4.2 (Seiten 136-138) und Kapitel 4.5.5 (Seiten 148-150) des Buchs Mining
of Massive Datasets von J. Leskovec, A. Rajamaran und J. Ullman
Heute: Approximative Bestimmung der Selektivität von Anfragen durch Nutzen einer Stichprobe geeigneter Größe; die Chernoff-Schranke; Häufigkeitsmomente; Intuition zur Bestimmung des 0-ten Häufigkeitsmoments F0 ("Wie viele verschiedene Elemente enthält der Strom?")
Material:
handschriftliche Notizen.
Weitere Lektüre:
Abschnitt 3.1 des Artikels Algorithmic
Techniques for Processing Data Streams von Elena Ikonomovska und Mariano
Zelke
(aus: Data
Exchange, Information, and Streams, Dagstuhl Follow-Ups, Vol. 5, 2013).
Kapitel 7.2.1 "Number of distinct elements in a data stream" im Buch
Foundations of Data Science von Blum, Hopcroft, Kannan (Version:
May 14, 2015) (erhältlich auf der Webseite von John E. Hopcroft)
Heute: ein Algorithmus zur approximativen Bestimmung des 0-ten Häufigkeitsmoments ("Wie viele verschiedene Elemente enthält der Strom?"), inkl. Beweis, dass der Algorithmus mit Wahrscheinlichkeit mindestens 2/3 einen Schätzwert F* liefert, für den gilt: 1/9 F0 ≤ F* ≤ 9 F0; dabei auch behandelt: eine 2-universelle (a.k.a. paarweise unabhängige) Familie von Hash-Funktionen; die Tschebyscheff-Ungleichung
Material:
handschriftliche Notizen.
Weitere Lektüre:
Kapitel 7.2.1 "Number of distinct elements in a data stream" im Buch
Foundations of Data Science von Blum, Hopcroft, Kannan (Version:
May 14, 2015) (erhältlich auf der Webseite von John E. Hopcroft)
Heute: Verbesserungen des Algorithmus zur approximativen Bestimmung des 0-ten Häufigkeitsmoments: Erhöhen der Approximationsgüte (von 1/9 F0 ≤ F* ≤ 9 F0 auf (1-ε)F0 ≤ F* ≤ (1+ε) F0) und Verstärkung der Erfolgswahrscheinlichkeit (von 2/3 auf 1-δ); dabei auch behandelt: der Median-Trick (generelle Methode zur Verstärkung der Erfolgswahrscheinlichkeit; inkl. Beweis); Vorarbeiten zum BJKST-Algorithmus
Material:
handschriftliche Notizen.
Weitere Lektüre:
Der hier vorgestellte Algorithmus ist "Algorithm 1" in der Arbeit Counting distinct elements in a data stream von
Bar-Yossef, Jayram, Kumar, Sivakumar und Trevisan, in Proceedings of the 6th International
Workshop on Randomization and Approximation Techniques (RANDOM'02),
Cambridge, MA, USA, 2002 (eine Vorabversion ist hier erhältlich).
Eine sehr lesenswerte Darstellung des Median-Tricks (und vieler andere
Datenstrom-Algorithmen) findet sich in
den Lecture
Notes zum Kurs Data Stream Algorithms
von Amit Chakrabarti.
Heute: Details zur Arbeitsweise des BJKST-Algorithmus; Bloom-Filter
Material:
handschriftliche Notizen.
Weitere Lektüre:
Der BJKST-Algorithmus ist "Algorithm 3" in der Arbeit Counting distinct elements in a data stream von
Bar-Yossef, Jayram, Kumar, Sivakumar und Trevisan, in Proceedings of the 6th International
Workshop on Randomization and Approximation Techniques (RANDOM'02),
Cambridge, MA, USA, 2002 (eine Vorabversion ist hier erhältlich).
Eine gut lesbare Darstellung des BJKST-Algorithmus (inkl. Beweis)
findet sich in
den Lecture
Notes zum Kurs Data Stream Algorithms
von Amit Chakrabarti.
Details zum Thema Bloom-Filter finden sich in
Kapitel 4.3 "Filtering Streams"
des Buchs Mining
of Massive Datasets von J. Leskovec, A. Rajamaran und J. Ullman; für eine
detaillierte Analyse der Eigenschaften des Bloom-Filters siehe Kapitel
5.5.2 "Bloom Filters" im Buch Probability and Computing von
Mitzenmacher und Upfal.
Heute: der Count-Min-Sketch; dabei auch behandelt: die Markov-Ungleichung
Material:
handschriftliche Notizen.
Weitere Lektüre:
Originalarbeit:
An improved data stream summary: the count-min sketch and its
applications von Graham Cormode und S. Muthukrishnan, in Journal of
Algorithms 55(1): 58-75, 2005 (eine Vorabversion ist hier erhältlich).
Einen kurzen Überblick über Arbeitsweise und Anwendungen des
Count-Min-Sketches gibt der von Graham Cormode verfasste und in der
der Encyclopedia
of Database Systems
enthaltene Eintrag zum Thema "Count-Min Sketch".
Viele weitere Informationen zum Count-Min-Sketch finden sich
hier.
Heute: einige Anwendungen des Count-Min-Sketch: Schätzung von Join-Größen, Sicherheit von Passwörtern, Bereichsanfragen
Material:
handschriftliche Notizen.
Weitere Lektüre:
Originalarbeit:
An improved data stream summary: the count-min sketch and its
applications von Graham Cormode und S. Muthukrishnan, in Journal of
Algorithms 55(1): 58-75, 2005 (eine Vorabversion ist hier erhältlich).
Einen kurzen Überblick über Arbeitsweise und Anwendungen des
Count-Min-Sketches gibt der von Graham Cormode verfasste und in der
der Encyclopedia
of Database Systems
enthaltene Eintrag zum Thema "Count-Min Sketch".
Eine Anmerkung zum Thema "Sicherheit von Passwörtern" findet sich in der
"Security"-Spalte New Passwords Approach von Phil Scott in
den Communications of the ACM, Vol. 53, No. 9, Seite 15 (siehe
letzte Spalte der letzten Seite
des hier
erhältlichen Artikels.
Mehr Details dazu finden sich im
Artikel Popularity
is everything: A new approach to protecting passwords from
statistical-guessing attacks von Stuart Schechter, Cormac Herley,
Michael Mitzenmacher, in HotSec'10: 5th USENIX Workshop on Hot Topics in Security, 2010.
Viele weitere Informationen zum Count-Min-Sketch finden sich
hier.