Theoreetesch Informatik

D'Theoreetesch Informatik beschäftegt sech mat der Abstraktioun an der Konstruktioun vu Modeller am Zesummenhank mat Problemer, déi an iergendenger Weis mat Computeren ze dinn hunn.

D'Theoreetesch Informatik ass méi al wéi aner Beräicher vun der Informatik an ass als wëssenschaftlech Disziplin méi wäit entwéckelt wéi beispillsweis Beräicher vun der Technescher oder der Praktescher Informatik. Vill grondleeënd Resultater goufe scho virum éischte Computer erfuerscht.

Si ass d'mathematesch Basis vun der Informatik a baséiert an éischter Linn op Definitiounen, Sätz a Beweiser.

Deelgebidder

Automatentheorie a Formal Sproochen

Automatentheorie a Formal Sproochen hänken an enkem Zesummenhang. Formal Sproochen erfuerschen de strukturellen Opbau vu Programméiersproochen. Déi meescht Sproochen hunn eng bestëmmt (einfach) Struktur a kënnen no hirer Komplexitéit a bekannt Sproocheklassen agedeelt ginn. Dat sinn no der Chomsky-Hierarchie déi regulär, kontextfräi a kontextsensitiv Sproochen. Déi éischt kënne vun endlechen Automaten, déi zweet vu Kellerautomaten an déi lescht vu linear beschränkten Turingmaschinnen erkannt ginn.

Berechebarkeet

Theorie vun der Berechebarkeet ënnersicht d'algorithmesch Léisbarkeet vu Problemer. Si probéiert, dat Berechebaart vum Netberechebarem ofzegrenzen, andeems se Problemer nennt, déi nimools vun engem Computer geléist kënne ginn. D'Zil ass fir ze beweisen, datt verschidde wënschenswäert Algorithmen net existéieren, soudatt een ophale kann no sou Algorithmen ze sichen.

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

Komplexitéitstheorie

D'Komlexitéitstheorie erfuerscht de rechnereschen Opwand, dee fir d'Léisung vun engem bestëmmte Problem mindestens opbruecht muss ginn. Sou klassifizéiert ee Problemer zum Beispill no Lafzäit a Späicherbesoine vun Algorithmen an effizient léisbar oder schwéier léisbar Problemer.

Déi bekanntst Klasse si warscheinlech P, déi vun den effizient léisbare Problemer an NP, déi Klass vu Problemer, deenen hir Léisungen effizient iwwerpréift kënne ginn.

Eng vun den zentralen an zanter Joren oppe Fro an der Komplexitéitstheorie ass, op d'Klasse P an NP iwwereneestëmmen.

Formal Semantik

D'Formal Semantik probéiert d'Bedeitung vun der Konstruktioun vu Programméiersprooche mathematesch exakt z'erfaassen. Si spezifizéiert wat bei der Ausféierung vun engem Programm geschéie soll.

Literatur

• Uwe Schöning: Theoretische Informatik - kurzgefasst. Spektrum Akademischer Verlag, 2001.
• Renate Winter: Theoretische Informatik. Oldenbourg Verlag, 2002.
• Peter Rechenberg: Was ist Informatik? Carl Hanser Verlag, 2000.