Theoretesch Informatik
Vu Wikipedia, der fräier Enzyklopedie.
D'Theoretesch Informatik beschäftegt sech mat der Abstraktioun an der Konstruktioun vu Modeller an Zesummenhang mat Problemer, déi an iergendenger Weis mat Computeren ze dinn hunn.
D'Theoretesch Informatik ass eeler als aner Beräicher vun der Informatik an ass als wëssenschaftlech Diziplin weider entwéckelt als beispillsweis Beräicher vun der Technescher oder der Praktescher Informatik. Vill grondleeënd Resultater goufe schonns virum éischte Computer erfuerscht.
Si déngt als mathematesch Basis vun der Informatik a baséiert an éischter Linn op Definitiounen, Sätz a Beweisen.
Inhaltsverzeechnis |
[Änneren] Deelgebidder
[Änneren] 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 Sprooche besëtzen eng bestëmmten (einfach) Struktur a kennen no hirer Komplexitéit a bekannte Sproochklassen agedeelt ginn. Dës sinn no der Chomsky-Hierarchie déi regulär, kontextfräi a kontextsentitiv Sproochen. Déi éischt kenne vun endlechen Automaten, déi zweet vu Kellerautomaten an déi lescht vu linear beschränkten Turingmaschinnen erkannt ginn.
[Änneren] Berechebarkeet
Theorie vun der Berechebarkeet ënnersicht d'algorithmesch Léisbarkeet vu Problemer. Si probéiert, dat Berechebart vum Netberechebarem ofzegrenzen, andeem se Problemer nennt, déi nimools vun engem Computer geléist kenne ginn. Ziel ass et fir ze beweisen, datt verschidde wënschenswäert Algorithmen net existéieren, sou datt een ophale kann no sou Algorithmen ze sichen.
Ee Resultat vun der Berechebarkeetstheorie ass d'Erkenntnis, datt d'Halteproblem semi-entscheedbar ass.
[Änneren] Komplexitéitstheorie
D'Komlexitéitstheorie erfuerscht de rechnereschen Opwand, deen zur Léisung vun engem bestëmmte Problem mindestens opbruecht muss ginn. Sou klassifizéiert ee Problemer zum Beispill no Lafzäit a Späicherbesoins vun Algorithmen an effizient léisbar oder schwéier léisbar Problemer.
Déi bekannste Klasse si wahrscheinlech P, déi vun den effizient léisbare Problemer an NP, déi Klass vu Problemer, däre Léisungen effizient iwwerpréift kenne ginn.
Eng vun den zentralen an zënter Joren oppe Fro an der Komplexitéitstheorie ass, op d'Klasse P an NP iwwereneestëmmen.
[Änneren] Algorithmen an Datestrukturen
[Änneren] Formal Semantik
D'Formal Semantik probéiert d'Bedeitung vun der Konstruktioun vu Programméiersprooche mathematesch exakt ze erfaassen. Si spezifizéiert wat bei Ausféierung vun engem Programm passéiere soll.
[Änneren] 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.