Theoretische Informatik I (Wintersemester 2013/2014)

Lecturer: Prof. Dr. Jürgen Dassow
Tutors: Dr. Henning Bordihn

General Information

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

Programs, Module Groups & Modules

Description

Berechenbarkeit auf der Basis von LOOP/WHILE-Programmen, partiell-rekursiven Funktionen, Registermaschinen, Turingmaschinen;

Äquivalenz der Berechenbarkeitsbegriffe;

Existenz von durch Algorithmen nicht berechenbarer Funktionen und unentscheidbarer Probleme;

Beispiele unentscheidbarer Probleme;

formale Grammatiken und die von ihnen erzeugten Sprachen;

rekursiv-aufzählbare, kontextabhängige, kontextfreie und reguläre Sprachen;

Normalformen;

Chomsky-Hierarchie

Literature

U. Schöning: Theoretische Informatik kurz gefasst. B.I.-Wissenschaftsverlag, 1992.

K. Wagner: Einführung in die Theoretische Informatik. Springer-Verlag, 2003.

I. Wegener: Theoretische Informatik. Teubner-Verlag, 1993.

J.E. Hopcroft, J.D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2. Aufl., Addison-Wesley, 1990.

G. Vossen, K.-U. Witt: Grundlagen der Theoretischen Informatik mit Anwendungen.

Vieweg-Verlag, Braunschweig, 2000.

A. Asteroth, Ch. Baier: Theoretische Informatik. Pearson Studium, 2002.

Learning

Ein Skript wird zur Verfügung gestellt.

Die Folien zur Vorlesung und wöchentliche Übungsaufgaben können hier abgerufen werden:

theo.cs.uni-magdeburg.de/lehre/lehre13w/potsdam

Examination

Klausur (120 Minuten)

Dates

Mittwoch, 11:00-12:30 Uhr, HS 1

Die Vorlesung beginnt am 23.10.

Zurück