inf401 - Grundlagen der Theoretischen Informatik (Veranstaltungsübersicht)

inf401 - Grundlagen der Theoretischen Informatik (Veranstaltungsübersicht)

Department für Informatik 6 KP
Modulteile Semesterveranstaltungen Wintersemester 2021/2022 Prüfungsleistung
Vorlesung
Übung
Hinweise zum Modul
Teilnahmevoraussetzungen
Keine Teilnehmervoraussetzungen
Prüfungszeiten
Am Ende des Semesters
Prüfungsleistung Modul
Klausur oder mündl. Prüfung
Kompetenzziele
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