|
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 eines Satzes, der den Zusammenhang zwischen der Page-Rank-Eigenschaft und linken Eigenvektoren zum Eigenwert 1 zusammenfasst
Material:
Vorlesungsskript zum Thema
Page-Rank — heute Seiten 1-17
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; Beweis eines Satzes, der den Zusammenhang zwischen der Page-Rank-Eigenschaft und linken Eigenvektoren zum Eigenwert 1 zusammenfasst; Markov-Ketten und stochastische Matrizen; 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 von "Satz 1.14", der besagt, dass jede streng positive stochastische Matrix ergodisch ist
Material:
Vorlesungsskript zum Thema
Page-Rank — heute Seiten 17-26
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.
Übungsaufgaben (fakultativ):
Lösen Sie die Aufgaben 1, 3 und 4 vom Theorie-Übungsblatt 1 aus dem Sommersemester 2016.
Weiter mit Kapitel "Page-Rank: Markov-Ketten als Grundlage für Suchmaschinen im Internet". Heute: kurze Wiederholung des Inhalts der letzten beiden Vorlesungen; Zusammenfassung der bisherigen Ergebnisse (unter Verwendung des - noch nicht in der Vorlesung bewiesenen - Satzes 1.14): 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; Überlegungen zur Berechnung des für einen einzelnen Iterationsschritt benögigten Vektor-Matrix-Produkts X':= X P mit Hilfe eines Rechnerclusters; Beginn des Beweises von "Satz 1.14", der besagt, dass jede streng positive stochastische Matrix ergodisch ist
Material:
Vorlesungsskript zum Thema
Page-Rank — heute Seiten 26-28 und 30-35
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.
Übungsaufgaben (fakultativ):
Lösen Sie die Aufgaben 1, 2 und 3 vom Theorie-Übungsblatt 2 aus dem Sommersemester 2016.
Abschluss von Kapitel "Page-Rank: Markov-Ketten als Grundlage für Suchmaschinen im Internet". Heute: kurze Wiederholung des Inhalts der letzten Vorlesung; Abschluss des Beweises von "Satz 1.14", der besagt, dass jede streng positive stochastische Matrix ergodisch ist (heute: Beweis der Behauptungen 2 und 3); Diskussion zu Aufgaben der Theorie-Übungsblätter 1 und 2 aus dem Sommersemester 2016.
Material:
Vorlesungsskript zum Thema
Page-Rank — heute Seiten 28-30
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 zur Einführung ins Thema "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 zur Einführung ins
Thema "Datenströme" — heute Folien 1-10
handschriftliche
Notizen zur Einführung ins Thema "Datenströme" — heute Seiten 1-8
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
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)
Übungsaufgaben (fakultativ):
Lösen Sie Aufgabe 1 vom Theorie-Übungsblatt 3 aus dem Sommersemester 2016.
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:
Folien zur Einführung ins
Thema "Datenströme" — heute Folie 10
handschriftliche
Notizen zur Einführung ins Thema "Datenströme" — heute Seiten 8-13
handschriftliche
Notizen zum Thema "Stichproben" — heute Seiten 1-6 des
pdf-Dokuments
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);
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
Übungsaufgaben (fakultativ):
Lösen Sie Aufgaben 2 und 3 vom Theorie-Übungsblatt 3 aus dem Sommersemester 2016.
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
Übungsaufgaben (fakultativ):
Lösen Sie Aufgabe 4 vom Theorie-Übungsblatt 3 aus dem Sommersemester 2016.
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, streng 2-universelle und streng k-universelle Familien von
Hash-Funktionen behandelt.
Start mit dem Kapitel zum Thema "Count-Min-Sketch". Heute:
Einführung ins Thema
Material:
handschriftliche Notizen
zum Thema "Hash-Funktionen" — heute komplett behandelt
handschriftliche Notizen
zum Thema "Count-Min-Sketch" — heute Seiten 1-3
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.
Übungsaufgaben (fakultativ):
Lösen Sie Aufgaben 1 und 2 vom Theorie-Übungsblatt 4 aus dem Sommersemester 2016.
Weiter mit dem Kapitel zum Thema "Count-Min-Sketch". Heute: CM-Sketch der Tiefe 1 und Formulierung und Beweis der Gütekriterien, sowie CM-Sketch der Tiefe d und Formulierung und Beweis von Gütekriterien des CM-Sketches der Tiefe d – dabei auch behandelt: die Markov-Ungleichung
Material:
handschriftliche Notizen
— heute Seiten 4-10
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.
Weiter mit dem Kapitel zum Thema "Count-Min-Sketch". Heute: Wiederholung des CM-Sketches; 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 zum
Thema "Count-Min-Sketch"
— heute Seiten 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).
Viele weitere Informationen zum Count-Min-Sketch finden sich
hier.
Übungsaufgaben (fakultativ):
Lösen Sie Aufgabe 3 vom Theorie-Übungsblatt 4 aus dem Sommersemester 2016.
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;
kurzer Hinweis auf 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-6 der pdf-Datei
Weitere Lektüre:
Übungsaufgaben (fakultativ):
Lösen Sie Aufgabe 1 vom Theorie-Übungsblatt 5 aus dem Sommersemester 2016.
Weiter mit dem Kapitel zum Thema "Häufigkeitsmomente": Ein einfacher Algorithmus zum Abschätzen von F0; der Median-Trick zur Verstärkung der Erfolgswahrscheinlichkeit; Verfeinerung des Algorithmus, um eine bessere Abschätzung von F0 zu erhalten; Beginn des Beweises, dass der einfache Algorithmus mit Wahrscheinlichkeit mindestens 2/3 einen Schätzwert F* liefert, für den gilt: 1/9 F0 ≤ F* ≤ 9 F0;
Material:
handschriftliche Notizen zum
Thema "Häufigkeitsmomente" — heute Seiten 6-9 und 13-17 der pdf-Datei
Weitere Lektüre:
Seiten 18-26 der handschriftlichen Notizen zum
Thema "Häufigkeitsmomente"
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":
Abschluss des Beweises, dass der einfache 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
Kurzer Überblick über im Theorie-Teil der Vorlesung behandelte Themen, sowie Tipps zur Vorbereitung auf die mündliche Modulabschlussprüfung
Material:
handschriftliche Notizen zum
Thema "Häufigkeitsmomente" — heute Seiten 9-13 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.
Übungsaufgaben (fakultativ):
Lösen Sie Aufgaben 2 und 3 vom Theorie-Übungsblatt 5 aus dem Sommersemester 2016.