Vorlesungen Einführung in die theoretische Informatik Diskrete Wahrscheinlichkeitstheorie Grundlagen: Algorithmen und Datenstrukturen Effiziente Algorithmen und Datenstrukturen II Online- und Approximationsalgorithmen Komplexitätstheorie Proseminar Graph Drawing Seminar / Masterseminar Approximationsalgorithmen Energieeffiziente Algorithmen Praktikum Algorithmen für Programmierwettbewerbe Lehrveranstaltungen für Doktoranden Oberseminar

Übung zu Komplexitätstheorie

Ankündigungen:

• Übungsblatt 0 wird in der ersten Übung am 10.04.2014 besprochen, eine Abgabe ist nicht vorgesehen. Die Übungen mit Abgabe starten am 14.4.2014.

Allgemeine Informationen:

• Übungsleitung:
  Chris Pinkau
• Zeit und Ort:
  Do, 12:30–14:00, Raum 03.11.018
• Sprechstunde:
  Di, 13:00–14:00, Raum 03.09.057, und nach Vereinbarung.

Übungsblätter und Lösungen:

• Übungsblatt 0 – Lösungsblatt 0
• Übungsblatt 1 – Lösungsblatt 1
• Übungsblatt 2 – Lösungsblatt 2
• Übungsblatt 3 – Lösungsblatt 3
• Übungsblatt 4 – Lösungsblatt 4
• Übungsblatt 5 – Lösungsblatt 5
• Übungsblatt 6 – Lösungsblatt 6
• Übungsblatt 7 – Lösungsblatt 7
• Übungsblatt 8 – Lösungsblatt 8
• Übungsblatt 9 – Lösungsblatt 9
• Übungsblatt 10 – Lösungsblatt 10
• Lösungen der Klausur

Sonstiges:

• Der Beweis vom Satz von Baker, Gill, Solovay etwas anders erklärt
• Big picture: Überblick einiger bekannten Komplexitätsklassen (wird fortlaufend aktualisiert)
• Überblick der wichtigsten Reduktionen
• Googles doodle für Alan Turing
•  
• Theoretical Computer Science Cheat Sheet
• The On-Line Encyclopedia of Integer Sequences
• History of Mathematics