Algorithmen und Komplexität - Hauptseite Algorithmen und Komplexität

Vorlesung: Theoretische Informatik II

Dozent: A. Taraz

Termine

Beginn der Vorlesung: 17.10.2001
Beginn der Übung: 24.10.2001
VL Mittwoch 14:00 - 16:00 (UL 6, 3038)
Freitag 09:00 - 11:00 (UL 6, 3094)
UE Mittwoch 10:00 - 12:00 (DOR 24, 310) Dr. T. Nierhoff
Mittwoch 10:00 - 12:00 (DOR 24, 403) M. Thimm
Mittwoch 12:00 - 14:00 (DOR 24, 310) Dr. T. Nierhoff
Mittwoch 12:00 - 14:00 (DOR 24, 403) M. Thimm
Mittwoch 12:00 - 14:00 (DOR 24, 405) Dr. A. Taraz
Freitag 08:00 - 10:00 (DOR 24, 309) Dr. A. Coja-Oghlan
Freitag 12:00 - 14:00 (DOR 24, 403) Dr. A. Taraz

Zuordnung

  • Grundstudium, 3. Semester

Inhalte und Lernziele

Die VL stellt verschiedene Gebiete der Theoretischen Informatik vor. Hierbei handelt es sich insbesondere um Automatentheorie und formale Sprachen. Ergänzend werden Themen der Berechenbarkeit und Algorithmik behandelt. Im Zentrum der VL stehen die Begriffe der NP-Vollständigkeit, der Effizienz von Algorithmen und Datenstrukturen. Es werden erste algorithmische Prinzipien zur approximativen oder randomisierten "Lösung" NP-vollständiger Probleme vorgestellt.

Folien

Übungen

Leiter: Dr. T. Nierhoff, M. Thimm, Dr. A. Taraz und Dr. A. Coja-Oghlan

Begleitend zur Vorlesung wird wöchentlich eine Übungsstunde angeboten, in der die gestellten Aufgaben besprochen werden.
Die Übungen sollten in Zweier- oder Dreiergruppen bearbeitet werden. Die Abgabe erfolgt zu Beginn jeder Übungsstunde.

  • Übungsblatt 1: Aufgaben 1-4, ps, pdf
  • Übungsblatt 2: Aufgaben 5-8, ps, pdf
  • Übungsblatt 3: Aufgaben 9-12, ps, pdf
  • Übungsblatt 4: Aufgaben 13-16, ps, pdf
  • Übungsblatt 5: Aufgaben 17-20, ps, pdf
  • Übungsblatt 6: Aufgaben 21-24, ps, pdf
  • Übungsblatt 7: Aufgaben 25-28, ps, pdf
  • Übungsblatt 8: Aufgaben 29-32, ps, pdf
  • Übungsblatt 9: Aufgaben 33-36, ps, pdf
  • Weihnachtsserie, ps, pdf
  • Übungsblatt 10: Aufgaben 37-40, ps, pdf
  • Übungsblatt 11: Aufgaben 41-44, ps, pdf
  • Übungsblatt 12: Aufgaben 45-48, ps, pdf
  • Übungsblatt 13: Aufgaben 49-52, ps, pdf
  • Übungsklausur, ps, pdf

Empfohlene Literatur

  • 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.
  • Hopcroft, Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 1979
  • Köbler, Theoretische Informatik II, Vorlesungsskript, Berlin 2000.
  • 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

Anmeldung
Für diejenigen Studierenden, die genügend Punkte in den Hausaufgaben erzielt haben aber nicht zur Klausur zugelassen worden sind, weil sie in den Übungen nicht vorgerechnet haben, besteht die Möglichkeit der Anfertigung einer schriftlichen Hausaufgabe. Interessierte Studierende melden sich bitte per email bis 22. April bei Anusch Taraz.
Klausur
Klausurzulassung, ps, pdf
Ergebnisliste
Die Klausuren können am 9. April von 13 Uhr bis 15 Uhr in Raum 3.320, RUD 25, eingesehen werden.
Nachklausur am 7.6.2002
Die Nachklausur findet am 7. Juni 2002, 15 Uhr, Hörsaal 3.001 RUD 25 statt.
Klausurzulassung, ps, pdf
Ergebnisliste, ps, pdf
zuletzt geändert am 23.01.2006 (alkox-www)