Automaten, Sprachen und Komplexität

Wintersemester 2004/2005
Lehrstuhl für Informatik II
Grundstudium (Serviceveranstaltung)
Technische Informatik
3. Fachsemester

Termine

Art	Termine	Beginn	Dozent
Vorlesung	Mo 10:00 - 11:30 VT	18. Oktober	Prof. Dr. K. Indermark
Zentralübung	Fr 09:00 - 09:45 VT	22. Oktober	B. Bollig
Diskussionsgruppen	Mo 09:00 - 09:45 SG 203, VT	25. Oktober	C. Roeckerath, E. Storch

Aktuelles

• Anstelle einer Wiederholungsklausur kann der Leistungsnachweis durch eine mündliche Prüfung von 15 bis 30 Minuten Dauer erworben werden. Gegenstand der Prüfung ist der Stoff der Übungsblätter 1 bis 10. Die Prüfungen finden nach Vereinbarung in der Woche vom 11. bis 15. April statt. Zur Anmeldung und Terminabsprache senden Sie bitte eine Email an B. Bollig.
• Diejenigen, die den Leistungsnachweis bereits erworben haben, sind direkt dem Zentralen Prüfungsamt mitgeteilt worden.
• Klausurergebnisse

Übungsaufgaben

• Ausgabe: Freitags vor der Zentralübung (1. Blatt: 22. Oktober)
• Abgabe: Eine Woche darauf vor der Zentralübung (1. Blatt: 29. Oktober)
• Rückgabe: Montags in der Diskussionsgruppe (1. Blatt: 08. November)
• Besprechung: In der Übung und in der Diskussionsgruppe

Die Übungsaufgaben sollen in Zweiergruppen bearbeitet werden.

Diskussionsgruppen

Die Diskussionsgruppen beginnen mit dem 25. Oktober. Dort werden evtl. fehlende Übungsaufgaben vorgerechnet, weitere Aufgaben besprochen und allgemeine Verständnisfragen geklärt. Die Anmeldung zu den Diskussionsgruppen erfolgte bereits in der ersten Vorlesungsstunde.

Gruppe 1

Gruppe 2

Gruppe	Termin	Ort
1	Mo, 09:00 - 09:45	SG 203
2	Mo, 09:00 - 09:45	VT

Erwerb eines Übungsscheins

Voraussetzung für den Erwerb eines Übungsscheins sind

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

Die Scheinklausur findet dabei in zwei jeweils 90-minütigen Teilen am

• 14. Dezember 2004 um 18:00 Uhr im Hörsaal Gr bzw. am
bzw.
• 31. Januar 2005 um 18:00 Uhr im Hörsaal Ro statt.

Zum Bestehen des Klausurteils sind erforderlich

• insgesamt 48 Punkte und
• in jedem Teil mindestens 12 Punkte.

Ü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
• Blatt 11 ps / pdf

Folien etc.

• Kapitel 0 ps / pdf (Organisatorisches)
• 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 2 (Teil 5) 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 (Teil 1) ps / pdf
• Kapitel 4 (Teil 2) ps / pdf
• PRIMES is in P

Veranstalter

Prof. Dr. K. Indermark	Benedikt Bollig
Raum 4214	Raum 4211
Tel.: 80-21201	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.

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