Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19
Autor
Torsten Ueckerdt, Dorothea Wagner
Herausgeber
Genre
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
Lizenz
Hinweis
Die Beiträge dieser Serie können Sie als Podcast abonnieren.
Embed-Code
