Informatik

III Systemnahe Programmierung.- 1. Prozesse, Koordination und Kommunikation in verteilten Systemen.- 1.1 Prozesse.- 1.1.1 Aktionsstrukturen als Prozesse.- 1.1.2 Strukturierung von Prozessen.- 1.1.3 Sequentielle Prozesse und Aktionsspuren.- 1.1.4 Zerlegung von Prozessen in Teilprozesse.- 1.1.5 Aktionen als Zustandsübergänge.- 1.2 Systembeschreibung durch Mengen von Prozessen.- 1.2.1 Petri-Netze.- 1.2.2 Prozeßalgebren.- 1.2.3 Synchronisation und Koordination von Agenten.- 1.2.4 Prädikate über Prozessen.- 1.3 Programmiersprachen zur Beschreibung kommunizierender Systeme.- 1.3.1 Kommunikation durch Nachrichtenaustausch.- 1.3.2 Gemeinsame Programmvariable und gemeinsamer Speicher.- 1.3.3 Sprachmittel für parallele Abläufe.- 1.3.4 Ein-/Ausgabeströme.- 2. Betriebssysteme und Systemprogrammierung.- 2.1 Grundlegende Betriebssystemaspekte.- 2.1.1 Aufgaben eines Betriebssystems.- 2.1.2 Betriebsarten.- 2.1.3 Ein einfaches Betriebssystem für den Stapelbetrieb.- 2.1.4 Ein einfaches Betriebssystem für Multiplexbetrieb.- 2.2 Benutzerrelevante Aspekte von Betriebssystemen.- 2.2.1 Kommandosprache.- 2.2.2 Benutzerverwaltung.- 2.2.3 Zugriff auf Rechenleistung.- 2.2.4 Dateiorganisation und -verwaltung.- 2.2.5 Übertragungsdienste.- 2.2.6 Zuverlässigkeit und Schutzaspekte.- 2.3 Betriebsmittelzuteilung.- 2.3.1 Prozessorvergabe.- 2.3.2 Hauptspeicherverwaltung.- 2.3.3 Zuteilung der Ein-/Ausgabegeräte.- 2.3.4 Betriebsmittelvergabe im Mehrprogrammbetrieb.- 2.3.5 Betriebsmittelzuteilung im Dialogbetrieb.- 2.4 Techniken der Systemprogrammierung.- 2.4.1 Das Unterbrechungskonzept.- 2.4.2 Koordination und Synchronisation.- 2.4.3 Segmentierung.- 2.4.4 Seitenaustauschverfahren.- 2.4.5 Verschiebbarkeit von Programmen.- 2.4.6 Simultane Benutzbarkeit von Unterprogrammen.- 2.4.7 Steuerung von E/A-Geräten.- 2.5 Betriebssystemstrukturen.- 2.5.1 Betriebssystemstrukturierung.- 2.5.2 Prozeßorientierte Betriebssystemstrukturen.- 3. Interpretation und Übersetzung von Programmen.- 3.1 Lexikalische Analyse von Programmiersprachen.- 3.1.1 Die Vorgruppierabbildung.- 3.1.2 Ein ausführlicheres Beispiel AS.- 3.1.3 Lexikalische Analyse von AS.- 3.2 Zerteilung von Programmen.- 3.2.1 Abstrakte Syntax.- 3.2.2 Baumdarstellung von AS-Programmen.- 3.2.3 Parsen von AS-Programmen.- 3.3. Kontextbedingungen.- 3.3.1 Kontextbedingungen und Prädikate.- 3.3.2 Kontextbedingungen für die Programmiersprache AS.- 3.3.3 Syntaktische Analyse von AS.- 3.4 Interpretation von Programmiersprachen.- 3.4.1 Semantik.- 3.4.2 Syntax und Semantik.- 3.4.3 Eingabe und Ausgabe.- 3.4.4 Interpretierer.- 3.4.5 Die Kellermaschine: Ein Beispiel für einen Interpretierer.- 3.4.6 Ein AS-Interpretierer.- 3.4.7 Allgemeine Bemerkungen zu Interpretierern.- 3.5 Übersetzung von Programmiersprachen.- 3.5.1 Übersetzer.- 3.5.2 Übersetzung von AS-Programmen in KMS-Programme.- 3.5.3 Allgemeine Bemerkungen zu Übersetzern.- Literaturangaben zu Teil III.- IV Formale Sprachen, Berechenbarkeit, Komplexität, Logikprogrammierung.- 1. Formale Sprachen.- 1.1 Relationen und Graphen.- 1.1.1 Zweistellige Relationen.- 1.1.2 Wege in Graphen und Hüllenbildung.- 1.2 Grammatiken.- 1.2.1 Reduktive und generative Grammatiken.- 1.2.2 Die Sprachhierarchie nach Chomsky.- 1.2.3 Strukturgraphen und Strukturbäume.- 1.2.4 Sackgassen und unendliche Ableitungspfade.- 1.3 Chomsky-3-Sprachen und endliche Automaten.- 1.3.1 Reguläre Ausdrücke.- 1.3.2 Endliche Automaten.- 1.3.3 Äquivalenz der Darstellungsformen.- 1.3.4 Reguläre Ausdrücke, endliche Automaten und Chomsky-3-Sprachen.- 1.3.5 Minimale Automaten.- 1.4 Kontextfreie Sprachen und Kellerautomaten.- 1.4.1 Die BNF-Notation.- 1.4.2 Kellerautomaten.- 1.4.3 Kellerautomaten und kontextfreie Sprachen.- 1.4.4 Greibach-Normalform.- 1.4.5 LR(k)-Sprachen.- 1.4.6 LL(k)-Grammatiken.- 1.4.7 Das Verfahren des rekursiven Abstiegs.- 1.5 Kontextsensitive Grammatiken.- 2. Berechenbarkeit.- 2.1 Hypothetische Maschinen.- 2.1.1 Die Turing-Maschine.- 2.1.2 Registermaschinen.- 2.2 Rekursive Funktionen.- 2.2.1 Primitiv rekursive Funktionen.- 2.2.2 µ-rekursive Funktionen.- 2.2.3 Allgemein rekursive Funktionen.- 2.3 Äquivalenz der Berechenbarkeitsbegriffe.- 2.3.1 Äquivalenz von µ-Berechenbarkeit und Turing-Berechenbarkeit.- 2.3.2 Äquivalenz von RM- und Turing-Berechenbarkeit.- 2.3.3 Die Churchsche These.- 2.4 Entscheidbarkeit.- 2.4.1 Nichtberechenbare Funktionen.- 2.4.2 Entscheidbare Prädikate.- 2.4.3 Rekursive und rekursiv aufzählbare Mengen.- 3. Komplexitätstheorie.- 3.1 Komplexitätsmaße.- 3.1.1 Zeitkomplexität.- 3.1.2 Bandkomplexität.- 3.1.3 Zeit-und Bandkomplexität von Problemen.- 3.1.4 Polynomiale und nichtdeterministisch polynomiale Zeitkomplexität.- 3.1.5 Backtracking-Nichtdeterminismus in Programmiersprachen.- 3.2 NP-Vollständigkeit.- 3.2.1 Das Erfüllbarkeitsproblem für Boolesche Ausdrücke.- 3.2.2 Weitere NP-vollständige Probleme.- 3.3 Effiziente Algorithmen für NP-vollständige Probleme.- 3.3.1 Geschicktes Durchsuchen großer Baumstrukturen.- 3.3.2 Alpha/Beta-Suche.- 3.3.3 Dynamisches Programmieren.- 3.3.4 Greedy-Algorithmen.- 4. Effiziente Algorithmen und Datenstrukturen.- 4.1 Ausgewählte Algorithmen.- 4.1.1 Komplexität von Sortieralgorithmen.- 4.1.2 Wege in Graphen.- 4.2 Bäume.- 4.2.1 Geordnete, orientierte und sortierte Bäume.- 4.2.2 Darstellung von Bäumen durch Felder.- 4.2.3 AVL-Bäume.- 4.2.4 B-Bäume.- 4.3 Effiziente Speicherung von Mengen.- 4.3.1 Die Rechenstruktur der Mengen mit Zugriff über Schlüssel.- 4.3.2 Mengendarstellung durch AVL-Bäume.- 4.3.3 Streuspeicherverfahren.- 5. Beschreibungstechniken in der Programmierung.- 5.1 Formalismen für die Spezifikation.- 5.1.1 Abstraktion in der Spezifikation.- 5.1.2 Die Spezifikation von abstrakten Rechenstrukturen.- 5.1.3 Spezifikation von Funktionen.- 5.1.4 Spezifikation von Anweisungen.- 5.2 Datenbanken und Informationssysteme.- 5.2.1 Die Entitäts/Relationsbeziehungsmodellierung.- 5.2.2 Entitäts/Relations-Diagramme.- 5.2.3 Charakterisierung von Relationen.- 5.2.4 Zur Verwendung von Datenbanksystemen.- 5.2.5 Das DB-Managementsystem.- 5.2.6 Datenbankabfragen und Ändern der Datenbestände.- 5.3 Logikprogrammierung.- 5.3.1 Eine Problemlösung mit Logikprogrammen.- 5.3.2 Die Auswertung von Logikprogrammen.- 5.3.3 Unifikation.- 5.4. Komponenten, Schnittstellen, Softwarearchitekturen.- 5.4.1 Komponenten und deren Schnittstellen.- 5.4.2 Zustandsmaschinen mit Ein/Ausgabe.- 5.4.3 Softwarearchitekturen als Datenflußdiagramme.- 6. Abschließende Bemerkungen zur Entwicklung und Anwendungsgebieten der Informatik.- 6.1 Anwendungsgebiete der Informatik.- 6.2 Informatik und Recht.- 6.3 Soziale Kompetenz der Informatiker.- 6.4 Informatik und Ökonomie.- 6.5 Informatik, Wissenschaftstheorie und Philosophie.- 6.6 Zur Verantwortung des Informatikers.- Literaturangaben zu Teil IV.- Stichwortverzeichnis.