Theoretische Informatik

Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Die theoretische Informatik beschäftigt sich mit der Theorie formaler Sprachen bzw. Automatentheorie Berechenbarkeitstheorie Komplexitätstheorie Logik (u. a. Aussagenlogik und Prädikatenlogik ) formaler Semantik und bietet Grundlagen für den Bau Programmiersprachen und die mathematische Formalisierung von Problemstellungen. Sie ist somit formale Rückgrat der Informatik.

Sie beschäftigt sich außerdem mit der Lösbarkeit von Problemen also inwieweit sich Probleme mathematisch formulieren und damit lösen lassen und Aufwand man dazu treiben muss.

Dabei werden formale Systeme Automaten Graphen und Syntaxdiagramme dazu genutzt die innere eines formalen Problems exakt wiederzugeben. Oft ist formale Schritt ein wesentlicher Teil zur Lösung eigentlichen Problemstellung und erschließt eine durch Maschinensemantik bequemer gewordene Welt der Mathematik und Computerei.

Zu den bekanntesten Problemen der theoretischen gehören die NP-vollständigen Probleme wie z.B. das Traveling-Salesperson-Problem und die sich daraus ergebende Frage P=NP ist.

Siehe auch: Algorithmus Entscheidbarkeit Alan Turing Turingmaschine Registermaschine Chomsky-Hierarchie mathematisches Beweisen Programmiermaschine Logik-Programmierung reflexiv-transitive Hüllen Graphentheorie Compiler Fixpunktsemantik Pumping-Lemma Kurt Gödel Backus-Naur-Form Halteproblem Churchsche These Stephen A. Cook

Bücher zum Thema Theoretische Informatik

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

Impressum • Lesezeichen setzen • Seite versenden • Seite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Theoretische_Informatik.html">Theoretische Informatik </a>