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 eine wichtige Grundlage für viele andere Teilgebiete der Informatik dar. Sie besteht aus mehreren Teildisziplinen, von denen in dieser hauptsächlich die Automatentheorie und die Theorie der formalen Sprachen behandelt werden. Dabei stehen sogenannte Wörter im Mittelpunkt, mit deren Hilfe viele Objekte 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 die Folien zur ersten, einführenden Vorlesung, zum Pumping Lemma und der Satz von Chomsky und Schützenberger mit dem Vorlesungs-Überblick. Hier etwas zum Thema: wie liest man einen mathematischen Text?

Organisation der Tutorien

Neues Tutorium montags 16–18 Uhr: dieses bieten wir ab sofort an, um die vollen Tutorien zu entlasten. Wer dorthin wechseln möchte, erscheint bitte am 4.11. um 16:15 Uhr in GW1 C1070.

Es stehen verschiedene Termine für Tutorien zur Auswahl, für Details sehen Sie bitte ins Vorlesungsverzeichnis. Für Informatik-Erstsemester erfolgt die Einschreibung zentral, weitere Informationen gibt es in der ersten Vorlesung von Praktische Informatik 1. Alle anderen schreiben bitte bis Freitag, 18.10., eine kurze Mail an Thomas Schneider und geben folgendes an: Name, Matrikelnummer, studiertes Fach, Semester, drei Wunschtermine in absteigender Reihenfolge. Die Tutorien beginnen in der 43. Kalenderwoche (ab 21.10.).

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, jeweils bis Montag 14:00 Uhr ins Fach Ihrer Tutorin oder Ihres Tutors, das erste Mal in KW 45.

Tutorium    Ort    Tutor(in)
Mo. 16–18 MZH 1100 Leif Sabellek
Mo. 16–18 ab 4.11. GW1 C1070 Dr. Thomas Schneider
Di. 10–12 MZH 1100 Dr. Frank Dylla
Di. 16–18 MZH 1100 Dr. Frank Dylla
Mi. 8–10 MZH 1450 Christopher Nottrodt
Mi. 12–14 MZH 1100 Dr. Thomas Schneider
Do. 10–12 MZH 1100 Melanie Luderer
Fr. 8–10 GW1-HS H1010 Manuel Schubert
Fr. 8–10 SH D1020 Peter Hansen, Krankheitsvertretung: Dr. Thomas Schneider

Aufgabenblätter

Nr. Art Abgabetermin Besprechung  
Blatt 1 ungewertet 21.–25.10.13   (KW 43)
Blatt 2 ungewertet 28.10.–1.11.13   (KW 44)
Blatt 3 gewertet 4.11.13 14:00 Uhr 4.–8.11.13   (KW 45)
Blatt 4 ungewertet 11.–15.11.13   (KW 46)
Blatt 5 gewertet 18.11.13 14:00 Uhr 18.–22.11.13   (KW 47)
Blatt 6 ungewertet 25.–29.11.13   (KW 48)
Blatt 7 gewertet 2.12.13 14:00 Uhr 2.–6.12.13   (KW 49)
Blatt 8 ungewertet 9.–13.12.13   (KW 50)
Blatt 9 gewertet 16.12.13 14:00 Uhr 16.–20.12.13   (KW 51)
Blatt 10 ungewertet 6.–10.1.14   (KW 2)
Blatt 11 gewertet 13.1.14 14:00 Uhr 13.–17.1.14   (KW 3)
Blatt 12 ungewertet 20.–24.1.14   (KW 4)
Blatt 13 gewertet 27.1.14 14:00 Uhr 27.–31.1.14   (KW 5)

Literatur


AG Theorie der künstlichen Intelligenz 20. Jan. 2013  Thomas Schneider
Valid HTML 4.0 Transitional