Einführung in grundlegende Konzepte der Theoretischen Informatik. Im Zentrum stehen Automatentheorie (endliche Automaten, Kellerautomaten und Turingmaschinen), formale Sprachen (Chomsky-Hierarchie), Berechenbarkeit (Unentscheidbarkeit des Halteproblems, Satz von Rice) und Komplexität („P vs. NP“-Problem, NP-Vollständigkeit). Daneben werden zum Umgang mit schwer lösbaren Problemen erste algorithmische Ansätze zur approximativen oder randomisierten Lösung von NP-schweren Problemen aufgezeigt.
Für den erfolgreichen Abschluss dieses Moduls werden 9 LP vergeben.
Die Veranstaltung wurde 1 mal im Vorlesungsverzeichnis WiSe 2025/26 gefunden:
