Komplexitätstheorie (SS 2010)

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.

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

Introduction

Concepts of Computational Complexity Theory

Linear acceleration

Date: May 4, 2010
Language: German
Duration: 01:00:23

Raumkomplexität und Platzsparen

Date: May 5, 2010
Language: German
Duration: 01:10:17

Komplexitätsklassen

Date: May 12, 2010
Language: German
Duration: 00:50:45

Hierarchie-Theoreme

Date: May 18, 2010
Language: German
Duration: 00:51:36

Erreichbarkeitsmethode 1/2

Date: May 19, 2010
Language: German
Duration: 01:09:36

Erreichbarkeitsmethode 2/2

Date: May 25, 2010
Language: German
Duration: 01:01:12

Reduktion und Vollständigkeit 1/3

Date: May 28, 2010
Language: German
Duration: 00:58:20

Reduktion und Vollständigkeit 2/3

Date: June 1, 2010
Language: German
Duration: 01:16:21

Reduktion und Vollständigkeit 3/3

Date: June 2, 2010
Language: German
Duration: 01:10:41

Problems and Algorithms

Date: April 27, 2010
Language: German
Duration: 01:36:43

Classes P and NP

Weitere Charakterisierungen von NP

Date: June 8, 2010
Language: German
Duration: 00:20:45

Weitere NP-vollständige Probleme 1/4

Date: June 9, 2010
Language: German
Duration: 01:03:36

Weitere NP-vollständige Probleme 2/4

Date: June 21, 2010
Language: German
Duration: 01:06:06

Weitere NP-vollständige Probleme 3/4

Date: June 22, 2010
Language: German
Duration: 01:22:15

Weitere NP-vollständige Probleme 4/4

Date: June 23, 2010
Language: German
Duration: 01:18:54

NP und coNP

Date: June 28, 2010
Language: German
Duration: 01:13:47

Randomisierte Berechnungen 1/2

Date: July 1, 2010
Language: German
Duration: 01:11:12

Randomisierte Berechnungen 2/2

Date: July 6, 2010
Language: German
Duration: 00:55:59

Polynomialzeithierarchie 1/2

Date: July 6, 2010
Language: German
Duration: 01:00:11

Polynomialzeithierarchie 2/2

Date: July 7, 2010
Language: German
Duration: 00:58:27

Approximation

Date: July 14, 2010
Language: German
Duration: 00:58:51

P versus NP

Date: July 21, 2010
Language: German
Duration: 00:50:06

NP-Vollständigkeit

Date: June 8, 2010
Language: German
Duration: 00:32:30