Am Ende des Semesters

Klausur oder mündl. Prüfung

Einführung in die Theorie der Automaten, formalen Sprachen, Berechenbarkeit und Komplexität

Fachkompetenzen
Die Studierenden:

• kennen verschiedene Sprachklassen (z.B. reguläre und kontextfreie Sprachen)
• kennen dazugehörige Automatenmodelle (z.B. endliche Automaten, Kellerautomaten, Turingmaschinen)
• erstellen Automaten,Turingmaschinen und Grammatiken zu gegebenen Aufgaben
• kennen äquivalente Formalisierungen des Begriffs des Algorithmus
• weisen Funktionen als algorithmisch berechenbar bzw.
• Probleme als algorithmisch entscheidbar nach
• kennen unentscheidbare Probleme
• schätzen die Komplexität von Algorithmen ab
• kennen Probleme, die deterministisch oder nichtdeterministisch in polynomieller Zeit lösbar sind

Methodenkompetenzen
Die Studierenden:

• lernen die Mächtigkeit von abstrakten Modellen von Berechenbarkeit kennen

Sozialkompetenzen
Die Studierenden:

• arbeiten in kleinen Gruppen an Lösungen von Aufgaben
• präsentieren Lösungen von Aufgaben vor Gruppen

Selbstkompetenzen
Die Studierenden:

• erlernen Ausdauer bei der Bearbeitung schwieriger Aufgaben
• erlernen Präzision beim Aufschreiben von Lösungen