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

Vorlesung: Einführung in die Theoretische Informatik

Dozent: Prof. Johannes Köbler

Beginn der Vorlesung: 14.10.2015

Beginn der Übungen: 19.10.2015


Termine:

VL
VL
UE
UE
UE
UE
UE
UE
UE
UE
UE
TU
TU
TU
TU

Mo
Mi
Mo
Mo
Mo
Di
Mi
Mi
Do
Do
Fr
Mo
Mi
Mi
Fr

15-17
15-17
9-11
9-11
13-15
11-13
9-11
9-11
9-11
11-13
9-11
13-15
13-15
17-19 (s.t.)
15-17 (s.t.)

RUD 26, 0'115
RUD 26, 0'115
RUD 26, 1'303
RUD 26, 1'303
RUD 26, 0'310
RUD 26, 1'306
RUD 26, 0'313
RUD 26, 1'303
RUD 26, 0'313
RUD 26, 0'313
RUD 26, 1'305
RUD 26, 0'313
RUD 26, 1'308
RUD 26, 0'307
RUD 26, 1'303

J. Köbler
J. Köbler
F. Fuhlbrück
wechselnd
F. Fuhlbrück
R. Prüfer
R. Prüfer
B. Grußien
W. Kössler
W. Kössler
B. Grußien
M.R. Jung
M.R. Jung
M.R. Jung
M.R. Jung

           

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 Klausur fand am 19.2.2016 statt (Ergebnisse).
Die Nachklausur fand am 22.3.2016 statt (Ergebnisse).
Die Klausureinsicht findet am Mittwoch, den 6.4.2016 von 10-12.30 Uhr im Raum RUD25 3.101 statt. Auch die erste Klausur kann noch eingesehen werden.

 


Empfohlene Literatur

  • Blum: Theoretische Informatik. Oldenbourg 1998.
  • Emden-Weinert, Hougardy, Kreuter, Prömel, Steger: Einführung in Graphen und Algorithmen, Vorlesungsskript, 450 Seiten, Berlin 1996.
  • 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 montags vor der VL bis 15.10 Uhr)

Rückgabe der Blätter erfolgt in den Übungen; dort nicht abgeholte Blätter können montags zwischen 14.45 Uhr und 15.10 Uhr im Raum RUD 25 3.321 abgeholt werden.

Blatt 1
Blatt 2
Blatt 3
Blatt 4
Blatt 5
Blatt 6
Blatt 7
Blatt 8
Blatt 9
Blatt 10
Blatt 11 (Lösung Aufgabe 81)
Blatt 12
Blatt 13
Blatt 14
Probeklausur (Lösung)
 

Alte Probeklausuren

 

Skript

 

Folien

Reguläre Sprachen
Kontextfreie Sprachen
Kontextsensitive Sprachen
Entscheidbare und Semi-entscheidbare Sprachen
Komplexität