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

Introduction and content

Date: April 21, 2010
Language: German
Duration: 01:03:58
Views: 324

Concepts of Computational Complexity Theory

Turing Machines

Date: April 28, 2010
Language: German
Duration: 01:37:27
Views: 349

Linear acceleration

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

Raumkomplexität und Platzsparen

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

Komplexitätsklassen

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

Hierarchie-Theoreme

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

Erreichbarkeitsmethode 1/2

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

Erreichbarkeitsmethode 2/2

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

Reduktion und Vollständigkeit 1/3

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

Reduktion und Vollständigkeit 2/3

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

Reduktion und Vollständigkeit 3/3

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

Problems and Algorithms

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

Classes P and NP

Weitere Charakterisierungen von NP

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

Weitere NP-vollständige Probleme 1/4

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

Weitere NP-vollständige Probleme 2/4

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

Weitere NP-vollständige Probleme 3/4

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

Weitere NP-vollständige Probleme 4/4

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

NP und coNP

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

Randomisierte Berechnungen 1/2

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

Randomisierte Berechnungen 2/2

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

Polynomialzeithierarchie 1/2

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

Polynomialzeithierarchie 2/2

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

Approximation

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

P versus NP

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

NP-Vollständigkeit

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