Informatik 3 - Theoretische Informatik

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

- be­herr­schen die Stu­die­ren­den den pro­fes­sio­nel­len Um­gang 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 Be­weis­tech­ni­ken wie wech­sel­sei­ti­ge Si­mu­la­ti­on oder be­rechen­ba­re Re­duk­tio­nen bei den Studierenden die Ein­sicht ge­reift, dass an der Ober­flä­che ver­schie­den aus­se­hen­de Kon­zep­te im Kern iden­tisch sein kön­nen. 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 Stu­die­ren­den 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 "Theo­re­ti­sche In­for­ma­tik - kurz­ge­fasst"
2. Hop­croft, John E., Mot­wa­ni, Ra­jeev, Ull­man, Jef­frey D. "Einführung in die Automatentheorie, Formale Sprachen und Komplexität"
3. Sip­ser, Micha­el "In­tro­duc­tion to the Theo­ry of Com­pu­ta­ti­on"

SONSTIGE INFORMATIONEN

Aktuelle Informationen wie Vorlesungstermine, Räume oder aktuelle Dozent*innen und Übungsleiter*innen sind im Vorlesungsverzeichnis der Ruhr-Universität https://vvz.rub.de/ und im eCampus https://www.rub.de/ecampus/ecampus-webclient/ zu finden.