Grundlagen der Theoretischen Informatik II für IF

Sommersemester 2010

Prüfung: Sie findet am Freitag, dem 16. Juli 2010, von 08:00 bis 10:00 Uhr im Gebäude 26, Hörsaal 1 statt. Die Plätze sind bis spätestens 07:45 Uhr einzunehmen.
Um an der Prüfung teilnehmen zu können, muss man die Zulassung zur Prüfung erworben haben und zur Prüfung angemeldet sein.
Es sind keine Hilfsmittel zugelassen, Papier und Schreibutensilien sind mitzubringen.

Prüfungszulassung: Über die Zulassung zur Prüfung haben alle Studierenden eine E-Mail an die E-Mail-Adresse bekommen, mit der sie sich zur Vorlesung angemeldet hatten.
Für die Studenten, die die Zulassung bereits aus einer vorherigen Vorlesung hatten, behält die Zulassung natürlich ihre Gültigkeit.

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.

Skript: Teil 6, Teil 7, Teil 8

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

Übungsblätter:

• Blatt 1 (14. KW), Blatt 2 (15. KW), Blatt 3 (16. KW), Blatt 4 (17. KW), Blatt 5 (18. KW), Blatt 6 (19./20. KW), Blatt 7 (20./21. KW)
• Blatt 8 (22. KW), Blatt 9 (23. KW), Blatt 10 (24. KW), Blatt 11 (25. KW), Blatt 12 (26. KW)

Informationen:

• Die Wiederholungsklausur der Grundlagen der Theoretischen Informatik I findet am Dienstag, dem 20. Juli 2010, im Raum G16-H5 von 08:00 bis 10:00 Uhr statt.
  Die Plätze sind spätestens 07:45 Uhr einzunehmen.

Stundenplan laut Univis