Theoretische Informatik

Theoretische-informatik.png 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 es 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 innenliegende 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.

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 bekanntesten derartigen Klassen sind vermutlich P und NP. P ist die Klasse der effizient lösbaren Probleme (genauer: P ist die Klasse der Probleme, die von einer deterministischen Turingmaschine in Polynomialzeit entschieden werden können), NP die Klasse der Probleme, deren Lösungen effizient überprüft werden können (genauer: NP ist die Klasse der Probleme, die von einer nichtdeterministischen Turingmaschine in Polynomialzeit entschieden 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 - ein NP-vollständiges Problem in deterministischer Polynomialzeit zu lösen würde als Beweis reichen. Äquivalent dazu kann versucht werden, ein NP-vollständiges Problem auf einem general purpose Computer effizient zu lösen (siehe auch Churchsche These).

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 wird in der Praxis benutzt, um die Grammatik von Programmiersprachen wie zum Beispiel Pascal als kontextfreie Sprache darzustellen.

Modelle für Rechensysteme

Stichpunkte wie Auftragssysteme, Funktionseinheiten, Nebenläufigkeit, Synchronisation, Unteilbarkeit, Wartesysteme (M/M/m/k), Bedienstrategien (M/G/1) etc.

Siehe auch

Bedeutende Forscher

Literatur

Alexander Asteroth, Christel Baier: Theoretische Informatik. Eine Einführung in Berechenbarkeit, Komplexität und formale Sprachen, Pearson, München 2003, ISBN 3-8273-7033-7
Katrin Erk, Lutz Priese: Theoretische Informatik. Eine umfassende Einführung, Springer, Berlin 2002, ISBN 3-540-42624-8
Bernhard Heinemann, Klaus Weihrauch: Logik für Informatiker. Eine Einführung, Teubner, Stuttgart 2000, ISBN 3-519-12248-0
John E. Hopcroft u.a.: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie, Pearson, München 2003, ISBN 3-8273-7020-5
John Kelly: Logik im Klartext, Pearson, München2003, ISBN 3-8273-7070-1
Uwe Schöning: Theoretische Informatik - kurzgefasst, Spectrum Akadem. Verlag, Heidelberg 2003, ISBN 3-8274-1099-1
Ingo Wegener: Theoretische Informatik. Eine algorithmische Einführung, Teubner, Stuttgart 1999, ISBN 3-519-12123-9
Klaus Weihrauch: Computability, Springer, Berlin 1987, ISBN 3-540-13721-1
Renate Winter: Theoretische Informatik. Grundlagen mit Übungsaufgaben und Lösungen, Oldenbourg, München 2002, ISBN 3-486-25808-7

Weblinks

Gute Website zum Thema Theoretische Informatik