Serie: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20
| Autor | Wagner, Dorothea Sauer, Jonas Brückner, Guido Zentrum für Mediales Lernen (ZML) [Hrsg.] |
| 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). |
| Fachgebiete | Informatik (inf) (DDC 004) |
| DOI | 10.5445/DIVA/2019-C35 |
| Reichweite | Veröffentlichung im Internet |
Folgen 1 - 18