Berechenbarkeit und Komplexität (WS 2008/09)
Sie dürfen die Themen in diesem Forum nicht sehen
Abschnittsübersicht
-
Berechenbarkeit und Komplexität (WS 2008/09)
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 den LVAen Mathematik für Informatiker I und II 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 (Vorlesung und Übung) anmelden. Wenn Sie sich auch im Moodle einloggen und als Kursteilnehmer eintragen, erhalten Sie per Email alle im Nachrichtenforum geposteten Nachrichten. -
Vorlesung (326.009)
A.Univ.Prof. DI Dr. Wolfgang Schreiner
Zeit: Freitag 12:00-13:30
Raum: HS 10
Beginn: 10. Oktober 2008
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)
- Rekursive Funktionen (4 auf 1)
- Komplexität von Algorithmen (4 auf 1)
- Entscheidbarkeit und Unentscheidbarkeit (4 auf 1)
- Problemkomplexität (4 auf 1)
- Termin: Montag, 30. März 2009, 17:15-18:45, HF 9901
- Anmeldung: bis Donnerstag, 26. März 2009, 12:00 im KUSSS
- Unterlagen: sind zugelassen.
- Lichtbildausweis: nicht vergessen!
Klausurergebnisse 30.1.2009
Klausurergebnisse 30.3.2009 -
Übungen (326.004, 326.316, 326.050)
Dr. Ralf Hemmecke (326.316, 326.050)
Zeit: Freitag 10:15-11:00, 11:00-11:45
Raum: HS 14
Beginn: 17. Oktober 2008
Dipl.Math. Johannes Middeke (326.004)
Zeit: Freitag 11:00-11:45
Raum: K033 C
Beginn: 17. Oktober 2008
Übungsklausuren (für alle 3 Übungsgruppen):
1. Klausur: 28.11.2008 11:00-11:45 H 10 (Lösungen, Ergebnisse)
2. Klausur: 16.01.2009 11:00-11:45 H 10 (Lösungen, Ergebnisse)
Übungszettel
- Aufgaben zum 17.10.2008
- Aufgaben zum 24.10.2008
- Aufgaben zum 31.10.2008
- Aufgaben zum 07.11.2008
- Aufgaben zum 14.11.2008
- Aufgaben zum 21.11.2008
- Aufgaben zum 05.12.2008
- Aufgaben zum 12.12.2008
- Aufgaben zum 19.12.2008
- Aufgaben zum 09.01.2009
- Aufgaben zum 23.01.2009