KIT-Bibliothek
Audio-/Videodatei publizieren
Anleitung zum Publizieren

Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20

Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20

Autor

Dorothea Wagner, Jonas Sauer, Guido Brückner

Herausgeber

Zentrum für Mediales Lernen (ZML)

Beteiligtes Institut

Genre

Vorlesung

Beschreibung

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