Teil I: Grundzüge der Logik
|
| 1) 18.10.2005 |
Einführung; Aussagenlogik (AL) |
Aufteilung der Übungsgruppen |
| 2) 20.10.2005 |
Syntax und Semantik der AL; Erfüllbarkeit von AL-Formeln |
|
| 3) 25.10.2005 |
Äquivalenz und Normalformen von AL-Formeln |
Übungszettel 1 |
| 4) 27.10.2005 |
Hornformeln, Schlussverfahren, Vollständigkeit; Resolution der AL |
|
| 5) 3.11.2005 |
Resolution; Prädikatenlogik erster Stufe (PL1): Syntax |
Übungszettel 2 |
| 6) 8.11. 2005 |
PL1: Semantik (Strukturen, Modelle); Äquivalenz und Normalformen |
Übungszettel 3 |
Teil II: Formale Sprachen & Grammatiken
|
| 7) 10.11.2005 |
Einführung; Formale Sprachen; Verkettung & Potenzen von Wortmengen |
|
| 8) 15.11.2005 |
Reguläre Ausdrücke/Sprachen; Backus-Systeme, Syntaxdiagramme |
Übungszettel 4 |
| 9) 17.11.2005 |
Kontextfreie Sprachen; Grammatik, Ableitung; Pumping-Lemma; XML |
|
| 10) 22.11.2005 |
Allgemeine Regelsprachen; Einseitig lineare Grammatiken |
Übungszettel 5 |
| 11) 24.11.2005 |
Äquivalenz rechts-/linkslineare Sprache und reguläre Sprache |
|
| 12) 29.11.2005 |
Bezug zu kfr. Sprachen; kss. Sprachen; Chomsky-Hierarchie |
Übungszettel 6 |
Teil III: Formale Sprachen & Automaten
|
| 13) 1.12.2005 |
Endliche Automaten (EA); akzeptierte Sprache |
|
| 14) 6.12.2005 |
EA und reguläre Sprachen; Nicht-det. endliche Automaten (NEA) |
Übungszettel 7 |
| 15) 8.12.2005 |
Äquivalenz EA und NEA; EA und reguläre Sprachen "revisited" |
|
| 16) 13.12.2005 |
EA als Rechner/Endliche Maschinen |
Übungszettel 8 |
| 17) 15.12.2005 |
Kellerautomaten; akzeptierte Sprache |
|
| 18) 20.12.2005 |
NKA und DKA; Akzeptieren durch leeren Stack; NKA und kfr. Sprachen |
Übungszettel 9 |
| 19) 22.12.2005 |
Turing-Maschinen; Äquivalenz mit allgemeinen Regelsprachen |
|
Teil IV: Berechenbarkeit, Entscheidbarkeit & Komplexität
|
| 20) 10.1.2006 |
Berechenbarkeitsbegriff; Turing-Maschinen |
Übungszettel 10 |
| 21) 12.01.2006 |
Turingsche These und Churchsche These |
|
| 22) 17.1.2006 |
Registermaschinen (RAM), RAM-Berechenbarkeit |
Übungszettel 11 |
| 23) 19.1.2006 |
Komplexität; uniforme/logarithmische Kosten; Aufwandsanalyse |
|
| 24) 24.1.2006 |
O-, Omega-Notation; Komplexitätsklassen P/NP |
Übungszettel 12 |
| 25) 26.1.2006 |
P-NP-Problem; NP-Vollständigkeit |
|
| 26) 31.1.2006 |
Nicht-/Berechenbarkeit; Un-/Entscheidbarkeit |
|
| 27) 2.2.2006 |
Halteproblem und andere unentscheidbare Probleme |
|
| 28) 7.2.2006 |
rekursiv aufzählbar; kss Sprachen |
|
| 29) 9.2.2006 |
- Klausurvorbereitung - |
|
| 30) 14.2.2006 |
Klausur, 10 s.t.(!!) - 12, H16 |
|