100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 10: Berechenbarkeits- und Komplexitätstheorie
Author
Participating institute
Genre
Description
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.
Duration (hh:mm:ss)
02:58:28
Series
100 Übungsaufgaben zu Grundlagen der Informatik : Band I: Theoretische Informatik
Published on
24.10.2013
Subject area
License
| Resolution | 1024 x 768 Pixel |
| Aspect ratio | 4:3 |
| Audio bitrate | 31997 bps |
| Audio channels | 1 |
| Audio Codec | aac |
| Audio Sample Rate | 22050 Hz |
| Total Bitrate | 100592 bps |
| Color Space | yuv420p |
| Container | mov,mp4,m4a,3gp,3g2,mj2 |
| Media Type | video/mp4 |
| Duration | 10708 s |
| Filename | 2013-724_cam.mp4 |
| File Size | 4.096 byte |
| Frame Rate | 25 |
| Video Bitrate | 63458 bps |
| Video Codec | h264 |
| Resolution | 1024 x 768 Pixel |
| Aspect ratio | 4:3 |
| Audio bitrate | 32000 bps |
| Audio channels | 1 |
| Audio Codec | mp3 |
| Audio Sample Rate | 22050 Hz |
| Total Bitrate | 818328 bps |
| Color Space | bgr24 |
| Container | avi |
| Media Type | video/x-msvideo |
| Duration | 10708 s |
| Filename | 2013-724_download.avi |
| File Size | 4.096 byte |
| Frame Rate | 25 |
| Video Codec | camtasia |
Media URL
Embed Code
