Einführung in die Theoretische Informatik

Worum geht's

Du erhältst eine systematische Einführung in die Theorie formaler Sprachen, Berechenbarkeit und Komplexität. Am Ende kannst du formale Sprachen mit passenden Beschreibungsmitteln (z. B. Automaten, Grammatiken, reguläre Ausdrücke) darstellen und analysieren, Unentscheidbarkeits- und Komplexitätseigenschaften nachweisen sowie grundlegende Reduktionen durchführen.

Was du danach kannst

• Formale Sprachen mit Grammatiken und Automaten beschreiben
• Äquivalenz von Beschreibungsmitteln beweisen und Transformationen durchführen
• nachweisen, dass eine Sprache nicht von einem gegebenen Modell beschrieben werden kann
• zentrale Konzepte der Berechenbarkeit und Halb-/Entscheidbarkeit erklären
• Unentscheidbarkeit mittels klassischer Ergebnisse und Reduktionen zeigen
• Grundbegriffe der Komplexitätstheorie (P, NP, NP-Vollständigkeit) erklären
• Entscheidungsprobleme algorithmisch unter Komplexitätsbeschränkungen reduzieren

Aus was das Modul besteht

• VorlesungVermittlung der theoretischen Inhalte und Beweise
• ÜbungEinübung der Lernziele an konkreten Aufgaben einzeln oder in Kleingruppen mit Betreuung

Lehrmethode

• Vorlesung im DialogInhalte werden vorgestellt und mit den Studierenden diskutiert
• Übungen mit BetreuerErarbeitung und Vertiefung der Konzepte an Beispielen und Aufgaben