course: Theoretische Informatik

number:
150302
teaching methods:
lecture with tutorials
responsible person:
Prof. Dr. Maike Buchin
lecturer:
Prof. Dr. Maike Buchin (Mathematik)
language:
german
HWS:
6
CP:
8
offered in:
winter term

dates in winter term

  • lecture Thursdays: from 10:00 to 12.00 o'clock in Online
  • lecture Thursdays: from 12:00 to 14.00 o'clock in HZO 10
  • tutorial (alternativ) Tuesdays: from 12:00 to 14.00 o'clock in Online
  • tutorial (alternativ) Wednesdays: from 12:00 to 14.00 o'clock in NB 6/99
  • tutorial (alternativ) Wednesdays: from 12:00 to 14.00 o'clock in NC 02/99

goals

Nach dem erfolgreichen Abschluss der Veranstaltung

  • beherrschen die Studierenden den professionellen Umgang mit Berechnungsmodellen und ihren Beziehungen zu Sprachklassen. Dazu gehört die intellektuelle und methodische Fähigkeit, den Nachweis der Zugehörigkeit bzw. Nichtzugehörigkeit zu einer solchen Klasse zu führen.
  • durch Einüben von Beweistechniken wie wechselseitige Simulation oder berechenbare Reduktionen ist die Einsicht gereift, dass an der Oberfläche verschieden aussehende Konzepte im Kern identisch sein können. Zudem erlaubt dies den Studierenden, neue Anwendungsprobleme selbständig zu klassifizieren.
  • erlernen die Studierenden ein einfach handhabbares Rechnermodell, die Turingmaschine, das ihnen fortan als Abstraktion für alle möglichen Rechner dient.
  • erlangen die Studierenden fundamentale Einsichten, welche Probleme mit Hilfe von Rechnern effizient entschieden, mit Hilfe effizient entschieden, entschieden, zum Teil entschieden oder prinzipiell nicht entschieden werden können. Dadurch erlangen Sie ein tieferes Verständnis von Komplexität von Berechnungsproblemen.

content

Die Vorlesung gibt einen systematischen Überblick über die folgenden Themengebiete:

  • Endliche Automaten und reguläre Ausdrücke
  • Kellerautomaten und kontextfreie Grammatiken
  • Turing-Maschinen und Entscheidbarkeit
  • Nichtdeterminismus und NP-Vollständigkeitstheorie