Theoretische Informatik I (Wintersemester 2013/2014)

Dozent: Prof. Dr. Jürgen Dassow
Tutoren: Dr. Henning Bordihn

Allgemeine Information

• Semesterwochenstunden: 4
• ECTS: 6
• Benotet: Ja
• Einschreibefrist: 1.10.2013 - 31.10.2013
• Lehrform: VU
• Belegungsart: Pflichtmodul

Studiengänge, Modulgruppen & Module

Beschreibung

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

Literatur

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.

Lern- und Lehrformen

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

Leistungserfassung

Klausur (120 Minuten)

Termine

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

Die Vorlesung beginnt am 23.10.

Zurück