Skripten

Auf dieser Seite finden sich Skripten zu den Vorlesungen im Bereich Mathematische Logik und Theoretische Informatik.

Theoretische Informatik (Prof. Dr. Ambos-Spies)

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)

Komplexitätstheorie (Prof. Dr. Ambos-Spies)

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  

Randomisierte Algorithmen (Priv.-Doz. Dr. Merkle)

Randomized Algorithms   (ps)    (pdf)   
(Dieses Skript ist älter als die Folien zur Vorlesung und ist nur als Ergänzung gedacht.)

Randomisierte Algorithmen (Priv.-Doz. Dr. Merkle)

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 (pdf)
14. Tail bounds and probability amplification (pdf) 
15. Satisfiability and randomized local search (pdf)
16. Satisfiability and exhaustive local search (pdf)
17. Cryptographic applications: Key agreement and public-key encryption  
18. Cryptographic applications: zeroknowledge protocols (pdf)   
19. Scheduling: Smith's rule, SRPT-rule    
20. Scheduling: Schedule-α and its derandomization    

      Additional material

     • A decidable fragment of first-order logic (pdf)

Mathematische Logik (Prof. Gloede)

Teil I: Collegium Logicum
  Kapitel 1: Die Aussagenlogik
  Kapitel 2: Strukturen und formale Sprachen
  Kapitel 3: Modelle und Theorien
  Kapitel 4: Gesetze der Prädikatenlogik

Teil II: Mengenlehre
  Kapitel 5: Grundlagen der Mengenlehre
  Kapitel 6: Mengen von Mengen von...
  Kapitel 7: Das Auswahlaxiom
  Kapitel 8: Mächtigkeiten und Kardinalzahlen

Teil III: Modelltheorie
  Kapitel 9: Hin und her: Vollständigkeit und elementare Äquivalenz
  Kapitel 10: Auf und ab: Elementare Substrukturen
  Kapitel 11: Vereinigungen, Durchschnitte und Ketten
  Kapitel 12: Produkte und Ultraprodukte
  Kapitel 13: Modellvollständigkeit

Teil IV: Unvollständigkeit und Unentscheidbarkeit
  Kapitel 14: Berechenbare Funktionen
  Kapitel 15: Definierbarkeit berechenbarer Funktionen
  Kapitel 16: Die Gödelschen Sätze

Literatur

Gesamtskript

Mengenlehre (Prof. Gloede)

Mengenlehre
Deskriptive Mengenlehre