Komplexitätstheorie (SS 2014)

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.

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

Einführung

Konzepte der Komplexitätstheorie

Lineares Beschleunigen

Date: April 24, 2014
Language: German
Duration: 00:51:32

Raumkomplexität und Platzsparen

Date: April 30, 2014
Language: German
Duration: 00:57:14

Komplexitätsklassen

Date: May 8, 2014
Language: German
Duration: 00:41:52

Hierarchie-Theoreme

Date: May 8, 2014
Language: English
Duration: 00:33:29

Erreichbrkeitsmethode 1/2

Date: May 14, 2014
Language: German
Duration: 00:56:39

Erreichbarkeitsmethode 2/2

Date: May 15, 2014
Language: German
Duration: 00:50:58

Reduktion und Vollständigkeit (1)

Date: May 21, 2014
Language: German
Duration: 01:07:03

Reduktion und Vollständigkeit (2)

Date: May 22, 2014
Language: German
Duration: 00:55:20

Reduktion und Vollständigkeit (3)

Date: June 11, 2014
Language: German
Duration: 00:57:57

Die Klassen P und NP

NP-Vollständigkeit

Date: June 12, 2014
Language: German
Duration: 00:35:02

Weitere Charakterisierungen von NP

Date: June 18, 2014
Language: German
Duration: 00:19:30

Weitere NP vollständige Probleme (1)

Date: June 18, 2014
Language: German
Duration: 00:58:00

Weitere NP-vollständige Probleme (2)

Date: June 19, 2014
Language: German
Duration: 00:54:32

Weitere NP-vollständige Probleme (3)

Date: June 25, 2014
Language: German
Duration: 01:08:55

Weitere NP-vollständige Probleme (4)

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

NP und coNP

Date: June 26, 2014
Language: German
Duration: 01:01:17

Approximation

Date: July 16, 2014
Language: German
Duration: 00:53:16

P versus NP

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