Hasso-Plattner-Institut Design IT. Create Knowledge.

News

10.03.2017

CeBIT 2017

Also this year, tele-TASK and openHPI are at CeBIT (20-24 March, 2017). You can find us at the HPI booth ... [more]
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]

Statistics

userclicks 35 M
lecture 6107
activelecturer 2505
series 501
Lecture-Feed of Series: Komplexitätstheorie (SS 2010) Feed of Series: Komplexitätstheorie (SS 2010)

Komplexitätstheorie (SS 2010)

Prof. Dr. Christoph Meinel

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

Predecessor of this series: Komplexitätstheorie (SS 2008)

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.

Introduction

Not enough ratings.
Date: 21.04.2010
Lang.: de
Dur.: 01:03:58
Play full lecture
• Was ist Komplexitätstheorie 00:29:02
• Grundrichtungen in der Komplexitätstheorie 00:09:10
• Ergebnisse der Komplexitätstheorie 00:09:38
• Ablauf der Vorlesungen 00:16:08

Concepts of Computational Complexity Theory

Not enough ratings.
Date: 28.04.2010
Lang.: de
Dur.: 01:37:27
Play full lecture
• Einführung 00:04:04
• Erweiterte Church'sche These 00:12:58
• K-Band Turing Maschine 00:25:22
• Konfiguration einer K-Band TM 00:22:39
• Zeitkomplexität 00:09:24
• Leistungsvergleich von Turing Maschinen 00:23:01
Not enough ratings.
Date: 04.05.2010
Lang.: de
Dur.: 01:00:23
Play full lecture
• Repetition 00:05:23
• Speedup proposition 00:07:06
• Idea of evidence 00:23:41
• Simulation of workingsteps from M by M' 00:20:11
• Definition of the complexityclass P 00:04:02
Not enough ratings.
Date: 05.05.2010
Lang.: de
Dur.: 01:10:17
Play full lecture
• Introduction 00:04:46
• Begriffsbestimmung 00:15:19
• Beispiel 00:13:39
• Turingmaschinen mit Ein- und Ausgabe 00:15:11
• Raumkomplexität 00:13:56
• Platzsparen 00:07:26
Not enough ratings.
Date: 11.05.2010
Lang.: de
Dur.: 01:30:29
Play full lecture
• Einführung 00:05:29
• NTM - Definitionen 00:18:49
• Nichtdeterministische Berechnungen 00:11:15
• Nichtdeterministische Komplexität 00:09:27
• Rundreiseproblem - TSP(D) 00:24:58
• Nichtdeterministische und deterministische TM 00:20:31
Not enough ratings.
Date: 12.05.2010
Lang.: de
Dur.: 00:50:45
Play full lecture
• Einführung 00:04:24
• Schrankenfunktionen 00:18:38
• Präzise Turing Maschinen 00:09:26
• Wichtige Komplexitätsklassen 00:03:48
• Komplementäre Komplexitätsklassen 00:14:29
Not enough ratings.
Date: 18.05.2010
Lang.: de
Dur.: 00:51:36
Play full lecture
• Zeit-Hierarchie-Theorem Satz 1 00:24:58
• Zeit-Hierarchie-Theorem Satz 2 00:24:31
• Raum-Hierarchie-Theorem 00:02:07
Not enough ratings.
Date: 19.05.2010
Lang.: de
Dur.: 01:09:36
Play full lecture
• Einführung 00:03:13
• NTIME vs. SPACE 00:13:34
• NSPACE vs. TIME 00:17:27
• Zwischenbilanz 00:08:16
• Satz von Savitch 00:27:06
Not enough ratings.
Date: 25.05.2010
Lang.: de
Dur.: 01:01:12
Play full lecture
• Wiederholung 00:09:52
• Satz von Immerman-Szelepcsenyi 00:13:43
• Beweis des Satzes 00:19:38
• Analyse des Satzes 00:07:53
• NSPACE vs. coNSPACE 00:10:07
Not enough ratings.
Date: 28.05.2010
Lang.: de
Dur.: 00:58:20
Play full lecture
• Einführung 00:12:07
• Grundidee der Reduktion 00:13:58
• HAMILTON PATH < SAT 00:17:04
• Behauptung und Beweis 00:15:11
Not enough ratings.
Date: 01.06.2010
Lang.: de
Dur.: 01:16:21
Play full lecture
• Grundidee der Reduktion 00:12:12
• Reduktion von REACHABILITY 00:27:22
• Reduktion durch Verallgemeinerung 00:04:26
• Reduktion von CIRCUIT SAT 00:18:25
• Komposition von Reduktionen 00:13:56
Not enough ratings.
Date: 02.06.2010
Lang.: de
Dur.: 01:10:41
Play full lecture
• Einführung 00:03:23
• K-Vollständigkeit 00:16:49
• Berechnungstabellen-Methode 00:16:20
• P-Vollständigkeit von CIRCUIT VALUE 00:29:58
• P-Vollständigkeit von MONTONE CIRCUIT VALUE 00:04:11
Not enough ratings.
Date: 27.04.2010
Lang.: de
Dur.: 01:36:43
Play full lecture
• Introduction 00:19:14
• Decision problems 00:06:04
• Algorithm for graphreachability 00:15:37
• O-Notation 00:19:48
• MAX FLOW - flows in networks 00:14:56
• Reduction-technique 00:10:18
• TSP-Round-trip-problem 00:10:46

Classes P and NP

Not enough ratings.
Date: 08.06.2010
Lang.: de
Dur.: 00:20:45
Play full lecture
• Polynomial entscheidbare Relation 00:05:04
• Charakterisierung von NP mittels Relationen 00:10:17
• Polynomiale Zeugnisse 00:05:24
Not enough ratings.
Date: 09.06.2010
Lang.: de
Dur.: 01:03:36
Play full lecture
• Erinnerung 00:14:35
• NP-vollständige SAT-Varianten 00:14:00
• 2-SAT gehört zu P 00:19:55
• 2-SAT gehört zu NL 00:00:46
• MAX-2-SAT ist NP-vollständig 00:11:59
• NAE-SAT ist NP-vollständig 00:02:21
Not enough ratings.
Date: 21.06.2010
Lang.: de
Dur.: 01:06:06
Play full lecture
• Erinnerung 00:10:12
• INDEPENDENT SET Problem 00:23:23
• CLIQUE und NODE COVER 00:05:27
• Schnitt-Probleme 00:17:43
• MIN CUT 00:09:21
Not enough ratings.
Date: 22.06.2010
Lang.: de
Dur.: 01:22:15
Play full lecture
• Erinnerung 00:10:07
• Wege Probleme 00:14:07
• Färbungsprobleme 00:18:51
• Matching (1) 00:16:58
• Matching (2) 00:22:12
Not enough ratings.
Date: 23.06.2010
Lang.: de
Dur.: 01:18:54
Play full lecture
• Erinnerung 00:12:28
• SET COVER 00:08:05
• INTEGER PROGRAMMING 00:11:58
• KNAPSACK 00:20:34
• BIN PACKING 00:25:49
Not enough ratings.
Date: 28.06.2010
Lang.: de
Dur.: 01:13:47
Play full lecture
• Einführung 00:18:29
• NP = coNP? 00:13:28
• Durchschnitt von NP und coNP 00:06:44
• Pratt's Theorem 00:22:46
• PRIMES gehört zu P 00:10:50
Not enough ratings.
Date: 01.07.2010
Lang.: de
Dur.: 01:11:12
Play full lecture
• Einführung 00:02:45
• Symbolische Determinante 00:13:45
• Gauß'sche Elimination 00:10:51
• Abschätzen der Zahl der Nullstellen 00:14:14
• Randomisierter Algorithmus 00:11:15
• Random Walks 00:07:09
• Fermat Test 00:11:13
Not enough ratings.
Date: 06.07.2010
Lang.: de
Dur.: 00:55:59
Play full lecture
• Wiederholung 00:04:12
• Fehlersituation 00:05:36
• Probabilistische Turing Maschinen 00:09:40
• Die Klasse PP 00:11:54
• Die Klasse BPP 00:08:24
• Die Klasse RP 00:08:53
• Die Klasse ZPP 00:07:20
Not enough ratings.
Date: 06.07.2010
Lang.: de
Dur.: 01:00:11
Play full lecture
• Einführung 00:03:57
• Orakel Turing Maschinen 00:07:45
• Einige Relativierungen 00:20:57
• Aufbau der Polynomialzeithirarchie 00:05:23
• Polynomial balancierte Relationen 00:22:09
Not enough ratings.
Date: 07.07.2010
Lang.: de
Dur.: 00:58:27
Play full lecture
• Wiederholung 00:16:52
• Kollabiert Polynomialzeithierarchie? 00:11:59
• MINIMUM CIRQUIT 00:05:55
• Vollständige Probleme 00:12:39
• PH und PSPACE 00:11:02
Not enough ratings.
Date: 14.07.2010
Lang.: de
Dur.: 00:58:51
Play full lecture
• Einführung 00:05:21
• e-Approximation 00:08:59
• NODE COVER 00:09:09
• MAXIMUM SATISFIABILITY 00:12:28
• TRAVELING SALESMAN PROBLEM 00:09:59
• Polynomiale Approximationsschemata 00:12:58
Not enough ratings.
Date: 21.07.2010
Lang.: de
Dur.: 01:23:39
Play full lecture
• Einführung 00:04:55
• Schaltkreise als Berechnungsmodell 00:05:51
• Schaltkreiskomplexität 00:10:19
• Typische Schaltkreisgröße 00:09:32
• Polynomiale Schaltkreisverbindungen 00:24:54