Sieben Wunder der Informatik

Die Zielsetzung der Vorlesung, auf der dieses Kapitel basiert, unterscheidet sich wesentlich von den nachfolgenden Vorträgen, die jeweils auf ein spezielles Thema eingehen. Hier wollen wir leicht verständlich und auf unterhaltsame Weise die Geschichte des Entstehens der Informatik als einer selbstständigen Wissenschaftsdisziplin erzählen und dadurch eine erste Vorstellung vermitteln, wie Wissenschaften aufgebaut sind und wie die Grundbausteine der Informatik aussehen. Dabei lernen wir einige Ziele der Grundlagenforschung in der Informatik, sowie ein Beispiel ihrer engen Verzahnung mit anderen Wissenschaftsdisziplinen kennen. Wir nutzen dieses Kapitel auch zur kurzen Vorstellung aller zehn Themen der nachfolgenden Kapitel, natürlich im Kontext der Entwicklung der Informatik.

Das Ziel dieses Kapitels ist es noch nicht, eines der versprochenen Wunder vorzustellen. Man kann Shakespeare oder Dostojevski nicht im Original lesen und genießen, ohne vorher den mühsamen Weg des Erlernens der englischen oder russischen Sprache zu gehen. Genauso können wir die Informatik auch nicht verstehen und über ihre Ideen und Resultate staunen, ohne die elementaren Grundlagen ihrer Fachsprache zu erlernen.

Das große bekannte Universum ist endlich und die meisten physikalischen Theorien bauen auf der Vorstellung einer endlichen Welt auf. Alles was wir sehen, alles was wir anfassen oder womit wir in Kontakt treten, ist endlich.

Im dritten Kapitel haben wir entdeckt, dass es unterschiedlich große Unendlichkeiten gibt. Beispielsweise ist die Anzahl der reellen Zahlen größer als die Anzahl der natürlichen Zahlen. Eine unendliche Menge ist genau so groß wie ℕ, wenn man die Elemente dieser Menge als Erstes, als Zweites, als Drittes usw. nummerieren kann. Hier wollen wir zeigen, dass es Probleme (Aufgabenstellungen) gibt, für die kein Algorithmic existiert. Die Grundidee ist sehr einfach. Wir zeigen, dass es mehr Probleme gibt als Programme. Also müssen Probleme existieren, die algorithmisch und somit automatisch mit einem Rechner nicht lösbar sind. Wir werden uns aber nicht damit zufrieden geben, nur zu beweisen, dass es algorithmisch unlösbare Probleme gibt. Man könnte denken, dass alle unlösbaren Probleme so unnatürlich sind, dass ihre Lösungen sowieso niemanden interessieren. Deswegen streben wir an, zu zeigen, dass es auch interessante und praktisch relevante Problemstellungen gibt, die man algorithmisch nicht lösen kann.

Im Kapitel 4 haben wir festgestellt, dass es interessante Aufgaben gibt, die man algorithmisch nicht lösen kann. Und wir haben sogar gelernt, wie man zeigen kann, dass einige Probleme im algorithmischen Sinne unlösbar sind. Bis Anfang der sechziger Jahre hat die Klassifikation (die Einteilung) der algorithmischen Aufgaben in algorithmisch lösbare und algorithmisch unlösbare die Grundlagenforschung dominiert. Die Situation änderte sich mit dem immer breiteren Einsatz der Rechner auch im zivilen Bereich. Rechner wurden immer häufiger zur Planung und zur Optimierung von Arbeitsprozessen und zur Simulation kostenintensiver Forschungsexperimente verwendet. Und da mussten sich die ersten Programmierer und Algorithmendesigner der harten Realität stellen. Programme wurden geschrieben, den Rechnern übergeben und alle im Raum schwitzten, weil die Computer im wahrsten Sinne des Wortes heiß liefen, da die Kühlung damals ein großes Problem war. Nur Resultate waren keine in Sicht. Damals mussten auch die Rechner haufiger gewartet werden und so hatte man für die Rechenarbeit nur die Zeit zwischen zwei Wartungen. Und dieses Zeitintervall reichte nicht aus, um die Berechnungen erfolgreich abzuschließen. Die Informatiker konnten die vorhandenen Aufgaben nicht lösen, obwohl die Aufgaben offensichtlich algorithmisch lösbar waren. Sie hatten ja für diese Aufgabenstellungen Algorithmen entwickelt, die dann in Programme umgesetzt worden waren. Vorhersagen über die benotigte Arbeitszeit von Algorithmen wurden benötigt.

In diesem Kapitel wollen wir eines der großartigsten Wunder der Informatik vorstellen. Dieses Wunder basiert auf geschickter Nutzung des Zufalls im Entwurf von effizienten Algorithmen für scheinbar praktisch unlösbare Aufgaben.

Im zwanzigsten Jahrhundert war wahrscheinlich die Physik die faszinierendste Wissenschaft. Sie hat tiefe grundlegende Erkenntnisse gebracht, die unsere Sichtweise der Welt wesentlich geandert haben. Viele von den Anwendungen und Interpretationen ihrer Entdeckungen, wie die Relativitätstheorie oder die Quantenmechanik, wirken wie ein Zauber, weil niemand glaubte, dass so etwas überhaupt moglich sei. Kryptologie ist meiner Meinung nach die magischste Wissenschaftsdisziplin der Gegenwart. Würden Sie glauben, dass man

Viele „Science Fiction“-Romane fangen mit einer Suppe von biologischen und elektronischen Resten an oder verbinden Teile des menschlichen Gehirns mit Computerteilen und am Ende kommt ein intelligenter Bioroboter heraus. Mit unserem Thema in diesem Kapitel sind wir weit von solchen utopischen Vorstellungen sowie unrealistischen Versprechungen einiger Vertreter der Forscher auf dem Gebiet der künstlichen Intelligenz in den sechziger Jahren entfernt. Wir stellen hier eine existierende Biorechnertechnologie vor, die nicht nur hypothetisch ist. Die Frage ihrer Durchsetzung hängt von dem denkbaren Fortschritt in der Weiterentwicklung der biochemischen Methoden für die Untersuchung von DNA-Sequenzen ab.

Physik ist eine wunderbare Wissenschaft. Wenn ich einen guten Physiklehrer auf dem Gymnasium gehabt hätte, ware ich vielleicht Physiker geworden. Ich bereue es aber nicht, Informatiker geworden zu sein. Wenn man tief genug in die Grundlagen der eigenen Wissenschaftsdisziplin einsteigt, dann berührt man auch andere Gebiete der Grundlagenforschung, erwirbt einen Zugang zu den gemeinsamen Fundamenten aller Wissenschaften und sieht vieles klarer und spannender, als wenn man es nur aus der engen Sicht einer Wissenschaftsdisziplin betrachtet. Die Physik bietet gleichzeitig einen breiteren und tieferen Blick auf die Welt und keine andere Wissenschaft hat unser Weltbild insbesondere im neunzehnten und in der ersten Hälfte des zwanzigsten Jahrhunderts so stark geprägt wie gerade die Physik. Spannende Entdeckungen, unerwartete Wendungen und spektakuläre Ergebnisse waren gang und gäbe in der physikalischen Forschung. Die Quantenmechanik selbst gehort für mich zu den größten Errungenschaften der Wissenschaft. Sie zu verstehen und zu akzeptieren, war für die Menschen nicht leichter als im Mittelalter den Glauben an die zentrale Position der Erde im Universum aufzugeben. Warum hatte die Quantenmechanik mit ihrer Anerkennung ähnliche Probleme wie Galileo Galilei? Die Gesetze der Quantenmechanik sind Regeln für das Verhalten der Elementarteilchen und diese Regeln stehen im Widerspruch zu unseren Erfahrungen aus der Makrowelt. Im Folgenden nennen wir die wichtigsten Prinzipien der Quantenmechanik, die die Weltanschauung der klassischen Physik sprengen.

Die Aufgabenstellungen, die wir bisher betrachtet haben, zeichnen sich dadurch aus, dass wir für eine gegebene Probleminstanz (eine konkrete Fragestellung) eine Lösung (richtige Antwort) berechnen sollen. Wir kennen also von Anfang an alle Informationen (die ganzen Eingaben), die man zur Berechnung der Lösung brauchen kann. Es gibt in der Praxis auch viele Aufgaben, wo man am Anfang nur einen Teil der Information über eine Probleminstanz hat und eine Teillösung berechnen und umsetzen muss, bevor man den nachsten Teil der Eingabe zur Verfügung hat.

Das letzte Kapitel unterscheidet sich in einem Punkt wesentlich von den vorherigen zehn. Alles was wir bisher aus der Wissenschaft gezeigt haben, hält man dort für Tatsachen. Wir haben zwar einerseits gelernt, dass die grundlegendsten Bausteine eher eine Frage des Glaubens und des Vertrauens sind, andererseits aber auch begriffen, dass die Wissenschaftler das Gebäude der Wissenschaft sehr sorgfältig gebaut haben und alle Bausteine, die man auf die Grundbausteine gelegt hat, wurden sehr sorgfältig theoretisch sowie experimentell überprüft. Die Mathematik, die Informatik und die Naturwissenschaften erreichen eine immer höhere Reife und dadurch eine größere Stabilität. Somit sind die Theorien und die daraus abgeleiteten Vorhersagen immer zuverlässiger. Es ist aber ein Irrtum zu glauben, dass die ganze Wissenschaft so aussieht oder immer so ausgesehen hat. Wo man wirklich gute Möglichkeiten hat, Experimente mit zuverlässigen Messungen durchzuführen und die Realität in der Sprache der Mathematik zu fassen, dort stehen wir auf einem relativ festen Boden. Aber was ist mit Erziehungswissenschaften, Didaktik, Soziologie, Ökonomie und anderen Gebieten, wo sich Wissenschaftler über sich gegenseitig widersprechende Theorien streiten und so viele Ansichten in der Vergangenheit mehrmals komplett umgeworfen wurden und vielleicht die heutigen bald auch widerrufen werden? Diese Sätze sollte man nicht als eine Kritik an diesen Wissenschaftsdisziplinen sehen. Es wird nur gesagt, dass die untersuchte Materie so komplex ist und die Grundbegriffe so ungenau verstanden werden, dass es manchmal auch nicht anders gehen kann.