Theoretische Informatik

1 Einleitung —; der rote Faden.- 2 Notationen.- 2.1 Bezeichnungen.- 2.2 Kalküle.- 3 Semantik von Programmiersprachen — Spezifizieren, Implementieren, Verifizieren.- 3.1 Datenstrukturen.- 3.2 Prädikatenlogik als Spezifikationssprache.- 3.3 Programme.- 3.4 Programmverifikation.- 3.5 Rekursive Programme.- 4 Berechenbarkeitstheorie — auf den Punkt gebracht.- 4.1 Primitiv rekursive Funktionen.- 4.2 ?-rekursive Funktionen.- 4.3 Universalität der ?-rekursiven Funktionen.- 4.4 Arithmetisierung der Semantik rekursiver Programme.- 4.5 Grundzüge der Rekursionstheorie.- 4.6 Die Churchsche These.- 4.7 Berechenbarkeit auf Zeichenreihen.- 4.8 Komplexitätsmaße.- 5 Komplexitätstheorie — das Wichtigste für den praktischen Informatiker.- 5.1 Problemtypen.- 5.2 NP-Theorie.- 5.3 Ausblick auf weitere Komplexitätsklassen.- 6 Chomsky-Hierarchie — nur ein kurzer Seitenblick.- 6.1 Grammatiken und Automaten.- 6.2 Chomsky-3: Reguläre Sprachen und endliche Automaten.- 6.3 Chomsky-2: Kontextfreie Sprachen.- 6.4 Chomsky-1: Kontextsensitive Sprachen.- 6.5 Chomsky-0: Allgemeine Grammatiken.- 7 Lösungen und Hinweise zu den Aufgaben.- Literaturangaben.- Symbolverzeichnis.