Seminar:  Perlen der Theoretischen Informatik

Dozenten: Prof. Johannes Köbler und Olaf Beyersdorff

Themen

 
22.10.   Themenvorstellung  Johannes Köbler  
5.11.  Lineare Kongruenz Generatoren (Knuth)  Dirk Deters  (Köbler)
12.11.  Lineare Kongruenz Generatoren und Quicksort (Tompa)  Mia Viktoria Meyer   (Köbler)
19.11.  Lineare Schieberegisterfolgen (Golomb)  Andrea Elsner  (Köbler)
26.11.  Einwegfunktionen, Motivation und Definition (Kap. 2.1, 2.2)  Hiep Han  (Beyersdorff) 
3.12.  Starke und schwache Einwegfunktionen (Kap. 2.3)  Daniela Weinberg  (Beyersdorff)
10.12.  Beispiele und Variationen von Einwegfunktionen (Kap.2.4)  Lukas Dölle  (Beyersdorff)
17.12.  Verstärken von Einwegfunktionen (Kap. 2.6)  Ralf Immig  (Beyersdorff)
7.1.  Berechnungsmäßige Ununterscheidbarkeit und Pseudozufallsgeneratoren (Kap. 3.1-3.3)  Marc Hochstrate  (Köbler)
14.1.  Konstruktionen mittels Einwegpermutationen (Kap. 3.4)  Andreas Glausch  (Köbler)
21.1.  Pseudozufällige Funktionen (Kap. 3.6)  Konrad Hilse  (Köbler)
28.1.  DES und Pseudozufällige Permutationen (Kap. 3.7 und Luby)  Hendrik Süß  (Köbler)
4.2.  Konstruktion und Analyse von Nisan-Wigderson -Generatoren (Trevisan)  Thomas Fuchs  (Beyersdorff)
11.2.  Einführung in die Quanteninformationsverarbeitung (Williams)  Jan Kinder  (Köbler)
18.2.  Erzeugung von Zufallszahlen mit Quantenrechnern (Williams)  Björn Karge  (Köbler)

Die Kapitelangaben beziehen sich auf das Buch von O. Goldreich.
Zu dem Buch gibt es auch eine online verfügbare Vorversion, die aber nicht vollständig identisch mit der Druckversion ist: http://theory.lcs.mit.edu/~oded/frag.html.
 
 
 
 
 

Literatur