News

03.06.2013

openHPI course "WWW"

Start of the openHPI course "Introduction to Web Technologies" (in German) on openHPI. You can enroll here.
08.04.2013

openHPI course "SQL"

Start of the openHPI course "Data Management with SQL" (in German) on openHPI. You can still enroll in the course ... [more]
05.03.2013

tele-TASK at CeBIT 2013

Also this year the project tele-TASK will be at CeBIT. You can find us at the booth of Hasso Plattner ... [more]
all news ...

Statistics

userclicks ~29 Mio.
lecture 4505
activelecturer 1692
series 358

Lectures & Courses

Lecture-Feed of Series: Komplexitätstheorie (SS 2008) Feed of Series: Komplexitätstheorie (SS 2008)

Komplexitätstheorie (SS 2008)

Image of
You can rate here if you log in!

Prof. Dr. Christoph Meinel

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

Erste Einführung
Not enough ratings.
You can rate here if you log in!
Date: 16.04.2008
Lang.: de
Dur.: 00:56:26

Erste Einführung

Prof. Dr. Christoph Meinel

Erste Einführung
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

Probleme und Algorithmen
Not enough ratings.
You can rate here if you log in!
Date: 17.04.2008
Lang.: de
Dur.: 01:13:56

Probleme und Algorithmen

Prof. Dr. Christoph Meinel

Probleme und Algorithmen
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
Turing Maschinen
Not enough ratings.
You can rate here if you log in!
Date: 23.04.2008
Lang.: de
Dur.: 01:28:50

Turing Maschinen

Prof. Dr. Christoph Meinel

Turing Maschinen
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
Lineares Beschleunigen
Not enough ratings.
You can rate here if you log in!
Date: 24.04.2008
Lang.: de
Dur.: 00:44:07

Lineares Beschleunigen

Prof. Dr. Christoph Meinel

Lineares Beschleunigen
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
Raumkomplexität und Platzsparen
Not enough ratings.
You can rate here if you log in!
Date: 30.04.2008
Lang.: de
Dur.: 01:00:42

Raumkomplexität und Platzsparen

Prof. Dr. Christoph Meinel

Raumkomplexität und Platzsparen
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
Nichtdeterministische Turing Maschinen
Not enough ratings.
You can rate here if you log in!
Date: 07.05.2008
Lang.: de
Dur.: 01:30:59

Nichtdeterministische Turing Maschinen

Prof. Dr. Christoph Meinel

Nichtdeterministische Turing Maschinen
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
Komplexitätsklassen
Not enough ratings.
You can rate here if you log in!
Date: 08.05.2008
Lang.: de
Dur.: 00:54:23

Komplexitätsklassen

Prof. Dr. Christoph Meinel

Komplexitätsklassen
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
Hierarchie-Theoreme
Not enough ratings.
You can rate here if you log in!
Date: 14.05.2008
Lang.: de
Dur.: 00:44:39

Hierarchie-Theoreme

Prof. Dr. Christoph Meinel

Hierarchie-Theoreme
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
Erreichbarkeitsmethode 1/2
Not enough ratings.
You can rate here if you log in!
Date: 15.05.2008
Lang.: de
Dur.: 01:05:49

Erreichbarkeitsmethode 1/2

Prof. Dr. Christoph Meinel

Erreichbarkeitsmethode 1/2
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
Erreichbarkeitsmethode 2/2
Not enough ratings.
You can rate here if you log in!
Date: 21.05.2008
Lang.: de
Dur.: 00:45:21

Erreichbarkeitsmethode 2/2

Prof. Dr. Christoph Meinel

Erreichbarkeitsmethode 2/2
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
Reduktion und Vollständigkeit 1/3
Not enough ratings.
You can rate here if you log in!
Date: 22.05.2008
Lang.: de
Dur.: 00:54:06

Reduktion und Vollständigkeit 1/3

Prof. Dr. Christoph Meinel

Reduktion und Vollständigkeit 1/3
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
Reduktion und Vollständigkeit 2/3
Not enough ratings.
You can rate here if you log in!
Date: 28.05.2008
Lang.: de
Dur.: 01:00:29

Reduktion und Vollständigkeit 2/3

Prof. Dr. Christoph Meinel

Reduktion und Vollständigkeit 2/3
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
Reduktion und Vollständigkeit 3/3
Not enough ratings.
You can rate here if you log in!
Date: 29.05.2008
Lang.: de
Dur.: 01:05:20

Reduktion und Vollständigkeit 3/3

Prof. Dr. Christoph Meinel

Reduktion und Vollständigkeit 3/3
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

NP-Vollständigkeit
Not enough ratings.
You can rate here if you log in!
Date: 11.06.2008
Lang.: de
Dur.: 00:36:46

NP-Vollständigkeit

Prof. Dr. Christoph Meinel

NP-Vollständigkeit
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
Weitere Characterisierungen von NP
Not enough ratings.
You can rate here if you log in!
Date: 12.06.2008
Lang.: de
Dur.: 00:27:22

Weitere Characterisierungen von NP

Prof. Dr. Christoph Meinel

Weitere Characterisierungen von NP
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
Weitere NP-vollständige Probleme 1/4
Not enough ratings.
You can rate here if you log in!
Date: 18.06.2008
Lang.: de
Dur.: 00:57:58

Weitere NP-vollständige Probleme 1/4

Prof. Dr. Christoph Meinel

Weitere NP-vollständige Probleme 1/4
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
Weitere NP-vollständige Probleme 2/4
Not enough ratings.
You can rate here if you log in!
Date: 19.06.2008
Lang.: de
Dur.: 00:57:13

Weitere NP-vollständige Probleme 2/4

Prof. Dr. Christoph Meinel

Weitere NP-vollständige Probleme 2/4
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
Weitere NP-vollständige Probleme 3/4
Not enough ratings.
You can rate here if you log in!
Date: 25.06.2008
Lang.: de
Dur.: 01:09:41

Weitere NP-vollständige Probleme 3/4

Prof. Dr. Christoph Meinel

Weitere NP-vollständige Probleme 3/4
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
Weitere NP-vollständige Probleme 4/4
Not enough ratings.
You can rate here if you log in!
Date: 26.06.2008
Lang.: de
Dur.: 01:12:17

Weitere NP-vollständige Probleme 4/4

Prof. Dr. Christoph Meinel

Weitere NP-vollständige Probleme 4/4
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
NP and co-NP
Not enough ratings.
You can rate here if you log in!
Date: 03.07.2008
Lang.: de
Dur.: 01:00:28

NP and co-NP

Prof. Dr. Christoph Meinel

NP and co-NP
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
Randomisierte Berechnungen 1/2
Not enough ratings.
You can rate here if you log in!
Date: 09.07.2008
Lang.: de
Dur.: 01:11:19

Randomisierte Berechnungen 1/2

Prof. Dr. Christoph Meinel

Randomisierte Berechnungen 1/2
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
Randomisierte Berechnungen 2/2
Not enough ratings.
You can rate here if you log in!
Date: 10.07.2008
Lang.: de
Dur.: 00:49:27

Randomisierte Berechnungen 2/2

Prof. Dr. Christoph Meinel

Randomisierte Berechnungen 2/2
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
Polynomialzeithierarchie 1/2
Not enough ratings.
You can rate here if you log in!
Date: 16.07.2008
Lang.: de
Dur.: 00:59:19

Polynomialzeithierarchie 1/2

Prof. Dr. Christoph Meinel

Polynomialzeithierarchie 1/2
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
Polynomialzeithierarchie 2/2
Not enough ratings.
You can rate here if you log in!
Date: 17.07.2008
Lang.: de
Dur.: 00:54:16

Polynomialzeithierarchie 2/2

Prof. Dr. Christoph Meinel

Polynomialzeithierarchie 2/2
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
Approximation
Not enough ratings.
You can rate here if you log in!
Date: 30.07.2008
Lang.: de
Dur.: 00:54:37

Approximation

Prof. Dr. Christoph Meinel

Approximation
Play full lecture
• Einführung 00:07:25
• e-Approximation 00:13:13
• Maximum Satisfiability 00:12:39
• Traveling Salesman Problem 00:08:57
• Knapsack 00:01:50
• Polynomiale Approximationsschemata 00:10:33
Polynomiale Schaltkreise
Not enough ratings.
You can rate here if you log in!
Date: 01.08.2008
Lang.: de
Dur.: 01:28:01

Polynomiale Schaltkreise

Prof. Dr. Christoph Meinel

Polynomiale Schaltkreise
Play full lecture
• Einführung 00:05:38
• Schaltkreise als Berechnungsmodell 00:20:54
• Typische Schaltkreisgröße 00:10:08
• Polynomiale Schaltkreisfamilien 00:24:33
• Uniforme Schaltkreisfamilien 00:10:57
• Polynomiale Schaltkreise für BPP 00:15:51
P versus NP
Not enough ratings.
You can rate here if you log in!
Date: 05.08.2008
Lang.: de
Dur.: 00:49:04

P versus NP

Prof. Dr. Christoph Meinel

P versus NP
Play full lecture
• Einführung 00:05:32
• Graph Isomorphie 00:04:05
• Landkarte von NP 00:22:42
• NP-vollständige unäre Sprachen 00:01:38
• Dünnbesetzte Sprachen 00:04:49
• Abschließende Bemerkungen 00:10:18
Tags added to this content

Theoretische Informatik (1); Turingmaschinen (1);

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.