KIT-Bibliothek
Audio-/Videodatei publizieren
Anleitung zum Publizieren

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

Autor

Hartmut Schmeck, Lukas König

Beteiligtes Institut

KIT-Bibliothek (BIB)

Genre

Vorlesung

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

Informatik

Lizenz

KITopen-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 kbps
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 kbps
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 kbps
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

100 Übungsaufgaben zu Grundlagen der Informatik : Band I: Theoretische Informatik Folgen 1-20 von 20