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 6001
activelecturer 2330
series 490
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