Theoretische Informatik II (Sommersemester 2014)

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

General Information

• Weekly Hours: 4
• Credits: 6
• Graded: yes
• Enrolment Deadline: 1.4.2014 - 28.4.2014
• Teaching Form: VU
• Enrolment Type: Compulsory Module

Programs, Module Groups & Modules

Description

• 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

Learning

Vorlesung und Übung

Examination

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.

Dates

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