Automatentheorie und Formale Sprachen [VAuFS]

Sommersemester 2003
Lehrstuhl für Informatik II
Grundstudium

Termine

Art	Termine	Beginn	Veranstalter
V3	Di 11:45 - 13:15 Fo 2	29.04.	Indermark
	Fr 10:45 - 11:30 Gr	25.04.
Ü1	Fr 10:00 - 10:45 Gr	25.04.	Indermark, Bollig

Veranstalter

Prof. Dr. K. Indermark	Benedikt Bollig
Raum 4214	Raum 4211
Tel.: 80-21201	Tel.: 80-21210

Zeitplan für die Diplom-Vorprüfung/Zwischenprüfung im Wintersemester 2003/2004

• Freitag, 27. Februar 2004: Klausur, 09:30 - 11:30 Uhr, Aula 2
• Mittwoch, 3. März 2004: Klausureinsicht, 15:00 - 17:00 Uhr, 5056, und Anmeldung zur mündlichen Nachprüfung
  (Zu einer mündlichen Nachprüfung sind Sie zugelassen, falls Sie die Vordiplomsklausur zum wiederholten Mal nicht bestanden haben.)
• Donnerstag, 4. März, und Freitag, 5. März 2004: Mündliche Nachprüfungen
• Klausur ps, pdf

Endergebnisse (ohne Berücksichtigung der mündlichen Nachprüfungen)

Zeitplan Diplom-Vorprüfung/Zwischenprüfung/Scheinklausur

• ab Montag, 25. August: Scheinausgabe im Sekretariat des Lehrstuhls
• Dienstag, 16. September: Fragestunde, 10:00 - 12:00 Uhr, AH I
• Dienstag, 23. September: Diplom-Vorprüfung bzw. Zwischenprüfung und Scheinklausur, 09:30 - 11:30 Uhr

  Hörsaal	Matrikelnummern
  Aula 2	100000 - 227699
  Fo 1	227700 - 233959
  Fo 4 (geändert!)	233960 - 234629
  Ro	234630 - 235679
  Gr	235680 - 249999

• Donnerstag, 25. September: Bekanntgabe der Ergebnisse auf dieser Seite, gegen 15:00 Uhr
• Donnerstag, 25. September: Klausureinsicht, 16:00 - 19:00 Uhr, AH I

  Uhrzeit	Matrikelnummern
  16:00 - 17:00	100000 - 229199
  17:00 - 18:00	229200 - 234699
  18:00 - 19:00	234700 - 249999

• 29. September - 2. Oktober: Anmeldung zur mündlichen Nachprüfung im Sekretariat des Lehrstuhls
  (Zu einer mündlichen Nachprüfung sind Sie zugelassen, falls Sie die Vordiplomsklausur zum wiederholten Mal nicht bestanden haben.)
• 7. Oktober - 9. Oktober: Mündliche Nachprüfungen
• Klausur ps, pdf

Endergebnisse (ohne Berücksichtigung der mündlichen Nachprüfungen)

Erwerb eines Übungsscheins

Voraussetzung für den Erwerb eines Übungsscheins sind 50% der erreichbaren Punkte bei den Übungsaufgaben und

• zwei bestandene Scheinklausuren während des Semesters (am 18. Juni 2003 bzw. 30. Juli 2003) oder
• eine bestandene Scheinklausur parallel zur Diplomvorprüfung am 23. September 2003.

Zum Bestehen des Klausurteils genügen dabei

• insgesamt 40 Punkte aus den beiden Scheinklausuren während des Semesters (z.B. 30 Punkte aus der ersten Scheinklausur und 10 Punkte aus der zweiten Scheinklausur) oder
• 32 Punkte aus der Scheinklausur am 23. September.

Erste Scheinklausur

• Die erste Scheinklausur (ps, pdf) fand am Mittwoch, den 18. Juni 2003, statt.
• Lösungsvorschlag ps, pdf
• Ergebnisse

Zweite Scheinklausur

• Die zweite Scheinklausur (ps, pdf) fand am Mittwoch, den 30. Juli 2003, statt.
• Lösungsvorschlag ps, pdf
• Ergebnisse

Erwerb eines Teilnahmenachweises

Einen Teilnahmenachweis erhalten Sie nach einer kurzen mündlichen Prüfung am Ende der Vorlesungszeit.

Diskussionsgruppen

Gruppeneinteilung

Die Diskussionsgruppen beginnen mit dem 28.04.

Gruppe	Gruppenleiter	Termin	Ort
1	Martin Kappe	Mo, 08:15 - 09:45	SG 12
2	Christian Stein	Mo, 09:45 - 11:15	5056
3	Tobias Latzke	Mo, 10:00 - 11:30	AH II
4a	Verena Vorbrüggen	Mo, 10:00 - 11:30	SG 413
4b	Johannes Pohl	Mo, 10:00 - 11:30	SG 512
5a	Niels Duhme	Mo, 11:45 - 13:15	SG 413
5b	Tobias Karns	Mo, 12:00 - 13:30	Fo 6
6a	Michael Holtmann	Mo, 11:45 - 13:15	5052
6b	Joachim Börger	Mo, 11:45 - 13:15	AH I
7	Thorsten Holz	Mo, 14:00 - 15:30	SG 203
8	Joachim Kneis	Mo, 15:45 - 17:15	SG 203
9	Piotr Cholewinski	Di, 08:30 - 10:00	AH I
10	Sandip Sar-Dessai	Di, 15:45 - 17:15	5052
11	Bastian Wegener	Mi, 11:45 - 13:15	5052
12	Bastian Braun	Mi, 11:45 - 13:15	Fo 8

Newsgroup

Die ATFS-Newsgroup bietet ein Forum zum gegenseitigen Informationsaustausch.

Inhalt

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.

Im Unterschied zur Vorlesung "Berechenbarkeit und Komplexität" steht nicht die Berechnung von Funktionen, sondern die Erzeugung und Erkennung formaler Sprachen im Vordergrund. Die größte Klasse solcher effektiv beschreibbaren Sprachen stellen die von Turing-Maschinen erkennbaren, rekursiv aufzählbaren Sprachen dar.

Themenübersicht:

• Reguläre Ausdrücke und endliche Automaten
• Kontextfreie Grammatiken und Kellerautomaten
• Turingmaschinen, Aufzählbarkeit und Entscheidbarkeit

Übungen

• Blatt 1 ps, pdf, Lösungsvorschlag ps, pdf
• Blatt 2 ps, pdf, Lösungsvorschlag ps, pdf
• Blatt 3 ps, pdf, Lösungsvorschlag ps, pdf
• Blatt 4 ps, pdf, Lösungsvorschlag ps, pdf
• Blatt 5 ps, pdf, Lösungsvorschlag ps, pdf
• Blatt 6 ps, pdf, Lösungsvorschlag ps, pdf
• Blatt 7 ps, pdf, Lösungsvorschlag ps, pdf
• Blatt 8 ps, pdf, Lösungsvorschlag ps, pdf
• Blatt 9 ps, pdf, Lösungsvorschlag ps, pdf
• Blatt 10 ps, pdf, Lösungsvorschlag ps, pdf
• Blatt 11 ps, pdf, Lösungsvorschlag ps, pdf
• Blatt 12 ps, pdf, Lösungsvorschlag ps, pdf
• Blatt 13 ps, pdf

Folien

• Kapitel 0 ps, pdf
• Kapitel 1 ps, pdf
• Kapitel 2 (Teil 1) ps, pdf
• Kapitel 2 (Teil 2) ps, pdf
• Kapitel 2 (Teil 3) ps, pdf
• Kapitel 2 (Teil 4) ps, pdf
• Kapitel 3 (Teil 1) ps, pdf
• Kapitel 3 (Teil 2) ps, pdf
• Kapitel 3 (Teil 3) ps, pdf
• Kapitel 3 (Teil 4) ps, pdf
• Kapitel 4 ps, pdf

Literatur

• 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
• A. Asteroth, C. Baier, Theoretische Informatik, Pearson Studium, 2002
• I. Wegener, Theoretische Informatik, Teubner, 2. Auflage, 1999

Verschiedenes und Links

• Automatentheorie und Formale Sprachen im Sommersemester 1999
• Automatentheorie und Formale Sprachen im Sommersemester 2001