Hasso-Plattner-Institut Design IT. Create Knowledge.

News

01.08.2016

openHPI Course "Internetworking 2016"

A new openHPI course about "Internetworking" starts on September 5, 2016. The course is held by Prof. Dr. Christoph Meinel ... [more]
19.05.2016

openHPI Workshop "Embedded Smart Home"

We are going to offer a new openHPI workshop "Embedded Smart Home" in German language. More Infocan be found here ... [more]
10.03.2016

New public demo

You can check out our public demo platform at https://tele-task-demo.hpi.uni-potsdam.de. Please let us know what you ...

Statistics

userclicks 35 M
lecture 5988
activelecturer 2323
series 489
Lecture-Feed of Series: Komplexitätstheorie (SS 2008) Feed of Series: Komplexitätstheorie (SS 2008)

Komplexitätstheorie (SS 2008)

Prof. Dr. Christoph Meinel

Successor of this series: Komplexitätstheorie (SS 2010)

Predecessor of this series: Einführung in die Komplexitätstheorie

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

Not enough ratings.
Date: 16.04.2008
Lang.: de
Dur.: 00:56:26
Play full lecture
• Was ist Komplexitätstheorie 00:17:45
• Grundrichtungen in der Komplexitätstheorie 00:02:20
• Hauptaufgabe der Komplexitätstheorie 00:07:03
• Welche Ergebnisse bringt die Komplexitätstheorie? 00:12:05
• Fahrplan für die Vorlesungen zur Komplexitätstheorie 00:12:48
• Leistungsnachweis 00:04:25

Konzepte der Komplexitätstheorie

Not enough ratings.
Date: 17.04.2008
Lang.: de
Dur.: 01:13:56
Play full lecture
• Einführung 00:03:59
• Reachability - Grapherreichbarkeit 00:08:10
• Entscheidungsprobleme 00:04:23
• Algorithmus für Grapherreichbarkeit 00:11:45
• O-Notation 00:08:10
• Polynomialzeit-Algorithmen 00:02:45
• Speicherplatzbedarf 00:02:20
• MAX Flow - Flüsse im Netzwerken 00:12:41
• Reduktionstechniken 00:08:56
• TSP - Rundreiseproblem 00:10:47
Not enough ratings.
Date: 23.04.2008
Lang.: de
Dur.: 01:28:50
Play full lecture
• Einführung 00:02:39
• Erweiterte Church´sche These 00:08:23
• Turing Maschine - Grundidee 00:06:01
• K-Band Turing Maschine (TM) 00:43:03
• Zeitkomplexität 00:06:33
• Leistungsvergleich von K-Band und 1-Band TM 00:22:11
Not enough ratings.
Date: 24.04.2008
Lang.: de
Dur.: 00:44:07
Play full lecture
• Wiederholung 00:04:35
• Speedup Theorem 00:06:05
• Speedup Theorem-Beweisidee 00:26:47
• Diskussion des Speedup Theorem 00:03:33
• Definition der Komplexitätsklasse P 00:03:07
Not enough ratings.
Date: 30.04.2008
Lang.: de
Dur.: 01:00:42
Play full lecture
• Wiederholung 00:04:00
• Begriffsbestimmung 00:11:57
• Beispiel 00:10:23
• TM mit Ein- und Ausgabe 00:12:44
• Raumkomplexität 00:05:41
• Raumkomplexitätsklassen 00:08:36
• Platzsparen 00:07:21
Not enough ratings.
Date: 07.05.2008
Lang.: de
Dur.: 01:30:59
Play full lecture
• Einführung 00:24:36
• Nichtdeterministische Berechnungen 00:08:31
• Nichtdeterministische Komplexität 00:11:06
• Rundreiseproblem - TSP (D) 00:15:26
• Nichtdeterministische und probabilistische TM 00:07:08
• Nichtdeterministische und deterministische TM 00:24:12
Not enough ratings.
Date: 08.05.2008
Lang.: de
Dur.: 00:54:23
Play full lecture
• Einführung 00:07:43
• Schrankenfunktionen 00:14:50
• Präzise Turing Maschinen 00:11:18
• Wichtige Komplexitätsklassen 00:04:07
• Komplementäre Komplexitätsklassen 00:16:25
Not enough ratings.
Date: 14.05.2008
Lang.: de
Dur.: 00:44:39
Play full lecture
• Zeit-Hierarchie-Theorem 1-5 00:20:13
• Zeit-Hierarchie-Theorem 6-10 00:21:17
• Raum-Hierarchie-Theorem 00:03:09
Not enough ratings.
Date: 15.05.2008
Lang.: de
Dur.: 01:05:49
Play full lecture
• Einführung 00:01:33
• Determinismus vs. Nichtdeterminismus 00:04:45
• NTIME vs. SPACE 00:10:06
• NSPACE vs. TIME 00:17:18
• Zwischenbilanz 00:08:59
• Satz von Sawitch 00:23:09
Not enough ratings.
Date: 21.05.2008
Lang.: de
Dur.: 00:45:21
Play full lecture
• Wiederholung 00:07:57
• Satz von Immerman Szelepcseny 00:08:53
• Beweis des Satzes 00:13:02
• Analyse des Satzes 00:05:43
• NSPACE vs coNSPACE 00:09:46
Not enough ratings.
Date: 22.05.2008
Lang.: de
Dur.: 00:54:06
Play full lecture
• Einführung 00:10:19
• Grundidee der Reduktion 00:03:11
• Logspace-Reduktion 00:10:10
• Hammilton Path 1-5 00:16:45
• Hammilton Path 6-10 00:13:41
Not enough ratings.
Date: 28.05.2008
Lang.: de
Dur.: 01:00:29
Play full lecture
• Einführung 00:01:50
• Grundlagen der Reduktion 00:10:48
• Reachability Cirquit Value 00:19:27
• Reduktion durch Verallgemeinerung 00:13:47
• Komposition von Reduktionen 00:14:37
Not enough ratings.
Date: 29.05.2008
Lang.: de
Dur.: 01:05:20
Play full lecture
• Einführung 00:04:25
• K-Vollständigkeit 00:14:24
• Berechnungstabellen Methode 00:15:05
• P-Vollständigkeit von CIRCUIT VALUE 1 00:09:55
• P-Vollständigkeit von CIRCUIT VALUE 5 00:21:31

Die Klassen P und NP

Not enough ratings.
Date: 11.06.2008
Lang.: de
Dur.: 00:36:46
Play full lecture
• Erinnerung 00:14:29
• Cook's Theorem 1 bis 3 00:09:21
• Cook's Theorem 4 bis 6 00:12:56
Not enough ratings.
Date: 12.06.2008
Lang.: de
Dur.: 00:27:22
Play full lecture
• Überleitung 00:01:13
• Polynomial entscheidbare Relation 00:04:33
• Charakterisierung von NP mittels Relationen 00:14:20
• Polynomiale Zeugnisse 00:07:16
Not enough ratings.
Date: 18.06.2008
Lang.: de
Dur.: 00:57:58
Play full lecture
• Erinnerung 00:10:36
• NP-vollständige SAT-Varianten 00:11:29
• 2-SAT gehört zu P 00:18:01
• 2-SAT gehört zu NL 00:02:01
• MAX-2-SAT ist NP-vollständig 00:15:51
Not enough ratings.
Date: 19.06.2008
Lang.: de
Dur.: 00:57:13
Play full lecture
• Erinnerung 00:08:27
• Independent Set Problem 00:19:37
• Clique und Note Cover 00:05:07
• Schnittprobleme 1 00:13:10
• Schnittprobleme 2 00:10:53
Not enough ratings.
Date: 25.06.2008
Lang.: de
Dur.: 01:09:41
Play full lecture
• Erinnerung 00:07:45
• Wege-Probleme 00:12:33
• Färbungsprobleme 00:17:14
• Matching 00:16:34
• Matching 00:15:35
Not enough ratings.
Date: 26.06.2008
Lang.: de
Dur.: 01:12:17
Play full lecture
• Erinnerung 00:08:52
• Set-Cover 00:09:51
• Integer Programming 00:16:38
• Knapsack 00:17:24
• Bin-Packing 00:19:33
Not enough ratings.
Date: 03.07.2008
Lang.: de
Dur.: 01:00:28
Play full lecture
• Einführung 00:08:53
• coNP -vollständige Probleme 00:05:35
• NP = coNP ? 00:15:36
• Pratt's Theorem 00:19:10
• PRIMES gehört zu P 00:11:14
Not enough ratings.
Date: 09.07.2008
Lang.: de
Dur.: 01:11:19
Play full lecture
• Einführung 00:02:42
• Symbolische Determinante 00:13:58
• Gauss'sche Elimination 00:24:54
• Randomisierter Algorithmus 00:09:10
• Random Walks 00:05:48
• Fermat Test 00:14:48
Not enough ratings.
Date: 10.07.2008
Lang.: de
Dur.: 00:49:27
Play full lecture
• Wiederholung 00:04:47
• Fehlersituation 00:13:07
• Die Komplexitätsklasse PP 00:10:17
• Die Komplexitätsklasse BPP 00:07:23
• Die Komplexitätsklasse RP 00:07:08
• Die Komplexitätsklasse ZPP 00:04:22
• Probabilistische Komplexitätsklassen 00:02:24
Not enough ratings.
Date: 16.07.2008
Lang.: de
Dur.: 00:59:19
Play full lecture
• Einführung 00:03:58
• Orakel Tuning Maschinen OTM 00:07:21
• Einige Relativierungen 00:19:10
• Aufbau der Polynomialzeithierarchie 00:05:55
• Polynomial balancierte Relationen 00:20:18
• Logische Charakterisierung 00:02:37
Not enough ratings.
Date: 17.07.2008
Lang.: de
Dur.: 00:54:16
Play full lecture
• Wiederholung 00:14:44
• Kolabiert Polynomialzeithierarchie? 00:13:00
• Minimum Circuit 00:05:42
• Vollständige Probleme 00:12:56
• PH und PSPACE 00:07:54
Not enough ratings.
Date: 30.07.2008
Lang.: de
Dur.: 00:54:37
Play full lecture
• Einführung 00:07:25