Komplexitätstheorie (SS 2008)

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 Master-Studenten der Studiengänge IT Systems Engineering, Informatik und Mathematik wendet, bietet eine fundierte Einführung in die Komplexitätstheorie. Schwerpunktmäßig wird die Bedeutung komplexitätstheoretischer Aussagen für den Algorithmenentwurf herausgearbeitet.

Einführung

Konzepte der Komplexitätstheorie

Turing Maschinen

Date: April 23, 2008
Language: German
Duration: 01:28:50
Turing Maschinen

Lineares Beschleunigen

Date: April 24, 2008
Language: German
Duration: 00:44:07
Lineares Beschleunigen

Raumkomplexität und Platzsparen

Date: April 30, 2008
Language: German
Duration: 01:00:42
Raumkomplexität und Platzsparen

Nichtdeterministische Turing Maschinen

Date: May 7, 2008
Language: German
Duration: 01:30:59
Nichtdeterministische Turing Maschinen

Komplexitätsklassen

Date: May 8, 2008
Language: German
Duration: 00:54:23
Komplexitätsklassen

Hierarchie-Theoreme

Date: May 14, 2008
Language: German
Duration: 00:44:39
Hierarchie-Theoreme

Erreichbarkeitsmethode 1/2

Date: May 15, 2008
Language: German
Duration: 01:05:49
Erreichbarkeitsmethode 1/2

Erreichbarkeitsmethode 2/2

Date: May 21, 2008
Language: German
Duration: 00:45:21
Erreichbarkeitsmethode 2/2

Reduktion und Vollständigkeit 1/3

Date: May 22, 2008
Language: German
Duration: 00:54:06
Reduktion und Vollständigkeit 1/3

Reduktion und Vollständigkeit 2/3

Date: May 28, 2008
Language: German
Duration: 01:00:29
Reduktion und Vollständigkeit 2/3

Reduktion und Vollständigkeit 3/3

Date: May 29, 2008
Language: German
Duration: 01:05:20
Reduktion und Vollständigkeit 3/3

Die Klassen P und NP

NP-Vollständigkeit

Date: June 11, 2008
Language: German
Duration: 00:36:46
NP-Vollständigkeit

Weitere Characterisierungen von NP

Date: June 12, 2008
Language: German
Duration: 00:27:22
Weitere Characterisierungen von NP

Weitere NP-vollständige Probleme 1/4

Date: June 18, 2008
Language: German
Duration: 00:57:58
Weitere NP-vollständige Probleme 1/4

Weitere NP-vollständige Probleme 2/4

Date: June 19, 2008
Language: German
Duration: 00:57:13
Weitere NP-vollständige Probleme 2/4

Weitere NP-vollständige Probleme 3/4

Date: June 25, 2008
Language: German
Duration: 01:09:41
Weitere NP-vollständige Probleme 3/4

Weitere NP-vollständige Probleme 4/4

Date: June 26, 2008
Language: German
Duration: 01:12:17
Weitere NP-vollständige Probleme 4/4

NP and co-NP

Date: July 3, 2008
Language: German
Duration: 01:00:28
NP and co-NP

Randomisierte Berechnungen 1/2

Date: July 9, 2008
Language: German
Duration: 01:11:19
Randomisierte Berechnungen 1/2

Randomisierte Berechnungen 2/2

Date: July 10, 2008
Language: German
Duration: 00:49:27
Randomisierte Berechnungen 2/2

Polynomialzeithierarchie 1/2

Date: July 16, 2008
Language: German
Duration: 00:59:19
Polynomialzeithierarchie 1/2

Polynomialzeithierarchie 2/2

Date: July 17, 2008
Language: German
Duration: 00:54:16
Polynomialzeithierarchie 2/2

Approximation

Date: July 30, 2008
Language: German
Duration: 00:54:37
Approximation

Polynomiale Schaltkreise

Date: August 1, 2008
Language: German
Duration: 01:28:01
Polynomiale Schaltkreise

P versus NP

Date: August 5, 2008
Language: German
Duration: 00:49:04
P versus NP