Informationen zur Vorlesung

Einführung in
»Berechenbarkeit und Formale Sprachen«

Wintersemester 2003/04

Inhalt

Berechenbarkeit

• Turingmaschinen
• entscheidbare und rekursiv aufzählbare Sprachen
• nicht entscheidbare Probleme
• Halteproblem
• nicht rekursiv aufzählbare Probleme

Formale Sprachen

• reguläre Sprachen, reguläre Grammatiken
• deterministische, nicht-deterministische Automaten
• reguläre Ausdrücke
• Äquivalenzsatz
• Pumping Lemma
• kontextfreie Sprachen, kontextfreie Grammatiken
• Kellerautomaten
• Chomsky Normalform, Äquivalenzsatz
• CYK-Algorithmus

Termine

Vorlesung

von: Friedhelm Meyer auf der Heide
Di 11-13, Raum C1, wöchentlich

Zentralübung

von: Friedhelm Meyer auf der Heide
Fr. 11-12, Raum C1, 2-wöchentlich und bei Bedarf

Übungen

von: wiss. Mitarbeitern und studentischen Hilfskräften Matthias Fischer,  Daniel Kuntze, Norbert Sondag, Klaus Volbert

Die Übungen (Präsenzübung) finden 2-wöchentlich statt, und zwar die Übungsgruppen g: Ü1,Ü3,Ü5,Ü7,Ü9,Ü11 in geraden Kalenderwochen und die Übungsgruppen u: Ü2, Ü4, Ü6, Ü8, Ü10, Ü12 ungeraden Kalenderwochen. Aufgrund des Ausfalls der ersten Vorlesungswoche beginnen wir mit den u-Gruppen in der Woche des 20.10.03.

Prüfungen

Die Prüfungstermine über diese  Vorlesung für Lehramtsstudierende und Austauschstudierende stehen fest:

Montag, 16.2.2004 und Montag, 29.3.2004

Die Anmeldung erfolgt durch E-Mail an Matthias Fischer (mafi@upb.de). Die Prüfungen sind mündliche Einzelprüfungen. Die Anmeldungen für Lehramtsstudierende liegen vor und die Uhrzeiten stehen fest. Die angemeldeten Studierenden sind von Matthias Fischer per E-Mail informiert worden. Falls jemand noch keine E-Mail bekommen hat, aber eine Prüfung für Lehramtsstudierende machen möchte, bitte melden.

Übungen

Hausaufgaben

Es wird 2-wöchentlich Freitags ein Übungsblatt mit jeweils 4 Aufgaben auf dieser Website herausgegeben (1. Termin 24.10.03), das von Ihnen zu bearbeiten ist. Die Lösung wird bis Donnerstag vor der Ausgabe des neuen Blattes in den Kästen auf Ebene D3 abgegeben (1. Termin Do. 6.11.03, 24 Uhr) und von den Betreuern der Übungsgruppe korrigiert und bewertet. Auf jedem Blatt können 20 Punkte erreicht werden. Uuml;berprüfen Sie auf Ihrem Punktekonto, ob Sie genau die Punkte bekommen haben, mit denen Ihre Lösung bewertet wurde.

Übungszettel Präsenzübung

Für jede Präsenzübung wird ein Übungsblatt mit 2 Aufgaben herausgegeben, das als Handzettel in der Präsenzübung ausgeteilt wird. Die beiden Aufgaben werden in der Übung durch Sie in Gruppenarbeit bearbeitet und eine Lösung von Ihnen an der Tafel präsentiert.

Gruppenarbeit

Wir fordern Sie ausdrücklich auf, in kleinen Gruppen (3-4 Personen) gemeinsam die Vorlesung nachzuarbeiten und die Übungen zu bearbeiten. Für den Lernerfolg (und den Spaß am Studieren) ist das sehr förderlich. Sie dürfen Ihre Übungen auch in solchen Gruppen abgeben.

Musterlösungen

Musterlösungen für die Hausaufgaben werden durch Sie erstellt. Dazu werden eine oder mehrere Ihrer Lösungen ausgewählt, zusammen mit den Betreuern ggfs. überarbeitet und im Netz zur Verfügung gestellt. Die nicht abgeholten Übungsblätter liegen ab spätestens Freitag (13.02.04) über den bekannten Kästen im Flur D3

Anmeldung

Die Anmeldung zu den Übungen erfolgt über StudInfo{flex}. Jede Gruppe ist auf 30 Teilnehmer begrenzt. Sie können Ihre persönlichen Informationen, sowie die Zugehörigkeit zu einer Übungsgruppe und Ihre Punkte aus den Hausaufgaben einsehen. Später finden Sie hier die Klausuranmeldung und erfahren Ihr Klausurergebnis. Bitte beachten Sie: Für jede Veranstaltung, die Sie besuchen und die zur Anmeldung StudInfo{flex} verwendet, müssen Sie sich erneut anmelden, jedes Teilnehmerkonto ist für genau eine Vorlesung gültig. Passwörter werden verschlüsselt gespeichert, d.h. als Administrator können wir nur ein neues Passwort setzen, falls Sie Ihr Passwort vergessen haben. Hier geht es zu Ihrem Teilnehmerkonto:

Prüfung

Im Anschluss an die Vorlesung "Algorithmen und Komplexität" im SS04 erfolgt eine Prüfung über den Stoff beider Vorlesungen durch eine Klausur. Für Lehramtsstudierende, die nur "Berechenbarkeit und Formale Sprachen" belegen müssen, erfolgt im Anschluss an die Vorlesung eine mündliche Prüfung. Wenn Sie aktiv in den Übungen mitarbeiten, können Sie Ihre Note wie folgt verbessern (Bonus):

• Erreichen Sie mindestens 50% der Punkte der Hausaufgaben, so verbessert sich die Note um 1/3.
• Erreichen Sie mindestens 75% der Punkte der Hausaufgaben, so verbessert sich die Note um 2/3.
• Erstellen Sie für eine Hausaufgabe Musterlösungen, die im Netz zur Verfügung gestellt werden, so verdoppelt sich die Punktezahl für die Aufgabe. Wenn Sie zu einer Aufgabe Musterlösungen erstellen wollen, dann melden Sie sich bei uns. Oder wir werden Sie auffordern Musterlösungen zu erstellen.

Als Bonusleistung zählen die Hausaufgaben von dieser Veranstaltung und der nachfolgenden Veranstaltung "Algorithmen und Komplexität" (Ausnahme: Studenten, die nur diese Veranstaltung belegen müssen, bspw. Lehramtsstudenten). Übungsleistungen aus früheren Veranstaltungen werden nicht anerkannt. Eine Verbesserung der Note 5 (nicht bestanden) ist nicht möglich.

Skript

Die Vorlesung wird sich an dem Skript "Einführung in Berechenbarkeit und Formale Sprachen" (WS 2002/03) von Johannes Blömer orientieren. Hier können Sie die PDF/PS - Version erhalten. Dieses Skript kann jedoch das Lesen von Lehrbüchern nicht ersetzen. Ergänzungen erscheinen im Laufe des Semesters begleitend zur Vorlesung.

Aktualisierung!
Die erste, hier angebote Version der Folien zur Vorlesung, hatte Fehler in der Fontsdarstellung. Da die Folien mit TexPoint-Unterstützung erstellt wurden, konnten sie nur richtig dargestellt werden, wenn Texpoint installiert war. Es gibt jetzt eine zweite Version die eingebettete Fonts verwendet. Diese wird auch ohne TexPoint in Powerpoint richtig angezeigt. Die pdf-Version ist dementsprechend berichtigt worden.

Literatur

• Introduction to Automata Theory, Languages, and Computation, John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Addsion Wesley, 2. Auflage, 2001.
  gibt es auch auf deutsch: Einführung in die Automatentheorie, Formale Sprachen und Komplexität, John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Pearson Studium, 2. Auflage, 2002.
• Introduction to the Theory of Computation, Michael Sipser, PWS, 1997.
• Theoretische Informatik, Christel Baier, Alexander Asteroth, Pearson Studium, 2002.
• Elements of the Theory of Computation, Harry R. Lewis, Christos H. Papadimitriou, Prentice Hall, 2. Auflage 1998.
• Theory of Computing - A Gentle Introduction, Efim Kinber, Carl Smith, Prentice Hall, 2001.
• Theoretische Informatk - kurzgefaßt, Uwe Schöning, Spektrum, akad. Verlag, Heidelberg, 3. Auflage 1997.
• Theoretische Informatik - Eine algorithmenorientierte Einführung, Ingo Wegener, Teubner, 1993.

Links mit Bezug zur Vorlesung

• Sehr schöne und anschauliche Animationen zur Arbeitsweise von Turingmaschinen findet man unter Animationen von Algorithmen der theoretischen Informatik, Ausarbeitung dazu.
• Einen C++ Simulator für deterministische und nichtdeterministische Turingmaschinen findet man bei Alex Vinokur.