Vorlesung: Einführung in die Theoretische Informatik

Komplexität und Kryptografie | Einführung in die Theoretische Informatik

Vorlesung: Einführung in die Theoretische Informatik

Beginn der Vorlesung: 16.10.2018

Beginn der Übungen: 23.10.2018

Beginn der Tutorien: 24.10.2018

Eintragen über: VL in Agnes

Zuordnung zu den Terminen: im Moodle-Kurs

Termine

VL	Di	15-17	RUD 26, 0'115	J. Köbler
VL	Do	15-17	RUD 26, 0'115	J. Köbler
UE	Di	09-11	RUD 26, 1'306	W. Kössler
UE	Di	11-13	RUD 26, 1'306	W. Kössler
UE	Di	13-15	RUD 26, 1'306	F. Fuhlbrück
UE	Mi	09-11	RUD 26, 1'306	F. Fuhlbrück
UE	Mi	13-15	RUD 26, 1'306	F. Nelles
UE	Mi	15-17	RUD 26, 1'306	F. Nelles
UE	Fr	09-11	RUD 26, 1'306	F. Hegerfeld
UE	Fr	11-13	RUD 26, 1'306	F. Hegerfeld
TU	Mi	17:00-18:30	RUD 25, 3.101	L. Kolb
TU	Fr	13-15	RUD 25, 3.101	L. Kolb

Inhalte und Lernziele

Die VL führt in die Kerngebiete der Theoretischen Informatik ein, wobei die Themengebiete Automaten und formale Sprachen im Mittelpunkt stehen. Die hierbei behandelten Fragen sind nicht nur aus theoretischer Sicht interessant, sondern bilden zugleich die Grundlage für so praktische Anwendungsgebiete wie den Compilerbau.

Aufbauend auf dem Automatenmodell der Turingmaschine lässt sich der Begriff des Algorithmus formalisieren, der in allen Bereichen der Informatik eine zentrale Rolle spielt. Die Frage, welche algorithmischen Probleme lösbar sind, beantwortet die Berechenbarkeitstheorie, indem sie uns die Grenzen der Berechenbarkeit aufzeigt.

Schließlich untersuchen wir die Komplexität von algorithmischen Problemen, indem wir den benötigten Rechenaufwand möglichst gut nach oben und unten abschätzen. Eine besondere Rolle spielen hierbei die NP-vollständigen Probleme, deren Komplexität bis heute offen ist.

Prüfung

Die erste Klausur fand am 28.02.2019 statt (Ergebnisse), die Nachklaursur am 02.04.2019 (Ergebnisse, Einsicht (auch der ersten Klausur): 9.4.2019 ab 12.45Uhr in RUD26 1'306) statt, Dauer (reine Klausurzeit) jeweils 120min (mit Einlass,Fragen,Abgabe etc. ca. 180min). Erlaubte Hilfsmittel sind das Skript sowie (auch gedruckte) eigene Notizen. Hingegen sind Bücher und elektronische Hilfsmittel (Taschenrechner, Handy, Smartwatch etc.) nicht zugelassen. Sie benötigen einen gültigen amtlichen Lichtbildausweis zur Klausur, ein Foto auf der CampusCard genügt nicht. Bitte bringen Sie Schreibpapier mit, es ist zur Not nur weißes Kopierpapier vorhanden.

Achtung: im WiSe 2019/2020 wird die Einführung in die Theoretische Informatik von Prof. Stefan Kratsch gehalten. Bei den Prüfungen im WiSe2019/20 sind keine Hilfsmittel zulässig. Details entnehmen Sie dem Moodle-Kurs.

Empfohlene Literatur

Blum: Theoretische Informatik. Oldenbourg 1998.
Garey, Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.
Hoffmann: Theoretische Informatik. Hanser 2009.
Hopcroft, Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison Wesley, 1994.
Lewis, Papadimitriou: Elements of the Theory of Computation. Prentice-Hall, 1981.
Motwani, Raghavan: Randomized Algorithms. Cambridge University Press, 1995.
Papadimitriou: Computational Complexity. Addison-Wesley, 1994.
Rich: Automata, Computability, and Complexity. Pearson Prentice Hall, 2008.
Schöning: Perlen der Theoretischen Informatik. BI-Wissenschaftsverlag, 1995.
Schöning: Theoretische Informatik - kurz gefaßt. Spektrum Akademischer Verlag, 2008.
Sipser: Introduction to the Theory of Computation. PWS Publishing Company, 2006.
Wagner: Einführung in die Theoretische Informatik, Grundlagen und Modelle. Springer Verlag, 1994.
Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung. Teubner Verlag, 1999.
Harry Mairson : The Pumping Lemma (poem)

Aufgabenblätter (Abgabe dienstags vor der VL bis 15.10 Uhr im Hörsaal, eine frühere Abgabe ist bis Montag in RUD25, 4.014 oder 3.317 möglich)

Blatt 1
Blatt 2
Blatt 3
Blatt 4
Blatt 5
Blatt 6
Blatt 7
Blatt 8
Blatt 9
Blatt 10
Blatt 11
Blatt 12
Blatt 13
Blatt 14
Blatt 15
Probeklausur

Folien

Organisatorisches, Einleitung und reguläre Sprachen

Kontextfreie Sprachen (Beispiel: Umwandlung PDA -> PDA mit einem Zustand)

Kontextsensitive Sprachen

Entscheidbare und semientscheidbare Sprachen

Komplexität

Skript

aktuelles Skript
Skript von 2017/18

Lehrevaluation

Die Token werden in der Vorlesung am 15.1. bzw. in den Übungen vom 15.1. bis 18.1. ausgeteilt. Der Fragebogen kann bis einschließlich 27.1. ausgefüllt werden.
Evaluation der Vorlesung
Evaluation der Übung