Berechenbarkeit und Komplexität (WS 2007/08)
Abschnittsübersicht
-
Berechenbarkeit und Komplexität (WS 2007/08)
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, dass 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.
Ort: HS 10.
Beginn: 5. Oktober 2007.
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: Freitag, 1. Februar 2008, 12:00-13:30, HS10
- Anmeldung: bis Donnerstag, 31.1.2008, 12:00 im KUSSS
- Unterlagen: sind zugelassen.
- Lichtbildausweis: nicht vergessen!
- Beispielklausur
- Ergebnisse
- Termin: Dienstag, 1. April 2008, 17:15-18:45, K269D.
- Anmeldung: bis Montag, 31.März.2008, 12:00 im KUSSS
- Unterlagen: sind zugelassen.
- Lichtbildausweis: nicht vergessen!
-
Übungen (326.304, 326.305, 326.050)
Dr. Ralf Hemmecke (326.304, 326.050)
Zeit: Freitag 10:15-11:00 (326.304), 11:00-11:45 (326.050)
Ort: HS12
Beginn: 12. Oktober 2007
Dipl.Inf. Christoph Koutschan (326.305)
Zeit: Freitag 11:00-11:45
Ort: K033C
Beginn: 12. Oktober 2007
Übungsklausuren (für alle 3 Übungsgruppen):
1. Klausur: 30.11.2007 11:00-11:45 H 10 (Lösungen, Ergebnisse)
2. Klausur: 25.01.2008 12:00-12:45 H 10 (Lösungen, Ergebnisse)
Übungszettel