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: October 28, 2003
Language: German
Duration: 00:53:34
Einführung
Einführung 00:53:34

Konzepte der Komplexitätstheorie

Probleme und Algorithmen

Date: October 30, 2003
Language: German
Duration: 01:29:36
Probleme und Algorithmen

Turing Maschinen

Date: November 4, 2003
Language: German
Duration: 01:16:47
Turing Maschinen

Lineares Beschleunigen

Date: November 6, 2003
Language: German
Duration: 01:18:36
Lineares Beschleunigen

Raumkomplexität und Platzsparen

Date: November 11, 2003
Language: German
Duration: 01:15:42
Raumkomplexität und Platzsparen

Nichtdeterministische Turing Maschinen

Date: November 13, 2003
Language: German
Duration: 01:34:48
Nichtdeterministische Turing Maschinen

Komplexitätsklassen

Date: November 18, 2003
Language: German
Duration: 00:55:36
Komplexitätsklassen

Hierarchie-Theoreme

Date: November 20, 2003
Language: German
Duration: 00:34:22
Hierarchie-Theoreme

Erreichbarkeitsmethode

Date: November 25, 2003
Language: German
Duration: 01:17:47
Erreichbarkeitsmethode

Erreichbarkeitsmethode (2)

Date: November 27, 2003
Language: German
Duration: 01:02:46
Erreichbarkeitsmethode (2)

Reduktion und Vollständigkeit

Date: December 2, 2003
Language: German
Duration: 01:08:19
Reduktion und Vollständigkeit

Reduktion und Vollständigkeit (2)

Date: December 4, 2003
Language: German
Duration: 01:21:48
Reduktion und Vollständigkeit (2)

Reduktion und Vollständigkeit (3)

Date: January 1, 1998
Language: German
Duration: 01:20:41

Die Klassen P und NP

NP - Vollständigkeit

Date: December 11, 2003
Language: German
Duration: 00:47:42
NP - Vollständigkeit

Weitere Charakterisierungen von NP

Date: December 16, 2003
Language: German
Duration: 00:35:17
Weitere Charakterisierungen von NP

Weitere NP-vollständige Probleme

Date: December 18, 2003
Language: German
Duration: 01:27:25
Weitere NP-vollständige Probleme

Weitere NP-vollständige Probleme (2)

Date: January 6, 2004
Language: German
Duration: 01:10:46
Weitere NP-vollständige Probleme (2)

Weitere NP-vollständige Probleme (3)

Date: January 8, 2004
Language: German
Duration: 01:14:07
Weitere NP-vollständige Probleme (3)

Weitere NP-vollständige Probleme (4)

Date: January 13, 2004
Language: German
Duration: 01:35:26
Weitere NP-vollständige Probleme (4)

NP und coNP

Date: January 15, 2004
Language: German
Duration: 01:21:10
NP und coNP
NP und coNP 01:21:10

Randomisierte Berechnungen

Date: January 20, 2004
Language: German
Duration: 01:23:13
Randomisierte Berechnungen

Polynomialzeithierarchie

Date: January 22, 2004
Language: German
Duration: 01:21:06
Polynomialzeithierarchie

Polynomialzeithierarchie (2)

Date: January 27, 2004
Language: German
Duration: 01:15:07
Polynomialzeithierarchie (2)

Approximation

Date: January 29, 2004
Language: German
Duration: 01:21:32
Approximation

Polynomiale Schaltkreise

Date: February 3, 2004
Language: German
Duration: 01:24:24
Polynomiale Schaltkreise

P versus NP

Date: February 5, 2004
Language: German
Duration: 01:13:33
P versus NP
P versus NP 01:13:33

Randomisierte Berechnungen (2)

Date: February 10, 2004
Language: German
Duration: 01:16:38
Randomisierte Berechnungen (2)