Theoretische Informatik

aus Wikipedia, der freien Enzyklopadie

Die theoretische Informatik beschaftigt sich mit der Abstraktion, Modellbildung und grundlegenden Fragestellungen, die mit der Struktur, Verarbeitung, Ubertragung und Wiedergabe von Informationen in Zusammenhang stehen. Ihre Inhalte sind die Automatentheorie, die Theorie der formalen Sprachen, die Berechenbarkeits- und Komplexitatstheorie, aber auch die Logik und formale Semantik sowie die Informations-, Algorithmen- und Datenbanktheorie.

Die theoretische Informatik wurde - von den Befurwortern dieser Wissenschaftskategorie - in die Strukturwissenschaften eingeordnet und bietet Grundlagen fur die Definition, Verifikation und Ausfuhrung der Programme von Programmiersprachen, den Bau der Compiler von Programmiersprachen - den Compilerbau - und die mathematische Formalisierung und Untersuchung von meist diskreten Problemstellungen und deren Modellen. Mit Hilfe mathematischer Abstraktion der Eigenschaften von gewonnenen Modellen ergaben sich nutzliche Definitionen, Satze, Beweise, Algorithmen, Anwendungen und Losungen von bzw. zu Problemen. Die theoretische Informatik bildet mit ihren zeitlosen, mathematischen Wahrheiten und Methoden ein formales Skelett, das die Informatik in der Praxis mit konkreten Implementierungen durchdringt. Die theoretische Informatik identifizierte viele unlosbare Problemstellungen mittels der Berechenbarkeitstheorie und erlaubt, haufig mit konstruktiver Beweisfuhrung der Komplexitatstheorie, die Abgrenzung der praktisch effizient losbaren Probleme von denen, fur die das Gegenteil gilt.

Zu den konstruktiven Methoden der theoretischen Informatik zahlt auch das Entwerfen von formalen Systemen, Automaten, Graphen und Syntaxdiagrammen sowie das Festlegen von Grammatiken und Semantiken, um eine Problemstellung mit mathematischen Ausdrucken formal zu fassen und von der informellen Ebene abzuheben. Die Konstrukte beschreiben so die innere Logik eines Problems mit mathematisch-logischen Aussagen, was im Weiteren eine formale Untersuchung erlaubt und potenziell neue - durch Beweise gestutzte - Aussagen und Algorithmen der formalen Modelle als Resultate erschliessbar macht. Neben dem mathematischen Erkenntnisgewinn lassen sich manche der gefundenen Losungen praktisch implementieren, um Menschen durch Maschinensemantik automatisierte Vorteile der Mathematik- und Computer-Nutzung zu verschaffen.

Die theoretische Informatik ist eng verbunden mit der Mathematik und Logik. Im 20. Jahrhundert erfolgte eine Emanzipation und Bildung als eigenstandige Disziplin.

Pioniere der Disziplin waren Kurt Godel, Alonzo Church, Alan Turing, Stephen C. Kleene, Claude Shannon, John von Neumann, Hans Hermes und Noam Chomsky.

Der Logiker Heinrich Scholz erbat (und erhielt) von Turing 1936 ein Exemplar von dessen wegweisender Arbeit On Computable Numbers, with an Application to the "Entscheidungsproblem".^[1] Auf Basis dieser Arbeit hielt Scholz (laut Achim Clausing) ,,das weltweit erste Seminar uber Informatik".

Die Automatentheorie definiert und formalisiert Automaten oder Rechenmaschinen und beschaftigt sich mit deren Eigenschaften und Berechnungsstarke. Unter anderem untersucht die Automatentheorie, welche Probleme von den unterschiedlichen Klassen von Rechenmaschinen gelost werden konnen.

Die Theorie der formalen Sprachen betrachtet formalisierte Grammatiken und die durch diese Grammatiken erzeugten formalen Sprachen. Sie beschaftigt sich mit syntaktischen und semantischen Merkmalen dieser formalen Sprachen uber einem Alphabet. Das Problem, ob ein Wort zu einer formalen Sprache gehort, wird durch Automaten gelost; dadurch besteht ein enger Zusammenhang zwischen den Grammatiken, die formale Sprachen erzeugen, und den Automaten, die sie erkennen.

Die meisten in der Praxis auftretenden formalen Sprachen, wie beispielsweise Programmiersprachen, besitzen eine einfache Struktur und konnen nach ihrer Komplexitat in eine der bekannten Sprachklassen der Chomsky-Hierarchie eingeteilt werden. Die Chomsky-Hierarchie - nach Noam Chomsky, einem Pionier der Sprachtheorie - besteht aus vier Klassen. Diese sind, nach ihrer Machtigkeit aufsteigend geordnet, die regularen Sprachen (Typ 3, R), die kontextfreien Sprachen (Typ 2, L_CF), die kontextsensitiven Sprachen (Typ 1, L_ECS) und die rekursiv aufzahlbaren Sprachen (Typ 0, L_RE).

Regulare Sprachen konnen von endlichen Automaten,

kontextfreie Sprachen von (nichtdeterministischen) Kellerautomaten,

kontextsensitive Sprachen von linear beschrankten Turingmaschinen und

rekursiv aufzahlbare Sprachen von allgemeinen Turingmaschinen erkannt werden.

Zwischen den vier Grammatikklassen und den vier Maschinenklassen der Chomsky-Hierarchie besteht eine Aquivalenz bezuglich ihrer erzeugten und erkannten Klassen von Sprachen. Die formalen Sprachen, die durch die jeweiligen Grammatikklassen der Chomsky-Hierarchie erzeugt werden, konnen - wie oben aufgefuhrt - von den entsprechenden Maschinenklassen erkannt werden und umgekehrt.

Bekannte praktische Hilfsmittel in der Charakterisierung von regularen und kontextfreien Sprachen sind die Pumping-Lemmata, die eine notwendige, aber nicht hinreichende Bedingung liefern, dass eine von einer Grammatik erzeugte Sprache regular oder kontextfrei ist.^[2] Auf Grund der Struktur der Aussagen der Lemmata wird das Pumping-Lemma fur regulare Sprachen auch uvw-Theorem und das Pumping-Lemma fur kontextfreie Sprachen auch uvwxy-Theorem genannt. Erweiterungen wie das Lemma von Jaffe liefern im Gegensatz zu den Pumping-Lemmata ein hinreichendes Kriterium.

Die Backus-Naur-Form (nach John W. Backus und Peter Naur) oder BNF ist eine Notationskonvention fur kontextfreie Grammatiken und somit fur kontextfreie Sprachen. Die BNF wird in der Praxis beispielsweise dazu benutzt, die Syntaxen von Programmiersprachen zu definieren. Die jeweilige Syntax der Programmiersprachen Pascal und Modula-2 ist in der erweiterten Backus-Naur-Form, EBNF, definiert worden. Die erweiterte Backus-Naur-Form unterscheidet sich nur in einigen Notationserweiterungen von der BNF.

In der Berechenbarkeitstheorie wird die algorithmische Losbarkeit von mathematischen Problemen - also deren Berechenbarkeit - untersucht. Insbesondere geht es um die Analyse der internen Struktur von Problemen und um die Klassifikation von Problemen nach verschiedenen Graden der Losbarkeit oder deren Unlosbarkeit.

Ausgehend von der intuitiven Berechenbarkeit, der gefuhlsmassigen Vorstellung, zu welchen Problemen sich Losungen imaginieren und formulieren lassen, entwickelte die Berechenbarkeitstheorie eine formal mathematische Definition von Berechenbarkeit, mit der sich mathematische Beweise fuhren lassen, die es ermoglichen, Aussagen zur Berechenbarkeit zu verifizieren oder zu falsifizieren. Versuche, den Berechenbarkeitsbegriff formal zu fassen, fuhrten auf die Churchsche These, die beansprucht, dass der Begriff der mathematischen Berechenbarkeit mit der Turingmaschine und gleich starken formalen Berechnungsmodellen gefunden wurde. Auf dem Fundament der mathematischen Modelle der Berechenbarkeit und der Churchschen These fussen die eigentlichen Erkenntnisse und Aussagen der Berechenbarkeitstheorie.

Mit den Methoden der Berechenbarkeitstheorie lasst sich beispielsweise auch Kurt Godels Unvollstandigkeitssatz formulieren und beweisen.^[3] Ein weiteres Ergebnis der Berechenbarkeitstheorie ist die Erkenntnis, dass das Halteproblem unentscheidbar ist,^[4] man also keinen Algorithmus finden kann, der beliebige Programme daraufhin untersucht, ob sie bei einer bestimmten Eingabe jemals anhalten oder nicht. Ebenfalls unentscheidbar ist nach dem Satz von Rice jedwede nicht-triviale Eigenschaft eines Programms in einer turingmachtigen Programmiersprache.^[5]

Die Komplexitatstheorie untersucht, welche Ressourcen (zum Beispiel Rechenzeit und Speicherplatz) in welchem Masse aufgewendet werden mussen, um bestimmte Probleme algorithmisch zu losen. In der Regel erfolgt eine Einteilung der Probleme in Komplexitatsklassen. Die bekanntesten derartigen Klassen sind P und NP (in deutscher Literatur Notation auch in Frakturlettern: ${\displaystyle {\mathfrak {P}}}$ und ${\displaystyle {\mathfrak {NP}}}$). P ist die Klasse der effizient losbaren Probleme (genauer: P ist die Klasse der Probleme, die von einer deterministischen Turingmaschine in Polynomialzeit entschieden werden konnen), NP die Klasse der Probleme, deren Losungen effizient uberpruft werden konnen (oder aquivalent: NP ist die Klasse der Probleme, die von einer nichtdeterministischen Turingmaschine in Polynomialzeit entschieden werden konnen).

Durch die Angabe eines Algorithmus zur Losung eines Problems lasst sich eine Oberschranke fur den oben erwahnten Bedarf an Ressourcen angeben. Die Suche nach unteren Schranken stellt sich hingegen als weitaus schwieriger dar. Hierzu muss nachgewiesen werden, dass alle moglichen Algorithmen, die nur eine bestimmte Menge von Ressourcen verwenden, ein Problem nicht losen konnen.

Eine (wenn nicht sogar die) zentrale und seit Jahrzehnten offene Frage in der Komplexitatstheorie ist, ob die Klassen NP und P ubereinstimmen - ein NP-vollstandiges Problem in deterministischer Polynomialzeit zu losen wurde als Beweis reichen. Aquivalent dazu kann versucht werden, ein NP-vollstandiges Problem auf einem Turing-aquivalenten Computer effizient zu losen (siehe auch Churchsche These).

Die parametrisierte Algorithmik ist ein relativ junges Teilgebiet der theoretischen Informatik, in dem genauer untersucht wird, welche Instanzen von NP-vollstandigen Problemen effizient zu losen sind. Im Bereich der sogenannten ,,fine-grained complexity" werden Beziehungen zwischen Problemen in P untersucht, insbesondere zwischen Problemen mit quadratischer und kubischer Laufzeit aus der Graphentheorie.

Die formale Semantik beschaftigt sich mit der Bedeutung von in einer formalen Sprache beschriebenen Programmen. Mathematisch ausgedruckt wird eine Semantikfunktion konstruiert, die ein gegebenes Programm auf die von ihm berechnete Funktion abbildet.

${\displaystyle {\mathcal {C}}:{\mathcal {P}}\to f}$

Dabei steht ${\displaystyle {\mathcal {C}}}$ fur die Semantikfunktion, ${\displaystyle {\mathcal {P}}}$ fur die Menge der syntaktisch korrekten Programme, ${\displaystyle f:\subseteq \Sigma \to \Sigma }$ fur die von dem Programm berechnete Funktion und ${\displaystyle \Sigma }$ fur die Menge der moglichen Speicherbelegungen.

Je nach mathematischem Ansatz unterscheidet man

• axiomatische Semantik
• denotationelle Semantik
• dialogische Semantik
• Fixpunktsemantik

Gegenstand der Informationstheorie ist die mathematische Beschreibung von Information. Der Informationsgehalt einer Nachricht wird durch seine Entropie charakterisiert. Damit ist es moglich, die Ubertragungskapazitat eines Informationskanals zu bestimmen, was die Verwandtschaft zur Kodierungstheorie begrundet. Weiterhin werden informationstheoretische Methoden auch in der Kryptologie verwendet, beispielsweise ist das One-Time-Pad ein informationstheoretisch sicheres Verschlusselungsverfahren.

Mathematische Logik wird in vielfaltiger Weise in der theoretischen Informatik verwendet; dies hat umgekehrt auch zu Impulsen fur die mathematische Logik gefuhrt. Aussagenlogik und Boolesche Algebra wird z. B. fur Beschreibung von Schaltkreisen verwendet; dabei kommen grundlegende Resultate der Logik wie Craig-Interpolation zum Einsatz. Zudem sind grundlegende Konzepte der Theorie der Programmierung naturlich mittels Logik ausdruckbar, neben der oben genannten Semantik vor allem im Bereich der Theorie der logischen Programmierung. Im Bereich der formalen Spezifikation werden verschiedene Logiken, u. a. Pradikatenlogik, Temporale Logik, Modallogik und dynamische Logik eingesetzt, um das intendierte Verhalten von Software- und Hardwaresystemen zu beschreiben, das dann mittels Model Checking oder Theorembeweisern verifiziert werden kann. Auch die in der kunstlichen Intelligenz eingesetzten Logiken, z. B. Modallogiken, mittels derer das Wissen eines Agenten reprasentiert wird, sind Gegenstand theoretischer Untersuchungen. Fur die Theorie der funktionalen Programmierung kommt die kombinatorische Logik zum Einsatz.

• Stephen A. Cook
• Gerhard Gentzen
• David Hilbert
• Richard M. Karp
• Donald E. Knuth
• Leslie Lamport
• Robin Milner
• Amir Pnueli
• Emil Post
• Dana Scott

• Alexander Asteroth, Christel Baier: Theoretische Informatik. Eine Einfuhrung in Berechenbarkeit, Komplexitat und formale Sprachen. Pearson, Munchen 2003, ISBN 3-8273-7033-7
• Katrin Erk, Lutz Priese: Theoretische Informatik. Eine umfassende Einfuhrung. 3. Auflage, Springer, Berlin 2008, ISBN 3-540-76319-8
• Bernhard Heinemann, Klaus Weihrauch: Logik fur Informatiker. Eine Einfuhrung. Teubner, Stuttgart 2000, ISBN 3-519-12248-0
• John E. Hopcroft, Rajeev Motwani, Jeffrey Ullman: Einfuhrung in die Automatentheorie, formale Sprachen und Komplexitatstheorie. 2., uberarb. Auflage. Pearson Studium, Munchen 2002, ISBN 3-8273-7020-5 (englisch: Introduction to automata theory, languages, and computation. Ubersetzt von Sigrid Richter, Ingrid Tokar).
• John Kelly: Logik im Klartext. Pearson, Munchen 2003, ISBN 3-8273-7070-1
• Uwe Schoning: Theoretische Informatik - kurzgefasst. Spektrum Akademischer Verlag, Heidelberg 2003, ISBN 3-8274-1099-1
• Christian Wagenknecht: Formale Sprachen, Abstrakte Automaten und Compiler. Lehr- und Arbeitsbuch fur Grundstudium und Fortbildung. Vieweg+Teubner, 2009, ISBN 3-8348-0624-2.
• Ingo Wegener: Theoretische Informatik. Eine algorithmische Einfuhrung. Teubner, Stuttgart 1999, ISBN 3-519-12123-9
• Klaus W. Wagner: Einfuhrung in die Theoretische Informatik. Grundlagen und Modelle. Springer, Berlin 1997, ISBN 3-540-58139-1
• Klaus Weihrauch: Computability. Springer, Berlin 1987, ISBN 3-540-13721-1
• Renate Winter: Theoretische Informatik. Grundlagen mit Ubungsaufgaben und Losungen. Oldenbourg, Munchen 2002, ISBN 3-486-25808-7
• Rolf Socher: Theoretische Grundlagen der Informatik. Hanser Verlag, Munchen 2005, ISBN 3-446-22987-6
• George M. Reed, A. W. Roscoe, R. F. Wachter: Topology and Category Theory in Computer Science. Oxford University Press 1991, ISBN 0-19-853760-3
• Klaus Keimel: Domains and Processes. Springer 2001, ISBN 0-7923-7143-7
• Dirk W. Hoffmann: Theoretische Informatik. 1. Auflage. Hanser Fachbuch, Munchen 2007, ISBN 978-3-446-41511-9.

• Theoretische Informatik - Seite bei informatikseite.de

1. | Das Exemplar wurde am Institut fur Informatik der Westfalischen Wilhelms-Universitat in Munster von Achim Clausing gefunden (Westfalische Nachrichten. 28. Januar 2013: Auf den Spuren eines Pioniers: In der Unibibliothek Munster liegen Originaldrucke des Informatikers Alan Turing; online).
2. | Uwe Schoning: Theoretische Informatik - kurzgefasst / Uwe Schoning. Spektrum, Akad. Verl., Heidelberg 2001, ISBN 3-8274-1099-1, S. 39,57.
3. | Uwe Schoning: Theoretische Informatik - kurzgefasst / Uwe Schoning. Spektrum, Akad. Verl., Heidelberg 2001, ISBN 3-8274-1099-1, S. 149 ff.
4. | Uwe Schoning: Theoretische Informatik - kurzgefasst / Uwe Schoning. Spektrum, Akad. Verl., Heidelberg 2001, ISBN 3-8274-1099-1, S. 127 ff.
5. | Uwe Schoning: Theoretische Informatik - kurzgefasst / Uwe Schoning. Spektrum, Akad. Verl., Heidelberg 2001, ISBN 3-8274-1099-1, S. 130 ff.

Abgerufen von ,,https://de.wikipedia.org/w/index.php?title=Theoretische_Informatik&oldid=248050027"

Kategorie:

• Theoretische Informatik