KIT-Bibliothek
Audio-/Videodatei publizieren
Anleitung zum Publizieren

Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18

Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18

Autor

Dorothea Wagner, Torsten Ueckerdt

Herausgeber

KIT | Webcast

Beteiligtes Institut

Genre

Vorlesung

Beschreibung

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

Literaturhinweise:
Uwe Schöning: Theoretische Informatik - kurz gefasst. Sprektrum (2001).
Ingo Wegener: Theoretische Informatik. Teubner (1999)
Ingo Wegener: Kompedium theoretische Informatik. Teubner (1996).

Lehrinhalt:
Es gibt wichtige Probleme, deren Lösung sich zwar klar definieren läßt, aber die man niemals wird systematisch berechnen können. Andere Probleme lassen sich "vermutlich" nur durch systematisches Ausprobieren lösen. Andere Themen dieser Vorlesungen legen die Grundlagen für Schaltkreisentwurf, Compilerbau, uvam. Die meisten Ergebnisse dieser Vorlesung werden rigoros bewiesen. Die dabei erlernten Beweistechniken sind wichtig für die Spezifikation von Systemen der Informatik und für den systematischen Entwurf von Programmen und Algorithmen.

Das Modul gibt einen vertieften Einblick in die Grundlagen und Methoden der Theoretischen Informatik. Insbesondere wird dabei eingegangen auf grundlegende Eigenschaften Formaler Sprachen als Grundlagen von Programmiersprachen und Kommunikationsprotokollen (regulär, kontextfrei, Chomsky-Hierarchie), Maschinenmodelle (endliche Automaten, Kellerautomaten, Turingmaschinen, Nichtdeterminismus, Bezug zu Familien formaler Sprachen), Äquivalenz aller hinreichend mächtigen Berechnungsmodelle (Churchsche These), Nichtberechenbarkeit wichtiger Funktionen (Halteproblem,...), Gödels Unvollständigkeitssatz und Einführung in die Komplexitätstheorie (NP-vollständige Probleme und polynomiale Reduktionen).

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz

Hinweis

Die Beiträge dieser Serie können Sie als Podcast abonnieren.

Embed-Code

Folgen 1-19 von 19