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.

Successor of this series: Komplexitätstheorie (SS 2016)
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
Views: 199

Raumkomplexität und Platzsparen

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

Komplexitätsklassen

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

Hierarchie-Theoreme

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

Erreichbarkeitsmethode 1/2

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

Erreichbarkeitsmethode 2/2

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

Reduktion und Vollständigkeit (1)

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

Reduktion und Vollständigkeit (2)

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

Reduktion und Vollständigkeit (3)

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

Die Klassen P und NP

NP-Vollständigkeit

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

Weitere Charakterisierungen von NP

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

Weitere NP vollständige Probleme (1)

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

Weitere NP-vollständige Probleme (2)

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

Weitere NP-vollständige Probleme (3)

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

Weitere NP-vollständige Probleme (4)

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

NP und coNP

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

Randomisierte Berechnungen (1)

Date: July 2, 2014
Language: German
Duration: 01:06:40
Views: 1787

Polynomialzeithierarchie (1)

Date: July 9, 2014
Language: German
Duration: 00:56:47
Views: 203

Approximation

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

P versus NP

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