Algorithmik für Einsteiger
Armin P. Barth
Springer Spektrum; Auflage: 2., überarb. Aufl. 2013 (24. Oktober 2013), 24,99 €
ISBN-10: 3658022817
ISBN-13: 978-3658022815
Gleich vorweg: Uneingeschränkt empfehlenswert ist dieses Lehrbuch für die vom Verlag genannte Zielgruppe, nämlich für Lehrer, Studierende und Gymnasialschüler der Fächer Mathematik und Informatik.
Die Auswahl der Inhalte und ihre Präsentation sind sehr gelungen.
Die Darstellung erfolgt tatsächlich strikt unter dem Motto „für Einsteiger“. So ist es sehr motivierend, dass die einzelnen Abschnitte stets mit einem Überblick über das Folgende eingeleitet werden und auf diese Weise den Leser auf die Inhalte der kommenden Seiten vorbereiten. Sehr hilfreich dürfte es auch sein, dass die Beweise – nicht wie von Autoren der mathematischen Eleganz wegen oft möglichst knapp gehalten – sondern sehr ausführlich und mit erläuternden Zwischenbemerkungen versehen sind. Auch Definitionen fallen nicht unmotiviert vom Himmel, sie werden vielmehr vorbereitet, bevor sie ihre endgültige Form erhalten. Dazu dienen auch immer wiederkehrende kurze Absätze, die die Aufforderung „Zum Nachdenken“ in der Überschrift tragen, und den Leser – auch mit zusätzlichen Informationen – zum Innehalten und selbständigen Nachdenken anleiten wollen.
Nach einführenden Bemerkungen zum Algorithmus-Begriff und seiner historischen Entwicklung im ersten Kapitel (25 Seiten) werden im zweiten wichtige Algorithmen vorgestellt, u. a. der euklidische Algorithmus, ein Primzahltest, die „Türme von Hanoi“ (mit einer ausführlichen Beschreibung der Funktionsweise der Rekursion), einfache (langsame) Sortieralgorithmen, der Dijkstra-Algorithmus zum Durchlaufen von Graphen und aus der Kryptologie der RSA- und ein Zero-Knowledge-Algorithmus (70 Seiten).
Das dritte Kapitel zum Thema „Effizienz von Algorithmen“ erläutert die Landausche Symbolik der O-Schreibweise, führt als Beispiel des divide-and-conquer-Prinzips das schnelle Sortierverfahren von Hoare vor und bringt eine Einführung in die Komplexitätstheorie (40 Seiten). Gerade hier werden die Beweise sehr übersichtlich und ausführlich dargestellt.
Das vierte Kapitel ist den Turing-Maschinen gewidmet (35 Seiten). Hier werden zunächst einige Programme für diese detailliert hergeleitet, bevor die universelle Turing-Maschine beschrieben wird. Die Diskussion der Church-Turing-These beschließt diesen Abschnitt.
Das letzte Kapitel (40 Seiten) – überschrieben mit „Grenzen des Formalisierens“ – führt zum einen die Entdeckung vor, dass es nicht-berechenbare Funktionen und damit Probleme gibt, die prinzipiell nicht von Computern gelöst werden können (neben dem bekannten Halteproblem werden auch weitere Beispiele vorgestellt). Zum anderen wird hier ausführlich auf die Komplexitätstheorie und die P-NP-Problematik der „schwierigsten Probleme der Welt“ eingegangen.
Jedes Kapitel endet mit einer Vielzahl von Aufgaben unterschiedlichen Schwierigkeitsgrades (für einige sind im Anhang Lösungen angegeben) sowie einer Literaturliste.
Rezension: Hartmut Weber (Uni Kassel)