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 ~29 Mio.
lecture 4514
activelecturer 1694
series 358

Lectures & Courses

Lecture-Feed of Series: Theoretische Informatik II (SS 2007) Feed of Series: Theoretische Informatik II (SS 2007)

Theoretische Informatik II (SS 2007)

Image of
Nicht genügend Bewertungen
Bewertung nach Login möglich

Prof. Dr. Christoph Kreitz

Die Theoretische Informatik beschäftigt sich mit den grundlegenden Fragestellungen der Informatik. Hierzu werden Computer- und Automatenmodelle idealisiert und mathematisch untersucht.

Die Automatentheorie und die Theorie der formalen Sprachen (Thema des ersten Semesters) ist grundlegend für die Entwicklung von Programmiersprachen und Compilern. Sie untersucht, mit welchen Techniken welche Arten von Sprachen effizient analysiert werden können.

Die Berechenbarkeitstheorie befasst sich mit den prinzipiellen Grenzen des Berechenbaren und der Relation zwischen verschiedenen Computer- und Programmiermodellen.

Die Komplexitätstheorie untersucht Effizienz von Algorithmen im Hinblick auf Platz- und Zeitbedarf und kümmert sich insbesondere um die Frage, wie effizient man bestimmte Probleme lösen kann.

Die Veranstaltung ist prinzipiell für Studenten des ersten Semesters geeignet, setzt jedoch ein gutes Verständnis mathematischer Konzepte und Methoden voraus. Für die meisten Studenten ist es daher sinnvoller, zunächst an den entsprechenden Mathematikveranstaltungen teilzunehmen und die theoretische Informatik erst im dritten Semester zu belegen.

Einführung

Semesterüberblick
Nicht genügend Bewertungen
Bewertung nach Login möglich
Datum: 20.04.2007
Sprache: de
Dauer: 01:28:13

Semesterüberblick

Prof. Dr. Christoph Kreitz

Semesterüberblick
Vorlesung abspielen
• Überblick - Themen der TI I 00:01:24
• Themen der TI II 00:04:06
• Theorie der Berechenbarkeit 00:24:59
• Turing Berechenbarkeit 00:12:53
• Rückblick Turingmaschinen 00:00:53
• Zeit und Platzbedarf von Turingmaschinen 00:23:17
• Die berechnete Funktion einer Turingmaschine 00:06:24
• Berechnung mit Turingmaschinen am Beispiel 00:06:43

Theorie der Berechenbarkeit

Theorie der Berechenbarkeit
Nicht genügend Bewertungen
Bewertung nach Login möglich
Datum: 27.04.2007
Sprache: de
Dauer: 01:15:34

Theorie der Berechenbarkeit

Jens Otten

Theorie der Berechenbarkeit
Vorlesung abspielen
• Turing-Berechenbarkeit 00:24:14
• Akzeptieren vs. Berechnen Beweisideen 00:17:04
• Rekursive Funktionen 00:28:31
• Programmierung mit primitiver Rekursion 00:19:47
Tutorium
Nicht genügend Bewertungen
Bewertung nach Login möglich
Datum: 02.05.2007
Sprache: de
Dauer: 01:07:12

Tutorium

Prof. Dr. Christoph Kreitz

Tutorium
Vorlesung abspielen
• Berechenbarkeit ohne Maschinenmodell 00:06:11
• Berechenbare Funktionen 00:12:55
• Addition von 2 00:48:42
Primitiv-rekursive Funktionen
Nicht genügend Bewertungen
Bewertung nach Login möglich
Datum: 04.05.2007
Sprache: de
Dauer: 01:27:57

Primitiv-rekursive Funktionen

Prof. Dr. Christoph Kreitz

Primitiv-rekursive Funktionen
Vorlesung abspielen
• Primitive und -rekursive Funktionen 00:05:51
• Analyse -Rekursiver Funktionen 00:10:27
• Entwurf Primitiv-rekursiver Funktionen 00:17:59
• Primitiv-rekursive Programmiertechniken 00:15:39
• Weitere Primitiv-rekursive Funktionen 00:01:45
• Berechnungen auf Zahlenpaaren und -listen 00:12:16
• Die Ackermann-Funktion 00:08:09
• Warum kann A nicht primitiv-rekursive sein? 00:03:25
• Warum ist die Ackermannfunktion berechenbar? 00:04:47
• Ausdruckskraft rekursive Funktionen 00:04:58
• Konsequenzen der Äquivalenzbeweise 00:02:28
• Rekursive Funktion im Rückblick 00:05:42
Funktionale und logische Programme
Nicht genügend Bewertungen
Bewertung nach Login möglich
Datum: 11.05.2007
Sprache: de
Dauer: 01:23:44

Funktionale und logische Programme

Prof. Dr. Christoph Kreitz

Funktionale und logische Programme
Vorlesung abspielen
• Der Lambda-Kalkuel 00:17:02
• Lambda-Kalkuel: Berechnen durch Auswertung 00:18:55
• Vom Lambda-Kalkuel zu echten Programme 00:18:26
• Programmierung im Lambda-Kalkuel 00:14:30
• Der Lambda-Kalkuel ist Turing-Maechtig 00:06:10
• Arithmetische Repraesentierbarkeit 00:14:25
Berechenbarkeitstheorie
Nicht genügend Bewertungen
Bewertung nach Login möglich
Datum: 18.05.2007
Sprache: de
Dauer: 01:21:37

Berechenbarkeitstheorie

Jens Otten

Berechenbarkeitstheorie
Vorlesung abspielen
• Die Arithmetische Theorie Q 00:12:35
• Die Churchsche These 00:04:11
• Elementare Berechenbarkeitstheorie 00:17:06
• Kernaxiome der Berechenbarkeit 00:04:33
• Nummerierung von Turingmaschinen 00:06:45
• Nummerierung Berechenbarer Funktionen 00:05:02
• UTM-Theorem 00:05:31
• SMN-Theorem 00:07:00
• Konsequenzen von UTM und SMN Theorem 00:22:36
Rekursion. Aufzaehlbarkeit, etc.
Nicht genügend Bewertungen
Bewertung nach Login möglich
Datum: 25.05.2007
Sprache: de
Dauer: 01:26:12

Rekursion. Aufzaehlbarkeit, etc.

Prof. Dr. Christoph Kreitz

Rekursion. Aufzaehlbarkeit, etc.
Vorlesung abspielen
• Rekursions- und Selbstreproduktionstheorem 00:10:12
• Berechenbarkeitskonzepte 00:04:14
• Aufzaehlbarkeit 00:05:50
• Beweis der Aequivalenz durch Ringschluss 00:15:00
• Wichtige entscheidbare und aufzaehlbare Mengen 00:04:12
• Aufzaehlbarkeit vs. Entscheidbarkeit 00:15:15
• Abschlusseigenschaften 00:11:11
• Unloesbarkeit
Nicht berechenbare Probleme
Nicht genügend Bewertungen
Bewertung nach Login möglich
Datum: 01.06.2007
Sprache: de
Dauer: 01:25:49

Nicht berechenbare Probleme

Prof. Dr. Christoph Kreitz

Nicht berechenbare Probleme
Vorlesung abspielen
• Das Halteproblem ist unentscheidbar 00:13:48
• Diagonalisierung 00:08:19
• Wachstums- und Monotonieargumente 00:02:42
• Das Busy-Beaver Problem 00:17:25
• Beweisfuehrung durch Reduktion 00:15:23
• Beispiele von Problemreduktion 00:17:28
• Der Satz von Rice 00:16:18
Das Post'sche Korrespondenzproblem, etc.
Nicht genügend Bewertungen
Bewertung nach Login möglich
Datum: 08.06.2007
Sprache: de
Dauer: 01:26:19

Das Post'sche Korrespondenzproblem, etc.

Prof. Dr. Christoph Kreitz

Das Post'sche Korrespondenzproblem, etc.
Vorlesung abspielen
• Das Post'sche Korrespondenzproblem 00:20:02
• Unentscheidbarkeit auf Grammatiken 00:15:44
• Rueckblick: Beweistechniken fuer Unloesbarkeit 00:06:32
• Komplexitätstheorie 00:08:27
• Die Mathematik Asymptotischer Vergleiche 00:10:06
• Zeit- und Platzbedarf von Maschinen 00:16:04
• Konkrete Komplexitaetsanalyse 00:14:09

Komplexitaetstheorie

Komplexitaetstheorie
Nicht genügend Bewertungen
Bewertung nach Login möglich
Datum: 15.06.2007
Sprache: de
Dauer: 00:00:00

Komplexitaetstheorie

Prof. Dr. Christoph Kreitz

Komplexitaetstheorie
Vorlesung abspielen
• Sortierverfahren 00:20:02
• Unentscheidbarkeit auf Grammatiken 00:15:44
• Rückblick: Beweistechniken fuer Unlösbarkeit 00:04:13
Das P-NP-Problem
Nicht genügend Bewertungen
Bewertung nach Login möglich
Datum: 22.06.2007
Sprache: de
Dauer: 01:24:19

Das P-NP-Problem

Prof. Dr. Christoph Kreitz

Das P-NP-Problem
Vorlesung abspielen
• Das P-NP - Problem 00:11:00
• Polynomielle Reduktion auf Graphenproblemen 00:11:12
• Reduzierbarkeit: Clique - Vertex Cover 00:17:46
• NP-Vollstaendigkeit 00:16:18
• Das Erfuellbarkeitsproblem 00:09:11
• Der Satz von Cook 00:13:21
• Die Codierung und iher Korrektheit 00:10:04
NP-Begriff
Nicht genügend Bewertungen
Bewertung nach Login möglich
Datum: 27.06.2007
Sprache: de
Dauer: 01:10:03

NP-Begriff

Prof. Dr. Christoph Kreitz

NP-Begriff
Vorlesung abspielen
• NP-Begriff 00:17:51
• Zeitkomplexität 00:12:43
• Reduktion 00:13:19
• NP-Vollständig 00:10:50
• Übungshinweise und Anreize 01:10:14
6.3 NP-vollstaendige Probleme (29.6.2007)
Nicht genügend Bewertungen
Bewertung nach Login möglich
Datum: 29.06.2007
Sprache: de
Dauer: 01:21:49

6.3 NP-vollstaendige Probleme (29.6.2007)

Prof. Dr. Christoph Kreitz

6.3 NP-vollstaendige Probleme (29.6.2007)
Vorlesung abspielen
• Methodik für Nachweis von NP-Vollständigkeit 01:21:49
Hamiltonscher Kreis
Nicht genügend Bewertungen
Bewertung nach Login möglich
Datum: 06.07.2007
Sprache: de
Dauer: 01:24:36

Hamiltonscher Kreis

Prof. Dr. Christoph Kreitz

Hamiltonscher Kreis
Vorlesung abspielen
• Auswertung 01:24:36
PSPACE-Vollstaendigkeit
Nicht genügend Bewertungen
Bewertung nach Login möglich
Datum: 13.07.2007
Sprache: de
Dauer: 01:22:56

PSPACE-Vollstaendigkeit

Prof. Dr. Christoph Kreitz

PSPACE-Vollstaendigkeit
Vorlesung abspielen
• PSPACE-Vollständigkeit 00:15:15
• QBF ist PSPACE-vollständig 00:09:04
• weitere PSPACE-vollständige Probleme 00:03:08
• LOGSPACE: Logarithmischer Platzverbrauch 00:05:10
• wichtige Vertreter weiterer Komplexitätsklassen 00:11:15
• das Platzhierarchie-Theorem 00:09:01
• 6.5 Grenzen überwinden 00:10:30
• nicht jedes NP-Problem ist wirklich schwer 00:14:18
• starke NP-Vollständigkeit 00:12:41
Approximationsalgorithmen
Nicht genügend Bewertungen
Bewertung nach Login möglich
Datum: 20.07.2007
Sprache: de
Dauer: 01:00:27

Approximationsalgorithmen

Prof. Dr. Christoph Kreitz

Approximationsalgorithmen
Vorlesung abspielen
• Approximationsalgorithmen 00:09:04
• Positive Ergebnisse 00:07:16
• Travelling Salesman mit Dreiecksgleichungen 00:10:21
• Negative Ergebnisse 00:05:55
• Probabilistische Algorithmen 00:10:09
• Probabilistische Berechnungsmodelle 00:07:34
• Beispiel Probabilistischer Algorithmen 00:11:32
Rueckblick
Nicht genügend Bewertungen
Bewertung nach Login möglich
Datum: 20.07.2007
Sprache: de
Dauer: 00:26:34

Rueckblick

Prof. Dr. Christoph Kreitz

Rueckblick
Vorlesung abspielen
• Theoretische Informatik im Rückblick 00:00:31
• Berechenbarkeitsmodelle 00:09:20
• Berechenbarkeitstheorie - Losgeloest vom Modell 00:05:33
• Komplexitätstheorie 00:06:24
• Wie loest man Aufgaben effektiv und korrekt? 00:05:44
Tags added to this content

Theoretische Informatik (1); Theoretische Informatik II (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.