Stefan Kopp > Teaching > Theoretische Informatik >
Teil I: Grundzüge der Logik | ||
1) 13.10. | Einführung; Aussagenlogik (AL) | Aufteilung der Übungsgruppen |
2) 15.10. | Syntax und Semantik der AL; Erfüllbarkeit von AL-Formeln | |
3) 20.10. | Äquivalenz und Normalformen von AL-Formeln | Übungszettel 1 |
4) 22.10. | Hornformeln, Schlussverfahren, Vollständigkeit; Resolution der AL | |
5) 27.10. | Resolution; Prädikatenlogik erster Stufe (PL1): Syntax | Übungszettel 2 |
6) 29.10. | PL1: Semantik (Strukturen, Modelle); Äquivalenz und Normalformen | |
Teil II: Formale Sprachen & Grammatiken | ||
7) 3.11. | Einführung; Formale Sprachen; Verkettung & Potenzen von Wortmengen | Übungszettel 3 |
8) 5.11. | Reguläre Ausdrücke/Sprachen; Backus-Systeme, Syntaxdiagramme | |
9) 10.11. | Kontextfreie Sprachen; Grammatik, Ableitung; Pumping-Lemma; XML | Übungszettel 4 |
10) 12.11. | Allgemeine Regelsprachen; Einseitig lineare Grammatiken | |
11) 17.11. | Äquivalenz rechts-/linkslineare Sprache und reguläre Sprache | Übungszettel 5 |
12) 19.11. | Bezug zu kfr. Sprachen; kss. Sprachen; Chomsky-Hierarchie | |
Teil III: Formale Sprachen & Automaten | ||
13) 24.11. | Endliche Automaten (EA); akzeptierte Sprache | Übungszettel 6 |
14) 26.11. | EA und reguläre Sprachen; Nicht-det. endliche Automaten (NEA) | |
15) 1.12. | Äquivalenz EA und NEA; EA und reguläre Sprachen "revisited" | Übungszettel 7 |
16) 3.12. | EA als Rechner/Endliche Maschinen | |
17) 8.12. | Kellerautomaten; akzeptierte Sprache | Übungszettel 8 |
18) 10.12. | NKA und DKA; Akzeptieren durch leeren Stack; NKA und kfr. Sprachen | |
19) 15.12. | Turing-Maschinen; Äquivalenz mit allgemeinen Regelsprachen | Übungszettel 9 |
Teil IV: Berechenbarkeit, Entscheidbarkeit & Komplexität | ||
20) 17.12. | Berechenbarkeitsbegriff; Turing-Maschinen | |
21) 22.12. | Turingsche These und Churchsche These | Übungszettel 10 |
22) 7.1. | Registermaschinen (RAM), RAM-Berechenbarkeit | |
23) 12.1. | Komplexität; uniforme/logarithmische Kosten | Übungszettel 11 |
24) 14.1. | Aufwandsanalyse; O-/Omega-/Theta-Notation | |
PROBEKLAUSUR: 18.1., 18-20, H7 | ||
25) 19.1. | Komplexitätsklassen P/NP, P-NP-Problem | Übungszettel 12 |
26) 21.1. | NP-Vollständigkeit; Nicht-/Berechenbarkeit | |
27) 26.1. | Un-/Entscheidbarkeit; Halteproblem | |
28) 28.1. | Weitere unentscheidbare Probleme; Semi-Entscheidbarkeit | |
29) 2.2. | Rekursiv aufzählbar; kss Sprachen | |
30) 4.2. | Wiederholung - Klausurvorbesprechung | |
Erste KLAUSUR: 11.2., 14-16, H4 | ||
Zweite KLAUSUR: 31.3., 10-12, H13 statt |
Verantwortlich für die Übungen ist Julia Tolksdorf. Bei Problemen oder Fragen wendet euch bitte innerhalb ihrer Sprechzeiten oder per email (siehe Homepage) an sie.
Probeklausur: 18.1., 18-20, H7