Skriptum Informatik — eine konventionelle Einführung

1. Grundlagen.- 1.1 Algorithmus und Berechenbarkeit.- 1.1.1 Algorithmus.- 1.1.2 Turing-Maschine.- 1.1.3 Berechenbarkeit.- 1.2 Sprache und Grammatik.- 1.2.1 Sprache.- 1.2.2 Grammatik.- 1.3 Rechner.- 1.3.1 Von-Neumann-Rechnerarchitektur.- 1.3.2 Rechnersysteme.- 1.4 Informatik als Wissenschaft.- 2. Imperative Programmierung -- die Sprache MODULA-2.- 2.1 Syntaxdarstellungen.- 2.2 Elementare funktionale Modula-2-Programme.- 2.2.1 Eine MODULA-2-Teilsprache.- 2.2.2 Programmverzweigungen.- 2.2.3 Funktionen und Prozeduren.- 2.2.4 Elementare Datentypen, Aufzählungs- und Bereichstypen.- 2.2.5 Eingabevariablen.- 2.2.6 Rekursive Funktionen und Prozeduren.- 2.2.7 Nachteile functional-rekursiver Programme.- 2.3 Iterative Programme.- 2.3.1 Wertzuweisungen und Referenzparameter.- 2.3.2 Gültigkeitsbereich und Lebensdauer.- 2.3.3 Anweisungen zur Iteration.- 2.3.4 Vergleich iterativer und rekursiver Lösungen.- 2.3.5 Sprunganweisungen.- 2.3.6 Prozedurtypen.- 2.4 Komplexe Datentypen.- 2.4.1 Mengen (Sets).- 2.4.1.1 Darstellung und Manipulation von Mengen.- 2.4.1.2 Ein Beispiel für Sets.- 2.4.2 Arrays (Felder).- 2.4.3 Records (Verbunde).- 2.4.3.1 Einfache Records.- 2.4.3.2 Records mit Varianten.- 2.4.4 Zeiger (Pointer) und dynamische Variablen.- 2.4.4.1 Die Speicherung auf der Halde.- 2.4.4.2 Operationen auf Zeigern.- 2.4.4.3 Verkettete Listen.- 2.4.4.4 Anwendungen und Probleme dynamischer Variablen.- 2.4.5 Dateien (Files).- 2.4.5.1 Eigenschaften und formale Beschreibung.- 2.4.5.2 Dateien in PASCAL.- 2.4.5.3 Dateien in MODULA-2.- 3. Abstraktion.- 3.1 Abstraktionskonzepte in Programmiersprachen.- 3.2 Abstraktion in MODULA-2.- 3.2.1 Das Prinzip der separaten Übersetzung.- 3.2.2 Modularisierung eines Programms.- 3.2.3 Datenkapselung.- 3.2.4 Abstrakte Datentypen.- 3.2.4.1 Das Prinzip des Abstrakten Datentyps.- 3.2.4.2 Abstrakte Datentypen Schlange und Stack.- 3.2.4.3 Abstrakter Datentyp für große Zahlen.- 3.2.4.4 Abstrakter Datentyp für komplexe Zahlen.- 4. Semantik, Verifikation und Test.- 4.1 Konzepte für eine Semantikdefinition.- 4.1.1 Semantik: Begriff und Motivation.- 4.1.2 Grundprinzipien von Semantiknotationen.- 4.1.3 Ein Beispiel für die operationale Semantik.- 4.2 Spezifikation und Verifikation von Programmen.- 4.2.1 Vor- und Nachbedingungen.- 4.2.2 Semantikdefinition einiger Anweisungen.- 4.2.3 Die Verifikation iterativer Programme.- 4.2.4 Beschreibung einer Schleife durch eine Invariante.- 4.2.5 Konstruktion iterativer Programme.- 4.2.6 Zusammenfassung.- 4.3 Test.- 4.3.1 Begriffsbildung und Prinzipien.- 4.3.2 Grenzen des Testens.- 4.3.3 Die Konstruktion von Testdaten.- 4.3.4 Zusammenfassung.- 5. Programmierparadigmen und -sprachen.- 5.1 Programmierparadigmen.- 5.1.1 Imperatives Programmieren.- 5.1.2 Funktionales Programmieren.- 5.1.3 Logikbasiertes Programmieren.- 5.1.4 Objektorientiertes Programmieren.- 5.1.5 Regelbasiertes Programmieren.- 5.1.6 Programmierung von Mehr-Prozessor-Systemen.- 5.2 Übersicht über Programmiersprachen.- 6. Datenstrukturen und Algorithmen.- 6.1 Komplexität und Effizienz.- 6.1.1 Motivation und Begriffsbildung.- 6.1.2 Effizienz und Komplexität von Algorithmen.- 6.1.3 Komplexität von Funktionen und Sprachen.- 6.2 Graphen und Bäume.- 6.2.1 Graphen.- 6.2.2 Bäume.- 6.3 Suchen in gegebenen Datenstrukturen.- 6.3.1 Suchen in Tabellen.- 6.3.2 Suchen von Zeichenketten.- 6.4 Datenorganisationen für effizientes Suchen.- 6.4.1 Suchverfahren auf Bäumen.- 6.4.1.1 Binäre Suchbäume.- 6.4.1.2 AVL-Bäume.- 6.4.1.3 Optimale Suchbäume.- 6.4.1.4 B-Bäume.- 6.4.1.5 Weitere balancierte Suchbäume.- 6.4.2 Hashing.- 6.4.2.1 Begriffsbildung und Anforderungen.- 6.4.2.2 Perfektes Hashing.- 6.4.2.3 Kollisionsbehandlung.- 6.4.2.4 Löschen in Hash-Tabellen.- 6.4.2.5 Aufwandsabschätzung.- 6.4.2.6 Implementierung von Kollisionsbehandlungen.- 6.5 Sortieren.- 6.5.1 Klassifizierung und allgemeine Betrachtungen.- 6.5.2 Interne Sortierverfahren.- 6.5.2.1 Einfache Sortierverfahren.- 6.5.2.2 Schnelle Sortierverfahren.- 6.5.2.3 Implementierung ausgewählter Sortierverfahren.- 6.5.2.4 Aufwandsvergleich der Sortierverfahren.- 6.5.2.5 Sortieren durch Streuen und Sammeln.- 6.5.3 Externe Sortierverfahren.- 6.5.3.1 Direktes Mischen.- 6.5.3.2 Natürliches Mischen.- 6.5.3.3 Mehrwege-Mischen.- 6.6 Speicherverwaltung.- 6.6.1 Algorithmische Konzepte.- 6.6.2 Implementierung von Stacks.- Anhang A: Mathematische Grundbegriffe und Formeln.- Anhang B: Syntaxdiagramme für MODULA-2.- Literatur.- Abkürzungsverzeichnis.- MODULA-2-Index.