Teil I: Grundzüge der Logik
|
| 1) 17.10.2006 |
Einführung; Aussagenlogik (AL) |
Aufteilung der Übungsgruppen |
| 2) 19.10.2006 |
Syntax und Semantik der AL; Erfüllbarkeit von AL-Formeln |
|
| 3) 24.10.2006 |
Äquivalenz und Normalformen von AL-Formeln |
Übungszettel 1 |
| 4) 26.10.2006 |
Hornformeln, Schlussverfahren, Vollständigkeit; Resolution der AL |
|
| 5) 31.10.2006 |
Resolution; Prädikatenlogik erster Stufe (PL1): Syntax |
Übungszettel 2 |
| 6) 2.11. 2006 |
PL1: Semantik (Strukturen, Modelle); Äquivalenz und Normalformen |
Teil II: Formale Sprachen & Grammatiken
|
| 7) 7.11.2006 |
Einführung; Formale Sprachen; Verkettung & Potenzen von Wortmengen |
Übungszettel 3 |
| 8) 9.11.2006 |
Reguläre Ausdrücke/Sprachen; Backus-Systeme, Syntaxdiagramme |
| 9) 14.11.2006 |
Kontextfreie Sprachen; Grammatik, Ableitung; Pumping-Lemma; XML |
Übungszettel 4 |
| 10) 16.11.2006 |
Allgemeine Regelsprachen; Einseitig lineare Grammatiken |
| 11) 21.11.2006 |
Äquivalenz rechts-/linkslineare Sprache und reguläre Sprache |
Übungszettel 5 |
| 12) 23.11.2006 |
Bezug zu kfr. Sprachen; kss. Sprachen; Chomsky-Hierarchie |
Teil III: Formale Sprachen & Automaten
|
| 13) 28.11.2006 |
Endliche Automaten (EA); akzeptierte Sprache |
Übungszettel 6 |
| 14) 30.11.2006 |
EA und reguläre Sprachen; Nicht-det. endliche Automaten (NEA) |
| 15) 5.12.2006 |
Äquivalenz EA und NEA; EA und reguläre Sprachen "revisited" |
Übungszettel 7 |
| 16) 7.12.2006 |
EA als Rechner/Endliche Maschinen |
| 17) 12.12.2006 |
Kellerautomaten; akzeptierte Sprache |
Übungszettel 8 |
| 18) 14.12.2006 |
NKA und DKA; Akzeptieren durch leeren Stack; NKA und kfr. Sprachen |
| 19) 19.12.2006 |
Turing-Maschinen; Äquivalenz mit allgemeinen Regelsprachen |
Übungszettel 9 |
Teil IV: Berechenbarkeit, Entscheidbarkeit & Komplexität
|
| 20) 21.12.2006 |
Berechenbarkeitsbegriff; Turing-Maschinen |
| 21) 9.01.2007 |
Turingsche These und Churchsche These |
Übungszettel 10 |
| 22) 11.1.2007 |
Registermaschinen (RAM), RAM-Berechenbarkeit |
| 23) 16.1.2007 |
Komplexität; uniforme/logarithmische Kosten |
Übungszettel 11 |
| 24) 18.1.2007 |
Aufwandsanalyse; O-/Omega-/Theta-Notation |
| 25) 23.1.2007 |
Komplexitätsklassen P/NP, P-NP-Problem |
Übungszettel 12 |
| 26) 25.1.2007 |
NP-Vollständigkeit; Nicht-/Berechenbarkeit |
|
| 27) 30.1.2007 |
Un-/Entscheidbarkeit; Halteproblem |
|
| 28) 1.2.2007 |
Weitere unentscheidbare Probleme; Semi-Entscheidbarkeit |
|
| 29) 6.2.2007 |
Rekursiv aufzählbar; kss Sprachen |
|
| 30) 8.2.2007 |
- Wiederholung und Klausurvorbereitung - |
|
| 30) 6.3.2007 |
Klausur: 10-12, H1 |
|