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
Views: 232

Konzepte der Komplexitätstheorie

Probleme und Algorithmen

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

Lineares Beschleunigen

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

Raumkomplexität und Platzsparen

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

Nichtdeterministische Turing Maschinen

Date: May 3, 2012
Language: German
Duration: 01:30:25
Views: 200

Komplexitätsklassen

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

Hierarchie-Theoreme

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

Erreichbarkeitsmethode 1/2

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

Erreichbarkeitsmethode 2/2

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

Reduktion und Vollständigkeit 1/3

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

Reduktion und Vollständigkeit 2/3

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

Reduktion und Vollständigkeit 3/3

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

Die Klassen P und NP

NP-Vollständigkeit

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

Weitere Charakterisierungen von NP

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

Weitere NP-vollständige Probleme 1/4

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

Weitere NP-vollständige Probleme 2/4

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

Weitere NP-vollständige Probleme 3/4

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

Weitere NP-vollständige Probleme 4/4

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

NP und coNP

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

Randomisierte Berechnungen 1/2

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

Randomisierte Berechnungen 2/2

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

Polynomialzeithierarchie 1/2

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

Polynomialzeithierarchie 2/2

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

Approximation

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

P versus NP

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