Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Vorlesung: Einführung in die Theoretische Informatik

Beginn der Vorlesung: 18.10.2022

Beginn der Übungen: 25.10.2022

Eintragen über: UE in Agnes bzw. UE (ÜWP) in Agnes

Moodle-Kurs: eintragen (Passwort in der VL und per Mail über Agnes, ca. am 14.10.)

Korrektor*innen (Kontakt per Mail oder Moodle): T. Berholdt, D. Ketels, T. Lantzsch, M. Lindner, Y. Verbitsky (Mail an alle)


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 digital F. Fuhlbrück
UE Di 13-15 RUD 26, 1'306 F. Fuhlbrück
UE Mi 09-11 digital L. Antipov
UE Mi 13-15 RUD 26, 1'306 L. Antipov
UE Do 09-11 RUD 26, 1'306 N. Bojikian
UE Do 13-15 RUD 26, 1'306 N. Bojikian
UE Fr 09-11 RUD 26, 0'313 F. Hegerfeld
UE Fr 11-13 RUD 26, 0'313 F. Hegerfeld
TU Mi 13-15 RUD 26, 0'310 T. Bertholdt, T. Lantzsch, M. Lindner
TU Do 17-19 RUD 26, 1'306 T. Bertholdt, T. Lantzsch, M. Lindner

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 02.03.2023 statt (Ergebnisse; Einsicht: 13.3.2023 ab 11 Uhr in RUD 26, 1'303 und 1'304), die Nachklaursur am 11.04.2023 (Ergebnisse, Einsicht (auch der ersten Klausur): 25.4.2023 ab 12.55Uhr in vsl. RUD 26 0'313). Dauer (reine Klausurzeit) ist 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 (z.B. kariertes) Schreibpapier mit, es ist zur Not nur weißes Kopierpapier vorhanden. Die Aufteilung der Räume wird jeweils erst am Klausurtag vor Ort bekannt gegeben, bitte erscheinen Sie spätestens zu Beginn des Einlasses vor Raum 0'115 im ESZ (RUD 26). Der Anmeldezeitraum für die erste Klausur ist 16.01.-29.01.2023 (Rücktritt bis 23.02.2023), für die zweite Klausur 06.03.-19.03.2023 (Rücktritt bis 04.04.2023). Falls Sie die Prüfungszulassung im WiSe 2022/23 erwerben, aber bis 29.01.2023 noch nicht genügend Punkte haben, melden Sie sich bitte trotzdem bereits an, wenn Sie mitschreiben möchten.


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
Blatt 15
Probeklausur (Lösungsvorschläge)

Skript

Aktuelles Skript

Skript vom Wintersemester 2020/21

Aktuelle Folien

Organisatorisches
Reguläre Sprachen
Kontextfreie Sprachen
Kontextsensitive Sprachen
Entscheidbare und semientscheidbare Sprachen
Komplexität

Folien vom Wintersemester 2020/21

Organisatorisches
Reguläre Sprachen
Kontextfreie Sprachen
Kontextsensitive Sprachen
Entscheidbare und semientscheidbare Sprachen
Komplexität

Alte Probeklausuren