Informatik

1. Information und ihre Repräsentation.- 1.1 Der Begriff„Information“.- 1.2 Ein Beispiel für Information und Repräsentation: Aussageformen.- 1.2.1 Boolesche Terme.- 1.2.2 Die Boolesche Algebra der Wahrheitswerte.- 1.2.3 Interpretation von Booleschen Termen.- 1.2.4 Die Gesetze der Booleschen Algebra und der Booleschen Terme.- 1.2.5 Anwendung der Gesetze für Boolesche Terme: Reduktion.- 1.3 Information und ihre Repräsentation in Normalform.- 1.3.1 Der Übergang von der Repräsentation zur Information.- 1.3.2 Umformungen von Repräsentationen.- 1.3.3 Normalformen und eindeutige Normalformen.- 1.3.4 Zeichensequenzen.- 1.3.5 Formale Sprachen.- 2. Rechenstrukturen und Algorithmen.- 2.1 Zum Begriff „Algorithmus“.- 2.1.1 Informelle Algorithmenbeschreibungen.- 2.1.2 Formale Algorithmenbeschreibung durch Textersetzung.- 2.1.3 Deterministische Textersetzungsalgorithmen.- 2.1.4 Durch Textersetzungsalgorithmen induzierte Abbildungen.- 2.2 Rechenstrukturen.- 2.2.1 Familien von Funktionen und Mengen als Rechenstrukturen.- 2.2.2 Signaturen.- 2.2.3 Grundterme.- 2.2.4 Rechnen mit Grundtermen: Formulare.- 2.2.5 Terme mit (freien) Identifikatoren.- 2.2.6 Interpretation von Termen mit (freien) Identifikatoren.- 2.2.7 Terme mit (freien) Identifikatoren als Formulare.- 2.3 Algorithmen als Termersetzungssysteme.- 2.3.1 Termersetzungsregeln.- 2.3.2 Termersetzungssysteme.- 2.3.3 Der Termersetzungsalgorithmus.- 2.3.4 Korrektheit von Termersetzungssystemen.- 2.4 Aussagenlogik und Prädikatenlogik.- 2.4.1 Aussagenlogik.- 2.4.2 Prädikatenlogik.- 3. Programmiersprachen und Programmierung.- 3.1 Syntax: Beschreibung formaler Sprachen durch BNF.- 3.1.1 BNF-Notation.- 3.1.2 Syntaxdiagramme.- 3.1.3 Kontextbedingungen.- 3.2 Semantik.- 3.3 Zur Implementierung von Programmiersprachen.- 3.4 Methodik der Programmierung.- 3.4.1 Prinzipien der Programmierung.- 3.4.2 Rechenstrukturen.- 4. Applikative Programmiersprachen.- 4.1 Elemente rein applikativer Programmiersprachen.- 4.1.1 Syntax von Ausdrücken und primitive Rechenstrukturen.- 4.1.2 Beschreibung der Bedeutung von Ausdrücken.- 4.1.3 Konstanten und Identifikatoren.- 4.1.4 Bedingte Ausdrücke.- 4.1.5 Funktionsapplikation.- 4.1.6 Bindung von (freien) Identifikatoren: Funktionsabstraktion.- 4.2 Erweiterung applikativer Sprachen: Deklarationen.- 4.2.1 Elementdeklaration.- 4.2.2 Deklarationen für Funktionen.- 4.3 Rekursive Funktionsdeklarationen.- 4.3.1 Induktive Deutung rekursiver Funktionsdeklarationen.- 4.3.2 Deutung als kleinster Fixpunkt.- 4.3.3 Rekursive Funktionsvereinbarungen in Termersetzungssystemen.- 4.3.4 Formulare für rekursive Funktionsdeklarationen.- 4.4 Rekursionsformen.- 4.4.1 Lineare Rekursion.- 4.4.2 Repetitive Rekursion.- 4.4.3 Kaskadenartige Rekursion.- 4.4.4 Vernestete Rekursion.- 4.4.5 Verschränkte Rekursion.- 4.5 Techniken applikativer Programmierung.- 4.5.1 Beschreibung der Aufgabenstellung: Spezifikation.- 4.5.2 Verallgemeinerung der Aufgabenstellung durch Einbettung.- 4.5.3 Zur Strukturierung von Aufgabenstellungen.- 4.5.4 Ableitung von Rekursionen aus Spezifikationen.- 4.5.5 Parameterunterdrückung, untergeordnete Rechenvorschriften.- 4.5.6 Effizienz applikativer Programme.- 4.5.7 Dokumentation.- 4.5.8 Test und Integration von Programmen.- 4.6 Beweistechniken für rekursive Programme.- 4.6.1 Induktion und Rekursion.- 4.6.2 Partielle Korrektheit.- 4.6.3 Terminierungsbeweise.- 5. Zuweisungsorientierte Ablaufstrukturen.- 5.1 Zuweisungsorientierte Sprachelemente: Anweisungen.- 5.1.1 Syntax.- 5.1.2 Programmvariable und Zuweisung.- 5.1.3 Zustände.- 5.1.4 Funktionale Bedeutung von Anweisungen.- 5.1.5 Operationelle Semantik von Anweisungen.- 5.2 Einfache Anweisungen.- 5.2.1 Die „leere“ Anweisung nop.- 5.2.2 Die nichtterminierende Anweisung abort.- 5.2.3 Die Zuweisung.- 5.3 Zusammengesetzte Anweisungen.- 5.3.1 Sequentielle Komposition.- 5.3.2 Bedingte Anweisungen.- 5.3.3 Wiederholungsanweisungen.- 5.4 Variablendeklarationen und Blöcke.- 5.5 Prozeduren.- 5.5.1 Prozedurdeklaration.- 5.5.2 Prozeduraufruf.- 5.5.3 Globale Programmvariablen in Prozeduren.- 5.5.4 Rekursive Prozeduren.- 5.6 Abschnitte, Bindungen, Gültigkeit, Lebensdauer.- 5.7 Programmiertechniken für zuweisungsorientierte Programme.- 5.7.1 Die Methode der Zusicherung.- 5.7.2 Terminierungsbeweise.- 6. Sortendeklarationen.- 6.1 Deklarationen von Sorten.- 6.1.1 Skalare Elemente: Enumeration.- 6.1.2 Direktes Produkt: Tupel.- 6.1.3 Direkte Summe: Variantensorten.- 6.1.4 Teilbereiche.- 6.2 Felder.- 6.2.1 Einstufige Felder.- 6.2.2 Felder in zuweisungsorientierten Sprachen: Selektives Ändern.- 6.2.3 Mehrstufige Felder und allgemeine Indexmengen.- 6.2.4 Dynamische und flexible Felder.- 6.3 Endliche Mengen als Rechenstrukturen.- 7. Maschinennahe Sprachelemente: Sprünge und Referenzen.- 7.1 Kontrollfluß.- 7.1.1 Marken und Sprünge.- 7.1.2 Kontrollflußdiagramme.- 7.2 Referenzen und Zeiger.- 8. Rekursive Sortendeklarationen.- 8.1 Sequenzartige Rechenstrukturen.- 8.1.1 Die Rechenstruktur der Sequenzen.- 8.1.2 Ein/Ausgabe und externe Rechenstrukturen.- 8.2 Baumartige Rechenstrukturen.- 8.3 Rekursive Vereinbarungen von Sorten.- 8.3.1 Induktive Deutung von rekursiven Sortendeklarationen.- 8.3.2 Fixpunktdeutung rekursiver Sortendeklarationen.- 8.3.3 Verwendung rekursiver Sortendeklarationen.- 8.4 Geflechte.- 8.4.1 Einfache Geflechte.- 8.4.2 Rekursiv vereinbarte Geflechtssorten.- 8.4.3 Implementierung von Sequenzen durch verkettete Listen.- 8.4.4 Zweifach verkettete Liste.- 8.4.5 Zyklische Geflechte.- 8.4.6 Gemeinsame Teilstrukturen.- Literaturangaben.- Stichwortverzeichnis.