News

08.04.2013

openHPI-Kurs SQL

Start des Kurses "Datenmanagement mit SQL" auf openHPI. Einschreiben in den Kurs können Sie sich noch jederzeit unter der Adresse ... [more]

05.03.2013

tele-TASK auf der CeBIT 2013

Auch dieses Jahr wird das Projekt tele-TASK wieder auf der CeBIT vertreten sein. Ihr findet uns am Stand des Hasso-Plattner-Instituts ... [more]

04.02.2013

Manuscript in Gruppen

Im Portal ist es möglich, eigene digitale Mitschriften anzufertigen, während man live oder on demand Vorlesungsvideos schaut. Die neue Funktionalität ... [more]

all news ...

Statistics

userclicks	~31 Mio.
lecture	4427
activelecturer	1664
series	357

Komplexitätstheorie (SS 2008)

Bewertung nach Login möglich

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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	16.04.2008
Sprache:	de
Dauer:	00:56:26

Erste Einführung

Prof. Dr. Christoph Meinel

Erste Einführung


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	17.04.2008
Sprache:	de
Dauer:	01:13:56

Probleme und Algorithmen

Prof. Dr. Christoph Meinel

Probleme und Algorithmen


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	23.04.2008
Sprache:	de
Dauer:	01:28:50

Turing Maschinen

Prof. Dr. Christoph Meinel

Turing Maschinen


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	24.04.2008
Sprache:	de
Dauer:	00:44:07

Lineares Beschleunigen

Prof. Dr. Christoph Meinel

Lineares Beschleunigen


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	30.04.2008
Sprache:	de
Dauer:	01:00:42

Raumkomplexität und Platzsparen

Prof. Dr. Christoph Meinel

Raumkomplexität und Platzsparen


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	07.05.2008
Sprache:	de
Dauer:	01:30:59

Nichtdeterministische Turing Maschinen

Prof. Dr. Christoph Meinel

Nichtdeterministische Turing Maschinen


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	08.05.2008
Sprache:	de
Dauer:	00:54:23

Komplexitätsklassen

Prof. Dr. Christoph Meinel

Komplexitätsklassen


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	14.05.2008
Sprache:	de
Dauer:	00:44:39

Hierarchie-Theoreme

Prof. Dr. Christoph Meinel

Hierarchie-Theoreme


Vorlesung abspielen
• Zeit-Hierarchie-Theorem 1-5	00:20:13
• Zeit-Hierarchie-Theorem 6-10	00:21:17
• Raum-Hierarchie-Theorem	00:03:09

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	15.05.2008
Sprache:	de
Dauer:	01:05:49

Erreichbarkeitsmethode 1/2

Prof. Dr. Christoph Meinel

Erreichbarkeitsmethode 1/2


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	21.05.2008
Sprache:	de
Dauer:	00:45:21

Erreichbarkeitsmethode 2/2

Prof. Dr. Christoph Meinel

Erreichbarkeitsmethode 2/2


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	22.05.2008
Sprache:	de
Dauer:	00:54:06

Reduktion und Vollständigkeit 1/3

Prof. Dr. Christoph Meinel

Reduktion und Vollständigkeit 1/3


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	28.05.2008
Sprache:	de
Dauer:	01:00:29

Reduktion und Vollständigkeit 2/3

Prof. Dr. Christoph Meinel

Reduktion und Vollständigkeit 2/3


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	29.05.2008
Sprache:	de
Dauer:	01:05:20

Reduktion und Vollständigkeit 3/3

Prof. Dr. Christoph Meinel

Reduktion und Vollständigkeit 3/3


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	11.06.2008
Sprache:	de
Dauer:	00:36:46

NP-Vollständigkeit

Prof. Dr. Christoph Meinel

NP-Vollständigkeit


Vorlesung abspielen
• Erinnerung	00:14:29
• Cook's Theorem 1 bis 3	00:09:21
• Cook's Theorem 4 bis 6	00:12:56

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	12.06.2008
Sprache:	de
Dauer:	00:27:22

Weitere Characterisierungen von NP

Prof. Dr. Christoph Meinel

Weitere Characterisierungen von NP


Vorlesung abspielen
• Überleitung	00:01:13
• Polynomial entscheidbare Relation	00:04:33
• Charakterisierung von NP mittels Relationen	00:14:20
• Polynomiale Zeugnisse	00:07:16

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	18.06.2008
Sprache:	de
Dauer:	00:57:58

Weitere NP-vollständige Probleme 1/4

Prof. Dr. Christoph Meinel

Weitere NP-vollständige Probleme 1/4


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	19.06.2008
Sprache:	de
Dauer:	00:57:13

Weitere NP-vollständige Probleme 2/4

Prof. Dr. Christoph Meinel

Weitere NP-vollständige Probleme 2/4


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	25.06.2008
Sprache:	de
Dauer:	01:09:41

Weitere NP-vollständige Probleme 3/4

Prof. Dr. Christoph Meinel

Weitere NP-vollständige Probleme 3/4


Vorlesung abspielen
• Erinnerung	00:07:45
• Wege-Probleme	00:12:33
• Färbungsprobleme	00:17:14
• Matching	00:16:34
• Matching	00:15:35

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	26.06.2008
Sprache:	de
Dauer:	01:12:17

Weitere NP-vollständige Probleme 4/4

Prof. Dr. Christoph Meinel

Weitere NP-vollständige Probleme 4/4


Vorlesung abspielen
• Erinnerung	00:08:52
• Set-Cover	00:09:51
• Integer Programming	00:16:38
• Knapsack	00:17:24
• Bin-Packing	00:19:33

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	03.07.2008
Sprache:	de
Dauer:	01:00:28

NP und co-NP

Prof. Dr. Christoph Meinel

NP und co-NP


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	09.07.2008
Sprache:	de
Dauer:	01:11:19

Randomisierte Berechnungen 1/2

Prof. Dr. Christoph Meinel

Randomisierte Berechnungen 1/2


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	10.07.2008
Sprache:	de
Dauer:	00:49:27

Randomisierte Berechnungen 2/2

Prof. Dr. Christoph Meinel

Randomisierte Berechnungen 2/2


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	16.07.2008
Sprache:	de
Dauer:	00:59:19

Polynomialzeithierarchie 1/2

Prof. Dr. Christoph Meinel

Polynomialzeithierarchie 1/2


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	17.07.2008
Sprache:	de
Dauer:	00:54:16

Polynomialzeithierarchie 2/2

Prof. Dr. Christoph Meinel

Polynomialzeithierarchie 2/2


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	30.07.2008
Sprache:	de
Dauer:	00:54:37

Approximation

Prof. Dr. Christoph Meinel

Approximation


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	01.08.2008
Sprache:	de
Dauer:	01:28:01

Polynomiale Schaltkreise

Prof. Dr. Christoph Meinel

Polynomiale Schaltkreise


Vorlesung abspielen
• 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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	05.08.2008
Sprache:	de
Dauer:	00:49:04

P versus NP

Prof. Dr. Christoph Meinel

P versus NP


Vorlesung abspielen
• 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

Playlists

Vorbereitung für die Vorlesung Komplexitätstheorie SS2010

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.