Theoretische Informatik 1

Vortragender: Prof. Carsten Lutz

V2Ü2, 1. Semester

Vorlesung: Mo 10-12 MZH 1400 (erster Termin: 26.10.)

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 formalen, nicht im sprachlichen Sinne) 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 und hier den kurzen Exkurs zu den Themen Komplexitätsanalyse, O-Notation und Entscheidbarkeit. Die Folien zu deterministischen Kellerautomaten sind hier und die Zusammenfassung mit Ausblick hier.

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 44. Kalenderwoche.

Auf dieser Seite wird jede Woche ein Aufgabenblatt zur Verfügung gestellt. Die Aufgaben werden in den Tutorien gemeinsam gelöst. Jede zweite Woche geben Sie Ihre Lösungen ab. Diese werden dann korrigiert und benotet. Das ist das erste mal in KW 45 der Fall. Die Bearbeitung der Übungsaufgaben erfolgt in Kleingruppen von 2-3 Personen.

Tutoren

Übungstermine

Di von 08:00 - 10:00 MZH 7050 (Sabine Kuske)
Di von 16:00 - 18:00 MZH 7220 (Carsten Lutz)
Mi von 08:00 - 10:00 MZH Kl. Senatssaal (1380) (Sabine Kuske)
Mi von 10:00 - 12:00 MZH 7250 (Sabine Kuske)
Do von 08:00 - 10:00 MZH 7220 (Sabine Kuske)
Do von 10:00 - 12:00 MZH 7260 (Stefan Göller)
Do von 14:00 - 16:00 MZH 7220 (Stefan Göller)

Aufgabenblätter

Ungewertetes Aufgabenblatt 1 (KW 44) (PDF) (PS)
Gewertetes Aufgabenblatt 1 (KW 45) (PDF) (PS)
Ungewertetes Aufgabenblatt 2 (KW 46) (PDF) (PS)
Gewertetes Aufgabenblatt 2 (PDF) (PS) (Abgabe bis Montag, den 16.11.09, 10 Uhr ins Postfach Ihres Tutors)
Ungewertetes Aufgabenblatt 3 (PDF) (PS)
Gewertetes Aufgabenblatt 3 (PDF) (PS) (Abgabe bis Montag, den 30.11.09, 24 Uhr ins Postfach Ihres Tutors)
Ungewertetes Aufgabenblatt 4 (PDF) (PS)
Gewertetes Aufgabenblatt 4 (PDF) (PS) Letzte Aktualisierung des Aufgabenblatts am 9.12, 10.50: In einer vorigen Version war ein Fehler bei Aufgabe 1: Aus a.{a,b}^+ wird a.{a,b}^* (Abgabe bis Montag, den 14.12.09, 24 Uhr ins Postfach Ihres Tutors)
Ungewertetes Aufgabenblatt 5 (PDF) (PS)
Gewertetes Aufgabenblatt 5 (PDF) (PS) (Abgabe bis Montag, den 11.01.10, 24 Uhr ins Postfach Ihres Tutors)
Ungewertetes Aufgabenblatt 6 (PDF) (PS)
Gewertetes Aufgabenblatt 6 (PDF) (PS) (Abgabe bis Montag, den 25.01.10, 24 Uhr ins Postfach Ihres Tutors)
Ungewertetes Aufgabenblatt 7 (PDF) (PS)

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