Theoreetesch Informatik

Automatentheorie a Formal Sproochen hanken an enkem Zesummenhang. Formal Sproochen erfuerschen de strukturellen Opbau vu Programmeiersproochen. Dei meescht Sproochen hunn eng bestemmt (einfach) Struktur a kennen no hirer Komplexiteit a bekannt Sproocheklassen agedeelt ginn. Dat sinn no der Chomsky-Hierarchie dei regular, kontextfrai a kontextsensitiv Sproochen. Dei eischt kenne vun endlechen Automaten, dei zweet vu Kellerautomaten an dei lescht vu linear beschrankten Turingmaschinnen erkannt ginn.

Theorie vun der Berechebarkeet ennersicht d'algorithmesch Leisbarkeet vu Problemer. Si probeiert, dat Berechebaart vum Netberechebarem ofzegrenzen, andeems se Problemer nennt, dei nimools vun engem Computer geleist kenne ginn. D'Zil ass fir ze beweisen, datt verschidde wenschenswaert Algorithmen net existeieren, soudatt een ophale kann no sou Algorithmen ze sichen.

Ee Resultat vun der Berechebarkeetstheorie ass d'Erkenntnes, datt d'Halteproblem semi-entscheedbar ass.

D'Komlexiteitstheorie erfuerscht de rechnereschen Opwand, dee fir d'Leisung vun engem bestemmte Problem mindestens opbruecht muss ginn. Sou klassifizeiert ee Problemer zum Beispill no Lafzait a Spaicherbesoine vun Algorithmen an effizient leisbar oder schweier leisbar Problemer.

Dei bekanntst Klasse si warscheinlech P, dei vun den effizient leisbare Problemer an NP, dei Klass vu Problemer, deenen hir Leisungen effizient iwwerpreift kenne ginn.

Eng vun den zentralen an zanter Joren oppe Fro an der Komplexiteitstheorie ass, op d'Klasse P an NP iwwereneestemmen.

D'Formal Semantik probeiert d'Bedeitung vun der Konstruktioun vu Programmeiersprooche mathematesch exakt z'erfaassen. Si spezifizeiert wat bei der Ausfeierung vun engem Programm gescheie soll.