Theoretische Informatik 1

Vortragender: Prof. Carsten Lutz

V2Ü2

Vorlesung Di 16-18 NW2 C0290 (Hörsaal 1)

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.

Materialien

Die Vorlesung wird im Wesentlichen die Kapitel I und II dieses Skriptes umfassen.

Hier etwas zum Thema: wie liest man einen mathematischen Text?

Für Teilnehmer, die nicht zu den Präsenzvorlesungen kommen können, werden Videos zur Verfügung gestellt. Ein Link findet sich in Stud.IP

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