Mehr als nur Programmieren¿ : Eine Einführung in die Informatik

Dieses Buch richtet sich an Menschen, die sich bislang nicht mit Fragen der Informatik beschaftigt haben, sich aber daftir interessieren. Zum Verstandnis werden keine informa- tikspezifischen Vorkenntnisse benOtigt. Die beiden Teile des Buches - "Grundbegriffe des Programmierens" und, Formale und ethische Grenzen" - konnen bei entsprechenden Vorkenntnissen unabhangig voneinander bearbeitet werden. Den Anfang bildet eine EinfUhmng in die Programmiersprache Pascal; wir versuchen allerdings nicht, ein vollstandiges Pascal-Lehrbuch zu ersetzen. Die Vorstel- lung von Pascal erfolgt nur insoweit, als die Sprache benotigt wird, urn gewisse Prinzipien von Algorithmen zu beschreiben. Den Zweck der Sprachbestandteile illustrieren wir durch ihre Verwendung in einem iiber die ersten beiden Kapitel hinweg entstehenden Programm, dem sogenannten "Spiel des Lebens". Dabei werden Besonderheiten und Schwierigkeiten besprochen, die bei der Programmierung, vor allem von nicht ganz trivialen Programmen, auftreten konnen. Die Kapitel iiber die Programmierung werden mit einer Vorstellung von Sortieralgorithmen beendet, die ebenfalls im Kontext des Spiels des Lebens Ver- wen dung finden. 1m dritten Kapitel wird eine kurze EinfUhmng in die Funktionsweise eines Rechners auf der Hardwareebene gegeben. Das nli. chste Kapitel befaBt sich mit der Aussagenlogik und Pradikatenlogik, die als Hilfsmittel zur Spezifikation benotigt werden. Die Spezifikation von Algorithmen ist damit das Haupthema dieses Kapitels. 1m fUnften Kapitel geht es urn die Fragen der Korrektheit eines Programms. Der Aufwand eines Algorithmus ist Thema des sechsten Kapitels. 1m letzten Kapitel schlieBlich geht es urn einige nichtbeabsichtigte Auswirkungen der Informatik.

I Grundbegriffe des Programmierens.- 1 Eine Einführung in die Grundlagen von Pascal.- 1.1 Überblick.- 1.2 Beispiel: Die Lösung einer quadratischen Gleichung.- 1.2.1 Lösung ohne Verständnis.- 1.3 Ein informeller Algorithmus.- 1.3.1 Auflösung komplizierter Schritte.- 1.3.2 Unübersichtlichkeit durch Länge.- 1.3.3 Mehrdeutigkeiten im Algorithmus.- 1.3.4 Auflösung von Mehrdeutigkeiten.- 1.4 Ein erstes Pascalprogramm.- 1.4.1 Struktur eines Pascalprogramms.- 1.4.2 Deklaration von Konstanten und Variablen.- 1.5 Übersetzung der ersten Programme.- 1.6 Ausgabe von Zahlen.- 1.7 Rechnerzahlen sind mangelhaft.- 1.8 Die Auswahlanweisung.- 1.8.1 Abwandlungen der Auswahlanweisung.- 1.9 Testausdrücke.- 1.10 Parametereingabe.- 1.11 Schleifen.- 1.11.1 DieWHILE-Schleife.- 1.11.2 Die FOR-Schleife.- 1.12 Syntaxdiagramme.- 1.13 Zusammenfassung.- 2 Ein umfangreicheres Beispiel: Das Spiel des Lebens.- 2.1 Überblick.- 2.2 Die Spielidee.- 2.2.1 Lebewesen in einer Schachbrettweit.- 2.2.2 Verschiedene Nöpelvölker.- 2.2.3 Ein Pflichtenheft zur Simulation der Nöpelwelt.- 2.2.4 Modularisierung von Algorithmen.- 2.2.5 Die Grobaufteilung der Aufgabe.- 2.2.6 Die Modulstruktur des Lebensspiel-Algorithmus.- 2.2.7 Der informelle Algorithmus.- 2.2.8 Die Einzelaufgaben.- 2.3 Ein Programm „Lebensspiel“.- 2.3.1 Die Darstellung der Nöpelwelt im Rechner mit einem Feld.- 2.3.2 Mehrdimensionale Felder.- 2.3.3 Prozeduren zur Lösung von Teilaufgaben.- 2.3.4 Sichtbarkeit von Namen.- 2.3.5 Wiederverwendung von Namen.- 2.3.6 Parameter für Unterprogramme.- 2.3.7 Das Hauptprogramm ohne Unterprogramme.- 2.3.8 Setzen der Anfangskonstellation.- 2.3.9 Einlesen der Laufparameter.- 2.3.10 Ausgabe der Nöpelwelt.- 2.3.11 Berechnung aller Generationen.- 2.3.12 Ausgabeparameter.- 2.3.13 Die Berechnung einer neuen Generation.- 2.3.14 Zählung der Nachbarn.- 2.3.15 Test auf Lebendigkeit.- 2.3.16 Rückschau auf das Programm.- 2.3.17 Probleme bei der Modularisierung von Algorithmen.- 2.4 Syntaxgraphen von Feldern und Prozeduren.- 2.5 Variationen der Aufgabenstellung.- 2.6 Eine sichere Eingabefunktion.- 2.6.1 Der Datentyp char.- 2.6.2 Typendeklarationen.- 2.6.3 Funktionen.- 2.6.4 Die Erkennung einer gültigen Zahl mit endlichen Automaten.- 2.6.5 Ein Programm mit Zustandsvariable.- 2.6.6 Die Berechnung des Zahlenwertes einer Ziffernfolge.- 2.7 Eine zufällige Anfangskonstellation.- 2.7.1 Ein Algorithmus zur Erzeugung einer Pseudozufallszahlenfolge.- 2.8 Eine Neuinterpretation der Zustände.- 2.8.1 Sortieren der Statistik.- 2.9 Rekursive Algorithmen.- 2.9.1 Rekursive Programme.- 2.9.2 Mergesort.- 2.10 Zusammenfassung.- 3 Hardware.- 3.1 Beschreibungsebenen der Hardware.- 3.2 Bits und Bytes.- 3.3 Funktionsgruppen im Rechner.- 3.4 Zusammenfassung.- II Formale und ethische Grenzen.- 4 Die formale Spezifikation von Problemen.- 4.1 Unzulänglichkeit informeller Aufgabenstellungen.- 4.2 Die Aussagen-und Prädikatenlogik.- 4.2.1 Logische Aussagen.- 4.2.2 Logische Operatoren.- 4.2.3 Distributivität, Assoziativität, Kommutativität, Modus Ponens.- 4.2.4 Modus Ponens.- 4.2.5 Prädikatenlogik.- 4.2.6 Formale Spezifikation: Das Beispiel Sortieren.- 4.3 Grenzen der Spezifikation.- 4.3.1 Bedeutungsverlust durch Spezifikation.- 4.3.2 Spezifikation von umfangreichen Aufgaben.- 4.3.3 Wirkungen auf die Gesellschaft.- 4.4 Zusammenfassung.- 5 Validierung von Programmen.- 5.1 Überblick.- 5.2 Der Test von Programmen.- 5.2.1 Teststrategie.- 5.2.2 Modultest und Systemtest.- 5.2.3 White-Box-Tests und Black-Box-Tests.- 5.3 Zur Leistungsfähigkeit von Black-Box-Tests.- 5.3.1 Leistungen und Mängel von Tests.- 5.4 Die formale Verifikation von Programmen.- 5.4.1 Ein Beweis.- 5.4.2 Die Beweisidee.- 5.4.3 Die Zuweisung.- 5.4.4 Folgerungen.- 5.4.5 Sequenz.- 5.4.6 Beispiel: Austausch zweier Werte.- 5.4.7 Auswahlanweisung.- 5.4.8 Ein Beispiel für den Beweis eines Programms mit Auswahlanweisung.- 5.4.9 Schleife.- 5.4.10 Ein Beispiel für einen Beweis mit Hilfe einer Schleifeninvariante.- 5.4.11 Terminierung von Schleifen.- 5.4.12 Ein etwas größeres Beispiel: Bestimmung des Maximums einer Liste.- 5.4.13 Einige Probleme bei formalen Verifikationen.- 5.4.14 Das Halteproblem.- 5.4.15 Folgerungen aus den Grenzen der formalen Beweise.- 5.5 Reviews.- 5.6 Zusammenfassung.- 6 Der Zeitbedarf beim Programmablauf.- 6.1 Die Stoppuhr-Zeit.- 6.2 Beispiel: Die Suche eines Elementes in einer Liste.- 6.3 Die Messung der „Gr??e“ von Eingabedaten.- 6.4 Ein schon bekanntes Beispiel: Selectionsort.- 6.5 Ein neues Beispiel: Heapsort.- 6.5.1 Der Algorithmus.- 6.5.2 Laufzeit.- 6.6 Vergleich der Laufzeiten von Selectionsort und Heapsort.- 6.6.1 Das O-Kalkül.- 6.6.2 „Schwere“ Probleme und Heuristiken.- 6.7 Zusammenfassung.- 7 Wirkungen der Informatik.- 7.1 Ein Fehler im Space Shuttle.- 7.2 Ein Programmierfehler in einem Bestrahlungsgerät.- 7.3 Gefahren durch Prozeßrechner.- 7.4 Gefahren durch Datenbanken.- 7.5 Begriffssphären.- 7.6 Verantwortbarkeit des Einsatzes von Informatik in der Großtechnik.- 7.7 Programmieren als ethisches Problem.- 7.8 Ein letztes Beispiel: Militärische Frühwarnsysteme.- 7.9 Zusammenfassung.- III Anhang.- Symbolverzeichnis.- Musterlösungen.