Theoretische Informatik
Die theoretische Informatik beschäftigt sich mit der Theorie formaler Sprachen bzw. Automatentheorie, Berechenbarkeits- und Komplexitätstheorie, Logik (u. a. Aussagenlogik und Prädikatenlogik), formaler Semantik und bietet Grundlagen für den Bau von Compilern von Programmiersprachen und die mathematische Formalisierung von Problemstellungen. Sie ist somit das formale Rückgrat der Informatik.
Dabei werden formale Systeme, Automaten, Graphen und Syntaxdiagramme dazu genutzt, die innere Logik eines formalen Problems exakt wiederzugeben. Oft ist dieser formale Schritt ein wesentlicher Teil zur Lösung der eigentlichen Problemstellung und erschließt eine durch Maschinensemantik noch bequemer gewordene Welt der Mathematik und Computerei.
Berechenbarkeitstheorie
In der Berechenbarkeitstheorie wird die algorithmische Lösbarkeit von Problemen untersucht. Insbesondere geht um die Analyse der internen Struktur von Problemen und um die Klassifikation von Problemen nach verschiedenen Graden der Unlösbarkeit.
Ein Ergebnis der Berechenbarkeitstheorie ist die Erkenntnis, dass das Halteproblem unentscheidbar ist, man also keinen Algorithmus finden kann, der ein beliebiges Programm daraufhin untersucht, ob es jemals (bei einer bestimmten Eingabe) anhält oder in einer Endlosschleife weiterläuft. Ebenfalls unentscheidbar ist das dem Halteproblem verwandte Verifikationsproblem, bei dem ein beliebiges Programm überprüft werden soll, ob es eine bestimmte mathematische Spezifikation erfüllt. Aus der Unentscheidbarkeit folgt, dass diese beiden Fragestellungen nicht für alle Algorithmen entschieden werden können. Im speziellen kann dies jedoch für bestimmte Algorithmen möglich sein. Dabei ist das Problem des Haltens eine Voraussetzung für das Problem der Verifikation.
Der Breechenbarkeitsbegriff ist auf Funktionen über natürliche Zahlen zugeschnitten. Eine entscheidbare Funktion hat eine kompette charakteristische Funktion. Ist eine Funktion semi-entscheidbar hat charakteristische Funktion nur einen definierten Ausgang für das Wortproblem und ist andernfalls undefiniert.
Komplexitätstheorie
Die Komplexitätstheorie untersucht, welche Ressourcen (zum Beispiel Rechenzeit und Speicherplatz) in welchem Maße mindestens aufgewendet werden müssen, um bestimmte Probleme algorithmisch zu lösen. In der Regel erfolgt eine Einteilung der Probleme in Komplexitätsklassen. Die bekannten derartigen Klassen sind vermutlich P und NP. P ist die Klasse der effizient lösbaren Probleme, NP die Klasse der Probleme, deren Lösungen effizient überprüft werden können.
Durch die Angabe eines Algorithmus zur Lösung eines Problemes lässt sich eine Oberschranke für den oben erwähnten Bedarf an Ressourcen angeben. Die Suche nach unteren Schranken stellt sich hingegen als weitaus schwieriger dar. Hierzu muss nachgewiesen werden, dass alle möglichen Algorithmen, die nur eine bestimmte Menge von Ressourcen verwenden, ein Problem nicht lösen können.
Eine (wenn nicht sogar die) zentrale und seit Jahrzehnten offene Frage in der Komplexitätstheorie ist, ob die Klassen NP und P übereinstimmen.
Automatentheorie und Formale Sprachen
Die Automatentheorie beschäftigt sich mit der Berechnungskraft von Rechenmaschinen. Dabei wird unter anderem untersucht, welche Probleme von Rechenmaschinen gelöst werden können, die nur bestimmte Arten von Operationen ausführen können (etwa Maschinen, die nur ein Zeichen speichern können).
Einen ähnlichen Ansatz verfolgt die Theorie der formalen Sprachen. Sie beschäftigt sich mit syntaktischen und semantischen Merkmalen von Sprachen (formal als Mengen von Zeichenketten definiert). Die meisten in der Praxis auftretenden Sprachen (zum Beispiel Programmiersprachen) besitzen eine bestimmte (einfache) Struktur und können daher nach ihrer Komplexität in eine der bekannten Sprachklassen eingeteilt werden. Dies sind zum Beispiel die regulären, kontextfreien und kontextsensitiven Sprachen. Erstere können von endlichen Automaten, zweitere von Kellerautomaten und letztere von linear beschränkten Turingmaschinen erkannt werden.
Bekannte praktische Hilfsmittel in der Charakterisierung von Sprachen sind die Pumping-Lemmata, die eine notwendige, aber nicht hinreichende Bedingung liefern, dass eine von einer Grammatik erzeugte Sprache regulär oder kontextfrei ist. Es gibt aber Erweiterungen, wie das Lemma von Jaffe, die ein hinreichendes Kriterium liefern.
Die Backus-Naur-Form von Programmiersprachen wie zum Beispiel Pascal ist eine kontextfreie Sprache.
Siehe auch
Schlagwörter
- Entscheidbarkeit
- Programmiermaschine
- Logik-Programmierung
- reflexiv-transitive Hüllen
- Graphentheorie
- Fixpunktsemantik
- Künstliche Intelligenz (KI)
Bedeutende Forscher
Literatur
- Erk, Priese: Theoretische Informatik. Springer, 2002, ISBN 3-540-42624-8
- Schöning: Theoretische Informatik - kurzgefasst. Spectrum, 2001, ISBN 3-8274-1099-1
- Winter: Theoretische Informatik. Grundlagen mit Übungsaufgaben und Lösungen. Oldenbourg, 2002, ISBN 3-486-25808-7
- Hopcroft, Motwani, Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson, 2002, ISBN 3-8273-7020-5
- Asteroth, Baier: Theoretische Informatik. Eine Einführung in Berechenbarkeit, Komplexität und formale Sprachen. Pearson, 2002, ISBN 3-8273-7033-7
- Heinemann, Weihrauch: Logik für Informatiker. Teubner, ISBN 3-519-12248-0
- Kelly: Logik im Klartext. Pearson, 2002, ISBN 3-8273-7070-1
- Weihrauch: Computability. Springer, 1987, ISBN 3-540-13721-1
- Wegener, Ingo: Theoretische Informatik - eine algorithmische Einführung. Teubner, ISBN 3-519-12123-9