Konstruktion digitaler Systeme

1 Grundbegriffe der Informatik.- 1.1 Mengen, Relationen, Funktionen und Computer.- 1.1.1 Teilmengen und Aussagen.- 1.1.2 Kartesische Produkte, Relationen, Graphen.- 1.1.3 Funktionen.- 1.1.4 Abstrakte, universelle Maschinen.- 1.2 Schleifenfreie Algorithmen und Boolesche Funktionen.- 1.2.1 Konstruktion von Funktionen.- 1.2.2 Schleifenfreie Algorithmen.- 1.2.3 Boolesche Funktionen.- 1.2.4 Codierung von Daten und reale Maschinen.- 1.2.5 Boolesche Algebren.- 1.2.6 Vereinfachung von Booleschen Algorithmen.- 1.3 Algorithmen, Berechenbarkeit, Komplexität.- 1.3.1 Rekursion.- 1.3.2 Berechenbare Funktionen.- 1.3.3 Verifikation von Algorithmen.- 1.3.4 Operativ definierte Mengen.- Zusammenfassung.- Übungsaufgaben zu Kapitel 1.- 2 Arithmetik und spezielle Funktionen.- 2.1 Zahlen und ihre Codierung.- 2.1.1 Polyadische Codes.- 2.1.2 Polyadische Arithmetik.- 2.1.3 Rechnen mit endlicher Wortlänge.- 2.1.4 Abgeleitete Codierungsarten.- 2.1.5 Fließkommaarithmetik.- 2.1.6 Codierung durch simultane Reste.- 2.1.7 Reelle Zahlen.- 2.2 Spezielle Funktionen.- 2.2.1 Polynomfunktionen.- 2.2.2 Approximation reeller Funktionen.- 2.2.3 Operationen auf Funktionen.- 2.2.4 Algorithmen für Permutationen.- Zusammenfassung.- Übungsaufgaben zu Kapitel 2.- 3 Rechenmaschinen mit Speicher.- 3.1 Aufgabe und Funktionsweise von Speichern.- 3.2 Endliche Automaten.- 3.3 Programmierbare Universalrechner.- 3.4 Ausführung rekursiver Algorithmen.- 3.5 Das Halteproblem.- 3.6 Harvard-Architektur und von—Neumann—Rechner.- 3.7 Mikroprozessoren.- 3.7.1 CPU und Speicher.- 3.7.2 Ein- und Ausgabeschnittstellen.- 3.7.3 Der Transputer T 225.- Zusammenfassung.- Übungsaufgaben zu Kapitel 3.- 4 Grundzüge der Programmierung.- 4.1 Das Zeitverhalten von Programmen.- 4.1.1 Befehls-Schedules.- 4.1.2 Parallele Programmierung.- 4.1.3 Parallele Verarbeitungsprozesse auf einem Rechner.- 4.1.4 Interrupts und Kontextwechsel.- 4.1.5 Modellierung durch Petri—Netze.- 4.1.6 Gegenseitiger Ausschluß.- 4.2 Die Verwendung des Speichers.- 4.2.1 Speicheradressierung.- 4.2.2 Wiederverwendung von Speicherzellen.- 4.2.3 Anordnung von Codes im Speicher.- 4.2.4 Abstrakte Datentypen: Beispiele und Implementierungen.- 4.2.5 Universelle Datentypen.- 4.2.6 Objekte, Funktionen, Prozesse.- Zusammenfassung.- Übungsaufgaben zu Kapitel 4.- 5 Spezielle Algorithmen.- 5.1 Asymptotische Komplexität.- 5.2 Algorithmen auf Zahlen.- 5.2.1 Schnelle Multiplikation.- 5.2.2 Faktorisierung.- 5.2.3 Ein Verschlüsselungsverfahren.- 5.3 Eine Vektortransformation.- 5.4 Suchalgorithmen.- 5.4.1 Implementierungen des Mengentyps.- 5.4.2 Lineare Suche.- 5.4.3 Das Hash-Verfahren.- 5.4.4 Binäre Suche.- 5.4.5 Suchen in Bäumen.- 5.4.6 Höhenbalancierte Bäume.- 5.5 Einfügen in einen Datensatz.- 5.5.1 Einfügen von Arrays.- 5.5.2 Einfügen in Bäume.- 5.6 Sortieralgorithmen.- 5.6.1 Bubble Sort.- 5.6.2 Merge Sort.- 5.7 Dynamische Programmierung.- 5.8 Backtracking im Zustandsgraph.- Zusammenfassung.- Übungsaufgaben zu Kapitel 5.- 6 Programmiersprachen.- 6.1 Programmiersprachen als Hilfsmittel.- 6.2 Abstraktion im Assembler.- 6.3 Interpreter und Compiler.- 6.4 Imperative Sprachen.- 6.4.1 Codierungsystem, Zuweisungen und Schedules.- 6.4.2 Verwendung abstrakter Datentypen.- 6.4.3 Nicht-sequenzielle Programmstrukturen.- 6.5 Funktionale Programmierung.- 6.6 Probleme mit vielfachen Lösungen.- 6.6.1 Mehrwertige Funktionen und Relationen.- 6.6.2 Logische Programmierung.- 6.7 Rechner mit verschaltbaren Logikelementen.- 6.7.1 Konfigurierbare Digitalschaltungen.- 6.7.2 Programmieraspekte.- 6.7.3 Sprachen zur Hardwarebeschreibung.- Zusammenfassung.- Übungsaufgaben zu Kapitel 6.- A Arbeitstechnik in Softwareprojekten.- Sachwortverzeichnis.