Es werden Themen aus der Theoretischen Informatik behandelt, die über das Modul Grundlagen der theoretischen Informatik hinausgehen.

Themen

• Alternative Berechnungsmodelle
  • rekursive Funktionen
  • primitiv-rekursive Funktionen, LOOP-Berechenbarkeit
  • Zählerautomaten
  • Tag-Systeme
  • RAM-Modell
• Fleißige Biber
• Universelle Turingmaschinen
• Rekursionssatz, Selbstbezüglichkeit
• Kontextfreie Sprachen
• deterministische Zweiwege-Kellerautomaten und das Teilwortproblem
• Unentscheidbare Probleme in anderen Gebieten [weggelassen]
• Probabilistische endliche Automaten [weggelassen]
• Lernen regulärer Sprachen [weggelassen]

Siebe https://mycampus.imp.fu-berlin.de/portal/tool/8c73097f-6707-404e-9945-fbd1ee6f69e6/printFriendly für eine genauere Inhaltsübersicht.