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)

Online-Anmeldung: Anmeldung für die Veranstaltung!

ACHTUNG : Die erste Vorlesung findet am 25.10., 10.00 - 12.00 Uhr im GW2 B 1400 statt!!

  • Folien
  • Aufgabenblätter
  • Fragenkatalog für die Fachgespräche (pdf, ps, ps verkleinert)

  • Kriterien zum Erwerb des Leistungsnachweises
    • Am Anfang des Semesters wurde folgendes vereinbart:
      1. Der Leistungsnachweis wird üblicherweise durch regelmäßige Bearbeitung von Übungsaufgaben und ein Fachgespräch erworben. Es wird 5 oder 6 Übungsblätter geben, 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 mindestens 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.
      2. Die Organisation der Fachgespräche wird später besprochen (spätestens Ende Januar 2007).
      3. Alternativ zu Punkt 1 kann auch eine mündliche Prüfung gemacht werden.

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

Email (Secr.)
Helga Reinermann

helga@tzi.de