Berechenbarkeit und Komplexität (WS 2011/12)
Abschnittsübersicht
-
In dieser LVA behandeln wir den formalen Berechenbarkeitsbegriff anhand von verschiedenen mathematischen Modellen (endliche Automaten, Random Access Machines, Turingmaschinen, rekursiven Funktionen). Darauf aufbauend befassen wir uns mit dem Begriff der algorithmischen Komplexität, der Entscheidbarkeit bzw. Unentscheidbarkeit von Problemen, und mit der Kategorisierung von entscheidbaren Problemen in verschiedene Komplexitätsklassen.
Es wird vorausgesetzt, daß die Teilnehmer die mathematischen Voraussetzungen, wie sie in der LVA "Mathematische Grundlagen" geboten werden, mitbringen. Weiters werden Grundkenntnisse über Programmierung und Programmiersprachen vorausgesetzt.
Um an der Lehrveranstaltung teilzunehmen, müssen Sie sich wie üblich im KUSSS System dafür (jeweils Vorlesung und Übung separat) anmelden. Wenn Sie sich auch im Moodle einloggen und als Kursteilnehmer eintragen, erhalten Sie per Email alle ins "Ankündigen"-Forum gestellte Nachrichten und können selbst Nachrichten ins "Fragen und Antworten"-Forum stellen.
-
A.Univ.Prof. DI Dr. Wolfgang Schreiner
Zeit: Freitag, 12:00-13:30.
Raum: HS 10.
Beginn: 14. Oktober 2011Skriptum
Folien- Einführung und Organisation (4 auf 1)
- Algorithmen (4 auf 1)
- Endliche Automaten (4 auf 1)
- Random Access Machines (4 auf 1)
- Turing-Maschinen (4 auf 1)
- Die Chomsky-Hierarchie (4 auf 1)
- Rekursive Funktionen (4 auf 1)
- Komplexität von Algorithmen (4 auf 1)
- Entscheidbarkeit und Unentscheidbarkeit (4 auf 1)
- Problemkomplexität (4 auf 1)
Klausur
- 2. Termin: Mittwoch, 28. März 2012, 17:15-18:45, S2 052 (Science Park)
- Anmeldung: bis Montag, 26. März 2012, 12:00 im KUSSS.
- Unterlagen: sind zugelassen.
- Lichtbildausweis: nicht vergessen!
- Beispielklausur
- Ergebnisse
Weiterführende Literatur
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation (deutsche Ausgabe: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit)
- Dirk W. Hoffmann: Theoretische Informatik
- Katrin Erk und Lutz Priese: Theoretische Informatik: Eine umfassende Einführung
- Uwe Schöning: Theoretische Informatik - kurz gefasst
- Boris Hollas: Grundkurs Theoretische Informatik
Die Bücher von Hoffmann und von Erk/Priese umfassen den gesamten Stoff der LVA (während bei den anderen der Bereich der rekursiven Funktionen meist nicht vorkommt).
-
Dr. Ralf Hemmecke (326.016, 326.050)
Mag. Burkhard Zimmermann (326.004)Zeit: Freitag, 10:15-11:00 (326.016), 11:00-11:45 (326.050, 326.004)
Raum: HS 12 (326.016, 326.004), BA 9910 (326.050)
Beginn: 21. Oktober 2011Übungsklausuren (für alle 3 Übungsgruppen):
(Unterlagen sind nicht zugelassen)
1. Klausur: 25.11.2011 11:00-11:45, H 16 (Lösungen, Ergebnisse)
2. Klausur: 20.01.2012 11:00-11:45, H 16