Veranstaltung: Theoretische Informatik

Nummer:
150240
Lehrform:
Vorlesung und Übungen
Medienform:
Folien, Tafelanschrieb
Verantwortlicher:
Prof. Dr. Hans Ulrich Simon
Dozent:
Prof. Dr. Hans Ulrich Simon (Mathematik)
Sprache:
Deutsch
SWS:
6
LP:
9
Angeboten im:
Wintersemester

Termine

Termine bitte im Vorlesungsverzeichnis nachschlagen.

Prüfung

Schriftlich

Termin wird vom Dozenten bekannt gegeben

Dauer: 180min
Prüfungsanmeldung: FlexNow

Ziele

Die studierenden haben fundamentale Einsichten zum Verhältnis zwischen Automaten und Grammatiken und zum Verhältnis von Determinismus und Nicht-Determinismus. Durch Einüben von Beweistechniken wie wechselseitige Simulation oder (polynomiell) berechenbare Reduktionen ist die Einsicht gereift, dass an der Oberfläche verschieden aussehende Konzepte im Kern identisch sein können. Zudem wurde ein tieferes Verständnis von Komplexität erreicht. Auf den unteren Ebenen der Chomsky-Hierarchie finden sich effizient lösbare Anwendungsprobleme der Textmanipulation und Textanalyse. Auf den oberen Ebenen der Hierarchie haben die Studierenden Bekanntschaft mit dem Phänomen der inhärenten Härte (oder gar Unentscheidbarkeit) eines Problems gemacht.

Inhalt

  • Grammatiken (mit Schwerpunkt auf kontextfreien Grammatiken)
  • Automaten
  • endliche Automaten
  • Kellerautomaten
  • Turing-Maschinen
  • Berechenbarkeitstheorie
  • NP-Vollständigkeitstheorie

Voraussetzungen

keine

Empfohlene Vorkenntnisse

Nützlich (aber nicht zwingend erforderlich) sind elementare Grundkenntnisse in Informatik und Diskreter Mathematik sowie Vertrautheit mit mindestens einer Programmiersprache.

Literatur

  1. Hopcroft, John E., Motwani, Rajeev, Ullman, Jeffrey D. "Introduction to Automata Theory, Languages, and Computation", Addison Wesley Longman Publishing Co, 2001
  2. Sipser, Michael "Introduction to the Theory of Computation", Brooks Cole, 2005
  3. Schöning, Uwe "Theoretische Informatik - kurzgefasst", Spektrum Akademischer Verlag, 2001

Sonstiges

Master-Studierende der Angewandten Informatik die Theoretische Informatik innerhalb des Bachelorstudiums abgelegt haben, belegen im Masterstudium die Veranstaltung Datenbanksysteme.