Algorithmik für Einsteiger

Es gibt Dinge, die für das Leben der Menschen von ungeheurer Wichtigkeit sind und dennoch kaum je von einem menschlichen Auge wahrgenommen werden: Sauerstoff und Stickstoff, Neuronen und Synapsen, DNA und Blutkörperchen, Magnetismus und Gravitation und vieles mehr. Die Algorithmen gehören unbedingt auch in diese Liste. Jeder und jede von uns konsumiert täglich Algorithmen und verlässt sich auf sie. Das Leben der heutigen Menschen würde sich drastisch verändern, wenn man von heute auf morgen alle Algorithmen abschaffen würde (und könnte). Sie arbeiten von den meisten Menschen unbemerkt zu Tausenden in Maschinen und Geräten aller Art, in Automaten, Rechnern, Computern und auf Computerchips. Und dass sie von Auge meist nicht wahrgenommen werden, ist wohl der Grund dafür, dass viele Menschen nicht einmal wissen, was Algorithmen sind. Das Ziel dieses Kapitels ist darum ein mehrfaches: Wir geben eine erste Antwort auf die Frage, was ein Algorithmus ist, liefern zahlreiche Beispiele, rollen kurz die Geschichte der Algorithmik auf und geben einen Einblick in den gewaltigen Entwicklungsschub, den die Algorithmen nahmen, nachdem sie lernten, sich in Computern zu entfalten.

Dieses Kapitel ist eine Modeschau. Nacheinander gehen wichtige und lehrreiche Algorithmen über den Laufsteg, präsentieren sich uns, lassen sich ausgiebig mustern und untersuchen. Sie entstammen einer bedeutenden Kollektion. Teils sind sie aus historischen Gründen interessant, teils aus mathematischen, teils auch deshalb, weil sie grundlegende Programmiermethoden wie etwa die rekursive Programmierung, Methoden der Numerik oder Monte-Carlo-Methoden exemplarisch vorzeigen. Teils beziehen sie ihren Reiz zudem aus der Tatsache, dass sie heute in der Praxis von unschätzbarem Wert sind.

Wir haben schon mehrfach gesehen, dass ein algorithmisches Problem nicht gelöst ist, wenn irgendein korrekter Algorithmus dafür gefunden werden kann. Eine wichtige Frage ist immer auch, ob das Verfahren in vertretbarer Zeit terminiert oder nicht. Ein Sortierverfahren, das zwar richtig sortiert, das für die Sortierung aber Monate aufwenden muss, ist praktisch wertlos. Darum muss die Frage nach der Effizient von Algorithmen in der Algorithmik eine zentrale Rolle spielen. Und genau darum wollen wir uns in Kap. 3 kümmern. Zuerst einmal ist a priori gar nicht klar, wie man den Aufwand eines Algorithmus messen soll. In Sekunden? Das hätte den Nachteil, dass der Aufwand rechnerspezifisch ist, denn dann hätte ein Algorithmus ja je nach Rechner, auf dem er läuft, einen anderen Aufwand. Soll man die Schritte des Algorithmus zählen? Aber was ist genau ein einzelner Schritt? Und wenn einmal klar ist, wie man die Effizienz eines Algorithmus angeben kann, dann stellen sich sofort weitere, anspruchsvollere, aber auch interessantere Fragen: Kann man die Effizienz eines Algorithmus verbessern? Ist es möglich, für ein und dasselbe Problem mehrere Algorithmen zu schreiben, die sich im Aufwand stark unterscheiden? Und gibt es allenfalls einen schnellstmöglichen Algorithmus? Und wie kann man das einsehen? Es sind solche Fragen, die uns in diesem Kapitel anstacheln werden. Antworten sind teilweise alles andere als leicht zu finden, aber es ist ein überaus faszinierendes Gebiet, dem wir hier erste zaghafte Besuche abstatten.

Ist das nicht erstaunlich? Nun haben wir drei umfangreiche Kapitel lang Algorithmik betrieben, ohne je präzise definiert zu haben, was ein Algorithmus genau ist. Wir haben Beschreibungen und Umschreibungen angegeben und zahlreiche Beispiele untersucht, und wir haben die Algorithmen im Hinblick auf Aufwand und Beschleunigung analysiert. Aber wir haben nie eine Definition angegeben, die diesen Namen auch verdient, und dies aus einem einzigen Grund: Es war bisher nie notwendig. Man kann algorithmische Lösungen für Probleme suchen und finden, ohne je mit mathematischer Präzision niederzuschreiben, was ein Algorithmus ist und was nicht. Im Laufe des 20. Jahrhunderts änderte sich alles; eine präzise Definition wurde auf einmal notwendig. Und wir werden in diesem Kapitel (Abschn. 4.1 und 4.2) einsehen, weshalb. In Abschn. 4.3 wird es dann darum gehen, den Menschen vorzustellen, auf den die wohl erfolgreichste Algorithmus-Definition zurückgeht, während Abschn. 4.4 diese Definition selber zum Inhalt hat. Die Abschn. 4.5 und 4.6 werden die Konsequenzen dieses neuen Konzeptes aufzeigen und deutlich werden lassen, dass die hier erläuterten Ideen grundlegend waren für die Entwicklung des modernen Computers. Wären die im vorliegenden Kapitel besprochenen Erfindungen nie gemacht worden, sähe unsere Welt heute mit Sicherheit anders aus.

In diesem Kapitel werden wir Probleme ins Zentrum rücken, die bewiesenermaßen algorithmisch unlösbar sind. Dabei gibt es viele schlechte Nachrichten. Vor ihnen die Augen zu verschließen, wäre nicht sinnvoll, denn es sind keine exotischen Randerscheinungen; sie betreffen vielmehr ganz wichtige und oft sogar alltagspraktische Bereiche. Die Tatsache, dass Turing-Maschinen so überaus einfach sind, wird diese schlechten Nachrichten noch beeindruckender aussehen lassen. Denn wenn wir nachwiesen würden, dass irgendein komplexes und mit zahlreichen Extras ausgestattetes Maschinenmodell nicht in der Lage ist, eine bestimmte Aufgabe zu lösen, wäre das nicht besonders beeindruckend; man könnte sich ja dann immer denken, dass ein anderes Maschinenmodell durchaus dazu in der Lage wäre. Wenn aber ein so elementares Modell wie die Turing-Maschine die Aufgabe nicht lösen kann, dann ist das viel beeindruckender, denn es betrifft alle nur denkbaren Computer, unabhängig von Architektur, Laufzeit, Speicherplatz, Prozessorgeschwindigkeit, und so weiter. Zu zeigen, dass eine bestimmte Aufgabe von einer Turing-Maschine nicht gelöst werden kann, bedeutet, dass sie grundsätzlich nicht algorithmisch lösbar ist, jetzt nicht und in Zukunft nicht, von keinem Computer dieser Welt und mit keiner denkbaren Programmiersprache. Die menschliche Kreativität, die bei einer solchen Aufgabe einzig noch helfen kann, scheint bis heute nicht vollständig mechanisierbar zu sein. Und das ist überaus tröstlich und faszinierend.

Kapitel 6 beinhaltet Lösungen zu ausgewählten Aufgaben.