Theoretische Informatik II (Sommersemester 2014)

Dozent: Prof. Dr. Jürgen Dassow , Dr. Henning Bordihn (Gastdozenten oder Dozenten der Uni-Potsdam)

Allgemeine Information

• Semesterwochenstunden: 4
• ECTS: 6
• Benotet: Ja
• Einschreibefrist: 1.4.2014 - 28.4.2014
• Lehrform: VU
• Belegungsart: Pflichtmodul

Studiengänge, Modulgruppen & Module

Beschreibung

• Endliche Automaten versus reguläre Grammatiken
• Kellerautomaten versus kontextfreie Grammatiken
• Abschluss- und Entscheidbarkeitseigenschaften der Sprachen der Chomsky-Hierarchie
• reguläre Ausdrücke für reguläre Sprachen
• Zeit- und Raumkomplexität
• NP-Vollständigkeit
• Beschreibungskomplexität
• Minimierung endlicher deterministischer Automaten

Lern- und Lehrformen

Vorlesung und Übung

Leistungserfassung

Die Leistungsbewertung erfolgt durch eine abschließende Klausur.

Zulassungsvoraussetzung für die Klausur ist die erfolgreiche Teilnahme an den Übungen.

Die Teilnahme an den Übungen ist für Studierende erfolgreich, wenn er oder sie durch Votierungen für mindestens zwei Drittel aller Übungsaufgaben erklärt, dass er oder sie die Lösung der jeweiligen Übungsaufgaben präsentieren kann und dies auf Aufforderung nachweist.

Termine

Zeiten und Raum siehe aktueller Stundenplan!

 

Vorlesung 

• Montags

 

Übungen

• Gruppe 1: Montags
• Gruppe 2: Montags
• Gruppe 3: Montags
• Gruppe 4: Dienstags

 

Die zwei Übungen am 14.04.2014 bei Herrn Dr. Bordihn entfallen. Nachholtermine: 

• Mittwoch, 23.04.2014, 17.00 - 18.30 Uhr, Raum A-1.1
• Freitag, 25.04.2014, 13.30 - 15.00 Uhr, Raum A-1.1

Die Übungen am Ostermontag (21.04.2014) sowie am Dienstag (22.04.2014) entfallen.

Zurück