Berechenbarkeit und Komplexität (WS 2010/11)
Abschnittsübersicht
-
Berechenbarkeit und Komplexität (WS 2010/11)
In dieser LVA (der früheren "Formale Grundlagen 2") behandeln wir den formalen Berechenbarkeitsbegriff anhand von rekursiven Funktionen und Turingmaschinen. Darauf aufbauend befassen wir uns mit der Entscheidbarkeit bzw. Unentscheidbarkeit von Problemen, mit Komplexitätsklassen und vollständigen Problemen.
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.
-
Vorlesung (326.023)
A.Univ.Prof. DI Dr. Wolfgang Schreiner
Zeit: Freitag, 12:00-13:30
Raum: HS 10
Beginn: 15. Oktober 2010
Skriptum
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)
- Termin: Mittwoch, 30. März, 17:15-18:45, BA 9911.
- Anmeldung: bis Montag, 28. März 2010, 12:00 im KUSSS
- Unterlagen: sind zugelassen.
- Lichtbildausweis: nicht vergessen!
- Beispielklausur
- Ergebnisse
- Ergebnisse Nachklausur
-
Übungen (326.004, 326.016, 326.050)
Dr. Ralf Hemmecke (326.016, 326.050)
Zeit: Freitag 10:15-11:00, 11:00-11:45
Raum: HS 12
Beginn: 22. Oktober 2010
Mag. Burkhard Zimmermann (326.004)
Zeit: Freitag 11:00-11:45
Raum: K 033C
Beginn: 22. Oktober 2010
Übungsklausuren (für alle 3 Übungsgruppen):
(Unterlagen sind nicht zugelassen)
1. Klausur: 26.11.2010 11:00-11:45, H 5 (Lösungen, Ergebnisse)
2. Klausur: 21.01.2011 11:00-11:45, H 10 (Lösungen, Ergebnisse)