| NUMMER: | 212002 |
| KÜRZEL: | INFO3 |
| MODULBEAUFTRAGTE:R: | Prof. Dr. Thomas Zeume |
| DOZENT:IN: | Prof. Dr. Maike Buchin |
| FAKULTÄT: | Fakultät für Informatik |
| SPRACHE: | Deutsch |
| SWS: | 6 SWS |
| CREDITS: | 8 CP |
| ANGEBOTEN IM: | jedes Wintersemester |
LINK ZUM VORLESUNGSVERZEICHNIS
Hier entlang.
PRÜFUNGEN
| FORM: | schriftlich |
| TERMIN: | Siehe Prüfungsamt. |
LERNFORM
Hörsaalvorlesung mit Medienunterstützung und Übungen, bei denen die vorgestellten Konzepte und Techniken praktisch umgesetzt werden, teilweise mit Rechnerübungen
LERNZIELE
Nach dem erfolgreichen Abschluss des Moduls- 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örig-keit zu einer solchen Klasse zu führen.
- ist durch Einüben von Beweistechniken wie wechselseitige Simulation oder berechenbare Reduktionen bei den Studierenden die Einsicht gereift, dass an der Oberfläche verschieden aussehende Konzepte im Kern identisch sein können. Zudem erlaubt dies den Studierenden, neue Anwendungsprobleme selbstständig zu klassifizieren.
- haben die Studierenden mit der Turingmaschine ein einfach handhabbares Rechnermodell erlernt, das ihnen fortan als Abstraktion für alle möglichen Rechner dient.
- haben die Studierenden fundamentale Einsichten erlangt, welche Probleme mithilfe von Rechnern effizient entschieden, zum Teil entschieden oder prinzipiell nicht entschieden werden können. Dadurch erlangen Sie ein tieferes Verständnis von der Komplexität von Berechnungsproblemen.
INHALT
Die Lehrveranstaltung gibt einen systematischen Überblick über die folgenden Themengebiete:- Endliche Automaten und reguläre Ausdrücke
- Kellerautomaten und kontextfreie Grammatiken
- Turingmaschinen und Entscheidbarkeit
- Nichtdeterminismus und NP-Vollständigkeitstheorie
VORAUSSETZUNGEN CREDITS
Bestandene Modulabschlussprüfung
EMPFOHLENE VORKENNTNISSE
Inhalte der Module Informatik 2 – Algorithmen und Datenstrukturen und Mathematik 2 -Algorithmische Mathematik
LITERATUR
1. Schöning, Uwe "Theoretische Informatik - kurzgefasst"2. Hopcroft, John E., Motwani, Rajeev, Ullman, Jeffrey D. "Einführung in die Automatentheorie, Formale Sprachen und Komplexität"
3. Sipser, Michael "Introduction to the Theory of Computation"