[ Inhalt ] [ Index ]

Theoretische Informatik

Reinhard Völler

• Inhalt
• Algorithmen, Berechenbarkeit, Entscheidbarkeit
  • Algorithmen
  • Eigenschaften eines Algorithmus
  • Aufzähl- und Entscheidungsverfahren
  • Berechenbare Funktionen
  • Abzählbarkeit
  • Entscheidbare Mengen
  • Charakteristische Funktionen
  • Aufzählbare Mengen
• Turing-Maschinen
  • Das Maschinenmodell
  • Turing-Maschinen als Akzeptoren
  • Zusammensetzen von Turingmaschinen
  • Spezielle Turing-Maschinen
  • Turing-Berechenbarkeit
  • Church-Turing-These
  • Turing-Aufzählbarkeit Turing-Entscheidbarkeit
  • Simulation von Turing-Maschinen
  • Turing-Maschinen mit linearer Bandbeschränkung
• Berechenbare Funktionen
  • Gödelisierung
  • Primitiv-rekursive Funktionen
  • Die Ackermann-Funktion
  • -rekursive Funktionen
• Komplexitätstheorie
  • Die Groß-O-Notation
  • Das Erfüllbarkeitsproblem
  • Färbung von Graphen
  • Komplexitätsklassen
  • NP-Vollständigkeit
  • Der Satz von Cook
  • NP-vollständige Probleme
• Index
• Literatur
• Über dieses Dokument ...