Theoretische Informatik 1

Vortragender: Prof. Carsten Lutz

V2Ü2, 1. Semester

Vorlesung: Mo 14–16 NW1 H1

Kurzbeschreibung

Die Theoretische Informatik beschäftigt sich auf systematische Weise und unter Verwendung mathematischer Mittel mit zentralen Fragen der Informatik und stellt damit eine wichtige Grundlage für viele andere Teilgebiete der Informatik dar. Sie besteht aus vielen Teildisziplinen, von denen in dieser Vorlesung hauptsächlich zwei behandelt werden: die Automatentheorie und die Theorie der formalen Sprachen. Dabei stehen sogenannte Wörter im Mittelpunkt, mit deren Hilfe viele Strukturen der Informatik wie z.B. Programme und verschiedene Datenstrukturen beschrieben werden können. Eine formale Sprache ist dann einfach eine Menge von Wörtern. Wir studieren verschiedene Mittel, um formale Sprachen zu beschreiben (insb. Automaten und Grammatiken), untersuchen Eigenschaften von wichtigen Klassen formaler Sprachen und studieren zentrale algorithmische Probleme, die im Zusammenhang mit Wörtern und formalen Sprachen stehen.

Skript

Die Vorlesung wird im Wesentlichen die Kapitel I und II des folgenden Skriptes umfassen. Auf Inhalte, die über das Skript hinausgehen, wird in der Vorlesung explizit hingewiesen. Diese sollten dann mitgeschrieben werden. Hier finden Sie die Folien aus der Einführungsveranstaltung. Hier sind die Folien zu Kapitel 3. Und hier Zusammenfassung und Ausblick vom Ende der Vorlesung.

Organisation der Tutorien

Es stehen verschiedene Termine für Tutorien zur Auswahl, für Details sehen Sie bitte ins Vorlesungsverzeichnis. Die Einschreibung erfolgt während des Erstsemesterfrühstücks in der ESO. Die Tutorien beginnen in der 45. Kalenderwoche.

Auf dieser Seite wird jede Woche ein Aufgabenblatt zur Verfügung gestellt. Die Aufgaben werden in Kleingruppen von 2–3 Personen bearbeitet und in den Tutorien gemeinsam besprochen. Jede zweite Woche geben Sie Ihre Lösungen zur Korrektur ab, das erste Mal in KW 46.

Tutorium	Ort	Tutor(in)
Mo. 16–18	MZH 1100	Dr. Thomas Schneider
Di. 16–18	MZH 1450	Dr. Stefan Göller
Mi. 8–10	MZH 1090	Dr. Sabine Kuske
Mi. 10–12	MZH 1100	Dr. Sabine Kuske
Mi. 12–14	GW1 B0080	Jean Christoph Jung
Mi. 12–14	9.11. MZH 1380/1400	Dr. Thomas Schneider
	ab 16.11. MZH 1090
Do. 10–12	MZH 1450	Melanie Luderer
	nur 17.11. MZH 3150
Do. 14–16	MZH 1380/1400	Dr. Stefan Göller
	nur 17.11. MZH 3150

Aufgabenblätter

Blatt 1 ungewertete Aufgaben (Besprechung 7.–10.11.11)
Blatt 2 gewertete Aufgaben (Abgabe bis 14.11.11 12:00; Besprechung 14.–17.11.11)
Blatt 3 ungewertete Aufgaben (Besprechung 21.–24.11.11)
Blatt 4 gewertete Aufgaben (Abgabe bis 28.11.11 14:00; Besprechung 28.11.–1.12.11)
Blatt 5 ungewertete Aufgaben (Besprechung 5.–8.12.11)
Blatt 6 gewertete Aufgaben (Abgabe bis 12.12.11 14:00; Besprechung 12.–15.12.11)
Blatt 7 ungewertete Aufgaben (Besprechung 19.–22.12.11)
Blatt 8 gewertete Aufgaben (Abgabe bis 9.1.12 14:00; Besprechung 9.–12.1.12)
Blatt 9 ungewertete Aufgaben (Besprechung 16.–19.1.12)
Blatt 10 gewertete Aufgaben (Abgabe bis 23.1.12 14:00; Besprechung 23.–26.1.12)
Blatt 11 ungewertete Aufgaben (Besprechung 30.1.–2.2.12)
Blatt 12 gewertete Aufgaben (Abgabe bis 6.2.12 14:00; Besprechung 6.–9.2.12)
Blatt 13 ungewertete Aufgaben (Besprechung 13.–16.2.12)

Literatur

Dexter Kozen, Automata and Computability, Springer Verlag, 2007
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullmann, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2006 (3rd edition)
Uwe Schöning, Theoretische Informatik - kurzgefaßt, Spektrum Akademischer Verlag, 1999
Ingo Wegener, Theoretische Informatik, Teubner-Verlag, 1993

AG Theorie der künstlichen Intelligenz