Grundlagen der Theoretischen Informatik II

Sommersemester 2012

Lehrbeauftragter: Prof. Dr. Jürgen Dassow
Wochenstunden: 2+2+0
Zuhörerkreis: Bachelor Inf, 4. Semester
Voraussetzungen: Grundlagen der Theoretischen Informatik I
Prüfung: durch Klausur, 120 Minuten, in der Prüfungszeit nach dem Semester
Unbenoteter Schein: durch Klausur in der Prüfungszeit nach dem Semester
Klausuranmeldung: über das Onlineportal HISQIS ( bis zum 30. Juni 2012)

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.

Zulassung zur Klausur: 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 Zulassung zur Klausur sind folgende Leistungen zu erbringen:

Den Studenten, die die Zulassung zur Klausur erworben haben, ist das per E-Mail bestätigt worden. Im Zweifelsfalle wenden Sie sich bitte an Ihren Übungsleiter.

Klausur: Die Klausur findet am Freitag, dem 3. August 2012, im Hörsaal 5 im Gebäude 16 von 12:00 bis 14:00 Uhr statt.
Damit pünktlich begonnen werden kann, sind die Plätze spätestens 15 Minuten vor Beginn einzunehmen.
Es sind keine Hilfsmittel zugelassen, Papier und Schreibutensilien sind mitzubringen.

Informationen:

Literatur: Siehe erste Folie.

Skript: Teil 4, Teil 5

Folien: Teil 1, Teil 2, Teil 3, Teil 4, Teil 5

Übungsblätter:

Zur Lehreseite der Forschungsgruppe Theoretische Informatik

Webmaster