100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 10: Berechenbarkeits- und Komplexitätstheorie
Autor
Beteiligtes Institut
Genre
Beschreibung
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. Im Zuge dessen werden die Begriffe NP-Vollständigkeit, NP-Schwere, Polynomialzeitreduktion usw. erläutert und ihre Anwendung an Beispielen dargestellt.
Laufzeit (hh:mm:ss)
02:58:28
Serie
100 Übungsaufgaben zu Grundlagen der Informatik : Band I: Theoretische Informatik
Publiziert am
24.10.2013
Fachgebiet
Lizenz
| Auflösung | 1024 x 768 Pixel |
| Seitenverhältnis | 4:3 |
| Audiobitrate | 31997 bps |
| Audio Kanäle | 1 |
| Audio Codec | aac |
| Audio Abtastrate | 22050 Hz |
| Gesamtbitrate | 100592 bps |
| Farbraum | yuv420p |
| Container | mov,mp4,m4a,3gp,3g2,mj2 |
| Medientyp | video/mp4 |
| Dauer | 10708 s |
| Dateiname | 2013-724_cam.mp4 |
| Dateigröße | 4.096 byte |
| Bildwiederholfrequenz | 25 |
| Videobitrate | 63458 bps |
| Video Codec | h264 |
| Auflösung | 1024 x 768 Pixel |
| Seitenverhältnis | 4:3 |
| Audiobitrate | 32000 bps |
| Audio Kanäle | 1 |
| Audio Codec | mp3 |
| Audio Abtastrate | 22050 Hz |
| Gesamtbitrate | 818328 bps |
| Farbraum | bgr24 |
| Container | avi |
| Medientyp | video/x-msvideo |
| Dauer | 10708 s |
| Dateiname | 2013-724_download.avi |
| Dateigröße | 4.096 byte |
| Bildwiederholfrequenz | 25 |
| Video Codec | camtasia |
Mediathek-URL
Embed-Code
