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)

Prüfungsstoff Sommersemester 2015

  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 (pdf)   
  12. Karger's algorithm for minimum cuts (Verifcation still missing)(pdf)   
  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 (pdf)
  18. Cryptographic applications: zeroknowledge protocols (pdf)   

      Additional material

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

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


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