Informatik 3 – Theoretische Informatik WS 2021/22

LVR-Nr:150 240
Veranstaltung:Theoretische Informatik
4 std.
Dozent:Maike Buchin
Übungen:Christoph Ries, Dennis Rohde und Marko SchmellenkampKorrektur der Hausaufgaben:Thorben Schweitzer und Markus Keil

Aktuelles

  • Alle weiteren Informationen werden über den Moodle-Kurs bekannt gegeben werden.

 

Informationen aus dem Vorlesungsverzeichnis

Voraussetzungen

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

Kommentar

Die Vorlesung richtet sich an Studierende der Mathematik, der Angewandten Informatik
und (als Wahlpflichtfach) an Studierende der IT-Sicherheit. Sie liefert eine Einführung
in die Theorie der Grammatiken (insbesondere kontextfreie Grammatiken) und Automaten
(endlicher Automat, Kellerautomat, Turing-Maschine). Sie gibt ferner einen Einblick in
die Berechenbarkeits- und NP-Vollständigkeitstheorie, wo es um die Frage geht, welche
Rechenprobleme (überhaupt bzw. mit vertretbarem Aufwand) gelöst werden können. Es wird
sich zeigen, dass es inhärent schwere Probleme gibt, die von Rechnern nicht
zufriedenstellend gelöst werden können.

In der Vorlesung ergeben sich fundamentale Einsichten zum Verhältnis zwischen
Automaten und Grammatiken und zum Verhältnis von Determinismus und Nicht-Determinismus.
Durch Einüben von Techniken wie wechselseitige Simulation oder (polynomiell) berechenbare
Reduktionen soll die Einsicht reifen, dass an der Oberfläche verschieden aussehende
Konzepte im Kern identisch sein können. Ziel ist zudem ein tieferes Verständnis von
Komplexität. Auf den unteren Ebenen der sogenannten Chomsky-Hierarchie finden sich
effizient lösbare Anwendungsprobleme der Textmanipulation und der Textanalyse. Auf den
oberen Ebenen machen wir Bekanntschaft mit dem Phänomen der inhärenten Härte
(oder gar Unentscheidbarkeit) eines Problems.

Literatur

Die Vorlesung orientiert sich in erster Linie an dem Buch „Theoretische Informatik – kurzgefasst“ von Uwe Schöning (Spektrum, 2008) bzw. an einem Skriptum zur Vorlesung.

Weitere empfehlenswerte Bücher sind:

  • Ingo Wegener: Theoretische Informatik – Eine algorithmenorientierte Einführung, 3. Auflage, Teubner, 2005
  • Ingo Wegener: Kompendium theoretische Informatik – Eine Ideensammlung, Teubner, 1996 (als Ergänzung)
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexität, Pearson Studium, 3. Auflage, 2011
  • Michael Sipser: Introduction to the Theory of Computation, 2nd ed., Thomson Course Technology, 2006

 

Kontakt