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

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. ... mehrIm Zuge dessen werden die Begriffe NP-Vollständigkeit, NP-Schwere, Polynomialzeitreduktion usw. erläutert und ihre Anwendung an Beispielen dargestellt.