show episodes
 
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 ...
 
Loading …
show series
 
19 |0:00:00 Starten0:01:39 Rückblick: Chomsky Typ 30:04:53 Rückblick: Chomsky-3 Verfahren0:22:29 Rückblick: Chomsky-20:35:13 Rückblick: Chomsky-0/10:40:32 Entscheidbarkeit0:47:05 Domino0:53:04 2-PLAYER COOPERATIVE DOMINOESVon Dr. Torsten Ueckerdt
 
18 |0:00:00 Starten0:03:53 Information0:12:40 Entropie0:18:49 (Platzsparende) Codierung0:20:33 Codierungsbäume0:25:54 Präfix-Codes0:28:27 Quellencodierungstheorem0:29:58 Beispiel: Shannon-Fano Codierung0:38:11 Beispiel: Huffman-Codierung0:46:53 Vorbereitendes Lemma0:56:09 Beweis - Induktionsschluss1:05:03 Lauflängenkodierung…
 
17 |0:00:00 Starten0:00:24 Übersicht Chomsky-20:03:13 WDh.: Greibach-Normalform, Kellerautomat0:09:07 Beweis0:47:57 Korollar0:48:46 Exkurs0:50:37 Zwischenfazit zu kontextfreien Grammatiken0:53:05 Unentscheidbare Probleme für kontextfreie Grammatiken0:55:26 Das Post'sche Korrespondenzproblem1:03:51 Eindeutigkeit von kontextfreien Grammatiken1:05:26 …
 
16 |0:00:00 Starten0:01:12 Chomsky Hierarchie0:15:28 Chomsky-0-Grammatiken und DTM's0:28:42 Konstruktion von Grammatiken0:46:58 Sprache der korrekten Klammerausdrücke0:57:09 Chomsky-Normalform1:08:19 Der Cocke-Younger-Kasami AlgorithmusVon Dr. Torsten Ueckerdt
 
15 |0:00:00 Starten0:00:19 Kontextfreie Sprachen, Kontextfreie Grammatiken0:06:01 Pumping-Lemma für kontextfreie Sprachen0:08:05 Ogden's Lemma für kontextfreie Sprachen0:23:12 Satz0:37:41 Nutzlose Variablen0:54:28 Korrolar0:58:14 BeispielgraphVon Prof. Dr. Dorothea Wagner
 
14 |0:00:00 Starten0:00:22 Die Chomsky Hierarchie0:08:09 Typ-2/Kontextfrwiw Grammatiken0:08:51 Typ-2/ Grammatiken: Beispiel 10:09:25 Typ-2/ Grammatiken: Beispiel 20:11:56 Syntacbäume0:13:34 Syntaxbäume Beispiel0:18:27 Links/ Rechtsabteilung, Eindeutigkeit0:20:14 Beispiel0:23:08 Chomsky- Normalform0:30:41 Schritt 10:34:39 Schritt 20:38:44 Schritt 30…
 
12 | 0:00:00 Starten0:02:26 Approximation mit relativer Gütegarantie0:03:38 Beispiel: Greedy-Algorithmus für KNAPSACK0:04:51 Definition0:06:07 Approximierbarkeit von COLOR0:20:05 Approximierbarkeit von TSP0:35:12 Approximationsschemata0:45:02 Ein FPAS für KNAPSACK1:04:10 Ein allgemeineres ResultatVon Prof. Dr. Dorothea Wagner
 
13 | 0:00:00 Starten0:01:15 Grammatiken0:06:22 Bemerkungen0:09:12 Die Chomsky Hierarchie0:19:54 Chomsky-0 Grammatiken und Semientscheidbarkeit0:22:25 Beweis- Beschreibung der Grammatik G0:28:36 Chomsky-3-Grammatiken und reguläre Sprachen0:37:52 Chomsky-1-Grammatiken bzw. kontextsensitive Sprachen0:41:58 Wiederholung: Das Problem CLIQUE0:49:01 Typ-2…
 
11 | 0:00:00 Starten0:00:57 Nichtdeterministische Turingmaschine(n)0:06:41 Die Klassen NP und ANP0:11:10 A-NTMs sind nicht mächtiger als NTMs0:23:31 Polynomiale Transformation0:25:23 Polynomielle Transformation0:29:26 Komplexitätsklassen und Werkzeugkasten0:38:14 2SAT ∈ P0:54:26 NP-Vollständigkeit0:57:35 MAX2SAT1:11:27 Tipps für Reduktion auf Max2C…
 
10 | 0:00:00 Starten0:03:27 Das Problem SUBSET SUM0:04:50 NP-Vollständigkeit von SUBSET SUM0:18:59 Das Problem Partition0:25:38 Das Problem KNAPSACK0:28:21 Beweis: NP-Vollständigkeit von KNAPSACK0:32:43 Auswirkung auf die Frage P=NP0:37:29 Zusammenfassung0:41:47 Die Klassen NPI, co-P und co-NP0:45:07 Vermutete Situation0:50:03 Das TSP-Komplement-Pr…
 
09 | 0:00:00 Starten0:00:39 NP-Vollständigkeit0:02:03 Transitivität der poly. Transformation0:02:31 Korollar0:03:49 Das Problem 3-SAT0:05:37 Beweis: NP-Vollständigkeit von 3-SAT0:20:16 Das Problem 2SAT0:22:09 Das Problem MAX2SAT0:24:18 Das Problem CLIQUE0:27:48 Beweis: NP-Vollständigkeit von CLIQUE0:36:44 Das Problem COLOR0:37:57 Beweis: NP-Vollstä…
 
08 | 0:00:00 Starten0:00:17 Gliederung0:01:30 Turingmaschinen0:19:04 Erweiterung von Turingmaschinen0:19:18 Mehrere Spuren0:23:26 Mehrere Bänder0:25:01 Erweiterte Turingmaschinen0:31:56 Entscheidbarkeit0:32:09 Entscheidbarkeit - Definitionen0:36:34 Entscheidbarkeit - Zusammenhänge0:45:32 Entscheidbarkeit - Überblick0:46:31 Entscheidbarkeit - Komple…
 
07 | 0:00:00 Starten0:00:06 Definitionen zur TM0:01:15 Unentscheidbarkeit der Diagonalsprache0:02:42 Die Universelle Sprache0:09:51 Satz von Rice - Motivation0:17:10 Das Post'sche Korrespondenzproblem0:21:44 Eigenschaften von (semi-)entscheibaren Sprachen0:28:02 Komplexitätstheorie0:32:53 Wie sieht ein Problem aus?0:37:56 Definition: Problem0:39:34…
 
06 | 0:00:00 Starten0:01:54 Formale Definition der Tuting-Maschine0:04:18 Definition zur TM0:07:42 Motation: Konfiguration0:10:03 Beispiel: Konfiguration0:20:09 Definition: berechenbar/ totalrekursiv0:22:30 Beispiel0:30:39 Entscheidbarkeit und Berechenbarkeit0:32:46 Korollar0:34:56 Die Church'sche These0:39:00 Erweiterungen der Turing-Maschine0:44:…
 
05 | 0:00:00 Starten0:00:21 Frage0:04:24 Wiederholung Äquivalenzklassenautomat0:09:44 Definitionen: Rechtsinvarianz und Index0:17:24 Nerode- Relation0:22:12 Satz von Nerode0:25:40 Beweis zu Satz von Nerode: (1)-->(2)0:31:49 Beweis zu Satz von Nerode: (2)-->(3)0:37:57 Beweis zu Satz von Nerode: (3)-->(1)0:46:16 Korollar0:49:09 Minimalitäat des Äquiv…
 
04 | 0:00:00 Starten0:01:20 Pumping-Lemma für reguläre Sprachen0:08:08 Verallgemeintertes PL für reguläre Sprachen0:23:36 Beispiel0:31:37 Äquivalenz0:34:26 Der Äquivalenzklassenautomat0:44:21 Frage0:54:24 Vorgehensweise0:55:57 Beispiel zur VorgehensweiseVon Prof. Dr. Dorothea Wagner
 
03 | 0:00:00 Starten0:00:05 letzte Vorlesung...0:05:42 Entfernen von Epsilon-Übergängen0:16:09 EA-Regularität0:37:53 Beispiel0:52:18 Frage: Was können endliche Automaten nicht?0:55:53 Pumping-Lemma für reguläre Sprachen1:06:31 Bemerkung und BeispieleVon Prof. Dr. Dorothea Wagner
 
02 | 0:00:00 Starten0:00:38 Endliche Automaten und Reguläre Sprachen0:16:02 Nichtdeterministische endliche Automaten0:22:10 Beispiele für NEA's0:27:11 Äquivalenz von NEA's und DEA's0:28:54 Beispiel PotenzmengenkonstruktionVon Dr. Torsten Ueckerdt
 
01 | 0:00:00 Starten0:01:06 Ziel der Vorlesung TGI0:07:08 Wiederholung aus Grundbegriffe der Informatik0:09:11 Wörter0:13:56 Formale Sprachen0:25:28 Reguläre Sprachen0:32:09 Reguläre Ausdrücke0:41:42 Endliche Automaten0:48:57 Kontextfreie GrammatikenVon Prof. Dr. Dorothea Wagner
 
18 | 0:00:00 Starten0:00:07 Fortsetzung Informationstheorie0:01:06 Wiederholung Quellkodierung0:01:46 Kanalkodierung0:02:24 Codierung zum Schutz gegen Übertragungsfehler0:04:17 Paritätscodes - Einfach Binär0:07:27 Kreuzsicherung0:12:20 Paritätscodes0:13:33 Beweis0:15:09 Paritätscodes gegen Vertauschungsfehler0:18:42 Bsp: ISBN-100:18:56 ISBN0:19:59 …
 
17 | 0:00:00 Starten0:01:45 Thema dieses Kapitels0:04:52 Material für Informationstheorie0:05:32 Information0:12:45 Wiederholung: Rechenregeln Logarithmus0:13:53 Definition Information0:14:52 Entropie0:19:16 Bemerkung zur Entropie0:19:31 Entropie einer Münze mit Wkt p für Zahl0:20:44 (Platzsparende) Codierungen0:22:12 Codierungsbäume0:26:49 Präfix-…
 
16 | 0:00:00 Starten0:00:37 Kellerautomaten0:03:49 Satz0:05:15 Satz (2)0:06:09 Beweis0:30:19 Korollar0:30:41 Übersicht Chomsky-20:32:46 Exkurs0:34:16 Zwischenfazit zu kontextfreien Grammatiken0:36:10 Satz (3)0:38:18 Das Post'sche Korrespondenzproblem0:39:47 Beweis (2)0:43:33 Beweisskizze0:44:07 Beweis (3)0:45:50 Sprache der korrekten Rechenwege0:51…
 
15 | 0:00:00 Starten0:00:07 Beweis0:03:26 Kellerautomaten0:09:17 Kellerautomaten - Visualisierung0:10:09 Kellerautomaten - Arbeitsweise0:18:33 Kellerautomaten - Beispiel0:27:20 Kellerautomaten - Beispiel 20:31:02 Satz (1)0:35:44 Satz (2)0:39:19 Satz (3)Von Prof. Dr. Dorothea Wagner
 
14 | 0:00:00 Starten0:00:07 Wiederholung0:12:03 Ogden´s Lemma für kontextfreie Sprachen0:14:31 Beweis0:29:20 Beweis - Teil 10:30:23 Beweis - Teil 20:39:23 Beweis - Teil 30:41:58 Nutzlose Variablen0:43:38 Schritt 10:47:24 Beispiel: Schritt 10:51:28 Schritt 20:53:16 Beispiel: Schritt 20:56:45 Korollar0:59:27 Beispielgraph…
 
13 | 0:00:00 Starten0:00:31 Wiederholung0:02:13 Die Chmosky Hierarchie0:08:16 Syntaxbäume0:10:28 Syntaxbäume - Beispiel0:15:54 Links/Rechtsabteilung, Eindeutigkeit0:17:31 Beispiel0:19:37 Chomsky-Normalform0:20:56 Die Chomsky Hierarchie0:21:21 Chomsky-Normalform0:31:01 Schritt 10:34:21 Schritt 20:38:20 Schritt 30:49:34 Schritt 40:53:36 Abhängigkeits…
 
12 | 0:00:00 Starten0:00:28 Grammatiken0:01:26 Beispiele0:05:33 Grammatiken0:07:12 Bemerkungen0:08:32 Beispiel0:09:22 Die Chomsky Hierarchie0:20:09 Chomsky-0 Grammatiken und Semientscheidbarkeit0:24:58 Beweis - Beschreibung der Grammatik G0:28:28 Beweis - Zusammenfassung0:29:42 Chomsky-0 Grammatiken und Semientscheidbarkeit0:32:04 Zwischenfazit0:34…
 
11 | 0:00:00 Starten0:02:50 Approximation mit relativer Gütegarantie0:03:31 Definition0:04:49 Approximierbarkeit von COLOR0:18:45 Approximierbarkeit von TSP0:28:12 Approximationsschemata0:38:45 Ein FPAS für KNAPSACK (1)0:40:02 Ein pseudopolynomialer, optimaler Algorithmus für KNAPSACK0:43:49 Ein FPAS für KNAPSACK (2)0:58:51 Ein allgemeineres Result…
 
10 | 0:00:00 Starten0:03:37 VerallgemeinerteNP-Schwere0:07:17 Das Problem INTEGER PROGRAMMING0:26:15 Pseudopolynomiale Algorithmen0:29:56 Beispiel: Problem KNAPSACK0:40:20 Starke NP-Vollständigkeit0:44:14 Absolute Approximationsalgorithmen0:46:31 Das allgemeine KNAPSACK-Suchproblem0:57:09 Approximation mit relativer Gütegarantie0:59:53 Beispiel: Gr…
 
09 | 0:00:00 Starten0:06:41 Das Problem SUBSET SUM0:07:46 NP-Vollständigkeit von SUBSET SUM0:24:03 Das Problem PARTITION0:31:06 Das Problem KNAPSACK0:37:32 Auswirkungen auf die Frage P=NP0:45:42 Zusammenfassung0:47:57 Die Klassen NPI, co-P und co-NP0:54:22 Das TSP-Komplement-Problem0:57:40 Lemma1:00:00 Bemerkung1:01:25 Das Problem Subgraphisomorphi…
 
08 | 0:00:00 Starten0:00:37 Wiederholung: NP-Vollständigkeit0:06:10 Wiederholung: Transitivität der poly. Transformation0:06:40 Wiederholung: Korollar0:07:37 Wiederholung: Das Problem SAT (satisfiability)0:12:17 Das Problem 3-SAT0:13:13 Beweis: NP-Vollständigkeit von 3-SAT0:30:07 Das Problem 2SAT0:34:40 Das Problem MAX2SAT0:38:02 Das Problem CLIQUE…
 
07 | 0:00:00 Starten0:01:06 Die Klasse P0:03:19 Die Klasse NP0:04:47 Die Nichtdeterministische Turingmaschine0:05:17 Zeitkomplexität für NTM0:08:55 Große Frage der Theoretischen Informatik0:11:38 NP-Vollständigkeit0:24:35 Transitivität der poly. Transformation0:25:46 Korollar0:28:28 Das Problem SAT (satisfiability)0:31:05 Weitere Beispiele für SAT-…
 
06 | 0:00:00 Starten0:00:54 Definitionen zur TM0:05:21 Notation: Konfiguration0:07:49 Beispiel: Konfiguration0:20:00 Definition: berechenbar / totalrekursiv0:22:30 Beispiel0:26:57 Entscheidbarkeit und Berechenbarkeit0:30:18 Korollar0:33:13 Die Church´sche These0:36:20 Erweiterungen der Turing-Maschine0:39:17 Die universelle Turing-Maschine0:45:24 D…
 
05 | 0:00:00 Starten0:00:54 Definitionen zur TM0:05:56 Notation: Konfiguration0:07:50 Beispiel: Konfiguration0:20:37 Definition: berechenbar / totalrekursiv0:23:01 Beispiel0:27:27 Entscheidbarkeit und Berechenbarkeit0:30:19 Korollar0:33:21 Die Church´sche These0:36:38 Ertweiterungen der Turing-Maschine0:39:39 Die universelle Turing-Maschine0:44:35 …
 
04 | 0:00:00 Starten0:00:12 Endliche Automaten, reguläre Sprachen0:00:57 Frage0:01:40 Äquivalenz0:04:24 Der Äquivalenzklassenautomat0:06:29 Vorgehensweise0:08:44 Frage0:10:29 Antwort0:13:49 Definitionen: Rechtsinvarianz und Index0:17:08 Nerode-Relation0:20:55 Satz von Nerode0:24:06 Beweis zu Satz von Nerode: (1) – (2)0:28:54 Beweis zu Satz von Nero…
 
02 | 0:00:00 Starten0:00:24 Letzte Vorlesung0:09:53 Entfernen von e-Übergängen0:20:42 EA – Regulärität0:22:44 Beweis: EA – Regulärität0:44:02 Beispiel0:54:15 Satz von Kleene0:55:54 Frage: Was können endliche Automaten nicht?0:59:14 Pumping-Lemma für reguläre Sprachen1:10:10 Bemerkung1:11:49 Beispiel (1) zum PL1:14:18 Beispiel (2) zum PL1:18:31 Beis…
 
03 | 0:00:00 Starten0:00:25 Verallgemeinertes PL für reguläre Sprachen0:17:18 Kapitel Minimierung von Automaten und Äquivalenzklassenautomat0:20:14 Frage: Kann man konstruktiv die Anzahl der Zustände eines deterministischen endlichen Automatens erheblich verringern?0:22:04 Beispiel0:34:34 Äquivalenz0:37:22 Der Äquivalenzklassenautomat0:48:03 Frage:…
 
01 | 0:00:00 Starten0:00:30 Ziele der Vorlesung TGI0:13:46 Wiederholung aus Grundbegriffe der Informatik0:17:17 Wörter0:21:24 Formale Sprachen0:31:12 Reguläre Sprachen0:36:04 Reguläre Ausdrücke0:39:46 Reguläre Ausdrücke – Beispiele0:43:48 Endliche Automaten0:53:24 Kontextfreie Grammatiken0:58:07 Beispiel Kontextfreie Grammatiken…
 
26: Übung|0:00:00 Starten0:00:12 Vorbereitung Klausur: 1. Übungsblatt0:05:44 2. Übungsblatt0:06:34 3. Übungsblatt0:08:49 4. Übungsblatt0:18:32 5. Übungslbatt0:25:58 6. Übungsblatt0:30:05 7. Übungsblatt0:34:44 8. Übungsblatt0:41:35 Weihnachtsblatt0:42:46 10. Übungsblatt0:45:17 Weiterführende Vorlesungen0:52:01 11. Übungsblatt0:55:22 12. Übungsblatt0…
 
25: Vorlesung und Übung |0:00:00 Starten0:02:07 Caesar-Chiffre 0:05:07 Monoalphabetische Verschiebungschiffre0:06:57 Vigenère-Verschlüsselung 0:20:34 Set Cover0:27:01 Set Cover Beispiel 10:27:37 Set Cover ist NP-vollständig0:27:53 Beweis ""Set Cover ist NP-hart""0:35:36 Set Cover Beispiel 20:37:40 Beweis F erfüllbar0:41:18 Bewies ""3SAT ist NP-hart…
 
24: Vorlesung und Übung |0:00:00 Starten0:00:18 Übung: Gedächtnislose Quellen0:02:16 Übung: Entropiemaximierung0:06:59 Übung: Decodierbarkeit0:11:32 Übung: Theoretische Grenzen der Kompression 0:15:27 Übung: Fakten zur Kolmogorov Koplexität0:20:03 Übung: Einige Beispiele für obere Schranken0:23:46 Vorlesung: Elias-Fano Kodierung0:24:37 Vorlesung: E…
 
20: Vorlesung und Übung |0:00:00 Starten0:00:11 Directed Hamilton Cycle (DHC)0:01:35 Beweis von »DHC ist NP-hart«0:02:03 Reduktionen0:02:43 DHC0:03:34 Beweis von »DHC ist NP-hart«0:05:07 Ein Knoten pro Variable0:05:47 Gadget Kj mit 6 Knoten je Klausel0:08:35 »Vorgesehene« Hamiltonkreise0:12:12 Unmögliche Hamiltonkreise0:14:16 Verbindungen der Gadge…
 
23: Vorlesung|0:00:00 Starten0:00:42 Thema dieses Kapitels0:04:32 Information0:09:03 Wiederholung: Rechenregeln Logarithmus0:11:49 Entropie0:13:45 Bemerkungen zur Entropie0:15:22 Entropie einer Münze mit Wkt p für Zahl0:16:01 (Platzsparende) Codierungen0:16:48 Codierungsbäume0:19:51 Beispiel0:20:57 Präfix-Codes0:21:43 Beispiel0:23:16 Quellencodieru…
 
22: Vorlesung und Übung|0:00:00 Starten0:00:10 2: Berechenbarkeitstheorie | 2.1 Intuitiver Berechenbarkeitsbegriff und Churchsche These0:00:41 Berechenbarkeit Hauptergebnis0:01:26 2.2 Intuitiver Berechenbarkeitsbgegriff0:01:48 Beispiel0:07:15 2.3 LOOP-, WHILE-, GOTO (=Registermaschinen) und RAM-Berechenbarkeit0:08:41 LOOP-Programme0:10:29 Äquivalen…
 
21: Vorlesung |0:00:00 Starten0:03:23 1.1 Allgemeines0:04:18 1.1.1 Grammatiken0:05:19 1.1.2 Chomsky-Hierachie0:11:12 1.1.3 Wortproblem0:12:17 1.1.4 Syntaxbäume0:13:02 1.2 Reguläre Sprachen0:14:03 1.2.1 (Deterministische) endliche Automaten0:14:30 1.2.2 Nichtderterministische (endliche) Automaten0:19:52 1.2.3 Reguläre Ausdrücke0:27:01 1.2.4 Das Pump…
 
19: Vorlesung |0:00:00 Starten0:03:08 Beweis SUBSET SUM 0:03:31 Beweis ""SUBSET SUM ist NP-hart""0:03:34 SUBSET SUM0:06:04 Die SUBSET SUM Instanz0:10:08 Beispiel0:13:55 Beweisidee0:18:29 F erfüllbar -> Instanz lösbar0:20:42 Instanz lösbar -> F erfüllbar0:23:44 Beispiel Rucksackproblem0:24:29 Rucksackproblem0:26:11 Reduktionen0:26:56 PARTITION0:28:3…
 
18: Vorlesung und Übung|0:00:00 Starten0:00:10 Wiederholung: Satz: 3SAT ist NP-vollständig0:02:06 Wiederholung: Beweis ""3SAT ist NP-hart""0:02:47 Wiederholung: Negationen in die Blätter drücken0:03:07 Wiederholung: Nichtblattknoten --> Neue Variablen0:03:37 Wiederholung: Erfüllbarkeitsäquivalenz0:05:05 Exkurs: 2SAT ∈ P0:10:27 CLIQUE0:14:22 Beweis …
 
17: Vorlesung|0:00:00 Starten0:00:53 Wiederholung Komplexitätstheorie0:08:54 Polynominale Reduzierbarkeit0:09:55 Beispiel0:10:57 NP-harte und Np-Vollständige Probleme0:13:22 Ein einfacher Weg zu Ruhm und Reichtum ? 0:13:50 SAT: Das Erfüllbarkeitsproblem 0:17:03 Beweis von SAT 0:17:31 Beweis das SAT-NP-hart ist.0:19:45 Variablen für F0:24:53 Die Arc…
 
16: Übung und Vorlesung|0:00:00 Starten0:00:56 Rückblick: Chomsky-30:05:29 Rückblick: Chomsky-3 Verfahren0:16:18 Rückblick: Chomsky-20:19:33 Rückblick: Chomsky-2 Verfahren0:27:23 Rückblick: Chomsky-0/10:30:41 Rückblick: Entscheidbarkeit0:36:54 Ausblick: Komplexitätstheorie0:38:54 Video: Game of Life Automat0:43:27 Video: Variante von Game of Life m…
 
15: Vorlesung|0:00:00 Starten0:01:24 Halteproblem0:02:27 Das beschränkte Halteproblem0:02:57 Mehr unentscheidbare Probleme0:03:15 Unentscheidbarkeit von Leerheit0:09:13 Unentscheidbarkeit von Vollständigkeit0:09:31 Metaprogrammierung0:11:03 Postsches Korrespondenzproblem (PKP)0:12:16 Beispiel0:19:04 PCP ist semientscheidbar0:20:25 PCP ist unentsche…
 
14: Vorlesung und Übung|0:00:00 Starten0:00:10 2.6 Halteproblem, Unentscheidbarkeit, Reduzierbarkeit0:00:44 Paradoxien und Selbstbezüglichkeit0:01:28 Entscheidbarkeit0:01:47 Äquivalente Aussagen0:02:37 2.7 Nicht-entscheidbare Probleme0:03:04 Normierung von Turing-Maschinen0:04:24 Gödelnummer (M) einer Turingmaschine M0:09:01 Gödelnummer0:09:59 Beis…
 
Loading …

Kurzanleitung

Google login Twitter login Classic login