Theoretische Informatik

Jeder, der Informatik studiert oder ausübt, sollte sich von Zeit zu Zeit die Frage stellen, wie er die Informatik definieren würde, und wie er die Rolle der Informatik im Kontext aller Wissenschaft, allgemeiner Bildung und der täglichen Praxis sieht. Wichtig ist dabei, dass sich mit tieferem Verständnis der Natur der Informatik auch unsere Vorstellung über die Informatik weiterentwickelt. Deswegen ist es insbesondere für die Studierenden im Grundstudium sehr wichtig, dass sie sich nach jedem Semester mit ihrer eigenen Vorstellung über Informatik beschäftigen. Eine Hilfe zu einer solchen Auseinandersetzung zwischen eigener Vorstellung und neu erworbenen Kenntnissen soll diese Einleitung bieten.¹

Die Rechner arbeiten im Prinzip mit Texten, die nichts anderes sind als Folgen von Symbolen aus einem bestimmten Alphabet. Die Programme sind Texte über dem Alphabet der Rechnertastatur, alle Informationen sind im Rechner als Folgen von Nullen und Einsen gespeichert, Eingaben und Ausgaben sind im Wesentlichen auch Texte (oder können zumindest als Texte dargestellt werden) über einem geeignet gewählten Alphabet. Aus dieser Sicht realisiert jedes Programm eine Transformation von Eingabetexten in Ausgabetexte.

Endliche Automaten sind das einfachste Modell der Berechnungen, das man in der Informatik betrachtet. Im Prinzip entsprechen endliche Automaten speziellen Programmen, die gewisse Entscheidungsprobleme lösen und dabei keine Variablen benutzen. Endliche Automaten arbeiten in Echtzeit in dem Sinne, dass sie die Eingabe nur einmal von links nach rechts lesen, das Resultat steht sofort nach dem Lesen des letzten Buchstabens fest.

Wenn man ursprünglich in der Mathematik einen Ansatz zur Lösung gewisser Probleme vermitteln wollte, hat man ihn als eine mathematische Methode formal genau beschrieben. Eine sorgfältige Beschreibung einer Methode hatte die Eigenschaft, dass ein Anwender gar nicht verstehen brauchte, warum die Methode funktioniert, und trotzdem die Methode erfolgreich zur Lösung seiner Probleminstanz verwenden konnte. Die einzige Voraussetzung für eine erfolgreiche Anwendung war das Verständnis des mathematischen Formalismus, in dem die Methode dargestellt wurde. Die Entwicklung des Rechners führte dazu, dass man Methoden zur Lösung von Problemen durch Programme beschreibt. Der mathematische Formalismus ist hier durch die benutzte Programmiersprache gegeben. Das wichtigste Merkmal aber bleibt. Der Rechner, der keinen Intellekt besitzt und daher kein Verständnis für das Problem sowie für die Methode zu seiner Lösung besitzt, kann das Programm ausführen und dadurch das Problem lösen. Deswegen können wir über automatische oder algorithmische Lösbarkeit von Problemen sprechen. Um zu zeigen, dass ein Problem automatisch lösbar ist, reicht es aus, eine Methode zu seiner Lösung zu finden und diese in Form eines Programms (Algorithmus) darzustellen. Deswegen kommen positive Aussagen über algorithmische (automatische) Problemlösbarkeit gut ohne eine Festlegung auf eine Formalisierung des Begriffs Algorithmus aus. Es reicht oft, eine Methode halb informell und grob zu beschreiben, und jedem wird klar, dass sich die Methode in die Form eines Programms umsetzen lässt. Daher ist es nicht verwunderlich, dass die Mathematik schon lange vor der Existenz von Rechnern die Lösbarkeit mathematischer Probleme mit der Existenz allgemeiner Lösungsmethoden¹ im Sinne von „automatischer Lösbarkeit“ verknüpft hat.

Die Theorie der Berechenbarkeit ist die erste Theorie, die in der Informatik entstanden ist. Sie entwickelte Methoden zur Klassifizierung von Problemen in algorithmisch lösbare und algorithmisch unlösbare. Dies bedeutet, dass diese Theorie uns Techniken zum Beweisen der Nichtexistenz von Algorithmen zur Lösung konkreter Probleme liefert. Das Erlernen dieser Techniken ist das Hauptziel dieses Kapitels.

Die Theorie der Berechenbarkeit liefert uns Methoden zur Klassifizierung von Problemen bezüglich ihrer algorithmischen Lösbarkeit. So ist ein Problem algorithmisch lösbar, wenn ein Algorithmus zur Lösung dieses Problems existiert, und ein Problem ist algorithmisch unlösbar, wenn kein Algorithmus für dieses Problem existiert.

Die Komplexitätstheorie liefert uns die Methoden zur Klassifikation der algorithmischen Probleme bezüglich ihrer Komplexität. Die Algorithmentheorie ist dem Entwurf von effizienten Algorithmen zur Lösung konkreter Probleme gewidmet. In diesem Kapitel wollen wir uns mit dem Entwurf von Algorithmen für schwere (z.B. NP-schwere) Probleme beschäftigen. Das mag etwas überraschend klingen, weil nach der in Kapitel 6 vorgestellten Komplexitätstheorie der Versuch, ein NP-schweres Problem zu lösen, an die Grenze des physikalisch Machbaren stößt. Z.B. würde ein Algorithmus mit der Zeitkomplexität 2 ⁿ für eine Eingabe der Länge 100 mehr Zeit brauchen, als das Universum alt ist. Auf der anderen Seite sind viele schwere Probleme von einer enormen Wichtigkeit für die tägliche Praxis, und deshalb suchen Informatiker seit über 30 Jahren nach einer Möglichkeit, schwere Probleme in praktischen Anwendungen doch zu bearbeiten. Die Hauptidee dabei ist, ein schweres Problem durch eine (nach Möglichkeit kleine) Modifikation oder eine Abschwächung der Anforderungen in ein effizient lösbares Problem umzuwandeln. Die wahre Kunst der Algorithmik besteht darin, dass man die Möglichkeiten untersucht, wie man durch minimale (für die Praxis akzeptable) Änderungen der Problemspezifikation oder der Anforderungen an die Problemlösung einen gewaltigen Sprung machen kann, und zwar von einer physikalisch nicht machbaren Berechnungskomplexität zu einer Angelegenheit von wenigen Minuten auf einem Standard-PC. Um solche Effekte, die zur Lösung gegebener Probleme in der Praxis führen können, zu erzielen, kann man folgende Konzepte oder deren Kombinationen benutzen.

Der Begriff Zufall ist einer der fundamentalsten und meist diskutierten Begriffe der Wissenschaft. Die grundlegende Frage ist, ob der Zufall objektiv existiert oder ob wir diesen Begriff nur benutzen, um Ereignisse mit unbekannter Gesetzmäßigkeit zu erklären und zu modellieren. Darüber streiten die Wissenschaftler seit der Antike. Demokrit meinte, dass

das Zufällige das Nichterkannte ist,

und dass die Natur in ihrer Grundlage determiniert ist.

Im 20. Jahrhundert hat sich die theoretische Informatik überwiegend der Untersuchung der sequentiellen Rechnermodelle gewidmet, die der Vorstellung von Neumanns entsprechen. Was sollten die zukünftigen Kernprobleme der Informatik sein? Die Vernetzung der Rechner konfrontiert den Nutzer nicht mehr nur mit einem einzelnen Rechner, sondern mit einer unübersichtlichen vernetzten Welt von vielen asynchronen und unvorhersehbaren Aktivitäten. Das Verständnis vom Rechnen in der vernetzten Welt ist derzeit nicht sehr tief und seine Entwicklung wird eine der Hauptaufgaben der Informatik sein. Die Vielfalt der Forschungsfragen, die im Zusammenhang mit verteiltem Rechnen, Kooperation und Kommunikation zwischen Rechnern, Prozessen und Menschen gestellt worden sind, kann man in dieser beschränkten Übersicht gar nicht vorstellen. Die Probleme, bezogen auf den Entwurf und die Analyse von effizienten Kommunikationsalgorithmen (Protokollen) und auf den Entwurf von leistungsfähigen Netzen, sind stark von den zugänglichen Technologien abhängig. Diese Technologien entwickelten sich schnell von klassischen Telefonverbindungen bis hin zu optischen Netzen, und jede Technologie ist an anderen Problemen und Fragestellungen interessiert. Weil wir keine Möglichkeit sehen, eine kurze, verständliche Übersicht über dieses Thema zu geben, beschränken wir uns hier auf ein Beispiel eines Netzentwurfes und konzentrieren uns mehr auf das Gebiet der Kryptographie, das sich mit der sicheren Kommunikation in Netzen beschäftigt.