Die Prüfung wird durch eine Klausur in der Prüfungszeit nach dem Semester abgeleistet.
Sie findet am Freitag, dem 25. Juli 2008, von 10:30 bis 12:30 Uhr im Gebäude 26, Hörsaal 1 statt.
Die Plätze sind bis spätestens 10:20 Uhr einzunehmen!
Eine Einsichtnahme der Klausuren ist zu folgenden Zeiten möglich:
Donnerstag, 18. September 2008, 14:00 bis 15:00 Uhr im Raum G29-011
Dienstag, 21. Oktober 2008, 11:00 bis 11:30 Uhr im Raum G29-011
Prüfungszulassung:
Zu den Übungen gibt es Übungsblätter. Es müssen zu Beginn jeder Übung Aufgaben votiert
werden. Damit zeigt die/der Studierende dem Übungsleiter, dass sie/er bereit ist,
bei Aufforderung zu den votierten Aufgaben vorzutragen
(Lösungsvorschläge werden diskutiert, sie müssen nicht gleich perfekt richtig sein!).
Für die Prüfungszulassung sind folgende Leistungen zu erbringen:
Mindestens 2/3 der Übungsaufgaben (also 66%) müssen am Ende des Semesters votiert worden sein.
Mindestens dreimal pro Semester muss man in den Übungen vorgetragen haben.
Inhalt:
Weitere Modelle der Berechenbarkeit (partiell-rekursive Funktionen, Registermaschinen)
und der Nachweis ihrer Äquivalenz zu Turing-Maschinen; Entscheidungsprobleme bei
formalen Sprachen; Operationen auf formalen Sprachen; Minimierung endlicher Automaten;
Approximation NP-vollständiger Probleme.