Theoretische Informatik für Medieninformatiker

3 - Weitere NP-Vollständige Probleme

(00:00:00) >: Organisatorisches

(00:06:50) >: Einleitung

(00:12:02) >: Graphenprobleme

(01:03:29) >: Das Problem des Handlungsreisenden

(01:10:29) >: Das Problem Subset Sum

Datum: 16.08.2013

Dozent(in): Dr. Jan Johannsen

NP-Vollständige Probleme

(00:00:00) >: Klausurrelevante Informationen

(00:06:27) >: Einleitung

(00:11:36) >: Aussagenlogik

(00:23:10) >: NP - Vollständigkeit von SAT

(00:30:49) >: Spezialfälle von SAT

Datum: 02.07.2013

Dozent(in): Dr. Jan Johannsen

3 - Die Klassen P und NP

(00:00:00) >: Einleitung

(00:07:38) >: Die Klasse P

(00:25:33) >: Die Klasse NP

Datum: 25.06.2013

Dozent(in): Dr. Jan Johannsen

2 - Unentscheidbare Probleme

(00:00:00) >: Einleitung

(00:02:55) >: Postsche Korrespondenzproblem

(00:52:24) >: Probleme über kontextfreie Grammatiken

Datum: 18.06.2013

Dozent(in): Dr. Jan Johannsen

2 - Unentscheidbarkeit

(00:00:00) >: Einleitung

(00:05:08) >: Codierung von Turing-Maschinen

(00:30:17) >: Das Halteproblem

(00:43:14) >: Reduktion

Datum: 11.06.2013

Dozent(in): Dr. Jan Johannsen

2 - Turing-Maschinen

(00:00:00) >: Einleitung

(00:03:02) >: Definition von Turing Maschinen

(01:21:01) >: Churchche These

Datum: 04.06.2013

Dozent(in): Dr. Jan Johannsen

1 - Pushdown-Automaten

(00:00:00) >: Information zu Klausur und Übungsblättern

(00:08:19) >: Parse-Bäume und Linksableitungen

(00:27:38) >: Definition von Pushdown-Automaten

(01:00:40) >: Äquivalenz von kontextfreien Grammatiken und Pushdown-Automaten

Datum: 28.05.2013

Dozent(in): Dr. Jan Johannsen

1 - Kontextfreie Sprachen

(00:09:18) >: Einleitung

(00:11:24) >: Grammatiken

(00:34:47) >: Chomsky-Hierarchie

(00:56:05) >: Kontextfreie Sprachen

Datum: 14.05.2013

Dozent(in): Dr. Jan Johannsen

1 - Pumping Lemma

(00:00:00) >: Einleitung

(00:03:17) >: Das Pumping Lemma

(00:15:50) >: Anwendungen

(00:32:55) >: Abschlusseigenschaften regulärer Sprachen

Datum: 07.05.2013

Dozent(in): Dr. Jan Johannsen

1 - Reguläre Ausdrücke

(00:02:31) >: Einleitung und Übersicht

(00:06:10) >: Operationen auf Sprachen

(00:09:57) >: Kleene'sche Hülle

(00:12:59) >: Reguläre Ausdrücke

(00:39:15) >: Vom regulären Ausdruck zum Automaten

(00:53:38) >: Das Arden'sche Lemma

(00:58:50) >: Regulärer Ausdruck aus NEA

Datum: 30.04.2013

Dozent(in): Dr. Jan Johannsen

1 - Äquivalenz der Automatenmodelle

(00:00:00) >: Information zur Klausur und Übungsblattabgabe

(00:02:49) >: Übersicht

(00:05:10) >: Determinisierung

(00:45:13) >: Automaten mit epsilon-Übergängen

Datum: 23.04.2013

Dozent(in): Dr. Jan Johannsen

1 - Endliche Automaten

(00:00:00) >: Begrüßung und Obligatorisches

(00:16:00) >: Einleitung

(00:20:55) >: Literatur

(00:25:00) >: Übersicht zu Automaten und Formale Sprachen

(00:27:29) >: Wörter und Sprachen

(00:28:00) >: Deterministische endliche Automaten

(01:06:45) >: Nichtdeterministische endliche Automaten

Datum: 16.04.2013

Dozent(in): Dr. Jan Johannsen

RSS-Feed abonnieren: