Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

EXPLORE

Society & Culture

Health & Fitness

© 2024 PodJoint

00:00 / 00:00

Sign in

or

Don't have an account?

Sign up

Forgot password

https://is1-ssl.mzstatic.com/image/thumb/Podcasts115/v4/37/d4/4f/37d44fdd-d411-06fd-1f86-64fe9a0ce7f3/mza_4153164030958866618.jpg/600x600bb.jpg

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Karlsruher Institut für Technologie (KIT)

26 episodes

5 months ago

Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen. Vorlesungsaufzeichnung: http://webcast.kit.edu

Show more...

All content for Theoretische Grundlagen der Informatik, Vorlesung, WS14/15 is the property of Karlsruher Institut für Technologie (KIT) and is served directly from their servers with no modification, redirects, or rehosting. The podcast is not affiliated with or endorsed by Podjoint in any way.

Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen. Vorlesungsaufzeichnung: http://webcast.kit.edu

Show more...

Episodes (20/26)

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 04.12.2014, Lektion 10

10: Vorlesung: NP-Vollständigkeit | Das Problem 3-SAT | Beweis: NP-Vollständigkeit von 3-SAT | Das Problem 2SAT | Das Problem MAX2SAT | Das Problem CLIEQUE | Beweis: NP-Vollständigkeit von CLIQUE | Das Problem COLOR | Beweis: NP-Vollständigkeit von 3COLOR | Konstruktion von 3COLOR-Instanz G | Beispielgraph zur Reduktion | Polynomialität der Reduktion

10 years ago

1 hour 15 minutes 21 seconds

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 09.12.2014, Lektion 11

11: Vorlesung: Das Problem COLOR

10 years ago

1 hour 24 minutes

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 11.12.2014, Übung 4

Übung 4: Turingmaschinen und Berechenbarkeit | Komplexitätsklassen

10 years ago

58 minutes 2 seconds

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 16.12.2014, Lektion 12

12: Vorlesung: Das Problem Subgraphisomorphie | Suchprobleme | Beispiel: TSP-Suchproblem | Beispiel: Hamilton-Kries Suchproblem | Aufzählungsprobleme | Reduzierbarkeit für Suchprobleme | Orakel-Turing-Maschine | Orakel-TM: Verhalten im Fragezustand | Turing-Reduktion | NP-schwer | Beweisskizze | Verallgemeinerte NP-Schwere | Das Problem INTERGER PROGRAMMING | Beweis | Pseudopolynomielle Algorithmen | Beispiel: Problem KNAPSACK | Starke NP-Vollständigkeit | Absolute Approximationsalgorithmen | Das allgemeine KNAPPSACK-Suchproblem | Satz | (Widerspruchs-)Beweis | Approximation mit relativer Gütegarantie | Beispiel: Greedy-Algorithmus für KNAPSACK

10 years ago

1 hour 24 minutes 37 seconds

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 18.12.2014, Lektion 13

13: Vorlesung: Komlexitätsklassen

10 years ago

1 hour 8 minutes 13 seconds

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 08.01.2015, Übung 5

Übung 5: Optimierungsproblem, Optimalwertproblem, Entscheidungsproblem | NP-vollständige Probleme

10 years ago

1 hour 17 minutes 25 seconds

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 13.01.2015, Lektion 14

14: Vorlesung: Grammatiken

10 years ago

1 hour 11 minutes 43 seconds

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 15.01.2015, Lektion 15

15: Vorlesung: Grammatiken

10 years ago

1 hour 23 minutes 49 seconds

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 20.01.2015, Übung 6

Übung 6: NP und co-NP | Pseudopolynomielle Algorithmen | Approximationsalgorithmen |Ganzzahlige Programme

10 years ago

1 hour 22 minutes 23 seconds

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 22.01.2015, Lektion 16

16: Vorlesung: Kontextfreie Sprachen

10 years ago

1 hour 24 minutes 11 seconds

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 27.01.2015, Lektion 17

17: Vorlesung: Kontextfreie Sprachen

10 years ago

1 hour 28 minutes 55 seconds

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 03.02.2015, Lektion 19

19: Vorlesung: Kontextfreie Sprachen

10 years ago

1 hour 23 minutes 5 seconds

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 05.02.2015, Lektion 19

19: Vorlesung: Informationstheorie

10 years ago

1 hour 17 minutes 46 seconds

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 12.02.2015, Übung 8

Übung 8: Kellerautomaten

10 years ago

1 hour 10 minutes 12 seconds

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 27.11.2014, Übung 3

Übung 3: Minimierung von Automaten | Nerode-Relation | Turing-Maschinen | Erweiterte Turingmaschinen | Universelle Turingmaschine

10 years ago

1 hour 21 minutes 16 seconds

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 25.11.2014, Lektion 09

09: Vorlesung: NP-vollständige Probleme

10 years ago

1 hour 28 minutes 30 seconds

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 18.11.2014, Übung 2

Übung 2: Formale Sprachen und reguläre Ausdrücke | Nicht deterministische endliche Automaten | Pumping-Lemma | Eigenschaften von endlichen Automaten | Potenzmengenkonstruktion

10 years ago

43 minutes 56 seconds

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 20.11.2014, Lektion 08

08: Vorlesung: Sprachen, Probleme und Zeitkomplexität | Nichtdeterministische Turingmaschinen und die Klasse NP

10 years ago

1 hour 18 minutes 28 seconds

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 11.11.2014, Lektion 06

06: Vorlesung: Turing-Maschinen und Berechenbarkeit

10 years ago

1 hour 28 minutes 13 seconds

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 06.11.2014, Lektion 05

05: Vorlesung: Organisatorisches | Definitionen: Rechtsinvarianz und Index | Nerode-Relation | Satz von Nerode | Beweis zu Satz von Nerode | Korollar | Minimalität des Äquivalenzklassenautomats | Zusammenfassung

10 years ago

53 minutes 53 seconds

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen. Vorlesungsaufzeichnung: http://webcast.kit.edu