Theoretische Grundlagen der Informatik

Prof.Dr. Clemens H. Cap, Universität Rostock

1 Logische Propädeutik.- 1.1 Aussagen und Operatoren.- 1.2 Wahrheit und Umformung.- 1.3 Implikation und Folgerung.- 1.4 Formale Logik.- 2 Mengenlehre.- 2.1 Elementare Definitionen.- 2.2 Vergleichen von Mengen.- 2.3 Operationen auf Mengen.- 2.4 Gesetze für Mengenoperationen.- 2.5 Familien von Mengen.- 2.6 Eigenschaften und Mengen.- 3 Quantoren.- 3.1 Elementare Definitionen.- 3.2 Bereichsangaben.- 3.3 Mehrstellige Eigenschaften.- 3.4 Freie und gebundene Variable.- 4 Relationen.- 4.1 Elementare Definitionen.- 4.2 Binäre Relationen.- 4.3 Funktionen.- 4.4 Ordnungsrelationen.- 4.5 Operationen auf Relationen.- 4.6 Aquivalenzrelationen.- 4.7 Hüllen.- 5 Graphen.- 5.1 Elementare Definitionen.- 5.2 Spezielle Graphen.- 5.3 Isomorphe Graphen.- 5.4 Verbindungen in Graphen.- 5.5 Darstellung von Graphen auf Rechnern.- 5.6 Spezielle Wege in Graphen.- 5.7 Attributierte Graphen.- 5.8 Planare Graphen.- 5.9 Bäume und Wälder.- 5.10 Petri-Netze.- 6 Sprachen.- 6.1 Sprachen und Grammatiken.- 6.2 Reguläre (Typ 3) Sprachen.- 6.3 Kontextfreie (Typ 2) Sprachen.- 6.4 Kontextsensitive (Typ 1) Sprachen.- 6.5 Rekursiv aufzählbare (Typ 0) Sprachen.- 7 Maschinen.- 7.1 Automaten.- 7.2 Kellerautomaten.- 7.3 Turing-Maschinen.- 7.4 Linear beschränkte Automaten.- 7.5 Automaten mit Ausgabewerten.- 8 Maschinen und Sprachen.- 9 Techniken und Beispiele formaler Sprachen.- 9.1 Einfache Beispiele.- 9.2 Vollständige Induktion.- 9.3 Strukturelle Induktion.- 9.4 Charakteristische Beispiele.- 9.5 Arithmetische Ausdrücke.- 9.6 Logische Ausdrücke.- 9.7 Reguläre Mengen und Ausdrücke.- 9.8 Arithmetische Sprachen.- 9.9 Programmiersprachen.- 9.10 Natürliche Sprachen.- 10 Semantik von Programmiersprachen.- 10.1 Die Programmiersprache Loop.- 10.2 Die Programmiersprache While.- 10.3 Die Programmiersprache Goto.-10.4 Die Programmiersprache Recur.- 10.5 Techniken zur Semantikdefinition.- 11 Berechenbarkeit.- 11.1 Primitiv rekursive Funktionen.- 11.2 Total und partiell rekursive Funktionen.- 11.3 Die Churchsche These.- 11.4 Berechenbarkeit bei Mengen.- 11.5 Berechenbarkeit bei formalen Sprachen.- 11.6 Rekursionstheorie.- 12 Komplexitätstheorie.- 12.1 Asymptotische Notationen.- 12.2 Wachstumsklassen.- 12.3 Komplexitätsaussagen.- 12.4 NP-Vollständigkeit.- 13 Information und Codierung.- 13.1 Elementare Wahrscheinlichkeitsrechnung.- 13.2 Information.- 13.3 Informationsquellen.- 13.4 Quellcodierung.- 13.5 Kanäle.- 13.6 Kanalcodierung.- 13.7 Kryptologische Codierung.- 14 Logik.- 14.1 Deduktion in der Aussagenlogik.- 14.2 Semantik der Aussagenlogik.- 14.3 Normalformen der Aussagenlogik.- 14.4 Deduktion in der Prädikatenlogik.- 14.5 Semantik der Prädikatenlogik.- 14.6 Normalformen der Prädikatenlogik.- 14.7 Zur Logik der Arithmetik und Informatik.- 15 Grenzen von Computern.- 15.1 Erste Beispiele.- 15.2 Allgemeine Probleme der Programmierung.- 15.3 Probleme der Sprachtheorie.- 15.4 Probleme aus Logik und Arithmetik.- Symbolverzeichnis.