Aktuelles | Skript | Logbuch | E-Lectures | Termine | Übungsblätter | Klausur | Literatur  

Theoretische Informatik 2

Vorlesung im SoSe 2014

Gehalten von Dr. Dominik D. Freydenberger
Betreuung der Übungen durch Dipl.-Inf. Joachim Bremer

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Ü.

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

Die Vorlesungen wurden von studiumdigitale, der E-Learning-Einrichtung der Goethe-Universität, auf Video aufgezeichnet und sind dort abrufbar. Direkte Links zu den einzelnen Aufzeichnungen finden Sie hier: Weitere Informationen zu den einzelnen Vorlesungen finden Sie im Logbuch.

Termine

ZeitOrtLeitung
Vorlesung Mittwoch 14:15-17:00
(vom 16.04.-16.07.)
Magnus-Hörsaal in der Informatik, Robert-Mayer-Str. 11-15 Dr. Dominik D. Freydenberger
Übung 1 Montag, 12:15-13:45 RMS 11-15, SR 307 Joachim Bremer
Übung 2 Dienstag, 12:15-13:45 RMS 11-15, SR 9 Sorin Constantinescu

Ü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 mittwochs nach der Vorlesung an dieser Stelle zu finden und wird außerdem mittwochs in gedruckter Form am Ende der Vorlesung ausgeteilt. Die Abgabe der bearbeiteten Übungsaufgaben erfolgt in der jeweils darauf folgenden Woche mittwochs, bis spätestens 14:14 Uhr vor Beginn der Vorlesung. Vorzeitig kann die Abgabe auch durch Einwurf in den Briefkasten neben Raum 114 (Robert-Mayer-Straße 11-15 1.Stock) erfolgen. Nach Beginn der Vorlesung werden keine Abgaben mehr entgegengenommen. 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.

Klausur

Termin:
Die Klausur (160 Minuten) findet am Dienstag, den 29.07.2014 von 10:00 bis 13: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 QIS/LSF-System der Goethe-Universtität und (2) per E-Mail bei Joachim Bremer mit dem Betreff "Klausuranmeldung" und den folgenden Informationen an: Name, Vorname, Matrikelnummer, 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) melden sich bitte per E-Mail bei Joachim Bremer mit dem Betreff "Klausuranmeldung" und den folgenden Informationen an: Name, Vorname, Matrikelnummer, 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 Joachim Bremer mit dem Betreff "Klausuranmeldung" und den folgenden Informationen an: Name, Vorname, Matrikelnummer, genauer Studiengang. Bei Studiengängen, bei denen wir einen schriftlichen Leistungsnachweis ausstellen (Schein), kann es sein, dass wir zusätzlich Ihr Geburtsdatum benötigen.
 
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 20% 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 + (20*y/100):

 

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%
 
Weitere Details:
Weitere Details zur Anmeldung und zum Ablauf der Klausur folgen später.

Literatur

[RS] G. Rozenberg und A. Salomaa. Handbook of Formal Languages, Vol. 1. Springer, 1997.
[S-GL2] G. Schnitger. Skript zur Vorlesung "Formale Sprachen und Berechenbarkeit", Goethe-Universität Frankfurt am Main, Sommersemester 2013. Link
[S-DisMod] N. Schweikardt. Skript zur Vorlesung "Diskrete Modellierung", Goethe-Universität Frankfurt am Main, 2013. Link
[W-Theo] I. Wegener. Theoretische Informatik. Teubner, 2005 (3. Auflage).
[S-Comp] M. Sipser. Introduction to the theory of computation. PWS Publishing, 2006 (2. Auflage).
[D-Dis] V. Diekert, M. Kufleitner, G. Rosenberger, Diskrete algebraische Methoden. De Gruyter Studium, 2013.
[S-Sec] J. Shallit. A Second Course in Formal Languages and Automata Theory. Cambridge University Press, 2008.
[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.
[S-Theo] U. Schöning. Theoretische Informatik - kurzgefasst. Springer, 2001 (4. Auflage).