KIT | KIT-Bibliothek | Impressum | Datenschutz

100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 10: Berechenbarkeits- und Komplexitätstheorie

Schmeck, Hartmut; König, Lukas

Abstract:
Der vorliegende Vorlesungszuschnitt beschäftigt sich mit der Berechenbarkeitstheorie und der Komplexitätstheorie. Die Berechenbarkeitstheorie beschäftigt sich mit der Frage, welche Funktionen prinzipiell berechenbar sind. Formalisiert wird diese Frage unter Zuhilfenahme von Turingmaschinen, die das mächtigste bekannte Berechnungsmodell sind. Es wird auf die Begriffe berechenbar, turingberechenbar, entscheidbar, semientscheidbar, unentscheidbar, aufzählbar, abzählbar und die Churchsche These eingegangen. Als Beispiel eines nicht berechenbaren (aber semientscheidbaren) Problems wird das Halteproblem betrachtet (?Hält eine gegebene Turingmaschine bei einer gegebenen Eingabe an oder läuft sie ewig weiter), als Beispiel eines nicht semientscheidbaren Problems wird die sogenannte Diagonalsprache entwickelt. Die Komplexitätstheorie untersucht für berechenbare Funktionen, mit welchem Zeit- und Platzaufwand diese berechnet werden können. Dabei wird verstärkt auf die Klassen der von deterministischen Turingmaschinen in polynomieller Zeit berechenbaren Funktionen (P) bzw. der von nichtdeterministischen Turingmaschinen in polynomieller Zeit berechenbaren Funktionen (NP) und ihr Verhältnis zueinander eingegangen. ... mehr


Zugehörige Institution(en) am KIT KIT-Bibliothek (BIB)
Publikationstyp Audio & Video
Publikationsdatum 24.10.2013
Erstellungsdatum 24.10.2013
Sprache Deutsch
DOI 10.5445/DIVA/2013-724
Identifikator KITopen-ID: 1000111698
Lizenz KITopen-Lizenz
Serie 100 Übungsaufgaben zu Grundlagen der Informatik : Band I: Theoretische Informatik
Folge 9
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page