News

03.06.2013

openHPI-Kurs "WWW"

Start des openHPI-Kurses "Einführung in die Web-Technologien" (in deutscher Sprache) bei openHPI. Anmelden können Sie sich hier.

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]

all news ...

Statistics

userclicks	~31 Mio.
lecture	4440
activelecturer	1665
series	357

Komplexitätstheorie (SS 2012)

Nicht genügend Bewertungen

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:	11.04.2012
Sprache:	de
Dauer:	00:37:42

Einführung und Inhalt

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	12.04.2012
Sprache:	de
Dauer:	01:38:17

Probleme und Algorithmen

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	19.04.2012
Sprache:	de
Dauer:	01:39:11

Turing Maschinen

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	24.04.2012
Sprache:	de
Dauer:	01:00:26

Lineares Beschleunigen

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	02.05.2012
Sprache:	de
Dauer:	01:19:03

Raumkomplexität und Platzsparen

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	03.05.2012
Sprache:	de
Dauer:	01:30:25

Nichtdeterministische Turing Maschinen

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	09.05.2012
Sprache:	de
Dauer:	00:48:16

Komplexitätsklassen

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	10.05.2012
Sprache:	de
Dauer:	00:42:20

Hierarchie-Theoreme

Prof. Dr. Christoph Meinel


Vorlesung abspielen
• Zeit-Hierarchie-Theorem	00:13:28
• Beweis durch Diagonalisierung	00:25:57
• Raum-Hierarchie-Theorem	00:02:55

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	16.05.2012
Sprache:	de
Dauer:	01:00:00

Erreichbarkeitsmethode 1/2

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	24.05.2012
Sprache:	de
Dauer:	01:07:26

Erreichbarkeitsmethode 2/2

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	30.05.2012
Sprache:	de
Dauer:	01:06:23

Reduktion und Vollständigkeit 1/3

Prof. Dr. Christoph Meinel


Vorlesung abspielen
• Einführung	00:11:43
• Grundidee der Reduktion	00:15:14
• Hamilton Path < SAT	00:19:49
• Beweis	00:19:37

Nicht genügend Bewertungen

Bewertung nach Login möglich

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

Reduktion und Vollständigkeit 2/3

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	06.06.2012
Sprache:	de
Dauer:	01:15:30

Reduktion und Vollständigkeit 3/3

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	07.06.2012
Sprache:	de
Dauer:	00:35:25

NP-Vollständigkeit

Prof. Dr. Christoph Meinel


Vorlesung abspielen
• Erinnerung	00:11:45
• Theorem nach Cook	00:09:07
• Annahme	00:14:33

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	13.06.2012
Sprache:	de
Dauer:	00:32:50

Weitere Charakterisierungen von NP

Prof. Dr. Christoph Meinel


Vorlesung abspielen
• Polynomial entscheidbare Relation	00:10:07
• Charakterisierung von NP mittels Relationen	00:16:54
• Polynomiale Zeugnisse	00:05:49

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	14.06.2012
Sprache:	de
Dauer:	01:02:48

Weitere NP-vollständige Probleme 1/4

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	20.06.2012
Sprache:	de
Dauer:	01:09:51

Weitere NP-vollständige Probleme 2/4

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	21.06.2012
Sprache:	de
Dauer:	01:13:06

Weitere NP-vollständige Probleme 3/4

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	27.06.2012
Sprache:	de
Dauer:	01:26:03

Weitere NP-vollständige Probleme 4/4

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

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

NP und coNP

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	04.07.2012
Sprache:	de
Dauer:	01:10:39

Randomisierte Berechnungen 1/2

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	05.07.2012
Sprache:	de
Dauer:	00:51:49

Randomisierte Berechnungen 2/2

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	10.07.2012
Sprache:	de
Dauer:	01:00:07

Polynomialzeithirarchie 1/2

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	10.07.2012
Sprache:	de
Dauer:	00:58:27

Polynomialzeithirarchie 2/2

Prof. Dr. Christoph Meinel


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

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	11.07.2012
Sprache:	de
Dauer:	01:02:22

Approximation

Prof. Dr. Christoph Meinel


Vorlesung abspielen
• 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
• Polynomiale Approximationsschemata	00:13:18

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	12.07.2012
Sprache:	de
Dauer:	01:23:39

Polynomiale Schaltkreise

Prof. Dr. Christoph Meinel


Vorlesung abspielen
• Einführung	00:04:55
• Schaltkreise als Berechnungsmodell	00:05:51
• Schaltkreiskomplexität	00:10:20
• Typische Schaltkreisgröße	00:09:32
• Polynomiale Schaltkreisverbindungen	00:24:54
• Polynomiale uniforme Schaltkreisfamilien	00:11:24
• Polynomiale Schaltkreise für BPP	00:16:43

Nicht genügend Bewertungen

Bewertung nach Login möglich

Datum:	12.07.2012
Sprache:	de
Dauer:	00:50:06

P versus NP

Prof. Dr. Christoph Meinel


Vorlesung abspielen
• Einführung	00:03:48
• Graph Isomorphie	00:04:52
• Landkarte von NP	00:26:45
• NP-vollständige unäre Sprache	00:06:26
• Abschließende Bemerkungen	00:08:15

Tags added to this content

No tags have been added to this content so far.

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.