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
Views: 228
Einführung
Einführung 00:53:34

Konzepte der Komplexitätstheorie

Probleme und Algorithmen

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

Turing Maschinen

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

Lineares Beschleunigen

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

Raumkomplexität und Platzsparen

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

Nichtdeterministische Turing Maschinen

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

Komplexitätsklassen

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

Hierarchie-Theoreme

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

Erreichbarkeitsmethode

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

Erreichbarkeitsmethode (2)

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

Reduktion und Vollständigkeit

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

Reduktion und Vollständigkeit (2)

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

Reduktion und Vollständigkeit (3)

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

Die Klassen P und NP

NP - Vollständigkeit

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

Weitere Charakterisierungen von NP

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

Weitere NP-vollständige Probleme

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

Weitere NP-vollständige Probleme (2)

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

Weitere NP-vollständige Probleme (3)

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

Weitere NP-vollständige Probleme (4)

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

NP und coNP

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

Randomisierte Berechnungen

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

Polynomialzeithierarchie

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

Polynomialzeithierarchie (2)

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

Approximation

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

Polynomiale Schaltkreise

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

P versus NP

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

Randomisierte Berechnungen (2)

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