Theoretische Informatik

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

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.

Zu den bekanntesten Problemen der theoretischen Informatik gehören die NP-vollständigen Probleme wie z.B. das Traveling-Salesperson-Problem und die sich daraus ergebende Frage, ob 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

Der Ursprungsartikel stammt von der deutschsprachigen Wiki pedia (siehe oben: "Original Artikel & Autoren Liste"). Der Text steht unter der GNU Freie Dokumentation Lizenz.