Informationen zur Vorlesung

Wintersemester 2004

Skript

• Vorlesungsunterlagen Teil 1: Einleitung und Kapitel 1, Berechenbarkeit [.pdf oder .ps]
• Vorlesungsunterlagen Teil 2: Komplexität [.pdf oder .ps]
• Vorlesungsunterlagen Teil 3: Algorithmen: Über die Behandlung NP-vollständiger Probleme [.pdf oder .ps]
• Vorlesungsunterlagen Teil 4: Formale Sprachen [.pdf oder .ps]

Folien

• 12.10.04: Themenvorstellung, einfache Beispiele zu Simulation, Diagonalisierung, Reduktion [.pdf]
• 19.10.04: Beschreibung von Turingmaschinen, Begriffe: berechenbar, entscheidbar, rekursiv aufzählbar [.pdf]
• 22.10.04: Beispiele für Turingmaschinen, Komplexitätsmaße, Mehrband Turingmaschinen [.pdf]
• 26.10.04: Simulation zwischen 1-Band und k-Band DTMs, Registermaschinen [.pdf]
• 02.11.04: Universelle Turingmaschinen, Eigenschaften entscheidbarer und rekursiv aufzählbarer Sprachen [.pdf]
• 05.11.04: Abschlusseigenschaften rekursiv aufzählbarer Sprachen [.pdf]
• 09.11.04: Beziehung zwischen rekursiv aufzählbar / entscheidbar, Unentscheidbarkeit [.pdf]
• 12.11.04: Diagonalisierung und Reduktion [.pdf]
• 16.11.04: Reduktion [.pdf]
• 19.11.04: Nichtdeterministische Turingmaschinen [.pdf]
• 23.11.04: Die Klassen P und NP, Beispielprobleme [.pdf]
• 26.11.04: Die Klasse NP, nichtdeterministische Algorithmen [.pdf]
• 30.11.04: NP-Vollständigkeit, polynomielle Reduktionen, Erfüllbarkeitsproblem [.pdf]
• 03.12.04: NP-Vollständigkeit des Erfüllbarkeitsproblems [.pdf]
• 10.12.04: NP-Vollständigkeit des Erfüllbarkeitsproblems [.pdf]
• 14.12.04: NP-Vollständigkeit des Erfüllbarkeitsproblems, weitere NP vollständige Probleme [.pdf]
• 17.12.04: Bemerkungen zu NP-vollständigen Problemen, algorithmische Behandlung NP-vollständiger Probleme [.pdf]
• 21.12.04: Algorithmische Behandlung NP-vollständiger Probleme [.pdf]
• 11.01.05: Grammatiken [.pdf]
• 14.01.05: Endliche Automaten [.pdf]
• 21.01.05: Anwendung des Pumping Lemma [.pdf]
• 25.01.05: Kontextfreie Sprachen [.pdf]
• 01.02.05: Kellerautomaten [.pdf]
• 04.02.05: Wiederholung [.pdf]