Informatik Eine grundlegende Einführung Band 1: Programmierung und Rechnerstrukturen

Diese Einführung in die Informatik behandelt die fundamentalen Modelle, Formalismen und sprachlichen Konstruktionen sowie die wichtigsten Anwendungsgebiete und technischen Konzeptionen der Informatik. Die Darstellung zeichnet sich durch saubere, formale Fundierung und begriffliche Klarheit aus. Der erste Teil stellt das gesamte Gebiet der problemnahen Programmierung vor, von Algorithmenbegriffen über Techniken der funktionalen und der prozeduralen Programmierung und Datenstrukturen zur Programmiermethodik. Der zweite behandelt die technische Informationsverarbeitung, von der Binärcodierung über digitale Schaltungen und Rechnerarchitekturen bis hin zu maschinennaher Programmierung.

I Problemnahe Programmierung.- 1. Information und ihre Repräsentation.- 1.1 Der Begriff „Information“.- 1.2 Aussagen als Beispiel für Informationen.- 1.2.1 Boolesche Terme.- 1.2.2 Die Boolesche Algebra der Wahrheitswerte.- 1.2.3 Interpretation Boolescher Terme.- 1.2.4 Gesetze der Booleschen Algebra.- 1.2.5 Anwendung der Gesetze der Booleschen Algebra.- 1.3 Information und 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 Textersetzungsalgorithmen.- 2.1.3 Deterministische Textersetzungsalgorithmen.- 2.1.4 Durch Textersetzungsalgorithmen induzierte Abbildungen.- 2.2 Rechenstrukturen.- 2.2.1 Funktionen und Mengen als Rechenstrukturen.- 2.2.2 Signaturen.- 2.2.3 Grundterme.- 2.2.4 Rechnen mit Grundtermen durch Formulare.- 2.2.5 Terme mit (freien) Identifikatoren.- 2.2.6 Interpretation von Termen.- 2.2.7 Terme 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.- 3.1 Syntax und 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 und Abstraktion.- 4. Applikative Programmiersprachen.- 4.1 Elemente rein applikativer Programmiersprachen.- 4.1.1 Ausdrücke und primitive Rechenstrukturen.- 4.1.2 Zur 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 Funktionsabstraktionen.- 4.2 Deklarationen in applikativen Sprachen.- 4.2.1 Elementdeklaration.- 4.2.2 Funktionsdeklaration.- 4.3 Rekursive Funktionsdeklarationen.- 4.3.1 Induktive Deutung rekursiver Funktionsdeklarationen.- 4.3.2 Deutung als kleinster Fixpunkt.- 4.3.3 Rekursion und Termersetzung.- 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 Spezifikation der Aufgabenstellung.- 4.5.2 Einbettung der Aufgabenstellung.- 4.5.3 Zur Strukturierung von Aufgabenstellungen.- 4.5.4 Ableitung von Rekursion aus Spezifikationen.- 4.5.5 Parameterunterdrückung.- 4.5.6 Effizienz applikativer Programme.- 4.5.7 Dokumentation.- 4.5.8 Test und Integration von Programmen.- 4.6 Korrektheitsbeweise für rekursive Programme.- 4.6.1 Induktion und Rekursion.- 4.6.2 Partielle Korrektheit.- 4.6.3 Terminierungsbeweise.- 5. Zuweisungsorientierte Programmierung.- 5.1 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 Operationale 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 Abschnitt, Bindung, Gültigkeit, Lebensdauer.- 5.7 Programmiertechniken für Zuweisungen.- 5.7.1 Die Methode der Zusicherung.- 5.7.2 Terminierungsbeweise.- 6. Sortendeklarationen.- 6.1 Deklarationen von Sorten.- 6.1.1 Skalare Elemente durch Enumeration.- 6.1.2 Direktes Produkt und Tupelsorten.- 6.1.3 Direkte Summe und Variantensorten.- 6.1.4 Teilbereiche.- 6.2 Felder.- 6.2.1 Einstufige Felder.- 6.2.2 Felder und selektives Ändern.- 6.2.3 Mehrstufige Felder und allgemeine Indexmengen.- 6.2.4 Dynamische und flexible Felder.- 6.3 Endliche Mengen als Rechenstrukturen.- 7. 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 und dynamische Sorten.- 8.1 Sequenzartige Rechenstrukturen.- 8.1.1 Die Rechenstruktur der Sequenzen.- 8.1.2 Die Rechenstruktur der Stapel und Keller.- 8.1.3 Die Rechenstruktur der Warteschlangen.- 8.1.4 Ein-/Ausgabe und externe Rechenstrukturen.- 8.2 Baumartige Rechenstrukturen.- 8.3 Rekursive Sortenvereinbarung.- 8.3.1 Induktive Deutung rekursiver 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 Geflechtsorten.- 8.4.3 Sequenzen durch verkettete Listen.- 8.4.4 Zweifach verkettete Listen.- 8.4.5 Zyklische Geflechte.- 8.4.6 Gemeinsame Teilstrukturen.- 9. Objektorientierte Programmierung.- 9.1 Klassen und Objekte.- 9.1.1 Klassen.- 9.1.2 Erzeugung von Objekten aus Klassen.- 9.1.3 Kapselung und Persistenz.- 9.2 Vererbung.- 9.2.1 Vererbungsbeziehung.- 9.2.2 Polymorphie.- 9.2.3 Erweiterungen der Objektorientierung.- Literaturangaben zu Teil I.- II Rechnerstrukturen und maschinennahe Programmierung.- 1. Codierung und Informationstheorie.- 1.1 Codes und Codierung.- 1.1.1 Codes einheitlicher Länge.- 1.1.2 Codes variierender Länge.- 1.1.3 Serien- und Parallelwortcodierung von Zeichenfolgen.- 1.2 Codes und Entscheidungsinformation.- 1.3 Sicherung der Übertragung von Nachrichten.- 1.3.1 Codesicherung.- 1.3.2 Übertragungssicherung.- 2. Binäre Schaltnetze und Schaltwerke.- 2.1 Boolesche Algebra und Boolesche Funktionen.- 2.1.1 Boolesche Funktionen.- 2.1.2 Ordnungen auf Booleschen Abbildungen.- 2.2 Normalformen Boolescher Funktionen.- 2.2.1 Das Boolesche Normalform-Theorem.- 2.2.2 Vereinfachte Normalformen.- 2.2.3 Binäre Entscheidungsdiagramme.- 2.3 Schaltnetze.- 2.3.1 Schaltfunktionen und Schaltnetze.- 2.3.2 Der Halbaddierer.- 2.3.3 Konstruktion von Schaltnetzen.- 2.3.4 Arithmetische Schaltnetze.- 2.3.6 Schaltnetze mit Steuerleitungen.- 2.3.7 Schaltelemente als Schalter.- 2.3.8 Technische Realisierung von Schaltnetzen.- 2.4 Schaltwerke.- 2.4.1 Schaltwerksfunktionen.- 2.4.2 Schaltfunktionen als Schaltwerksfunktionen.- 2.4.3 Schaltwerke.- 2.4.4 Schaltwerksfunktionen und endliche Automaten.- 2.4.5 Schaltwerke mit verzögerungsfreier Rückkopplung.- 2.4.6 Sinnbilder für Schaltwerke und ihre Funktionen.- 2.4.7 Komposition von Schaltnetzen und Schaltwerken.- 2.4.8 Technische Realisierung von Schaltwerken.- 2.4.9 Höchstintegration.- 3. Aufbau von Rechenanlagen.- 3.1 Zum strukturellen Aufbau von Rechnern.- 3.1.1 Der Rechnerkern.- 3.1.2 Die Speichereinheit.- 3.1.3 Ein-/Ausgabe.- 3.1.4 Befehle und Daten auf Rechnerkernebene.- 3.1.5 Operandenspezifikation und Adreßrechnung.- 3.1.6 Der Befehlszyklus.- 3.2 Überblick über heutige Hardwarekomponenten.- 3.2.1 Prozessoren und Verarbeitungselemente.- 3.2.2 Speichergeräte.- 3.2.3 Eingabegeräte.- 3.2.4 Ausgabegeräte.- 3.2.5 Datenübertragungsgeräte.- 3.3 Rechnerarchitekturen.- 3.3.1 Monoprozessorrechner.- 3.3.2 Multiprozessorrechner.- 3.3.3 Neuartige Rechnerarchitekturen.- 3.4 Rechnernetze.- 3.4.1 Grundbegriffe.- 3.4.2 Rahmenbildung für Nachrichten.- 3.4.3 Netzwerktypen.- 3.4.4 Vermittlungsarten.- 3.4.5 Nachrichtenstruktur.- 4. Maschinennahe Programmstrukturen.- 4.1 Maschinennahe Programmsprachen.- 4.1.1 Maschinenwörter als Befehle.- 4.1.2 Der Befehlsvorrat der MI.- 4.1.3 Einfache Maschinenprogramme.- 4.1.4 Assemblersprachen.- 4.1.5 Einadreßform und Mehradreßform.- 4.1.6 Einfache Unterprogrammtechniken.- 4.2 Adressiertechniken.- 4.2.1 Konstante.- 4.2.2 Operandenversorgung über Register.- 4.2.3 Absolute Adressierung.- 4.2.4 Relative Adressierung.- 4.2.5 Indexi