University of Bremen Logo  
 
Research Group Theoretical Computer Science
 
HOME
TEAM
TEACHING
RESEARCH

Theoretische Informatik 1


VAK 03-05-G-601.01

Endliche Automaten, kontextfreie Sprachen und Grundelemente der Berechenbarkeit



Gibt es Möglichkeiten, zuverlässig festzustellen, dass die für ein Datenverarbeitungsproblem entwickelte Lösung wirklich die gestellte Aufgabe bearbeitet und auch anderen vorgegebenen Anforderungen (wie z. B. dem Erfordernis einer schnellen Laufzeit) genügt? In der Theoretischen Informatik werden derartige Fragen mit Hilfe mathematischer Methoden beantwortet. Die Lehrveranstaltung Theoretische Informatik 1 zeigt das exemplarisch. Es wird in die Theorie endlicher Automaten und kontextfreier Sprachen und in die Berechenbarkeitstheorie eingeführt, die neben der Komplexitätstheorie, wie sie u. a. in der Lehrveranstaltung Theoretische Informatik 2 behandelt wird, zu den klassischen und gut untersuchten Gebieten der Theoretischen Informatik gehören. Ein wichtiger Gegenstand sind Mengen von Zeichenketten, wie z. B. die Menge aller syntaktisch korrekten Programme einer Programmiersprache oder die Menge aller zulässigen Ereignissequenzen in einem technischen System. Es geht vor allem um Instrumente, mit denen solche Mengen beschrieben und Zeichenketten als Elemente solcher Mengen erkannt werden können, die also insbesondere bei der Definition und Übersetzung von Programmiersprachen und der Kontrolle technischer Systeme Verwendung finden. Außerdem wird gezeigt, dass Fragen, wie die eingangs gestellte, sich nicht algorithmisch und damit auch durch kein Computerprogramm beantworten lassen, wenn man sie für beliebige Programme stellt.

Kategorie: G (ECTS: 6)


Mail Address
University of Bremen
Dept. for Math. &
Computer Science
P.O. Box 330 440
28334 Bremen
Germany

Physical Address
Linzer Strasse 9a
OAS 3002
28359 Bremen

Phone
++49 (421) 218 3697
Fax
++49 (421) 218 4322

Email (Secr.)
Helga Reinermann
helga@tzi.de