Theoretische Informatik
thumb|480px|right|Hauptgebiete der Theoretischen 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.
| Inhaltsverzeichnis |
Berechenbarkeitstheorie
Im Rahmen der Berechenbarkeitstheorie untersucht die theoretische Informatik, welche Probleme prinzipiell lösbar sind. Dabei hilft die churchsche These, den Bogen von Register- und Turingmaschinen zur Realität moderner Computer zu schlagen.
Ein Ergebnis der Berechenbarkeitstheorie ist die Erkenntnis, dass das Halteproblem unentscheidbar ist.
Komplexitätstheorie
In der Komplexitätstheorie wird der Rechenzeit- und Speicherplatzbedarf für die Lösung von Problemen allgemein untersucht. Dabei werden Komplexitätsklassen definiert, deren bekannteste Vertreter wohl P und NP sein dürften.
Man kann durch die Angabe eines Algorithmus leicht eine Oberschranke für die Komplexitätsmaße angeben. Für untere Schranken stellt sich die Situation allerdings anders dar, da diese für alle (insbesondere auch alle noch nicht entdeckten) Algorithmen gelten muss. Die Angabe einer Unterschranke erfolgt meist durch sehr aufwendige, formale Beweise. Häufig wird dazu das Verfahren der Reduktion genutzt.
Dabei stellt sich die Frage, ob die NP-vollständigen Probleme (z.B. Problem des Handlungsreisenden) alle auch in P lösbar sind. Könnte man das für nur ein NP-vollständiges Problem zeigen, wäre damit das wohl bekannteste Problem der theoretischen Informatik P=NP gelöst.
Automatentheorie und Formale Sprachen
Die Theorie der formalen Sprachen ordnet Sprachen in die Chomsky-Hierarchie ein, die zwischen regulären, kontextfreien und kontextsensitiven Sprachen unterscheidet. Erstere werden mit endlichen Automaten, zweitere von Kellerautomaten und letztere von linear beschränkten Turingmaschinen erkannt.
Es werden zwei Pumping-Lemmata definiert, die einen notwendigen, aber nicht hinreichenden Beweis liefern können, dass eine von einer Grammatik erzeugte Sprache regulär oder kontextfrei ist.
Die Backus-Naur-Form von Programmiersprachen wie z.B. Pascal ist eine kontextfreie Sprache.
Siehe auch
Schlagwörter
- Entscheidbarkeit
- Programmiermaschine
- Logik-Programmierung
- reflexiv-transitive Hüllen
- Graphentheorie
- Fixpunktsemantik
Bedeutende Forscher
- Alan Turing
- Kurt Gödel
- Stephen A. Cook
- Dana Scott
- Nick Pippenger
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