Einführung in die Komplexitätstheorie

Prof. Dr. Christoph Meinel


Ziel der Komplexitätstheorie ist die Quantifizierung von Computerressourcen (Rechenzeit, Speicherplatz, Hardwareaufwand, Kommunikationsaufwand, ...), die zur algorithmischen Lösung konkreter Probleme bzw. von Problemklassen benötigt werden. Die Vorlesung, die sich an Studenten des Informatik- bzw. Mathematikhauptstudiums wendet und Kernvorlesung für den Bereich theoretischen Informatik ist, bietet eine fundierte Einführung in die Komplexitätstheorie. Schwerpunktmäßig wird die Bedeutung komplexitätstheoretischer Aussagen für den Algorithmenentwurf herausgearbeitet.

Successor of this series: Komplexitätstheorie (SS 2008)

Einführung

Einführung

Date: 2003-10-28
Lang: de
Dur: 00:53:34
Einführung
Einführung 00:53:34

Konzepte der Komplexitätstheorie

Probleme und Algorithmen

Date: 2003-10-30
Lang: de
Dur: 01:29:36
Probleme und Algorithmen

Turing Maschinen

Date: 2003-11-04
Lang: de
Dur: 01:16:47
Turing Maschinen

Lineares Beschleunigen

Date: 2003-11-06
Lang: de
Dur: 01:18:36
Lineares Beschleunigen

Raumkomplexität und Platzsparen

Date: 2003-11-11
Lang: de
Dur: 01:15:42
Raumkomplexität und Platzsparen

Nichtdeterministische Turing Maschinen

Date: 2003-11-13
Lang: de
Dur: 01:34:48
Nichtdeterministische Turing Maschinen

Komplexitätsklassen

Date: 2003-11-18
Lang: de
Dur: 00:55:36
Komplexitätsklassen

Hierarchie-Theoreme

Date: 2003-11-20
Lang: de
Dur: 00:34:22
Hierarchie-Theoreme

Erreichbarkeitsmethode

Date: 2003-11-25
Lang: de
Dur: 01:17:47
Erreichbarkeitsmethode

Erreichbarkeitsmethode (2)

Date: 2003-11-27
Lang: de
Dur: 01:02:46
Erreichbarkeitsmethode (2)

Reduktion und Vollständigkeit

Date: 2003-12-02
Lang: de
Dur: 01:08:19
Reduktion und Vollständigkeit

Reduktion und Vollständigkeit (2)

Date: 2003-12-04
Lang: de
Dur: 01:21:48
Reduktion und Vollständigkeit (2)

Reduktion und Vollständigkeit (3)

Date: 1998-01-01
Lang: de
Dur: 01:20:41

Die Klassen P und NP

NP - Vollständigkeit

Date: 2003-12-11
Lang: de
Dur: 00:47:42
NP - Vollständigkeit

Weitere Charakterisierungen von NP

Date: 2003-12-16
Lang: de
Dur: 00:35:17
Weitere Charakterisierungen von NP

Weitere NP-vollständige Probleme

Date: 2003-12-18
Lang: de
Dur: 01:27:25
Weitere NP-vollständige Probleme

Weitere NP-vollständige Probleme (2)

Date: 2004-01-06
Lang: de
Dur: 01:10:46
Weitere NP-vollständige Probleme (2)

Weitere NP-vollständige Probleme (3)

Date: 2004-01-08
Lang: de
Dur: 01:14:07
Weitere NP-vollständige Probleme (3)

Weitere NP-vollständige Probleme (4)

Date: 2004-01-13
Lang: de
Dur: 01:35:26
Weitere NP-vollständige Probleme (4)

NP und coNP

Date: 2004-01-15
Lang: de
Dur: 01:21:10
NP und coNP
NP und coNP 01:21:10

Randomisierte Berechnungen

Date: 2004-01-20
Lang: de
Dur: 01:23:13
Randomisierte Berechnungen

Polynomialzeithierarchie

Date: 2004-01-22
Lang: de
Dur: 01:21:06
Polynomialzeithierarchie

Polynomialzeithierarchie (2)

Date: 2004-01-27
Lang: de
Dur: 01:15:07
Polynomialzeithierarchie (2)

Approximation

Date: 2004-01-29
Lang: de
Dur: 01:21:32
Approximation

Polynomiale Schaltkreise

Date: 2004-02-03
Lang: de
Dur: 01:24:24
Polynomiale Schaltkreise

P versus NP

Date: 2004-02-05
Lang: de
Dur: 01:13:33
P versus NP
P versus NP 01:13:33

Randomisierte Berechnungen (2)

Date: 2004-02-10
Lang: de
Dur: 01:16:38
Randomisierte Berechnungen (2)