Übungen


Übungsblätter

  1. Übung (pdf): (25.10.06/Besprechung ab 30.10.06) Endliche Automaten,
  2. Übung (pdf): (02.11.06/Besprechung ab 06.11.06) Umformung DFA in NFA, Reguläre Ausdrücke, Umformung von NFA zum regulären Ausdruck
  3. Übung (pdf): (09.11.06/Besprechung ab 13.11.06) Pumping-Lemma, Reguläre Ausdrücke, NFA
  4. Übung (pdf): (16.11.06/Besprechung ab 20.11.06) Reguläre Sprachen, Kontextfreie Sprachen
  5. Übung (pdf): (23.11.06 / Besprechung ab 27.11.06)Turing-Maschinen
  6. Übung (pdf): (30.11.06 / Besprechung ab 04.12.06) Unentscheidbarkeit, Reduktion
  7. Übung (pdf): (07.12.06 / Besprechung ab 11.12.06) Aufzählbere Sprachen, Entscheidbarkeit, Satz von Rice
  8. Übung (pdf): (15.12.06 / Besprechung ab 18.12.06) Rekursionstheorem, Turing-Reduktion, Kolmogorov-Komplexität
  9. Übung (pdf): (28.12.06 / Besprechung ab 08.01.07) Wachstumsklassen, TIME, NTIME, P, NP
  10. Übung (pdf): (12.01.07/ Besprechung ab 15.01.07) CNF, DNF, P, NP, 2-SAT, Reduktionen
  11. Übung (pdf): (19.01.07/ Besprechung ab 22.01.07) Rucksack, Partition, NP, co-NP, Reduktionen, Suchproblem von SAT
  12. Übung (pdf): (25.01.07/ Besprechung ab 19.01.07) NP-vollständigkeit, Independent Set, (Sub-) Graphisomorphie, Approximation von 3-SAT
  13. Übung (pdf): (05.02.07/ Besprechung ab 05.02.07) Reduktion und Vollständigkeit von NP und PSPACE, KURZSCHLUSS (GEO), k-Clique ist in P
  14. Übung (pdf): (08.02.07/ Besprechung ab 12.02.07) Komplexität von Spielen, Chomsky-0,1,2,3-Sprachen

Übungsgruppen
  • Gruppe 1: Mo 14-16, SR 00-006, Geb. 051 (Christoph Betz)
  • Gruppe 2: Mo 14-16, SR 03-026, Geb. 051 (Matthias Heizmann)
  • Gruppe 3: Mo 14-16, SR 02-017, Geb. 052 (Daniel Fader)
  • Gruppe 4: Di 11-13, SR 00-034, Geb. 051 (Patrick Eyerich)
  • Gruppe 5, Di 11-13, SR 03-026, Geb. 051 (Omar Hentati)
  • Gruppe 6, Di 14-16, SR 02-017, Geb. 052 (Andreas Knab)

Die Übungen bestehen aus Wochenübungsblättern und Präsenzübungsblättern. Die Teilnahme und Lösung dieser Übungen ist keine Voraussetzung zur Teilnahme an der Klausur.

Die Wochenübungsblätter sind jeden Donnerstags vor der Übung hier erhältlich. Die Aufgaben werden in der Folgewoche von den Studenten vorgerechnet. Für das Vorrechnen und die aktive Teilnahme an der Übung kann man Bonuspunkte erhalten.

Die Präsenzübungsblätter werden zu Beginn der Übung ausgeteilt und werden in der Übung gelöst und anschließend bewertet. Auf die Lösungen erhält man ebenfalls Bonuspunkte. Die Gesamtanzahl der Bonuspunkte aus einer Übung ergibt sich aus dem Maximum der mündlichen Leistung und der schriftlichen Abgabe in der Präsenzübung. In jeder Wochen können so maximal 1.000 Punkte erreicht werden.

Diese Punkte werden über das Semester addiert, anschließend skaliert und der erreichten Punkteanzahl der Klausur hinzuaddiert, falls die Klausur ohne diese Punkte bestanden wurde. Auf diese Weise kann man sich dann um bis zu einer Notenstufe in der Klausur verbessern.