SS 2011: Automaten und formale Sprachen

Dozent:
Dr. Sander Bruggink (Email)

Übungsleitung:
Jan Stückrath (Email)

Inhalt und Lernziele

Die Theorie der formalen Sprachen bildet die Grundlage für viele andere Gebiete der Informatik, beispielsweise für Informationsverarbeitung, Compilerbau, Verifikation, Modellierung. Im Rahmen dieser Veranstaltung werden die Grundlagen der formalen Sprachen vermittelt und Fertigkeiten im Umgang mit Automaten und Grammatiken eingeübt. Außerdem soll vermittelt werden, in welchen Bereichen diese Theorie zur Anwendung kommt. Im Einzelnen wird dabei behandelt:

  • Grammatiken, Chomsky-Hierarchie
  • Wortproblem, Syntaxbäume
  • Reguläre Sprachen (Endliche Automaten, Reguläre Ausdrücke, Pumping-Lemma, Äquivalenzrelationen und Minimalautomaten, Abschlusseigenschaften, Endscheidbarkeit, Anwendung: Verifikation eines Protokolls zum wechselseitigen Ausschluss)
  • Kontextfreie Sprachen (Normalformen, Pumping-Lemma, CYK-Algorithmus, Kellerautomaten, deterministisch kontextfreie Sprachen, Abschlusseigenschaften, Entscheidbarkeit)
  • Kontextsensitive und Typ-0-Sprachen

Die Vorlesung wird sich inhaltlich stark an der Vorlesung aus dem SS 2010 orientieren, wobei die Folien des aktuellen Semesters durchaus abweichen können.

Hinweise

  • Diese Vorlesung kann von Studierenden verschiedener Studiengänge gehört werden. Insbesondere handelt es sich dabei um:
    • Studierende im Duisburger Bachelor-Studiengang "Angewandte Informatik (Ingenieur- und Medieninformatik)"
    • Studierende mit Nebenfach Informatik
    • Studierende im Master-Studiengang "International Studies in Engineering"
  • Die Teilname an den Übungen und die Bearbeitung der Übungszettel ist dringend erwünscht, da sich ein Großteil des Stoffes durch Anwendung am Beispiel deutlich besser verstehen lässt als bei reinem Studium der Folien. Die Abgabe der Übungen ist sowohl online über MOODLE als auch in Papierform möglich. Die Papierabgaben müssen in den mit "Automaten und Formale Sprachen" beschrifteten Briefkasten neben Raum LF 259 geworfen werden.
    Es gilt folgende Bonuspunkteregelung:
    Den Bonus von einer Notenstufe (z.B. 2,0 statt 2,3) erhält, wer am Ende der Vorlesung mindestens 50% der Übungspunkte erhalten hat.
    Außerdem ist es möglich, durch Vorrechnen der eigenen Lösung während einer Übung einmalig Zusatzpunkte im Umfang eines halben Übungsblattes zu erreichen.

Prüfungen

  • Für Studierende des Bachelor-Studiengangs "Angewandte Informatik" wird am Ende des nächsten Wintersemesters eine mündliche Prüfung des Moduls "Theoretische Informatik" (in Kombination mit "Berechenbarkeit und Komplexität") stattfinden. Studenten im ersten Semester, die im nächsten Semester nicht "Berechenbarkeit und Komplexität" hören werden, können bereits dieses Semester eine mündliche Prüfung in "Automaten und formale Sprachen" ablegen.
  • Für die restlichen Studierenden (siehe Hinweise) wird am Ende dieses Sommersemesters eine schriftliche Klausur stattfinden. Nebenfach-Studenten melden sich bitte per Email an den Dozenten oder die Übungleitung an.
  • Für Schülerstudenten gelten die Regelungen des Studiengangs, für den sie eingetragen sind. Es ist keine Anmeldung beim Prüfungsamt erforderlich.

Literatur

Termine

Vorlesung:

  • Di, 12–14, LB 131

Die Vorlesung beginnt am Dienstag, den 5. April.

Übungen:

  • Mi, 12–14, LB 117, Gruppe ISE (Englisch)
  • Do, 14–16, LE 120, Gruppe 1 (Deutsch)
  • Do, 16–18, LE 120, Gruppe 2 (Deutsch)
  • Fr, 10–12, LE 120, Gruppe 3 (Deutsch)

Die Übungsgruppen beginnen in der dritten Vorlesungswoche (ab 20. April).

Klausur (SS 2011):

  • Tag: Di, der 16. August 2011
  • Uhrzeit: 8:30
  • Raum: LB 107 (nicht wie vorher angegeben LF 035)

mündliche Prüfungen (SS 2011):

  • Zeit: 1. - 3. und 5. August 2011
  • Raum: LF 265

Klausur (WS 2011/12):

  • Tag: Di, der 06. März 2012
  • Uhrzeit: 8:30
  • Raum: LA 013

Aktuelles

Keine Artikel in dieser Ansicht.

© Universität Duisburg-Essen, Lehrstuhl Theoretische InformatikLogin