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

Stefan Kopp, 2006-02-02