Direkt zum InhaltDirekt zur SucheDirekt zur Navigation
▼ Zielgruppen ▼

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

Vorlesung: Einführung in die Theoretische Informatik

Beginn der Vorlesung: 3.11.2020

Beginn der Übungen: vsl. 3.11.2020

Beginn der Tutorien: noch offen

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

Moodle-Kurs: wird noch angegeben eintragen--> (Passwort per Mail über Agnes).


Termine

VL Di 15-17 J. Köbler
VL Do 15-17 J. Köbler
UE Di 09-11 IMP F. Fuhlbrück
UE Di 11-13 R. Bredereck
UE Di 13-15 F. Fuhlbrück
UE Mi 09-11 F. Nelles
UE Mi 13-15 F. Nelles
UE Do 13-15 R. Bredereck
UE Fr 09-11 F. Hegerfeld
UE Fr 11-13 F. Hegerfeld

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

Klausur über 120 min, genaues Format und Datum der Prüfungen werden noch bekannt gegeben.

 

 


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)

aktuelle Folien

Skript

Skript von 2018/19

Folien von 2018/19

Organisatorisches, Einleitung und reguläre Sprachen

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

Kontextsensitive Sprachen

Entscheidbare und semientscheidbare Sprachen

Komplexität

 

Alte Probeklausuren