Theoretische Informatik II Universität Potsdam, Sommersemester 2005

Die Folien der Veranstaltung werden in zwei Versionen bereitgestellt. Die normalen ps und pdf Files enthalten eine Druckversion der Folien ohne eventuell benutzte "Animationen". Das anim file enthält die vollständige PDF Version mit Animationen.

Einführung: Theoretische Informatik im Sommersemester 2005  
Teil IV: Berechenbarkeitstheorie
Einheit 4.1: Turingmaschinen  
Einheit 4.2: Rekursive Funktionen  
Einheit 4.3: Andere Berechenbarkeitsmodelle  
Einheit 4.4: Berechenbarkeit, Aufzählbarkeit und Entscheidbarkeit  
Einheit 4.5: Unlösbare Probleme  
Teil V: Komplexitätstheorie
Einheit 5.1: Konkrete Komplexitätsanalyse  
Einheit 5.2: Das P - NP Problem  
Einheit 5.3: NP-vollständige Probleme  
Einheit 5.4: Grenzen überwinden  
  Theoretische Informatik im Rückblick