Hasso-Plattner-Institut Design IT. Create Knowledge.

News

11.09.2017

New tele-TASK Web Portal

At beta.tele-task.de you can already the future web portal of tele-TASK before being officially launched. We are thankful ... [more]
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]

Statistics

userclicks 35 M
lecture 6162
activelecturer 2573
series 505
Lecture-Feed of Series: Komplexitätstheorie (SS 2012) Feed of Series: Komplexitätstheorie (SS 2012)

Komplexitätstheorie (SS 2012)

Image of
Not enough ratings.

Prof. Dr. Christoph Meinel

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

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

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: 11.04.2012
Lang.: de
Dur.: 00:37:42
Play full lecture
• Was ist Komplexitätstheorie 00:25:32
• Hauptaufgabe der Komplexitätstheorie 00:04:50
• Welche Ergebnisse bringt die Komplexitätstheorie? 00:07:20

Konzepte der Komplexitätstheorie

Not enough ratings.
Date: 12.04.2012
Lang.: de
Dur.: 01:38:17
Play full lecture
• Einführung 00:15:09
• Entscheidungsprobleme 00:20:12
• O-Notation 00:19:41
• Polynomialzeit-Algorithmen 00:09:32
• MAX FLOW - Flüsse in Netzwerken 00:16:57
• Reduktionstechniken 00:16:46
Not enough ratings.
Date: 19.04.2012
Lang.: de
Dur.: 01:39:11
Play full lecture
• Einführung 00:16:42
• Turing Maschinen - Grundidee 00:07:39
• K-Band Turing Maschine 00:20:45
• Konfiguration einer k-Band TM 00:16:00
• Arbeitsweise einer k-Band TM 00:13:48
• Zeitkomplexität 00:05:18
• Leistungsvergleich von k-Band und 1-Band Turing Maschinen 00:18:59
Not enough ratings.
Date: 24.04.2012
Lang.: de
Dur.: 01:00:26
Play full lecture
• Wiederholung 00:05:23
• Speedup Theorem 00:07:06
• Beweisidee 00:23:41
• Simulation der Arbeitsschritte von M durch M' 00:20:11
• Definition der Komplexitätsklasse P 00:04:05
Not enough ratings.
Date: 02.05.2012
Lang.: de
Dur.: 01:19:03
Play full lecture
• Einführung 00:06:47
• Begriffsbestimmung 00:14:53
• Beispiel 00:12:47
• Turingmaschinen mit Ein- und Asgabe 00:19:00
• Rauumkomplexität 00:17:17
• Platzsparen 00:08:19
Not enough ratings.
Date: 03.05.2012
Lang.: de
Dur.: 01:30:25
Play full lecture
• Einführung 00:06:46
• NTM - Definition 00:17:57
• Nichtdeterministische Berechnungen 00:19:35
• Rundreiseproblem - TSP (D) 00:18:06
• Probabilistische Turing Maschinen 00:12:26
• Probabilistische Turing Maschinen (3) 00:15:35
Not enough ratings.
Date: 09.05.2012
Lang.: de
Dur.: 00:48:16
Play full lecture
• Einleitung 00:06:02
• Schrankenfunktionen 00:16:01
• Präzise Turing Maschinen 00:08:10
• Wichtige Komplexitätsklassen 00:04:21
• Komplementäre Komplexitätrsklassen 00:13:42
Not enough ratings.
Date: 10.05.2012
Lang.: de
Dur.: 00:42:20
Play full lecture
• Zeit-Hierarchie-Theorem 00:13:28
• Beweis durch Diagonalisierung 00:25:57
• Raum-Hierarchie-Theorem 00:02:55
Not enough ratings.
Date: 16.05.2012
Lang.: de
Dur.: 01:00:00
Play full lecture
• Einführung 00:06:31
• NTIME vs. SPACE 00:09:02
• NSPACE vs. TIME 00:18:59
• Zwischenbilanz 00:06:07
• Satz von Savitch 00:14:47
• Beweisen 00:11:22
Not enough ratings.
Date: 24.05.2012
Lang.: de
Dur.: 01:07:26
Play full lecture
• Wiederholung 00:13:28
• Satz von Immerman-Szelepcsenyi 00:13:08
• Beweis des Satzes 00:23:12
• Analyse des Satzes 00:07:55
• NSPACE vs. coNSPACE 00:09:43
Not enough ratings.
Date: 30.05.2012
Lang.: de
Dur.: 01:06:23
Play full lecture
• Einführung 00:11:43
• Grundidee der Reduktion 00:15:14
• Hamilton Path < SAT 00:19:49
• Beweis 00:19:37
Not enough ratings.
Date: 31.05.2012
Lang.: de
Dur.: 00:54:06
Play full lecture
• Grundidee der Reduktion 00:04:21
• Longspace-Reduktion 00:03:07
• Reachability < Circuit Value 00:19:57
• Reduktion durch Verallgemeinerung 00:15:49
• Kompositionen von Reduktionen 00:10:52
Not enough ratings.
Date: 06.06.2012
Lang.: de
Dur.: 01:15:30
Play full lecture
• Einführung 00:03:08
• K-Vollständigkeit 00:13:54
• Berechnungstabellen-Methode 00:19:42
• P-Vollständigkeit von CIRQUIT VALUE 00:27:24
• Behauptung 00:11:22

Die Klassen P und NP

Not enough ratings.
Date: 07.06.2012
Lang.: de
Dur.: 00:35:25
Play full lecture
• Erinnerung 00:11:45
• Theorem nach Cook 00:09:07
• Annahme 00:14:33
Not enough ratings.
Date: 13.06.2012
Lang.: de
Dur.: 00:32:50
Play full lecture
• Polynomial entscheidbare Relation 00:10:07
• Charakterisierung von NP mittels Relationen 00:16:54
• Polynomiale Zeugnisse 00:05:49
Not enough ratings.
Date: 14.06.2012
Lang.: de
Dur.: 01:02:48
Play full lecture
• Erinnerung 00:10:40
• NP-vollständige SAT-Varianten 00:12:57
• 2-SAT gehört zu P 00:15:07
• Beweis 00:07:37
• MAX-2-SAT ist NP-vollständig 00:16:27
Not enough ratings.
Date: 20.06.2012
Lang.: de
Dur.: 01:09:51
Play full lecture
• Einführung 00:06:15
• INDEPENDENT SET Problem 00:25:40
• CLIQUE und NODE COVER 00:06:23
• Schnittprobleme 00:11:25
• Behauptung 00:10:19
• MIN CUT 00:09:49
Not enough ratings.
Date: 21.06.2012
Lang.: de
Dur.: 01:13:06
Play full lecture
• Erinnerung 00:07:01
• Wege-Probleme 00:10:37
• Färbungsprobleme 00:17:33
• Matching 00:09:59
• Beispiel 00:17:57
• Behauptung 00:09:59
Not enough ratings.
Date: 27.06.2012
Lang.: de
Dur.: 01:26:03
Play full lecture
• Erinnerung 00:12:38
• SET COVER 00:10:29
• INTEGER PROGRAMMING 00:18:02
• KNAPSACK 00:21:44
• BIN PACKING 00:14:43
• Behauptung 00:08:27
Not enough ratings.
Date: 28.06.2012
Lang.: de
Dur.: 01:12:17
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: 04.07.2012
Lang.: de
Dur.: 01:10:39
Play full lecture
• Einführung 00:03:47
• Symolische Determinante 00:15:41
• Gaußsche Ellimination 00:11:25
• Abschätzung der Zshl der Nullstellen 00:17:20
• Randomisierter Algorithmus 00:06:56
• Random Walks 00:05:24
• Fermat Test 00:10:06
Not enough ratings.
Date: 05.07.2012
Lang.: de
Dur.: 00:51:49
Play full lecture
• Wiederholung 00:02:37
• Fehlersituation 00:03:41
• Probabilistische Turing Maschinen 00:09:55
• Die Klasse PP 00:12:07
• Die Klasse BPP 00:07:37
• Die Klasse RP 00:08:31
• Die Klasse 2 PP 00:07:21
Not enough ratings.
Date: 10.07.2012
Lang.: de
Dur.: 01:00:07
Play full lecture
• Einführung 00:03:54
• Orakel Turing Maschinen 00:07:45
• Einige Relativierungen 00:20:57
• Aufbau der Polynomialzeithirarchie 00:05:23
• Polynomial balancierte Relationen 00:22:08
Not enough ratings.
Date: 10.07.2012
Lang.: de
Dur.: 00:58:27
Play full lecture
• Wiederholung 00:16:52
• Kollabiert Polynomialzeithirarchie 00:11:59
• MINIMUM CIRQUIT 00:05:55
• Vollständige Probleme 00:12:39
• PH und PSPACE 00:11:02
Not enough ratings.
Date: 11.07.2012
Lang.: de
Dur.: 01:02:22
Play full lecture
• Einfürung 00:05:22
• Epsilon-Approximation 00:08:49
• NOTE COVER 00:09:39
• MAXIMUM SATISFIABILITY 00:15:56
• TRAVELING SALESMAN PROBLEM 00:07:36
• KNAPSACK 00:01:42