Informatik

Inhaltsverzeichnis

• Vorbemerkung.
• 1. Information und Nachricht.
• 1.1 Nachricht und Information.
• 1.1.1 Sprachliche Nachrichten.
• 1.1.2 Schrift.
• 1.2 Sinnesorgane.
• 1.2.1 Arbeitsweise der Sinnesorgane, Reizleitung.
• 1.2.2 Reizverarbeitung im Gehirn.
• 1.2.3 Tragweite informationistischer Vorstellungen.
• 1.3 Nachrichtengeräte.
• 1.3.1 Arten von Nachrichtengeräten.
• 1.3.2 Signale und Signalparameter.
• 1.4 Digitale Nachrichten.
• 1.4.1 Zeichen, Zeichenvorräte, Alphabete.
• 1.4.2 Codes und Codierungen.
• 1.4.3 Serien- und Parallelübertragung.
• 1.4.4 Symbole.
• 1.5 Nachrichtenverarbeitung und Informationsverarbeitung.
• 1.5.1 Nachrichtenverarbeitung als Codierung.
• 1.5.2 Die Interpretation einer Nachrichtenverarbeitung.
• 1.6 Algorithmen.
• 1.6.1 Charakteristische Eigenschaften von Algorithmen.
• 1.6.2 Beispiele von Algorithmen.
• 1.6.3 Rekursion und Iteration.
• 1.6.4 Besondere Beschreibungsformen von Algorithmen.
• 1.6.4.1 Beispiel: Markov-Algorithmen.
• 1.6.4.2 Rekursive Algorithmen nach McCarthy.
• 2. Begriffliche Grundlagen der Programmierung.
• 2.1 Grundlegende Rechenstrukturen.
• 2.1.1 Objekte.
• 2.1.1.1 Sorten von Objekten.
• 2.1.1.2 Standardbezeichnungen für Objekte.
• 2.1.2 Operationen.
• 2.1.3 Rechenstrukturen.
• 2.1.3.1 Die Rechenstruktur ? der ganzen Zahlen.
• 2.1.3.2 Die Rechenstruktur ? der natürlichen Zahlen.
• 2.1.3.3 Rechenstrukturen für rationale, numerisch-reelle und numerisch-komplexe Rechnung.
• 2.1.3.4 Rechenstrukturen für nicht-numerisches Rechnen: Zeichenfolgen.
• 2.1.3.5 Rechenstrukturen für nicht-numerisches Rechnen: Binäre (Zeichen-)Listen.
• 2.1.3.6 Die Rechenstruktur B2 der Wahrheitswerte.
• 2.1.3.7 Übergänge zwischen Sorten.
• 2.1.3.8 Zusammengesetzte Objekte.
• 2.2 Formeln.
• 2.2.1 Parameterbezeichnungen.
• 2.2.2 Formeln und Formulare.
• 2.2.2.1 Aufbau von Formeln.
• 2.2.2.2 Formulare.
• 2.2.2.3 Striktheit der Operationen.
• 2.2.2.4 Umformungen von Formeln.
• 2.2.3 Bedingte Formeln.
• 2.2.3.1 Alternative und sequentielle Fallunterscheidung.
• 2.2.3.2 Bewachte Fallunterscheidung.
• 2.2.3.3 Durchführung der Berechnung auf Formularen mit Fallunterscheidungen.
• 2.2.3.4 Der nicht-strikte Charakter der Fallunterscheidung...
• 2.3 Rechenvorschriften.
• 2.3.1 Vereinbarung von Rechenvorschriften.
• 2.3.1.1 Schreibweisen.
• 2.3.1.2 Systeme von Rechenvorschriften.
• 2.3.1.3 Zusicherungen.
• 2.3.1.4 Gebundene Bezeichnungen.
• 2.3.2 Rekursion.
• 2.3.3 Die (rekursive) Formularmaschine.
• 2.4 Zur Technik der rekursiven Programmierung.
• 2.4.1 Wie kommt man zu rekursiven Rechenvorschriften?.
• 2.4.1.1 Inhärent rekursive Definitionen.
• 2.4.1.2 Ableitung einer Rekursion aus der Aufgabenstellung.
• 2.4.1.3 Einbettung.
• 2.4.1.4 Verwandte Aufgaben.
• 2.4.1.5 Das Arbeiten mit charakterisierenden Eigenschaften.
• 2.4.1.6 Umkehrung.
• 2.4.2 Wie beweist man Eigenschaften von Algorithmen?.
• 2.4.3 Bemerkungen über Terminierung und die Bedeutung von Zusicherungen und Wächtern.
• 2.5 Unterordnung von Rechenvorschriften.
• 2.5.1 Untergeordnete Rechenvorschriften.
• 2.5.2 Unterdrückte Parameter.
• 2.5.2.1 Globale und nichtlokale Parameter.
• 2.5.2.2 Verschattung.
• 2.5.2.3 Konstant besetzte Parameter.
• 2.5.3 Parameterfreie Rechenvorschriften.
• 2.6 Rechenvorschriften als Parameter und als Ergebnisse.
• 2.6.1 Rechenvorschriften als Parameter.
• 2.6.2 Verzögerte Auswertung durch Verwendung parameterfreier Rechenvorschriften als Parameter.
• 2.6.3 Rechenvorschriften als Ergebnisse.
• 3. Maschinenorientierte algorithmische Sprachen.
• 3.1 Allgemeine Abschnitte.
• 3.1.1 Zwischenergebnis-Vereinbarungen.
• 3.1.1.1 Eine vereinfachte Notation.
• 3.1.1.2 Zwischenergebnisbezeichnungen in rekursiven Rechenvorschriften.
• 3.1.1.3 Sequentialisierung des Berechnungsganges.
• 3.1.1.4 Anmerkung betreffend PASCAL.
• 3.1.2 Kollektive Zwischenergebnisvereinbarungen.
• 3.2 Programmierung mit Variablen.
• 3.2.1 Wiederverwendbare Zwischenergebnisbezeichnungen.
• 3.2.2 Vereinbarungen und Zuweisungen.
• 3.2.3 Konstant gehaltene Variable.
• 3.2.4 Anweisungen.
• 3.2.5 Beispiele.
• 3.2.6 Kollektive Variablenvereinbarungen und kollektive Zuweisungen.
• 3.3 Iterative Programmierung.
• 3.3.1 Iterative Auffassung repetitiver Rechenvorschriften.
• 3.3.2 Wiederholung.
• 3.3.2.1 Iterative Programme.
• 3.3.2.2 Gestaffelte repetitive Systeme und geschachtelte Wiederholung.
• 3.3.2.3 Nassi-Shneidermann-Diagramme.
• 3.3.3 Problemlösung in iterativer Form.
• 3.3.4 Sequentialisierung.
• 3.3.5 Bedingte Anweisungen.
• 3.3.5.1 Alternative Anweisungen.
• 3.3.5.2 Sequentielle bedingte Anweisungen.
• 3.3.5.3 Bewachte Anweisungen.
• 3.3.6 Die leere Anweisung.
• 3.4 Sprünge.
• 3.4.1 Schlichte Aufrufe und Sprünge.
• 3.4.2 Wiederholungen mittels Sprüngen.
• 3.4.3 Programmablaufpläne.
• 3.5 Prozeduren.
• 3.5.1 Variable als Parameter.
• 3.5.2 Prozedurvereinbarungen.
• 3.5.3 Aufrufe von Prozeduren.
• 3.5.4 Transiente Parameter und Resultatparameter.
• 3.5.5 Eingangsparameter.
• 3.5.6 Unterdrückte Variablenparameter.
• 3.5.7 Prozeduren als Strukturierungsmittel.
• 3.5.8 Rekursive Definition der Wiederholung.
• 3.5.8.1 Sprung als schlichter parameterfreier Prozeduraufruf.
• 3.5.8.2 Rekursive Definition der bedingten Wiederholung.
• 3.5.8.3 Rekursive Definition der gezählten Wiederholung.
• 3.6 Felder.
• 3.6.1 Indizierte Variable.
• 3.6.2 Mehrstufige Felder.
• 3.6.3 Zurückführung mehrstufiger Felder auf einstufige.
• 3.6.4 Statische Speicherverteilung.
• 3.7 Aufbrechen von Formeln.
• 3.7.1 Aufbrechen nach dem Kellerprinzip.
• 3.7.2 Verwendung eines Zwischenergebniskellers.
• 3.7.3 Überführung in Drei-Adreß-Form.
• 3.7.4 Überführung in Ein-Adreß-Form.
• 3.7.5 Grenzen des Kellerprinzips.
• 3.7.6 Behandlung von Fallunterscheidungen.
• 3.7.7 Elimination Boolescher Operationen.
• 4. Binäre Schaltnetze und Schaltwerke.
• 4.1 Boolesche Algebra.
• 4.1.1 Abstrakte Definition einer Booleschen Algebra.
• 4.1.2 Das Boolesche Normalform-Theorem.
• 4.1.3 Ordnungsrelation einer Booleschen Algebra, Implikation.
• 4.1.3.1 Die Stärker-Relation.
• 4.1.3.2 Stärker-Relation auf Booleschen Funktionen.
• 4.1.3.3 Ordnungsrelation zwischen Booleschen Ausdrücken.
• 4.1.3.4 Anwendungen auf Aussagen und Prädikate.
• 4.1.4 Entscheidungstabellen.
• 4.1.4.1 Kollaterale Entscheidungstabellen.
• 4.1.4.2 Sequentielle Entscheidungstabellen.
• 4.1.5 Schaltfunktionen.
• 4.1.5.1 Sinnbilder für Schaltfunktionen.
• 4.1.5.2 Zusammensetzung von Sinnbildern.
• 4.1.5.3 Beispiel: Halbaddierer, Volladdierer.
• 4.1.5.4 Beispiel: Codeumsetzer.
• 4.1.6 Technische Verwirklichung von Schaltnetzen.
• 4.2 Binärcodierung.
• 4.2.1 Binärer Vergleich.
• 4.2.2 Binäre Arithmetik.
• 4.2.2.1 Binärzähler.
• 4.2.2.2 Addition und Subtraktion.
• 4.2.2.3 Multiplikation.
• 4.2.2.4 Operationen mit binär dargestellten Zeichenfolgen und beblätterten Bäumen.
• 4.2.3 Arithmetik mit beschränkter Stellenzahl.
• 4.3 Schaltwerke.
• 4.3.1 Speichervariable für Binärworte.
• 4.3.1.1 Beispiel: Addition.
• 4.3.1.2 Binäre Register und Merkglieder.
• 4.3.1.3 Zusammenschaltung von Merkgliedern und Verknüpfungsgliedern.
• 4.3.2 Aufbau von Schaltwerken.
• 4.3.2.1 Serienaddierer und Paralleladdierer.
• 4.3.2.2 Verschiebe-Schaltwerke.
• 4.3.3 Flipflops.
• 4.3.4 Flipflopschaltwerke.
• 4.3.4.1 Flipflopschaltwerke für die Arithmetik.
• 4.3.4.2 Flipflopschaltwerke für nicht-arithmetische Operationen.
• 4.3.5 Technische Verwirklichung von Schaltwerken.
• 4.4 Leistungen und Grenzen der Technologie.
• Anhang A: Zahlsysteme.
• A.1 Stellenwertcodes und Konvertierung ganzer Zahlen.
• A.2 Darstellung negativer Zahlen.
• A.3 Die vier Grundrechenarten.
• A.4 Gleitpunktzahlen.
• Anhang B: Shannonsche Informationstheorie.
• B.1 Diskretisierung.
• B.1.1 Rasterung.
• B.1.2 Quantelung.
• B.2 Probabilistische Theorie der Information.
• B.2.1 Shannonsche Nachrichten.
• B.2.2 Die Entscheidungsinformation.
• B.2.3 Kanalkapazität.
• B.2.4 Codesicherung.
• Ergänzende Literatur.
• Namen- und Sachverzeichnis.