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: 18.10.2017

Beginn der Übungen: 17.10.2017

Beginn der Tutorien: 18.10.

Eintragen über: VL in Agnes

Zuordnung zu den Terminen: im Moodle-Kurs (Passwort in der VL am 18.10. sowie am 16.10. per Mail über Agnes).


Termine

VL Mo 15-17 RUD 26, 0'115 J. Köbler
VL Mi 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 09-11 RUD 26, 1'303 F. Nelles
UE Do 15-17 RUD 26, 1'306 F. Nelles
UE Fr 09-11 RUD 26, 1'306 L. Heimberg
UE Fr 11-13 RUD 26, 1'306 L. Heimberg
TU Di 13-15 RUD 26, 1'308 R. Enseleit
TU Mi 17-19 RUD 26, 1'303 R. Enseleit

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 findet am 23.2.2018 statt (Einlass: 12:00 Uhr, Beginn 12.30 Uhr, Dauer: 120min, Räume: RUD 26, 0'115 und 0'110). Dazu gibt es am 21.2. ab 9.30Uhr in RUD26 0'307 eine Fragestunde. Die Nachklausur findet am 28.3.2018 statt (Einlass: 9:00 Uhr, Beginn 9.30 Uhr, Dauer: 120min, Raum: RUD 26, 0'115)
Erlaubte Hilfsmittel sind das Skript sowie (auch gedruckte) eigene Notizen. Hingegen sind Bücher und elektronische Hilfsmittel (Taschenrechner, Handy, Smartwatch etc.) nicht zugelassen.

 


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 mittwochs vor der VL bis 15.10 Uhr im Hörsaal)

Blatt 0
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

 

Alte Probeklausuren

 

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 2016/17

Lehrevaluation

Die Token werden in der Vorlesung am 24.1. bzw. in den Übungen vom 23.1. bis 26.1. ausgeteilt. Der Fragebogen kann bis einschließlich 1.2. ausgefüllt werden.
Evaluation der Vorlesung
Evaluation der Übung