Komplexitätstheorie (SS 2021)

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.

Einführung

Einführung und Inhalt

Date: April 13, 2021
Language: German
Duration: 01:05:46

Konzepte der Komplexitätstheorie

Probleme und Algorithmen

Date: April 20, 2021
Language: German
Duration: 01:20:32

Turing Maschinen

Date: April 27, 2021
Language: German
Duration: 01:39:50

Lineares Beschleunigen

Date: May 11, 2021
Language: German
Duration: 00:41:22

Raumkomplexität und Platzsparen

Date: May 4, 2021
Language: German
Duration: 00:54:25

Nichtdeterministische Turing Maschinen

Date: May 11, 2021
Language: German
Duration: 01:12:33

Komplexitätsklassen

Date: May 18, 2021
Language: German
Duration: 00:43:34

Hierarchie-Theoreme

Date: May 18, 2021
Language: German
Duration: 00:28:30

Erreichbarkeitsmethode

Date: May 25, 2021
Language: German
Duration: 00:58:48

Reduktion und Vollständigkeit (1)

Date: June 1, 2021
Language: German
Duration: 01:19:52

Reduktion und Vollständigkeit (2)

Date: June 8, 2021
Language: German
Duration: 01:10:27

Die Klassen P und NP

NP-Vollständigkeit

Date: June 15, 2021
Language: German
Duration: 00:53:58

Weitere NP-vollständige Probleme (1)

Date: June 22, 2021
Language: German
Duration: 01:08:10

Weitere NP-vollständige Probleme (2)

Date: June 29, 2021
Language: German
Duration: 01:08:10

NP vs. coNP und P vs. NP

Date: July 6, 2021
Language: German
Duration: 01:22:29

Randomisierte Berechnungen

Date: July 15, 2021
Language: German
Duration: 01:35:52

Approximation

Date: July 20, 2021
Language: German
Duration: 00:36:04

Polynomiale Schaltkreise

Date: July 20, 2021
Language: German
Duration: 00:48:38