Theoretische Informatik 1
Vortragender: Prof. Carsten Lutz
V2Ü2
Mi 10-12, eventuell weitere Termine
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 dieses
Skriptes umfassen.
Hier etwas zum Thema: wie liest man einen mathematischen Text?
Organisation der Vorlesung und Tutorien
Die Vorlesungen werden als Videos bereitgestellt und können von den Teilnehmern zu einem Zeitpunkt ihrer Wahl angesehen werden. Es gibt ein wöchentliches Treffen auf BigBlueButton, bei dem die Vorlesungsinhalte der jeweiligen Woche nachbesprochen werden und Fragen gestellt werden können.
Diese Edition der Vorlesung übernimmt eine „Brückenfunktion“ zwischen der alten (bis SS20) und neuen (ab WS20/21) Bachelorstudienordnung.
Regelhaft hören Studierende des Jahrgangs 2020 die Vorlesung Theoretische Informatik I erst im 3. Studiensemester, d.h. im WS21/22. Die Vorlesung richtet sich daher in erster Linie an Wiederholer und Quereinsteiger.
Aufgrund der Sonderstellung dieser Edition der VL lässt sich die Teilnehmerzahl nur schwer vorhersagen. Der Übungsbetrieb wird daher erst kurzfristig vor Vorlesungsbeginn organisiert.
Aufgabenblätter
Werden in Stud.IP zur Verfügung gestellt.
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
20. Jan. 2013
Thomas Schneider
