Informatik 3 - Theoretische Informatik

NUMMER: 150240
KÜRZEL: INFO3
DOZENT: Prof. Dr. Eike Kiltz
FAKULTÄT: Fakultät für Mathematik
SPRACHE: Deutsch
SWS: 6 SWS
CREDITS: 8 CP
WORKLOAD: 240 h
ANGEBOTEN IM: jedes Sommersemester

INFOS

Informatik 3 – Vorlesung (4 SWS)
Informatik 3 – Übung (2 SWS)


PRÜFUNGUNGSFORM

Schriftliche Modulabschlussprüfung über 150 Minuten


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

keine


VORAUSSETZUNGEN CREDITS

Bestandene Modulabschlussprüfung


EMPFOHLENE VORKENNTNISSE

Inhalte der Module Informatik 2 – Algorithmen und Datenstrukturen und Mathematik 2 -Algorithmische Mathematik


LITERATUR

1. John E. Hopcroft und Jeffrey D. Ullman: „Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie“, Addison-Wesley
2. M. F. Sipser: „Introduction to the Theory of Computation“, PWS Publishing


Computer Science 3 - Theoretical Computer Science

NUMMER: 150240 KÜRZEL: INFO3 DOZENT: Prof. Dr. Eike Kiltz FAKULTÄT: Fakultät für Mathematik SPRACHE: German SWS: 6 SWS CREDITS: 8 CP WORKLOAD: 240 h ANGEBOTEN IM: each summer semester

INFOS

Informatik 3 – Lecture (4 SWS)
Informatik 3 – Exercise (2 SWS)


PRÜFUNGUNGSFORM

Written final exam of 150 minutes


LERNFORM

Lecture with media support and exercises in which the presented concepts and techniques are put into practice, some with computer exercises


LERNZIELE

After successfully completing the module
- the students master the professional handling of calculation models and their relationships to language classes. This includes the intellectual and methodological ability to provide evidence of membership or non-membership in such a class
- by practicing proof techniques such as mutual simulations or calculable reductions, students have come to realize that concepts that look different on the surface can be identical in essence. In addition, this allows students to classify new application problems independently.
- with the Turing machine, the students learned an easy-to-use computer model, which from now on serves as an abstraction for all possible computers.
- -the students have gained fundamental insights into which problems can be efficiently decided with the help of computers, partly decided or not in principle decided with the help of computers. This will give them a deeper understanding of the complexity of computational problems.


INHALT

The course gives a systematic overview of the following topics:
- - Finite automata and regular expressions
- - Push-down automata and context-free grammars
- - Turing machines and decidability
- - Nondeterminism and NP-Completeness Theory


VORAUSSETZUNGEN

None


VORAUSSETZUNGEN CREDITS

Passed examination


EMPFOHLENE VORKENNTNISSE

Contents of the modules Computer Science 2 - Algorithms and Data Structures and Mathematics 2 - Algorithmic Mathematics


LITERATUR

1. John E. Hopcroft und Jeffrey D. Ullman: „Einführung in die Automatentheorie,
Formale Sprachen und Komplexitätstheorie“, Addison-Wesley
2. M. F. Sipser: „Introduction to the Theory of Computation“, PWS Publishing