Algorithms and Complexity - Main page Algorithms and Complexity

Vorlesung: Theoretische Informatik 2

Dozent: T. Nierhoff

Termine

Beginn der Vorlesung: 16.10.2002
Beginn der Übung: 21.10.2002
VL Mittwoch 10:00 - 12:00 (UL 6, 3038)
Freitag 10:00 - 12:00 (UL 6, 2091/92)
UE Mittwoch 12:00 - 14:00 (DOR 24, 207) T. Nierhoff
Mittwoch 12:00 - 14:00 (DOR 24, 407) M. Behrisch
Mittwoch 12:00 - 14:00 (DOR 24, 409) D. Osthus
Mittwoch 14:00 - 16:00 (DOR 24, 407) M. Behrisch
Mittwoch 14:00 - 16:00 (DOR 24, 409) D. Osthus, Übung für Fortgeschrittene
Freitag 08:00 - 10:00 (DOR 24, 205) J. Böttcher, Basisübung
Freitag 10:00 - 12:00 (DOR 24, 407) M. Füssel, Basisübung

Zuordnung

  • Grundstudium, 3. Semester

Voraussetzungen

  • Theoretische Informatik 1

Inhalte und Lernziele

Teil I: Chomsky-Hierarchie
  1. Turingmaschinen
  2. Entscheidbarkeit
  3. Grammatiken
  4. Reguläre Sprachen
  5. Kontextfreie Sprachen
Teil II: Elementare Strukturen und Algorithmen
  1. Graphen
  2. Greedy-Algorithmen
  3. Dynamische Programmierung

Lernziele: Selbständige Lösungsfindung, schlüssige Argumentation, saubere Dokumentation

Folien

  • VL 18.10. (Definitionen Turingmaschine) ps pdf
  • VL 23.10. (Definitionen Sprachen) ps pdf
  • VL 30.10. (Definitionen Reduktionen) ps pdf
  • VL 06.11. (Regeln H < MPKP) ps pdf
  • VL 20.11. (Grammatik aus Satz 3.1) ps pdf

Übungen

Leiter: Dr. T. Nierhoff, M. Behrisch, D. Osthus, J. Böttcher und M. Füssel.

In den Übungen kann ein Übungsschein "Theoretische Informatik 2" erworben werden. Voraussetzung ist das Erreichen von mindestens 50% aller möglichen Punkte in den Übungsaufgaben.

Jeder Teilnehmer der Vorlesung muss sich über Goya in einer der Übungen anmelden.

Es gibt differenzierte Übungen: zwei Basisübungen und eine Übung für Fortgeschrittene. In allen Übungen werden die Übungsaufgaben besprochen und Fragen beantwortet. Die Differenzierung dient lediglich dazu, den Stand der Vorkenntnisse in den einzelnen Gruppen zu homogenisieren. Ähnlich wie in der Theorie 1 sollten Studierende mit verkürzter, lückenhafter oder lange zurückliegender Mathematikausbildung bevorzugt eine der Basisgruppen wählen und Studierende mit Spezial- oder außerunterrichtlicher Mathematikausbildung oder auch mit Hauptfach Mathematik die Übung für Fortgeschrittene wählen.

Die Übungsaufgaben werden jede Woche am Ende der Mittwochsvorlesung ausgeteilt. Sie sollen innerhalb von einer Woche in Arbeitsgruppen von bis zu drei Studierenden bearbeitet werden. Die Abgabe erfolgt zu Beginn der nächsten Mittwochsvorlesung bis 10:10 Uhr.

Achtung: Nach 10:10 Uhr werden keine Abgaben mehr angenommen! Sie sollten also pünktlich abgegeben werden, wenn sie bewertet werden sollen. Abgaben können auch vor diesem Termin im Sekretariat, 3.320, RUD 25, oder per Email (Postscript-Datei) an den Übungsleiter/die Übungsleiterin erfolgen.

Empfohlene Literatur

  • Cormen, Leiserson, Rivest, Introduction to Algorithms, McGraw-Hill, 1990.
  • Emden-Weinert, Hougardy, Kreuter, Prömel, Steger, Einführung in Graphen und Algorithmen, Vorlesungsskript, 450 Seiten, Berlin 1996.
  • Hopcroft, Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 1979.
  • Hougardy, Prömel, Graphen und Algorithmen 1, Vorlesungsskript, Berlin 2000.
  • Köbler, Theoretische Informatik II, Vorlesungsskript, Berlin 2000.
  • Papadimitriou, Complexity Theory, Addison Wesley, 1994.
  • Schöning, Theoretische Informatik - kurz gefaßt, Spektrum Akademischer Verlag, 1997.
  • Steger, Diskrete Strukturen 1, Springer Verlag, 2001.
  • Wegener, Theoretische Informatik, Teubner Verlag, 1993.

Prüfung

Übungsklausur
Diese Übungsklausur hat rein fakultativen Charakter: Alle Teilnehmer sind eingeladen sie zu bearbeiten und ihre Lösung bei ihrem Übungsleiter abzugeben, um ein Feedback über ihren Stand zu erhalten. Die erzielten Punkte haben aber mit dem Scheinerwerb nichts zu tun.
ps, pdf
Klausuren
1. Klausur: 15.02.03, 9-13, Audimax
2. Klausur: 07.04.03, 12-16, Audimax
3. Klausur: 20.06.03, 15-19, RUD25, 3.001
Die Klausuren können noch bis zum 8. August in Raum 3.320 eingesehen werden.
last modified 09/23/09 (alkox-www)