Theoretische Informatik 2

Vorlesung im SoSe 2012

Gehalten von Prof. Dr. Nicole Schweikardt
Betreuung der Übungen durch Dipl.-Inf. Joachim Bremer, M.Sc. Frederik Harwath

Aktuelles

 Im Logbuch finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.

Einführung

Die Vorlesung befasst sich mit Automaten und formalen Sprachen und gliedert sich im Wesentlichen in vier Teile: Charakterisierungen der regulären Sprachen durch deterministische und nichtdeterministische endliche Automaten sowie durch reguläre Ausdrücke werden als äquivalent nachgewiesen. Es werden Verfahren zur Minimierung endlicher Automaten entwickelt. Mit dem Pumping-Lemma werden die Grenzen der regulären Sprachen aufgezeigt.
Die kontextfreien Sprachen werden über kontextfreie Grammatiken eingeführt und anhand von Syntaxbäumen veranschaulicht. Pumping-Lemmata, Normalformen und Abschlusseigenschaften der kontextfreien Sprachen werden behandelt, und das Wortproblem für kontextfreie Sprachen wird algorithmisch gelöst. Es wird gezeigt, dass die kontextfreien Sprachen auch durch Kellerautomaten definiert werden können.
Im Anschluss daran wird die Chomsky-Hierarchie eingeführt und es werden insbesondere kontextsensitive Grammatiken und linear beschränkte Automaten betrachtet.
Als weiterführende Themen stehen u.A. zur Auswahl: Baumautomaten, erweiterte Grammatik-Modelle (z.B. programmierte Grammatiken), platzbeschränkte Komplexitätsklassen (z.B. PSPACE, LOGSPACE), Pattern-Matching-Algorithmen.

Kürzel laut Studienordnung: B-GL2.  Creditpoints: 8.  SWS: 3V, 2Ü.

Inhalte

Skript

Logbuch

 Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, die in der Vorlesung verwendeten Folien und gelegentlich ergänzende Bemerkungen.

E-Lectures

 Im Sommersemester 2012 wurden die Vorlesungen von studiumdigitale, der E-Learning-Einrichtung der Goethe-Universität, auf Video aufgezeichnet. Die einzelnen Aufzeichnungen finden Sie hier:

Termine
ZeitOrtLeitung
Vorlesung Donnerstag 8:15-11:00
(vom 12.04.-12.07.)		 Magnus-Hörsaal in der Informatik, Robert-Mayer-Str. 11-15 Prof. Dr. Nicole Schweikardt
Übung 1 Montag 14:00-15:30
(vom 16.04.-09.07.)		 NM 123, Neue Mensa Alexander Adler
Übung 2 Dienstag 12:15-13:45
(vom 17.04.-10.07.)		 NM 117, Neue Mensa Oguz Tuna
Übung 3 Mittwoch 12:15-13:45
(vom 18.04.-11.07.)		 AfE 102a, Robert-Mayer-Str. 5-7 Christoph Burschka
Übung 4 Donnerstag 12:15-13:45
(vom 19.04.-12.07.)		 NM 125, Neue Mensa Hannes Seiwert

Übungsblätter

Es wird regelmäßige Übungsaufgaben geben. Die Teilnahme an den Übungsstunden und das Bearbeiten der Übungsaufgaben ist für das Verständnis der Vorlesung und eine erfolgreiche Prüfung unbedingt empfohlen. Insbesondere kann durch die in den Übungen gesammelten Punkte ein Bonus für die Klausur erworben werden (Details siehe Klausur).

Das aktuelle Übungsblatt ist jeweils spätestens donnerstags nach der Vorlesung an dieser Stelle zu finden und wird außerdem donnerstags in gedruckter Form am Ende der Vorlesung ausgeteilt. Die Abgabe der bearbeiteten Übungsaufgaben erfolgt in der jeweils darauf folgenden Woche donnerstags, bis spätestens 8:14 Uhr vor Beginn der Vorlesung. Achtung: Auf dem abgegebenen Übungsblatt müssen Name, Matrikelnummer und Übungsgruppe vermerkt sein. Mehrseitige Abgaben sind zusammenzuheften. Die Abgabe erfolgt in Papierform (eine elektronische Abgabe ist aus logistischen Gründen leider nicht möglich).

Obwohl es sicherlich sinnvoll ist, über die Aufgaben mit Kommilitonen/innen gemeinsam zu reden und nachzudenken, sollte jede/r Student/in seine eigene Lösung aufschreiben und abgeben.

Anleitung für die Übungsgruppen-Anmeldung im LSF

 Falls Sie an den Übungen teilnehmen wollen, müssen Sie sich über HIS-LSF bis Freitag, 13.04.2012, 11:59 Uhr (Vormittag) für die Übung anmelden.
Zur Anmeldung für die Übungen verfahren Sie am besten wie folgt:

Klausur
Termin:
Die Klausur (160 Minuten als Modulabschlussprüfung für "Theoretische Informatik 2" (neue Studienordnung) bzw. 180 Minuten als benotete Studienleistung für "Formale Sprachen und Berechenbarkeit" (alte Studienordnung)) findet am Mittwoch, den 25.07.2012 von 9:00 bis 12:00 Uhr in Hörsaal V (Jügelhaus) statt.
Die Nachklausur findet am Donnerstag, den 11.10.2012 von 9:00 bis 12:00 Uhr in Hörsaal V (Jügelhaus) statt.
Anmeldung:
Zur Teilnahme an der Klausur ist eine vorherige Anmeldung erforderlich.

Studierende der Studiengänge Bachelor-Informatik nach PO 06.12.2010 (neue Studienorordnung) und Bachelor-Bioinformatik melden sich bitte (1) im Prüfungsamt Informatik und (2) per E-Mail bei Frederik Harwath mit dem Betreff "Klausuranmeldung" und den folgenden Informationen an: Name, Vorname, Matrikelnummer, Geburtsdatum, genauer Studiengang (inkl. Studienordnung). Weitere Informationen erhalten Sie hier bzw. hier. Bitte stellen Sie sicher, dass Sie die Anmeldefristen nicht verpassen!

Studierende der Studiengänge Bachelor-Informatik nach PO 12.02.2007 (alte Studienordnung) und Diplom-Informatik melden sich bitte per E-Mail bei Frederik Harwath mit dem Betreff "Klausuranmeldung" und den folgenden Informationen an: Name, Vorname, Matrikelnummer, Geburtsdatum, genauer Studiengang (inkl. Studienordnung).

Studierende anderer Studiengänge melden sich bitte (1) ggf. beim für sie zuständigen Prüfungsamt und (2) per E-Mail bei Frederik Harwath mit dem Betreff "Klausuranmeldung" und den folgenden Informationen an: Name, Vorname, Matrikelnummer, Geburtsdatum, genauer Studiengang.
 
Benotung:
Durch die in den Übungen gesammelten Punkte kann ein Bonus für die Klausur erworben werden. Zur Benotung werden neben dem Klausurergebnis Bonuspunkte mit einem Maximalgewicht von 10% eingehen. Achtung: Die Bonuspunkte werden Ihnen für die Klausur nur unter der Bedingung gutgeschrieben, dass Sie mindestens einmal im Tutorium vorgerechnet haben.
Die Klausur ist bestanden, wenn mit dem Bonus mindestens 50% der in der Klausur erzielbaren Punkte erreicht werden.

Bei einem Ergebnis von x% aus der Klausur und y% aus den Übungen werden die folgenden Noten vergeben, wobei   z = x + (y/10):

 

Note   Prozentpunkte
1.0 95% <= z
1.3 90% <= z < 95%
1.7 85% <= z < 90%
2.0 80% <= z < 85%
2.3 75% <= z < 80%
2.7 70% <= z < 75%
3.0 65% <= z < 70%
3.3 60% <= z < 65%
3.7 55% <= z < 60%
4.0 50% <= z < 55%
 
Details zum Ablauf der Klausur:
  • Grundsätzlich gelten die in der Ordnung Ihres Studiengangs festgelegten Regelungen. Dieses hier sind nur ergänzende Hinweise.
  • Alle Klausurteilnehmer/innen müssen sich zu Beginn der Klausur durch (1) den Studierendenausweis und (2) die "Goethe-Card" oder einen Lichtbildausweis ausweisen.
  • Außer einem dokumentenechten Schreibstift sind keine weiteren Hilfsmittel zugelassen. (Insbesondere: Kein Vorlesungsskript, keine mitgebrachten Notizen, kein von Ihnen mitgebrachtes Papier, kein Taschenrechner, kein Handy. Bitte beachten Sie, dass ein während der Klausur eingeschaltetes Handy als Betrugsversuch gewertet wird.)
  • Schreibpapier wird von uns bereitgestellt.
  • Während der Klausur werden wir Ihnen als "offiziell erlaubten Spickzettel" die hier verfügbare 1-seitige Zusammenstellung von in der Vorlesung behandelten Definitionen und Resultaten zur Verfügung stellen.
  • Die Sitzordnung wird von uns festgelegt und kurz vor Beginn der Klausur bekanntgegeben.
 
Checkliste — zur Klausur müssen Sie mitbringen:
  • einen dokumentenechten Schreibstift
  • einen gültigen Lichtbildausweis (z.B. Ihre Goethe-Card oder Ihren Personalausweis)
  • Ihren Studierendenausweis (... es sei denn, Sie sind als "Schülerstudent" für die Veranstaltung angemeldet)

Literatur
[S-GL2] G. Schnitger. Skript zur Vorlesung "Formale Sprachen und Berechenbarkeit", Goethe-Universität Frankfurt am Main, Sommersemester 2011.
[S-DisMod] N. Schweikardt. Skript zur Vorlesung "Diskrete Modellierung", Goethe-Universität Frankfurt am Main, 2011. Link
[HU] J. E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
[W-Komp] I. Wegener. Kompendium Theoretische Informatik - eine Ideensammlung. Teubner, 1996.
[W-Theo] I. Wegener. Theoretische Informatik. Teubner, 1999 (2. Auflage).
[S-Theo] U. Schöning. Theoretische Informatik - kurzgefasst. Springer, 2001 (4. Auflage).
[S-Comp] M. Sipser. Introduction to the theory of computation. PWS Publishing, 1997.
zuletzt geändert: Wed Feb 12 12:38:41 2014 von Lucas Heimberg