Art der Veranstaltung: Vorlesung und Übung
Thema der Veranstaltung sind Grundlagen von deterministischen und nichtdeterministischen Algorithmen und ihrer Komplexität. Im einzelnen:
- Turingmaschinen,
- Chomsky Hierarchie,
- Berechenbarkeit und Entscheidbarkeit,
- Komplexität,
- NP-Vollständigkeit.
Die Veranstaltung findet statt: jährlich im Sommersemester.
Empfohlene Literatur:
J. E. Hopcroft, R. Motwani und J. D. Ullman:
Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie, 2. Auflage, Pearson Studium 2002.
H.R. Lewis und C.H. Papdimitriou:
Elements of the Theory of Computation,2. Auflage, Prentice Hall, 1998.
Diese Lehrveranstaltung wird angeboten in folgenden Studiengängen:
- Diplom - Informatik
- Diplom - Wirtschaftsinformatik
- Bachelor - Informatik 2008
- Bachelor - Informatik
- Bachelor - Mathematik
- Master - Informations-Systemtechnik
- Bachelor - Wirtschaftsinformatik 2008
| Workload: | 150 h |
| Präsenzzeit: | 56 h |
| Selbststudium: | 94 h |
| Anzahl Semester: | 1 |
| Leistungspunkte: | 5 |
| SWS: | 3+1 |
aktualisiert am 31.10.2008
