Termine

Di 10:00 – 12:00, AM 4; Do 10:00 – 12:00 AM 4

Klausur

Die Klausur findet am Donnerstag, den 18.02.10, von 10.00h-12.00h im AM1 statt.

Die Nachklausur findet am Donnerstag, den 25.03.10, von 10.00h-12.00h im AM4 statt.

Klausureinsicht

Die Klausureinsicht findet am Dienstag, den 02. März von 14-16 Uhr im TCS Seminarraum statt.

Skript

Die aktuellste Skriptversion wird es immer hier geben.

• Das Vorlesungsskript, komplett, mit Korrekturen

• Die Vorlesungskarte der gesamten Veranstaltung

• Das Vorlesungsskript aus dem Vorjahr, komplett

Inhalt

Syntaxbeschreibung

1. Alphabet, Wort, Sprache, Sprachklasse, 2009-10-22, Präsentation, Skriptfassung

2. Grammatiken, 2009-10-27, Präsentation, Skriptfassung

3. Die Chomsky-Hierarchie, 2009-10-29, Präsentation, Skriptfassung

Wie analysiert man Syntax?

4. Deterministische endliche Automaten, 2009-11-03, Präsentation, Skriptfassung

5. Grenzen regulärer Sprachen, 2009-11-05, Präsentation, Skriptfassung

6. Nichtdeterministische endliche Automaten, 2009-11-10, Präsentation, Skriptfassung

7. Zwei-Wege-Automaten, 2009-11-12, Präsentation, Skriptfassung

8. Reguläre Ausdrücke, 2009-11-17, Präsentation, Skriptfassung

9. Nerode-Klassen, 2009-11-19, Präsentation, Skriptfassung

10. Kontextfreie Grammatiken, 2009-11-24, Präsentation, Skriptfassung

11. Analyse kontextfreier Sprachen, 2009-11-26, Präsentation, Skriptfassung

Was ist berechenbar?

12. Maschinen I:Die Turingmaschine, 2009-12-01, Präsentation, Skriptfassung

13. Maschinen II: Nichtdeterministische Turingmaschineń, 2009-12-03, Präsentation, Skriptfassung

14. Maschinen III: Register-Maschinen, 2009-12-08, Präsentation, Skriptfassung

15. Programme I: Loop- und While-Programme, 2009-12-10, Präsentation, Skriptfassung

16. Programme II: Rekursion, 2009-12-15, Präsentation, Skriptfassung

17. Die Church-Turing-These, 2009-12-17, Präsentation, Skriptfassung

18. Unentscheidbarkeit I: Das Halteproblem, 2010-01-07, Präsentation, Skriptfassung

19. Unentscheidbarkeit II: Satz von Rice, 2010-01-12, Präsentation, Skriptfassung, Lösung von Übung 19.2

20. Unentscheidbarkeit III: Unentscheidbare Probleme, 2010-01-14, Präsentation, Skriptfassung

Wie schwierig sind Probleme?

21. Die O-Notation, 2010-01-19, Präsentation, Skriptfassung

22. Einführung in die Komplexitätstheorie, 2010-01-21, Präsentation, Skriptfassung

23. Reduktionen, 2010-01-26, Präsentation, Skriptfassung

24. Einführung zur Vollständigkeit, 2010-01-28, Präsentation, Skriptfassung

25. NL-Vollständigkeit, 2010-02-02, Präsentation, Skriptfassung

26. P-Vollständigkeit, 2010-02-04, Präsentation, Skriptfassung

27. NP-Vollständigkeit, 2010-02-09, Präsentation, Skriptfassung

28. Das P-NP-Problem, 2010-02-11, Präsentation, Skriptfassung, Der Song