Perlen der Informatik Sommersemester 2014

Neuigkeiten | Termine | Inhalt | Folien | Übungen | Literatur

18.6.2014

Übungsblatt 2 ist jetzt online.

12.05.2014

Hausaufgabe 3 (ILP) in Blatt 1 hat sich geändert. Lösungen sollen nicht-negativ sein, die Koeffizienten können negativ sein.

07.05.2014

In der Vorlesung wurden folgende Inhalte betrachtet:

• Begriff der Reduktion: Problem A läst sich auf Problem B reduzieren, wenn es einen Transducer oder Übersetzer gibt, der in polynomieller Zeit läuft, und eine "ja"- bzw. "nein"-Instanz von A in eine "ja"- bzw. "nein"-Instanz von B übersetzt.
• Reduktion von 3SAT auf Knotenüberdeckung (vertex cover). Siehe z.B. hier
• Reduktion von SAT auf 3SaT (Konstruktion von Tseitin). Siehe z.B. den Artikel "Tseitin transformation" in Wikipedia.

29.04.2014

Handgeschriebene Notizen von heute finden Sie hier und hier.

15.04.2014

Die Folien über Schaltkreise finden Sie hier.

17.03.2014

Erstellung der Webseite. Unter "Inhalt" findet man einige Informationen zur Vorlesung.