|
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
Material:
Vorlesungsskript zum Thema
Page-Rank (Version vom 24.05.2016) — heute Seiten 1-12
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; 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; Markov-Ketten und stochastische Matrizen
Material:
Vorlesungsskript zum Thema
Page-Rank (Version vom 24.05.2016) — heute Seiten 13-19
Weitere Lektüre:
"Chapter 5: Link Analysis" des Buchs Mining
of Massive Datasets von J. Leskovec, A. Rajamaran und J. Ullman und
die Originalarbeit von Brin und Page: "The anatomy of a large-scale
hypertextual web search engine", Computer Networks, 30(1-7):107-117, 1998.
Weiter mit Kapitel "Page-Rank: Markov-Ketten als Grundlage für Suchmaschinen im Internet". Heute: kurze Wiederholung des Inhalts der letzten beiden Vorlesungen; Verteilungen; 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 1.14", der besagt, dass jede streng positive stochastische Matrix ergodisch ist
Material:
Vorlesungsskript zum Thema
Page-Rank (Version vom 24.05.2016) — heute Seiten 19-25
Weitere Lektüre:
"Chapter 5: Link Analysis" des Buchs Mining
of Massive Datasets von J. Leskovec, A. Rajamaran und J. Ullman und
die Originalarbeit von Brin und Page: "The anatomy of a large-scale
hypertextual web search engine", Computer Networks, 30(1-7):107-117, 1998.
Weiter mit 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 1.14", der besagt, dass jede streng positive stochastische Matrix ergodisch ist (heute: Beweis der Behauptungen 2 und 3); Zusammenfassung der bisherigen Ergebnisse: Existenz und Eindeutigkeit eines Tupels, das die Page-Rank-Eigenschaft bzgl. Dämpfungsfaktor d besitzt, sowie ein iteratives Verfahren zur approximativen Berechnung dieses Tupels; Überlegungen zur kompakten Speicherung der Page-Rank-Matrix P
Material:
Vorlesungsskript zum Thema
Page-Rank (Version vom 14.06.2016) — heute Seiten 24-30
Theorie-Übungsblatt 1 (Aufgabe 2
wird auf Theorie-Übungsblatt 2 verschoben)
Weitere Lektüre:
"Chapter 5: Link Analysis" des Buchs Mining
of Massive Datasets von J. Leskovec, A. Rajamaran und J. Ullman
Abschluss von Kapitel
"Page-Rank: Markov-Ketten als Grundlage für Suchmaschinen im Internet". Heute:
Überlegungen zur Berechnung des für einen einzelnen Iterationsschritt
benögigten Vektor-Matrix-Produkts X':= X P mit Hilfe eines Rechnerclusters
Start mit dem Kapitel zur Einführung ins Thema
"Datenströme".
Heute: Einführung ins Thema; die Suche nach der fehlenden Zahl (Verfahren
und untere Schranke)
Material:
Vorlesungsskript zum Thema
Page-Rank (Version vom 14.06.2016) — heute Seiten 30-33
Folien zur Einführung ins
Thema "Datenströme" — heute Folien 1-5
Theorie-Übungsblatt 2
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
Weiter mit dem Kapitel zur Einführung ins Thema "Datenströme". Heute: Details zur unteren Schranke für den Platzbedarf zur Lösung der Suche nach der fehlenden Zahl; das Multiset-Equality Problem: untere Schranke unter Verwendung der Kommunikationskomplexität, ein randomisierter Algorithmus zur Lösung des Problems
Material:
Folien zur Einführung ins
Thema "Datenströme" — heute Folien 5-10
handschriftliche
Notizen zur Einführung ins Thema "Datenströme" — heute Seiten 1-7
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)
Abschluss des Kapitels zur Einführung ins Thema "Datenströme". Heute:
Details zum randomisierten Algorithmus zum Lösen des
Multiset-Equality Problems (detaillierte Analyse und Korrektheitsbeweis).
Start mit dem Kapitel zum Thema "Stichproben aus Datenströmen".
Heute: das Erstellen einer Stichproben der Größe 1 mittels "Reservoir Sampling"
Material:
handschriftliche
Notizen zur Einführung ins Thema "Datenströme" — heute Seiten
4-13
handschriftliche
Notizen zum Thema "Stichproben" — heute Seiten 1-6 des
pdf-Dokuments
Theorie-Übungsblatt 3
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)
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).
Abschluss des Kapitels zum Thema "Stichproben aus Datenströmen". Heute: das Erstellen einer Stichproben der Größe s > 1 mittels "Reservoir Sampling"; Stichproben variabler Größe mittels Hash-Funktionen
Material:
handschriftliche
Notizen zur Einführung ins Thema "Datenströme" — heute Seiten
7-15 des pdf-Dokuments
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) des Buchs Mining
of Massive Datasets von J. Leskovec, A. Rajamaran und J. Ullman
Kapitel zum Thema "Hash-Funktionen": die Begriffe "Familie von
Hash-Funktionen", "k-universell" und "streng k-universell" eingeführt
sowie Beispiele für 2-universelle bzw. streng 2-universelle Familien von
Hash-Funktionen behandelt.
Start mit dem Kapitel zum Thema "Count-Min-Sketch". Heute:
CM-Sketch der Tiefe 1 und Formulierung der Gütekriterien (heute ohne Beweis);
CM-Sketch der Tiefe d und Formulierung und Beweis von Gütekriterien des
CM-Sketches der Tiefe d
Material:
handschriftliche Notizen
zum Thema "Hash-Funktionen" — heute komplett behandelt
handschriftliche Notizen
zum Thema "Count-Min-Sketch" — heute Seiten 1-4 und 7-9
Theorie-Übungsblatt 4
Weitere Lektüre:
Viele Informationen zum Thema Hash-Funktionen finden sich in dem Buch Probability and Computing von
Mitzenmacher und Upfal (Cambridge Univ. Press, 2005).
Originalarbeit zum Thema "Count-Min-Sketch":
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.
Weiter mit dem Kapitel zum Thema "Count-Min-Sketch". Heute: Beweis der in der letzten Vorlesung formulierten Gütekriterien des CM-Sketch der Tiefe 1 – dabei auch behandelt: die Markov-Ungleichung; erstes Beispiel zur Anwendung des CM-Sketch: Vergleich zwischen dem Speicherverbrauch des CM-Sketch und dem Speicherverbrauch bei Nutzung einer herkömmlichen Datenbank; zweites Beispiel zur Anwendung mehrerer CM-Sketches zum Beantworten von Bereichsanfragen
Material:
handschriftliche Notizen
— heute Seiten 4-7 und 10-17.
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.
Abschluss des Kapitels zum Thema "Count-Min-Sketch". Heute:
drittes Beispiel: Anwendung des CM-Sketch zur Abschätzung von Join-Größen;
viertes Beispiel: Anwendung des CM-Sketch zur Sicherheit von Passwörtern;
fünftes Beispiel: CM-Sketch zum Berechnen von Heavy Hitters
Start mit dem Kapitel zum Thema "Häufigkeitsmomente":
Definition des k-ten Häufigkeitsmoments Fk; Bedeutung von
F0, F1 und F2;
Intuition zur Bestimmung des 0-ten Häufigkeitsmoments F0
("Wie viele verschiedene Elemente enthält der Strom?")
Material:
handschriftliche Notizen zum
Thema "Count-Min-Sketch"
— heute Seiten 18-25
handschriftliche Notizen zum
Thema "Häufigkeitsmomente" — heute Seiten 1-8 und 13-16 der pdf-Datei
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).
Viele weitere Informationen zum Count-Min-Sketch finden sich
hier.
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.
Kapitel 4.5.5 (Seiten 148-150) des Buchs Mining
of Massive Datasets von J. Leskovec, A. Rajamaran und J. Ullman
Der in der Vorlesung vorgestellte Algorithmus zum Abschätzen von F0 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).
Weitere Informationen zum Thema finden sich in 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)
Weiter mit dem Kapitel zum Thema "Häufigkeitsmomente": Beweis, dass der in der letzen Vorlesung behandelte Algorithmus mit Wahrscheinlichkeit mindestens 2/3 einen Schätzwert F* liefert, für den gilt: 1/9 F0 ≤ F* ≤ 9 F0; dabei auch die Tschebyscheff-Ungleichung behandelt; der Median-Trick zur Verstärkung der Erfolgswahrscheinlichkeit; dabei auch die Chernoff-Schranke behandelt
Material:
handschriftliche Notizen zum
Thema "Häufigkeitsmomente" — heute Seiten 8-12 und 17-21 der pdf-Datei
Weitere Lektüre:
Kapitel 4.5.5 (Seiten 148-150) des Buchs Mining
of Massive Datasets von J. Leskovec, A. Rajamaran und J. Ullman
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)
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.
Abschluss des Kapitels zum Thema "Häufigkeitsmomente":
der BJKST-Algorithmus (ohne Korrektheitsbeweis)
Kapitel zum Thema "Bloom-Filter": Funktionsweise und Anwendungen von
Bloom-Filtern (ohne theoretische Analyse)
Material:
handschriftliche Notizen zum
Thema "Häufigkeitsmomente" — heute Seiten 22-26 der pdf-Datei
handschriftliche Notizen zum Thema "Bloom-Filter" —
heute Seiten 1-5 der pdf-Datei
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.