Arbeitsgruppe Mathematische Logik und Theoretische Informatik 

1. Alphabete, Wörter, Sprachen        (ps)    (pdf)
2. Algorithmen: Berechenbarkeit, Entscheidbarkeit und Aufzählbarkeit       
   (ps)     (pdf)
3. Mathematische Maschinen        (ps)     (pdf)
4. Turingmaschinen        (ps)    (pdf)
5. Varianten des Turingmaschinen-Konzeptes I: Varianten der Programmstruktur        (ps)    (pdf)
6. Varianten des Turingmaschinen-Konzeptes II:Varianten der Speicherstruktur        (ps)    (pdf)
7. Registermaschinen        (ps)    (pdf)
8. Rekursive und primitiv rekursive Funktionen        (ps)    (pdf)
9. Beispiele primitiv rekursiver Funktionen        (ps)    (pdf)
10. Der Äquivalenzsatz        (ps)    (pdf)
11. Universelle Turingmaschinen und der Normalformsatz von Kleene        (ps)    (pdf)
12. Unentscheidbare Mengen und die Diagonalisierungsmethode        (ps)    (pdf)
13. Reduktionsmethode und rekursive Reduzierbarkeiten        (ps)    (pdf)
14. Rekursiv aufzählbare Mengen        (ps)    (pdf)
15. Das Rekursionstheorem        (ps)    (pdf)
16. Allgemeine Komplexitätsmaße        (ps)    (pdf)
17. Zeit- und Platzkomplexität von Turingmaschinen        (ps)    (pdf)
18. Platz- und Zeithierarchiesätze        (ps)    (pdf)
19. Nichtdeterministische Turingmaschinen und ihre Komplexität        (ps)    (pdf)
20. Die polynomiell beschränkten Komplexitätsklassen        (ps)    (pdf)
21. Termersetzungssysteme und Chomsky-Grammatiken        (ps)    (pdf)
22. Die Chomsky-Hierarchie        (ps)    (pdf)
23. Kontextsensitive Sprachen        (ps)    (pdf)
24. Kontextfreie Sprachen        (ps)    (pdf)
25. Reguläre Sprachen        (ps)    (pdf)

1. Alphabete, Wörter, Sprachen  (ps)    (pdf)
2. Turingmaschinen (ps)     (pdf)
3. Zeit- und Platzkomplexität  (ps)     (pdf)
4. Bandreduktionssätze   (ps)    (pdf)
5. Universelle Maschinen und uniform rekursive Klassen   (ps)    (pdf)
6. Abstrakte Komplexitätsmaße   (ps)    (pdf)
7. Deterministische Platz- und Zeithierarchiesätze   (ps)    (pdf)
8. Nichtdeterministische Platzklassen  
9. Relativierte Rechnungen und Reduzierbarkeiten  
10. Die Klassen P, NP und PSPACE 
11. NP-vollständige Probleme  
12. Unvollständige Probleme in NP-P 
13. Lösungen des relativierten P-NP-Problems   
14. Probabilistische Turingmaschinen  
15. Schaltkreisfamilien und nichtuniforme Komplexität  
16. Alternierende Turingmaschinen und die Polynomialzeithierarchie  

1. Some examples (pdf)   
2. Some facts from probability theory (pdf)   
3. The tenure game (pdf)   
4. Basic derandomization techniques (pdf)   
5. The probabilistic method (pdf)   
6. The Byzantine agreement problem (pdf)   
7. Stable marriages (pdf)   
8. Yao's Minimax Principle (pdf)   
9. The complexity of randomized sorting (pdf)   
10. Checking and correcting (pdf)   
11. The Lovasz Local Lemma (proof still missing) (pdf)   
12. Probabilistic complexity classes   
13. PAC-Learning and VC-Dimension   
14. Cryptographic applications: key agreement   
15. Cryptographic applications: public-key encryptions   
16. Cryptographic applications: zeroknowledge protocols (pdf)   
17. Scheduling: Smith's rule, SRPT-rule    
18. Scheduling: Schedule-α and its derandomization    

Zurück

Startseite der Arbeitsgruppe