Theoretische Informatik I
(Informatik, berufsbgl. Lehramt Gymn.)

Wintersemester 2006/07

Vorlesung und Übungen:
Stundenplan

Inhalt:
Dies ist der erste Teil einer zweisemestrigen Vorlesung, die eine Einführung in formale Sprachen, Automatentheorie, Berechnenbarkeitstheorie und Komplexitätstheorie gibt.

Vorlesungsfolien

1. Vorlesung (8 auf 1 zum Ausdrucken)   2. Vorlesung (8 auf 1 zum Ausdrucken)   3. Vorlesung (8 auf 1 zum Ausdrucken)   4. Vorlesung (8 auf 1 zum Ausdrucken)   5. Vorlesung (8 auf 1 zum Ausdrucken)   6. Vorlesung (8 auf 1 zum Ausdrucken)   7. Vorlesung (8 auf 1 zum Ausdrucken)   8. Vorlesung (8 auf 1 zum Ausdrucken)   9. Vorlesung (8 auf 1 zum Ausdrucken) 10. Vorlesung (8 auf 1 zum Ausdrucken) 11. Vorlesung (8 auf 1 zum Ausdrucken) Übungsblätter: Jedes Übungsblatt enthält mit einem * gekennzeichnete Aufgaben. Diese Aufgaben sind schriftlich zu bearbeiten und vor(!) dem angegebenen Abgabetermin im ISG-Sekretariat (Geb. 29 - R. 218) abzugeben. Eine dieser Aufgaben wird ausgelost und korrigiert. In den Übungen werden alle Aufgaben besprochen, jeder Teilnehmer sollte mindestens einmal eine Aufgabe vorrechnen. Sie dürfen sich in kleinen Gruppen (maximal 2-3 Personen) zusammen tun und gemeinsame Lösungen abgeben (bitte aber nur eine Lösung abgeben), jedoch muss jeder alle bearbeiteten Aufgaben vorrechnen können. Zum Erwerb der Leistungspunkte für diese Veranstaltung müssen insgesamt mindestens 50% der Punkte der korrigierten Aufgaben erreicht werden. Der Erwerb der Leistungspunkte ist Voraussetzung für die Teilnahme an der Vordiplomsklausur zur Theoretischen Informatik. Bearbeiten Sie bitte auch die Aufgaben, die nicht schriftlich abzugeben sind!   1.Übungsblatt   2.Übungsblatt   3.Übungsblatt   4.Übungsblatt   5.Übungsblatt   6.Übungsblatt   7.Übungsblatt   8.Übungsblatt Literatur: Die Vorlesung ist zum großen Teil eng an folgendes Lehrbuch angelehnt: Lewis, Papadimitriou; Elements of the Theory of Computation (2nd Edition); Prentice Hall; Weitere Literatur zur Theoretischen Informatik (nur eine kleine Auswahl): Sipser; Introduction to the Theory of Computation (2nd International Edition); Thomson; Hopcroft, Motwani, Ullmann; Introduction to Automata, Languages, and Computation (2nd Edition); Pearson-Education; Hopcroft, Motwani, Ullmann; Einführung in der Automatentheorie, Formale Sprachen und Komplexitätstheorie (2., überarbeitete Auflage); Pearson-Education; Schöning; Theoretische Informatik - kurgefasst (4. Auflage); Spektrum Verlag; Socher; Grundlagen der Theoretischen Informatik; Fachbuchverlag Leipzig; Wagner; Theoretische Informatik - Eine kompakte Einführung; Springer Verlag;