Vorlesung Theoretische Informatik 2: Berechenbarkeit und Komplexität, SS 2023

Quick links

Wir haben jede Woche eine Umfrage, wie Sie die Vorlesung, das Tutorium und das Übungsblatt finden. Einsendeschluss ist jeweils Donnerstag Abend, in Ilias. Die Umfrage ist anonym, wir können nicht sehen, wer welche Antworten gibt.


Wann, wo, wie

  • Vorlesung (Prof. U. von Luxburg): Di 12:15-14:00 Hörsaal N7, Hörsaalzentrum Morgenstelle; Do 10:15-12:00, Hörsaal N7, Hörsaalzentrum Morgenstelle;
  • Übungsgruppen werden koordiniert von Solveig Klepper. Sie starten in der dritten Semesterwoche. Registrierung zu den Übungsgruppen über Ilias bis Mittwoch 15:00 Uhr. Die Zuteilung erfolgt dann Freitag den 28.04.2023.
  • Anmeldung zur Vorlesung ueber Ilias bis spaetestens zum Semesteranfang.

Materialien zur Vorlesung

Informationen zur Vorlesung und Klausurzulassung

Folien

  • Aktuelle Version (last updated 2023-05-23) aktuelle Version der Folien
  • Aus dem letzten Jahr stammen folgende handgeschriebene Folien von mir: pdf (Achtung, 190 MB).
  • Die gleichen Folien als getippte Version (koennten aber noch Fehler enthalten, da ich sie jetzt zum ersten mal benutze): pdf

Probeklausur

Hier finden Sie die Probeklausur vom 25.05.2023.

Videos

... aus dem letzten Jahr sind in dieser youtube playlist.

Übungsblätter

Abgabe immer bis Sonntag Abend, 23:59 elektronisch auf Ilias.

Namen und Kontakt zu den Tutoren

Klausuren

Der Termin der ersten Klausur steht fest, es ist der 1.8. von 11:30-13:30, an der Morgenstelle. Der Termin der zweiten Klausur wird im Oktober sein (Termin wird noch bekannt gegeben).
Am 25.5. wird es eine Probeklausur in der Vorlesung geben. Teilnahme ist freiwillig.

Literatur

  • Der erste Teil der Vorlesung wird aufgebaut auf Sipser: Introduction to the Theory of Computation. Als deutsche Lehrbuecher verwenden wir Hromkovic: Theoretische Informatik und Schöning: Theoretische Informatik kurz gefasst.
  • Ein weiteres gutes Buch (noch als Draft) ist Introduction to Theoretical Computer Science von Boaz Barak. Hier ist der link zum Buch.
  • Der zweite Teil der Vorlesung benutzt auch: Arora, Barak: Computational Complexity: A Modern Approach. Das Buch ist super und elegant, aber geht deutlich ueber unseren Stoff hinaus.
  • Ein populärwissenschaftliches Buch, dass gut zum Thema unserer Vorlesung passt, ist "Gödel, Escher, Bach" von Douglas Hofstadter. Will ich Ihnen ans Herz legen, zumindest hat es mich als Studi fasziniert.

Sie brauchen Unterstützung?


Fragen? Kommentare? Anregungen?

Wir wollen wissen, was Ihnen an der Veranstaltung gefällt und was Ihnen nicht gefällt. Dazu gibt es ein woechentliches Feedback-Formular in Ilias. Wenn Sie das aus irgendeinem Grund nicht benutzen wollen, können Sie auch unser anonymes Feedback-Formular benutzen. Je konstruktiver die Kritik, desto höher die Chance, dass wir darauf eingehen.