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 5733
activelecturer 2371
series 472
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
• Polynomiale uniforme Schaltkreisfamilien 00:11:25
• Polynomiale Schaltkreise für BPP 00:16:43
Not enough ratings.
Date: 21.07.2010
Lang.: de
Dur.: 00:50:06
Play full lecture
• Einführung 00:03:48
• Graph Isomorphie 00:04:52
• Landkarte von NP 00:26:44
• NP-vollständige unäre Sprache 00:06:26
• Abschließende Bemerkungen 00:08:16
Not enough ratings.
Date: 08.06.2010
Lang.: de
Dur.: 00:32:30
Play full lecture
• Erinnerung 00:11:04
• Cook's Theorem 00:21:26
Tags added to this content
Tag this content

Please enable javascript to use this function.

Dear user,
with the tagging function you'll be able to add taggs to videos.
However, in order to link all your tags with your user profile it is required that you
login to the tele-TASK portal to use this functionality.
If you don't have an account yet, you may register for a tele-TASK account here.
Links added to this content

No links have been added to this content so far.

Add Link to this content

Please enable javascript to use this function.

Dear user,
with the links function you'll be able to add links to other resources to this content.
However, in order to link all your links with your user profile it is required that you
login to the tele-TASK portal to use this functionality.
If you don't have an account yet, you may register for a tele-TASK account here.