Einführung in die Theoretische Informatik

What it is about

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.

What you will be able to do

• 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

What the module consists of

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

Teaching method

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