Einführung in die Informatik. Algorithmenentwicklung. (Introduction into computer science. Development of algorithms.) (Q1188922)

Dieses Buch gibt eine ausgezeichnete Einführung in die Entwicklung und Analyse von Algorithmen für Informatikstudenten des ersten Studienjahres. Statt auf einer konkreten Programmiersprache baut das Buch auf ``Konzept-'' Sprachen auf; so wird jeweils ein Prototyp einer funktionalen und einer imperativen Programmiersprache vorgestellt. Nach Definition grundlegender mathematischer Konzepte wie Bäume, Matrizen etc. werden Grundtechniken wie Induktion und Rekursion behandelt, sowie Syntaxdefinitionen mittels BNF. Es werden die Begriffe der Rechenstruktur und des abstrakten Datentyps eingeführt. Über diesen Strukturen wird eine funktionale Sprache in 3 Stufen entwickelt: 1) Terme, 2) bedingte Terme (Fallunterscheidungen) und 3) Ausdrücke mit Rekursion. An dieser Sprache wird die Technik des rekursiven Programmierens demonstriert und auch induktionsbasierte Korrektheitsbeweise von Programmen gegeben (u.a. wird der Euklidische Algorithmus verifiziert). In dem darauf folgenden Kapitel wird ein ablauforientiertes Algorithmenkonzept durch Einführung einer einfachen imperativen Programmiersprache vorgestellt. Funktionale und imperative Algorithmennotationen werden verglichen und die Kombinierbarkeit und Terminations- sowie Korrektheitsbeweise für einfache Programme gegeben. Nach Entwicklung der Sprachen wird die Programmierung als Prozeß von der Spezifikation zur Codierung analysiert; dieser Prozeß der Algorithmenentwicklung wird an zahlreichen mathematischen Problemen (wie Berechnung einer Nullstelle durch Bisektion, Primzahltest, die Türme von Hanoi etc.) anschaulich dargestellt. Weiter wird die Gewinnung von iterativen aus rekursiven Algorithmen (mit Hilfe von Kellern) vorgeführt. Auch der Begriff des nondeterministischen Algorithmus wird kurz skizziert. Ein Kapitel des Buches ist dem Problem der Effizienz und Komplexität von Algorithmen gewidmet; hierbei werden Zeit- und Speicherkomplexität einfacher Algorithmen abgeschätzt und die Landau'sche 0-Symbolik eingeführt. Auch Suchalgorithmen, Backtracking und parallele Algorithmen finden hier Erwähnung. Am Ende setzt dann das Buch den Schritt zur ``konkreten'' Programmiersprache MODULA-2, wobei die Erstellung von Programmen als natürliche Konsequenz der in den vorigen Kapiteln erarbeiteten Techniken und Konzepte präsentiert wird. Die schrittweise Aufschichtung von Grundtechniken und Grundbegriffen zum Programmieren in einer realen Programmiersprache ist didaktisch gekonnt und überzeugend durchgeführt. Ohne die Verwendung formaler, abstrakter Theorien (wie etwa die der denotationalen Semantik oder der algebraischen Spezifikation) werden dem Studenten doch die wesentlichen Grundeinsichten in Entwicklung, Effizienz und Korrektheit von Algorithmen vermittelt. Das Buch ist daher als Informatikeinführung ausdrücklich zu empfehlen.