Theoretische Grundlagen der Informatik

Angesichts der Komplexität der Produkte der modernen Informatik wird eine saubere, theoretische Fundierung immer wichtiger. Das Buch wendet sich an Studierende im ersten Studienabschnitt und an Praktiker und gibt eine Einführung in die theoretischen und zumeist mathematischen Grundlagen der Informatik. Lesern ohne mathematische Vorbildung wird eine Vorstellung von der Denk- und Arbeitsweise der theoretischen Informatik vermittelt. Angesichts der Stoffülle und Komplexität dieses Gebietes werden detaillierte oder auch nur ausführlichere Kenntnisse in theoretischer Informatik wohl dem Spezialisten vorbehalten bleiben. Das Buch ist deshalb betont breit gehalten und zielt auf einen Überblick unterschiedlichster Techniken und Ansätze ab. Der Autor behandelt nach einer Einführung in mathematische Grundbegriffe die klassischen Themen wie formale Sprachen oder Berechenbarkeit, wendet sich aber auch der Semantik von Programmiersprachen und der Codierungstheorie zu und beantwortet die Frage, wie Information gemessen werden kann.

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.