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

Theoretische Informatik 1: Endliche Automaten, kontextfreie Sprachen und Grundelemente der Berechenbarkeit (Wintersemester 2010/2011)



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.

VAK 03-05-G-601.01

Kategorie: G (ECTS: 6)

Termine

    Vorlesung: 2 SWS Mo von 10:00 - 12:00 GW2 B1400 (Die erste Vorlesung findet am 25.10. statt.)

    Übungen: 2 SWS (Beginn: 1.11.2010)

TutorInnen
Skript Folien
Aufgabenblätter Arbeitsbögen Fachgespräche
Kriterien zum Erwerb des Leistungsnachweises
    Der Leistungsnachweis wird durch regelmäßige Bearbeitung von Übungsaufgaben und ein Fachgespräch erworben. Es gibt 5 Übungsblätter, die überwiegend richtig bearbeitet werden müssen. Um die Bewertung transparenter zu machen, ist jeder Aufgabe eine Punktzahl zugeordnet. Die Summe der Punktzahlen pro Übungsblatt ist 100, von denen 50 erreicht werden müssen. Wird die Punktzahl nicht erreicht, kann mindestens einmal nachgearbeitet werden. Die Übungsaufgaben dürfen einzeln oder zu zweit oder zu dritt abgegeben werden. Die Fachgespräche dienen insbesondere zur Feststellung der individuellen Leistungsfähigkeit. Zur Orientierung gibt es einen Fragenkatalog , der sich auf den Stoff bezieht, der in der Vorlesung erarbeitet wird und im Skript dokumentiert ist. Das Nähere wird in den Tutorien besprochen. Wer die Bearbeitung der Übungsaufgaben nicht ausreichend schafft, kann auch eine mündliche Prüfung machen.

Kontakt
Prof. Dr. Hans-Jörg Kreowski
Raum: OAS 3001
kreo@informatik.uni-bremen.de

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

Physical Address
Bibliothekstrasse 5
MZH 5130
28359 Bremen

Phone
++49(421)218 64451