Vorlesung: Einführung in die Theoretische Informatik
Beginn der Vorlesung: 3.11.2020
Beginn der Übungen: 10.11.2020
Eintragen über: UE in Agnes bzw. UE (ÜWP) in Agnes
Moodle-Kurs: eintragen (Passwort per Mail über Agnes, ca. am 30.10.).
Korrektoren (Kontakt per Mail oder Moodle): N. Bojikian, H. Guo, D. Ketels, L. Kluge, T. Lantzsch (Mail an alle)
Termine
Die Vorlesung wird zu den angegebenen Zeiten per Zoom übertragen und aufgezeichnet. Die Übungen finden ebenfalls per Zoom statt, werden aber nicht aufgezeichnet, allerdings werden Materialien dazu in Moodle hochgeladen. Auf Grund der gestiegenen Infektionszahlen sind alle vormaligen Präsenzangebote nun ebenfalls digital.
VL | Di | 15-17 | digital | J. Köbler |
VL | Do | 15-17 | digital | J. Köbler |
UE | Di | 09-11 | digital, u.a. für IMP | F. Fuhlbrück |
UE | Di | 11-13 | digital | R. Bredereck |
UE | Di | 13-15 | digital | F. Fuhlbrück |
UE | Mi | 09-11 | digital | F. Nelles |
UE | Mi | 13-15 | digital | F. Nelles |
UE | Do | 13-15 | digital | R. Bredereck |
UE | Fr | 09-11 | digital | F. Hegerfeld |
UE | Fr | 11-13 | digital | F. Hegerfeld |
TU | Mi | 17-19 | digital | D. Ketels/T. Lantzsch |
TU | Do | 11-13 | digital | D. Ketels/T. Lantzsch |
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 Klausuren werden in diesem Semester als Take-Home-Klausuren stattfinden, d.h. die Aufgaben werden Ihnen per PDF in einem separaten Klausur-Moodle-Kurs zur Verfügung gestellt. Der Klausur-Kurs ist nun erstellt und alle zugelassenen Studierenden eingetragen, Sie sollten in Moodle Zugriff auf den Kurs haben (prüfen Sie diesen Direktlink). Falls nicht kontaktieren Sie uns. Sie bearbeiten dann auf Papier die Aufgaben in 120 Minuten und haben danach zusätzlich Zeit abfotografierte oder gescannte Blätter hochzuladen. Zugelassene Hilfsmittel sind das Skript sowie eigene Notizen auf Papier (gedruckt oder handschriftlich). Eine Nutzung des Internets während der Klausur ist nicht zulässig. Sie müssen vor der Klausur eine Selbständigkeitserklärung abgeben. Eine Vorlage für diese zum Ausdrucken oder Abschreiben werden sie im Klausurkurs finden. Die Ausweiskontrolle wird per Zoom erfolgen, sie benötigen einen amtlichen Lichtbildausweis (Reisepasse/Personalausweis/Führerschein), die Campuscard mit Foto genügt nicht.
Die erste Klausur findet am 09.03.2021 ab 10.00 Uhr statt. Bitte rechnen Sie mit erhöhtem Zeitaufwand und planen Sie Zeit bis 14 Uhr ein, auch wenn die reine Schreibzeit viel kürzer ist. Bitte beachten Sie, dass die Anmeldefrist in Agnes bereits am 23.02.2021 endet. Am 04.03. ab 15 Uhr wird eine technische Probe stattfinden (PDF herunterladen, abfotografiertes/gescanntes Blatt hochladen), Sie werden von uns bis dahin in den Klausur-Moodle-Kurs eingeschrieben und müssen dafür nichts selbst tun. Wir empfehlen Ihnen dringend daran teilzunehmen. Falls Sie bis zum 23.02.2021 den Übungsschein noch nicht erhalten haben, melden Sie sich bitte trotzdem an. Falls Sie den Übungsschein am Ende tatsächlich nicht erhalten werden Sie wieder abgemeldet.
Die Nachklausur wird am 07.04.2021 in demselben Modus stattfinden (Anmeldung bis 24.03.2021).
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 der schriftlichen Aufgaben jeweils bis Dienstag 23:59 per Moodle)
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
Probeklausur
Skript
Aktuelles Skript
Skript vom Wintersemester 2018/19
Aktuelle Folien
Organisatorisches
Reguläre Sprachen
Kontextfreie Sprachen
Kontextsensitive Sprachen
Entscheidbare und semientscheidbare Sprachen
Komplexität
Folien vom Wintersemester 2018/19
Organisatorisches, Einleitung und reguläre Sprachen
Kontextfreie Sprachen (Beispiel: Umwandlung PDA -> PDA mit einem Zustand)
Entscheidbare und semientscheidbare Sprachen
Alte Probeklausuren
- Wintersemester 18/19
- Wintersemester 17/18 (Lösungsvorschläge)
- Wintersemester 16/17
- Wintersemester 15/16 (Lösungsvorschläge)
- Wintersemester 14/15
- Wintersemester 13/14
- Wintersemester 12/13
- Wintersemester 11/12
- Wintersemester 09/10 (Lösungsvorschläge)
- Wintersemester 08/09 (Lösungsvorschläge)
- Wintersemester 07/08