Theoretische Informatik
Inhaltsverzeichnis
Die Theoretische Informatik ist eine Strukturwissenschaft und ein Teilgebiet der Informatik, das sich mit verschiedenen Fragestellungen über die Struktur, Verarbeitung, Übertragung und Wiedergabe von Informationen, sowie der Definition, Formalisierung, Verifikation und Ausführung von Programmen und Algorithmen, und der Modellierung beschäftigt. Auf Grundlage dessen können Lösungsansätze für praktische Probleme gefunden oder Beweise durchgeführt werden.
Die theoretische Informatik ist eng mit der Mathematik und Logik verbunden, sodass die Grundlagen des Fachgebiets in der Geschichte weit zurück reichen. Im 20. Jahrhundert wurde die theoretische Informatik zu einer eigenen Disziplin, indem Kurt Gödel 1931 mit seinem Unvollständigkeitssatz die Grenzen formaler Systeme definierte. Auf Grundlage seiner Arbeit, und auch der Arbeit anderer bedeutender Informatiker wie Alan Turing, Claude Shannon, Stephen Cook und Leonid Levin, wurden die moderne Logik und Berechenbarkeitstheorie entwickelt, die die theoretische Informatik heute als wichtiges, eigenes Forschungsgebiet prägen.
Insbesondere gegen Ende des 20. Jahrhunderts kam mit der Entdeckung der Quantenmechanik auch die Idee der Quantencomputer auf, die nicht auf Basis der Gesetze der klassischen Physik bzw. Informatik arbeiten, sondern auf der Grundlage quantenmechanischer Zustände, und so großes Potential für die Lösung bisher nur schwer oder nicht lösbarer Probleme bieten.
Welche Teilgebiete gibt es in der theoretischen Informatik?
Die theoretische Informatik, wie sie heute auch als fester Teil des Informatikstudiums gelehrt wird, umfasst verschiedene Teilgebiete, denen voranging mathematische Logik und Algorithmik zugrunde liegen. Die vier wichtigsten Gebiete sind die Automatentheorie, die Theorie der formalen Sprachen, die Berechenbarkeitstheorie und die Komplexitätstheorie.
Formale Sprachen dienen der präzisen Beschreibung einer Syntax oder Grammatik, durch die ganze Programmiersprachen definiert werden können. Zusammen mit der Automatentheorie sind formale Sprachen notwendig, um Algorithmen und Compiler zu entwickeln oder Korrektheitsbeweise durchzuführen.
Die Berechenbarkeits- und Komplexitätstheorie beschäftigt sich konkret mit Algorithmen, die durch eine formale Syntax definiert werden. In der Berechenbarkeitstheorie wird untersucht, ob ein Algorithmus durch eine Maschine entschieden bzw. ein Problem prinzipiell algorithmisch gelöst werden kann, während die Komplexitätstheorie den Ressourcenverbrauch, wie Rechenzeit und Speicherplatz, beispielsweise durch die Analyse der asymptotischen Laufzeit, betrachtet. Die Komplexitätstheorie kategorisiert auf diese Weise die lösbaren Probleme.
Wo ist theoretische Informatik aktuell relevant?
Die theoretische Informatik ist in fast jeder Branche, in der Informatik eine Rolle spielt, relevant, denn sie stellt vor allem durch die Komplexitätstheorie die Grundlagen für die Lösung und Optimierung verschiedenster Probleme dar. Diese reichen von der Entwicklung von effizienten und schnellen Algorithmen zur Routenplanung bis hin zu der Konstruktion von selbstlernenden Systemen.
Besonders wichtig ist die theoretische Informatik für das sichere Versenden von Nachrichten und Informationen im Rahmen ihrer Anwendung in der Kryptographie. Durch die Entwicklung zahlreicher Strategien, durch denen heutige Verschlüsselungstechniken geknackt werden können, müssen immer bessere Kryptographieverfahren entwickelt werden, um sensible Daten zu schützen. Um die Sicherheit eines Verschlüsselungsalgorithmus zu bewerten ist unter anderem eine Laufzeitanalyse, aber auch ein formaler Korrektheitsbeweis, notwendig, die auf Basis der Techniken der theoretischen Informatik durchgeführt werden können.