Sommersemester 2010
Prof. Dr.  M. Dietzfelbinger

[Mitteilungen] [Inhalte] [Termine] [Scheinerhalt] [Literatur] [Materialien]

Mitteilungen

Beginn: Mittwoch, den 7.4. 2010

Hörer:

• Studierende der Informatik (Diplom) im 8./10. Semester, Schwerpunkt- /Ergänzungskomplex "Komplexitätstheorie und Effiziente Algorithmen" 
• Studierende der Informatik (M.Sc.) im 2. Semester, Vertiefungsgebiet "Algorithmik und Komplexität"
• Interessierte
  

Inhalte

Hashing: Algorithmen- und Analysetechniken

Hashfunktionen bilden Schlüssel auf eine Indexmenge {1,....,m} ab.
Aus dieser Grundsituation ergeben sich viele Anwendungen und Fragestellungen.
Verschiedene Funktionalitäten, die in der Vorlesung diskutiert werden, sind:

• Dynamische Mengen ("`member"'-Test)
• Wörterbücher (dynamische Abbildungen mit "`member"'-Test)
• Retrieval (dynamische Abbildungen ohne "`member"'-Test)
• Approximative Mengen ("`Bloom-Filter"'-Funktionalität)
• (Minimale) Perfekte Hashfunktionen
• Analyse von Datenströmen

In der Vorlesung werden klassische und neue Algorithmen und ihre Analysen besprochen.
Die hierfür nötigen Techniken aus der Wahrscheinlichkeitsrechnung, der (Hyper-)Graphentheorie und der
Linearen Algebra werden bereitgestellt. -- Die Vorlesung bereitet auch auf
weiterführende Arbeiten in dem Gebiet vor. 

Konkrete Themen:

• Universelles Hashing
•  Konstruktion universeller Klassen
•  Anwendungen universeller Klassen: $O(1)$-Suche und perfekte Hashfunktionen. 
•  Momentanalyse bei Datenströmen mit 4-facher Unabhngigkeit
•  Lineares Sondieren und 5-fache Unabhängigkeit
•  High-Performance-Hashklassen und ihre Analyse
•  Verhalten von voll zufälligen Funktionen:
   Negative Korrelation, Poisson-Approximation, größte Buckets
•  Simulation von voll zufälligen Funktionen: "Split-and-Share"
•  Das Mehrfunktionen-Paradigma: Bloom-Filter
•  Cuckoo-Hashing
•  Grenzen der Leistungsfähigkeit beim Cuckoo-Hashing
•  Verallgemeinertes Cuckoo-Hashing
•  Zufällige Hypergraphen, bipartite Graphen, Matrizen
•  "Retrieval": Werte ohne Membership-Test
•  Neuere Konstruktionen perfekter Hashfunktionen
  

Termine

• Vorlesung
• Mittwoch, 13:00-14:30 Uhr, Sr  H 1520a
• Freitag (U), 9:00 -10:30 Uhr, Sr H 1520a
• Übung
  
  • Freitag (G), 9:00-10.30 Uhr, Sr H1520a
    

Prüfung/Scheinerwerb

Scheinerwerb (Diplom):  Fachgespräch, 20 Minuten, am Semesterende

Prüfung (M.Sc.): Mündlich, 20 Minuten, am Semesterende

Bonuspunkte:  1/3 oder 2/3 oder 1/1 einer Notenstufe durch Vortragen von Übungsaufgaben, Ausarbeitung eines Abschnitts oder einen eigenen Vortrag. ( Keine automatische Verbesserung von 5,0 auf 4,0)

Literatur und Links

•  M. Mitzenmacher und E. Upfal, Probability and Computing, Cambridge University Press, 2005.
•  R. Motwani und P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
•  Originalliteratur, wird in der Vorlesung angegeben.
  

Materialien und Übungsblätter

Übungsblätter

Übungsblatt 1

Übungsblatt 2