Automaten, Sprachen und Komplexität

Wintersemester 2006/2007
Lehrstuhl Informatik 2
Grundstudium (Serviceveranstaltung)
Technische Informatik
3. Fachsemester

Termine

Art	Termine	Beginn	Dozent
Vorlesung	Mo 10:00 - 11:30 VT	23.10.2006	Prof. Dr. J.P.Katoen
Zentralübung	Mo 08:15 - 09:00 VT	30.10.2006	H. Bohnenkamp, C. Kern
Diskussionsstunde	Mo 09:00 - 09:45 VT	30.10.2006	H. Bohnenkamp, C. Kern

Aktuelles

Die Information im Campus-System ist nicht akkurat. Verbindliche Informationen zur Vorlesung finden sich nur auf dieser Webseite.

• 16.2.2007 Die Ergebnisse zur Schinklausur sind nun weiter unten zu besichtigen.
• 12.2.2007 Die korrigierten Lösungen zum 12. Übungblatt können im Sekretariat des LS 2 abgeholt werden.
• 7.2.2007 Unten findet sich jetzt die Liste der zur Klausur zugelassenen Leute (also Matrikelnummern).
• 4.2.2007 Am 5.2.07 findet keine Vorlesung mehr statt. Die Übung fängt um 10 Uhr an, statt 8:15.
• 26.1.2007 Die Punkte-Tabelle ist aktualisiert worden, und gibt jetzt den Stand der Dinge bis einschliesslich Übung 10 wieder.
• 18.12.2006 Unten ist jetzt eine Tabelle angegeben, die prozentual angibt, wieviel der erreichbaren Punkte erreicht worden sind (bis einschliesslich Übung 6).
• 04.12.2006 Hinweis zu Übung 6 Aufgabe 3b): in diesem Aufgabenteil können Sie wie auch in den anderen beiden Teilen 2 Punkte erreichen.
• 20.11.2006 Hinweis zu Übung 4 Aufgabe 4a): die Funktion odd(i) bestimmt zu einer gegebenen Zahl i, ob diese ungerade ist oder nicht. Falls i ungerade ist, so wird true und anderenfalls false zurückgegeben. Außerdem kann diese Funktion in O(1) durchgeführt werden.
• 3.11.2006 Hinweis zu Aufgabe 1 a) i), erster Übungszettel: die Wörter der Sprache L1 dürfen mehrere a enthalten. Auf ein a muß ein b folgen.
• 27.10.2006 Hinweis: Am 27. Oktober findet keine Zentralübung statt. Ausserdem beginnt die erste Übung am 30. Oktober ausnahmsweise erst um 9 Uhr und dauert nur 45 Minuten.
• 23.10.2006 Hier die Übersichtsfolien zum Übungsbetrieb, wie in der ersten Vorlesung aufgelegt.
• 23.10.2006 Wie in der ersten Vorlesung besprochen, werden Zentralübung und Diskussionstunde zusammengelegt und finden nun Montags von 8:15 -- 9:45 im Hörsaal VT statt.
• 20.10.2006 Zum Thema "Vorlesungsbegleitende Literatur" hat sich ein Änderung ergeben. Siehe unten.

Erwerb eines Übungsscheins

Voraussetzung für den Erwerb eines Übungsscheins sind

• 50% der erreichbaren Punkte bei den Übungsaufgaben und
• eine bestandene Scheinklausur.

Scheinklasur

• Die Klausur findet am 15. Februar 2007 im Audimax statt.
• Beginn ist 8:00, Einlass ab 7:55. Bearbeitungszeit: 2 Zeitstunden.
• Mitzubringen sind nur Schreibzeug. Hilfsmittel sind nicht zugelassen. Papier wird gestellt.
• Teilnahmebedingung: 40% der in den Hausaufgaben erreichbaren Punkten
• Bestehensgrenze: 50%
• Die Ergebnisse werden auf dieser Webseite bekanntgegeben (siehe unten).
• Die Ergebnisse werden direkt ans Prüfungsamt gemeldet.
• Im März wird es nachprüfungen für diejenigen geben, die bei der Klausur durchgefallen sind. Ob das eine Nachklausur oder eine mdl. Prüfung ist, wird sich nach der Klausur entscheiden.

Ergebnisse zur Scheinklausur vom 15. Februar

Die Studis mit den folgenden Matrikelnummern haben die Scheinklausur vom 15. Februar bestanden:

222896	265618	269386
241545	265710	269793
244300	265718	269811
250863	265804	277022
252266	265932	258648
252850	266128	258329
257867	266669
262165	266703
262692	266917
264548	266967
264585	267165
264737	267251
264784	267540
265207	267636
265241	267673
265243	267884
265401	267944
265424	267948
265581	268388
265582	268394

Damit haben 5 von 51 nicht bestanden. Im März werden wir für diese sieben eine zweite Chance bieten, den Schein doch noch zu erwerben. Das wird keine Klausur, sondern eine kleine mündliche Prüfung (15-20 min.) sein. Wir haben Donnerstag, den 15. März, dafür im Auge. Die betroffenen Personen mögen sich bitte bei Carsten Kern oder Henrik Bohnenkamp melden, um einen genauen Termin auszumachen.

Übungsaufgaben

• Ausgabe: Montags nach der Vorlesung, nur elektronisch auf dieser Webseite (siehe unten)
• Abgabe: Eine Woche darauf in der Übung
• Rückgabe: Montags in der Übung
• Besprechung: In der Zentralübung

Die Übungsaufgaben sollen in Zweiergruppen bearbeitet werden.

Übung

Entgegen der ursprünglichen Ankündigung werden Zentralübung und Diskussionsgruppen zusammengelegt. Die Übung findet Montags morgens, 8:15 -- 9:45 im Hösaal VT statt.

Hinweis: Am 27. Oktober findet demnach keine Zentralübung statt. Ausserdem beginnt die Übung am 30. Oktober ausnahmsweise um 9 Uhr und dauert nur 45 Minuten.

Übungen

• Blatt 1 ps / pdf,
• Blatt 2 ps / pdf
• Blatt 3 ps / pdf
• Blatt 4 ps / pdf
• Blatt 5 ps / pdf
• Blatt 6 ps / pdf
• Blatt 7 ps / pdf
• Blatt 8 ps / pdf
• Blatt 9 ps / pdf
• Blatt 10 ps / pdf
• Blatt 11 ps / pdf
• Blatt 12 ps / pdf

Folien etc.

Veranstalter

Prof. Dr. J.P. Katoen	Raum 4201	Tel.: 80-21201
Henrik Bohnenkamp	Raum 4210	Tel.: 80-21203
Carsten Kern	Raum 4206	Tel.: 80-21210

Inhalt

Diese Vorlesung richtet sich an Studierende des Ingenieurstudiengangs "Technische Informatik" im 3. Fachsemester. Es wird - verankert in Beispielen aus den Anwendungen - eine Einführung in zentrale Begriffe und Sachverhalte der theoretischen Informatik gegeben. Dabei werden verschiedene Automatenmodelle, Methoden der Spezifikation formaler Sprachen sowie Fragen zur Berechenbarkeit und Berechnungskomplexität behandelt. Die Beschreibung syntaktischer Strukturen durch reguläre Ausdrücke und kontextfreie Grammatiken sowie ihre effiziente Erkennung durch endliche Automaten und Kellerautomaten bilden eine wichtige Grundlage für die Übersetzung von Programmiersprachen und die Konstruktion zahlreicher Software-Werkzeuge.

Vorlesungsbegleitende Literatur

Entgegen der vorherigen Ankndigung, daß sich die Vorlesung an dem Buch von Asteroth/Baier orientieren wird, werden wir jetzt das Skript von Prof. W. Thomas verwenden, das auch schon fr ASK im WS 2005/06 benutzt wurde. Das Skript kann für 3 Euro im Sekretariat des Lehrstuhl 2, 2. Etage des Erweiterungsbau 1 des Informatik-Zentrums, Raum 4213, erworben werden. Geld bitte passend mitbringen!

Weitere Literatur

• A. Asteroth, C. Baier, Theoretische Informatik, Pearson Studium, 2002
• U. Schöning: Theoretische Informatik kurz gefaßt, Spektrum-Akademischer Verlag, 3. Auflage, 1997 (Bibliothek)
• J.E. Hopcroft, R. Motwani, J.D. Ullmann: Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison-Wesley, 2001
• I. Wegener, Theoretische Informatik, Teubner, 2. Auflage, 1999