Übungen

Anmeldung

Für die Übungsanmeldung bitte in dem entsprechenden Thread des Forums den eigenen Namen posten.
Übungen
  1. Übung (pdf): Analyse eines Automaten, Abschluss regulärer Sprachen unter Komplement und Differenz, Konstruktion von DFAs und NFAs (24.10.07)
    • Besprechung der Lösung der 1. Aufgabe (Quicktime)
  2. Übung (pdf): Umwandlung von NFA in DFA, Umwandlung NFA in regulären Konstruktion von DFAs und NFAs (31.10.07)
    • Besprechung der Lösung der 5. Aufgabe (Quicktime)
  3. Übung (pdf): Pumping-Lemma, Myhill-Nerode, reguläre Ausdrücke (07.11.07)
    • Besprechung der Lösung der 8. Aufgabe (Quicktime)
  4. Übung (pdf): Kontextfreie Grammatik, CYK, Reguläre Sprachen, Kellerautomat
    • Besprechung der Lösung der 12. Aufgabe (Quicktime)
  5. Übung (pdf): Kontextfreie Grammatik, CYK, Reguläre Sprachen, Kellerautomat
    •  Besprechung der Lösung der 16. Aufgabe (Quicktime)
  6. Übung (pdf): Turing-Maschinen
    • Lösung als pdf
  7. Übung (pdf): Berechenbarkeit und rekursive Aufzählbarkeit
    • Lösung als pdf
  8. Übung (pdf): Reduktionen, rekursive Aufzählbarkeit und Entscheidbarkeit
    • Lösung als pdf
  9. Übung (pdf): Reduktionen, Satz von Rice, rekursive Aufzählbarkeit, Entscheidbarkeit, Beschreibungskomplexität
  10. Übung (pdf): Asymptotische Wachstumsklassen, Konfigurationen einer Turing-Maschine
    • Besprechung der Lösung der 35. Aufgabe (Quicktime)
  11. Übung (pdf): NP, Polynom-Zeit-Reduktionen
    • Lösung als pdf
  12. Übung (pdf): Polynom-Zeit-Reduktionen, NP-Vollständigkeit
    • Lösung als pdf
  13. Übung (pdf): NP-Vollständigkeit, Approximationsalgorithmen
  14. Übung (pdf): PSPACE, PSPACE-Vollständigkeit
Übungsgruppen
  • Gruppe A
    • Freitag, 9-11 Uhr, SR 01-016, Geb. 101
    • Artem Remenyuk
  • Gruppe B
    • Dienstag, 11-13 Uhr, SR 02-017, Geb. 052
    • Tilman Thiry
  • Gruppe C
    • Dienstag, 11-13 Uhr, SR 00-034, Geb. 051
    • Juri Lichtner
  • Gruppe D
    • Mittwoch, 11-13 Uhr, SR 00-006, Geb. 051
    • Sebastian Sebald
  • Gruppe E
    • Mittwoch, 11-13 Uhr, SR 00-034, Geb. 051
    • Andreas Knab
  • Gruppe F
    • Mittwoch, 14-16 Uhr, SR 00-034, Geb. 051
    • Daniel Fader

Abgabe

Die Abgabe der Lösungen geschieht ausschließlich elektronisch. Hierzu erstellen Sei ein PDF-Dokument ihrer Lösung, z.B. durch LaTeX, Word, Einscannen oder Fotografieren einer handschriftlichen Lösung. Je nach Tutor erhalten Sie Ihre korrigierten Lösungen per E-Mail oder persönlich in der Übungsgruppe.
  • Mailen Sie Ihre Lösung an info3w07@informatik.uni-freiburg.de
  • Verwenden Sie als Subject: XX-G-MMMMMMM Vorname Nachname
    • XX ist die zweistellige Nummer des Übungsblatts, also 01, 02, 03,...
    • wobei G der Gruppenname ist, also A, B, C, D, E oder F
    • MMMMMMM ist die siebenstellige Matrikelnummer
    • Vorname ist Ihr Vorname
    • Nachname ist Ihr Nachname
  • Beachten Sie auch die korrekte Verwendung der Trenner: "-" und " "
  • Beispiele:
    • 01-A-1234567 Hans Moser
      • 1. Übungsblatt von Hans Moser in Gruppe A mit Matrikelnummer 1234567
    • 15-F-7654321 Groucho Marx
      • 15. Übungsblatt von Groucho Marx in Gruppe F mit Matrikelnummer 7654321
    • F-01-7654323 Harpo Marx
      • akzeptieren wir auch (für die ersten zwei Wochen, weil wir zuerst eine falsche Darstellung im Web hatten und weil Harpo so ein netter Kerl ist)
  • Falsches Format:
    • B 5 Heribert Übermut
      • 0 Punkte für Herrn Übermut wegen falschen Subject.
    • 5162474 Norbert Ärger
      • 0 Punkte für Herrn Ärger
    • B 02 1234567 Fast Richtig
      • Fast Richtig geht auch leer aus.