Komplexitätstheorie (SS 2012)

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 2014)
Predecessor of this series: Komplexitätstheorie (SS 2010)

Einführung

Einführung und Inhalt

Date: April 11, 2012
Language: German
Duration: 00:37:42

Konzepte der Komplexitätstheorie

Probleme und Algorithmen

Date: April 12, 2012
Language: German
Duration: 01:38:17

Lineares Beschleunigen

Date: April 24, 2012
Language: German
Duration: 01:00:26

Raumkomplexität und Platzsparen

Date: May 2, 2012
Language: German
Duration: 01:19:03

Komplexitätsklassen

Date: May 9, 2012
Language: German
Duration: 00:48:16

Hierarchie-Theoreme

Date: May 10, 2012
Language: German
Duration: 00:42:20

Erreichbarkeitsmethode 1/2

Date: May 16, 2012
Language: German
Duration: 01:00:00

Erreichbarkeitsmethode 2/2

Date: May 24, 2012
Language: German
Duration: 01:07:26

Reduktion und Vollständigkeit 1/3

Date: May 30, 2012
Language: German
Duration: 01:06:23

Reduktion und Vollständigkeit 2/3

Date: May 31, 2012
Language: German
Duration: 00:54:06

Reduktion und Vollständigkeit 3/3

Date: June 6, 2012
Language: German
Duration: 01:15:30

Die Klassen P und NP

NP-Vollständigkeit

Date: June 7, 2012
Language: German
Duration: 00:35:25

Weitere Charakterisierungen von NP

Date: June 13, 2012
Language: German
Duration: 00:32:50

Weitere NP-vollständige Probleme 1/4

Date: June 14, 2012
Language: German
Duration: 01:02:48

Weitere NP-vollständige Probleme 2/4

Date: June 20, 2012
Language: German
Duration: 01:09:51

Weitere NP-vollständige Probleme 3/4

Date: June 21, 2012
Language: German
Duration: 01:13:06

Weitere NP-vollständige Probleme 4/4

Date: June 27, 2012
Language: German
Duration: 01:26:03

NP und coNP

Date: June 28, 2012
Language: German
Duration: 01:12:17

Randomisierte Berechnungen 1/2

Date: July 4, 2012
Language: German
Duration: 01:10:39

Randomisierte Berechnungen 2/2

Date: July 5, 2012
Language: German
Duration: 00:51:49

Polynomialzeithirarchie 1/2

Date: July 10, 2012
Language: German
Duration: 01:00:07

Polynomialzeithirarchie 2/2

Date: July 10, 2012
Language: German
Duration: 00:58:27

Approximation

Date: July 11, 2012
Language: German
Duration: 01:02:22

P versus NP

Date: July 12, 2012
Language: German
Duration: 00:50:06