Theoretische Informatik 1

Vortragender: Prof. Dr. Thomas Schneider

V2Ü2, 1. Semester

Vorlesung: Mo 14–16 MZH 1380/1400

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 und Folien

Die Vorlesung wird im Wesentlichen die Kapitel I und II des Skriptes von Prof. Dr. Carsten Lutz umfassen. Auf Inhalte, die über das Skript hinausgehen, wird in der Vorlesung explizit hingewiesen. Diese sollten dann mitgeschrieben werden. Hier etwas zum Thema: wie liest man einen mathematischen Text?

Ergänzungen zum Skript

Aktualisierte Version des Abschnitts 2 (Pumping-Lemma)
Errata

Die Folien stehen in StudIP zur Verfügung und werden regelmäßig aktualisiert.

Video-Vorlesung

Hier findet man die Vorlesung als "Mobile Lecture".

Organisation der Tutorien

Es stehen die folgenden Termine für Tutorien zur Auswahl. Die Tutorien beginnen in der 43. Kalenderwoche (ab 19.10.). Die Einschreibung in die Tutorien erfolgt für Studierende im 1. Semester ab Mi 7.10.2015, 06:30 Uhr über eine gesonderte Veranstaltung in StudIP ("Tutoriumseinschreibung für Erstsemester"). Zur einfacheren Orientierung sind die IDs der Musterstundenpläne in der zweiten Spalte angegeben. Alle anderen Studierenden können sich ab Mo 12.10.2015, 10:00 Uhr in Stud.IP direkt in ein Tutorium eintragen.

Tutorium	Stundenplan ID	Ort	Tutor(in)
Mo. 16–18	IM3	MZH 1110	Christopher Nottrodt
Di. 8–10	IM2	MZH 1110	M.Sc. Peter Hansen
Di. 12–14	IM1	MZH 1110	Gerrit Felsch
Di. 16–18	IM4	MZH 1110	Alicia Pagel
Mi. 8–10	IM5	MZH 1460	Jan Mantei
Mi. 10–12	IW2	MZH 1110	Dr. Jean Christoph Jung
Mi. 16–18	IM6	MZH 5210	Arved Friedemann
Do. 10–12	IW1	MZH 1110	Dr. Jean Christoph Jung

Aufgabenblätter

An dieser Stelle 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. Auf jedem Arbeitsblatt gibt es gewertete Aufgaben, deren Lösungen Sie jeweils bis Montag 14:00 Uhr in das entsprechende Fach im Erdgeschoss des Cartesiums zur Korrektur abgeben.

Nr.	Abgabetermin	Besprechung
Blatt 1	(ungewertet)	19.–23.10.15
Blatt 2	bis 26.10.2015, 14 Uhr	26.–30.10.15
Blatt 3	bis 02.11.2015, 14 Uhr	02.–06.11.15
Blatt 4	bis 09.11.2015, 14 Uhr	09.–13.11.15
Blatt 5	bis 16.11.2015, 14 Uhr	16.–20.11.15
Blatt 6	bis 23.11.2015, 14 Uhr	23.–27.11.15
Blatt 7	bis 30.11.2015, 14 Uhr	30.11.–04.12.15
Blatt 8	bis 07.12.2015, 14 Uhr	07.12.–11.12.15
Blatt 9	bis 14.12.2015, 14 Uhr	14.12.–18.12.15
Blatt 10	bis 11.01.2016, 14 Uhr	11.01.–15.01.16
Blatt 11	bis 18.01.2016, 14 Uhr	18.01.–22.01.16
Blatt 12	bis 25.01.2016, 14 Uhr	25.01.–29.01.16
Blatt 13	(ungewertet)	01.02.–05.02.16

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 11. Jan. 2016 Thomas Schneider Jean Christoph Jung