622.102 (22S) Algorithmen und Komplexitätstheorie
Überblick
Weitere Informationen zum Lehrbetrieb vor Ort finden Sie unter: https://www.aau.at/corona.
- Lehrende/r
- LV-Titel englisch Algorithms and Complexity Theory
- LV-Art Übung (prüfungsimmanente LV )
- LV-Modell Präsenzlehrveranstaltung
- Semesterstunde/n 2.0
- ECTS-Anrechnungspunkte 4.0
- Anmeldungen 7 (25 max.)
- Organisationseinheit
- Unterrichtssprache Deutsch
- mögliche Sprache/n der Leistungserbringung Deutsch , Englisch
- LV-Beginn 07.03.2022
- eLearning zum Moodle-Kurs
-
Anmerkungen
Zu "LV-Modell": Die LV wird als Präsenz-LV abgehalten. Sollte sich die Pandemie-Lage wieder verschärfen, wird auf On-line-Lehre umgestellt.
Zu "Zeit und Ort": Möglicherweise muss die Lehre in der KW 14 und in der KW 21 entfallen – es werden ggfs. entsprechende Ersatztermine vereinbart.
Zu "Sprache der Leistungserbringung": Sie können auf Deutsch gestellte Fragen auf Englisch beantworten.
- Seniorstudium Liberale Ja
Zeit und Ort
LV-Beschreibung
Intendierte Lernergebnisse
Aufbauend auf der Einführung in die theoretische Informatik setzt dieser LV fort mit der Betrachtung von Design-Prinzipien für schnelle bzw. effiziente Algorithmen. Die Betrachtung liegt hierbei auf den Komplexitätsmaßen Zeit und Platz, sowie deren Wechselwirkungen. Wir analysieren ausgewählte Algorithmen im Hinblick auf deren Komplexität und betrachten allgemeine Prinzipien und Vorgehensweisen für deren Konstruktion.
Lehrmethodik
Bearbeitung von Übungsbeispielen (wöchentlich). Wettbewerbe (z.B.: "Schnellster Algorithmus zur Lösung des Closest Pair of Points Problems") mit "Punkte-Preisen". Ausarbeitung und Vortrag kleinerer Themenbereiche in Form von "Video-Happen".
Inhalt/e
- Rekursive Algorithmen
- Zahlen- und Matrizenmultiplikation
- Greedy-Algorithmen und Matroide
- Deterministische Komplexitätsklassen
- Nichtdeterministische Komplexitätsklassen
- Die Klasse NP
- Reduktionen und Vollständigkeit
- Orakel-Turingmaschinen und polynomiale Hierarchie
- Approximationsalgorithmen
- Probabilistische Algorithmen und Komplexitätsklassen
- Interaktive Beweissysteme
- Schaltkreiskomplexität
Erwartete Vorkenntnisse
Grundkenntnisse des Turing-Maschinenmodells (LV "Einführung in die theoretische Informatik"); Basismaterial hierzu wird (zum Zwecke der Wiederholung, Auffrischung oder Eigenstudium) im Kurs zur Verfügung gestellt.
Programmierkenntnisse
Curriculare Anmeldevoraussetzungen
keine
Literatur
- Hopcroft, J. E.; Motwani, R. & Ullman, J. D. Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie, Addison-Wesley Longman Publishing Co., Inc., 1988 ∗ .
- Arora, S. & Barak, B. Computational Complexity: A Modern Approach, Cambridge University Press, 2009
- Papadimitriou, C. H. Computational Complexity, Addison-Wesley, 1994
- Garey, M. R. & Johnson, D. S. Computers and intractability, Freeman, 1979
Weitere relevante Quellen und weiterführende Literatur ist jeweils am Ende der einzelnen Kapitel angegeben.
Prüfungsinformationen
Geänderte Prüfungsinformationen (COVID-19 Ausnahmeregelung)
Bei Bedarf findet die LV und damit auch die immanente Beurteilung on-line statt.
Prüfungsmethode/n
Beurteilung der laufenden Mitarbeit (Ausarbeitung und Vortrag von Übungsbeispielen), Ergänzt durch optionale Beiträge (Wettbewerbe, Ausarbeitung von Themen etc.)
Prüfungsinhalt/e
Die Beispiele und Themen orientieren sich am Stoff der Vorlesung.
Beurteilungskriterien/-maßstäbe
Bei Übungsbeispielen ist der Maßstab die Korrektheit der Lösung, bei Wettbewerben das jeweilige Evaluierungskriterium (i.A. Laufzeit), bei Ausarbeitung von Themen die Qualität und der didaktische Ansatz.
Beurteilungsschema
Note BenotungsschemaPosition im Curriculum
- Diplom-Lehramtsstudium Unterrichtsfach Informatik und Informatikmanagement
(SKZ: 884, Version: 04W.7)
-
2.Abschnitt
-
Fach: Angewandte Informatik (LI 2.3)
(Pflichtfach)
-
Algorithmen und Komplexitätstheorie (
2.0h PR / 4.0 ECTS)
- 622.102 Algorithmen und Komplexitätstheorie (2.0h UE / 4.0 ECTS)
-
Algorithmen und Komplexitätstheorie (
2.0h PR / 4.0 ECTS)
-
Fach: Angewandte Informatik (LI 2.3)
(Pflichtfach)
-
2.Abschnitt
- Bachelorstudium Angewandte Informatik
(SKZ: 511, Version: 19W.2)
-
Fach: Vertiefung Informatik
(Wahlfach)
-
7.1 Algorithmen und Komplexitätstheorie (
2.0h UE / 4.0 ECTS)
- 622.102 Algorithmen und Komplexitätstheorie (2.0h UE / 4.0 ECTS) Absolvierung im 4., 5., 6. Semester empfohlen
-
7.1 Algorithmen und Komplexitätstheorie (
2.0h UE / 4.0 ECTS)
-
Fach: Vertiefung Informatik
(Wahlfach)
- Bachelorstudium Angewandte Informatik
(SKZ: 511, Version: 17W.1)
-
Fach: Mathematik und Statistik
(Wahlfach)
-
3.1 Algorithmen und Komplexitätstheorie (
2.0h UE / 4.0 ECTS)
- 622.102 Algorithmen und Komplexitätstheorie (2.0h UE / 4.0 ECTS) Absolvierung im 5. Semester empfohlen
-
3.1 Algorithmen und Komplexitätstheorie (
2.0h UE / 4.0 ECTS)
-
Fach: Mathematik und Statistik
(Wahlfach)
- Bachelorstudium Angewandte Informatik
(SKZ: 511, Version: 12W.1)
-
Fach: Mathematik und Statistik
(Wahlfach)
-
Algorithmen und Komplexitätstheorie (
2.0h UE / 4.0 ECTS)
- 622.102 Algorithmen und Komplexitätstheorie (2.0h UE / 4.0 ECTS)
-
Algorithmen und Komplexitätstheorie (
2.0h UE / 4.0 ECTS)
-
Fach: Mathematik und Statistik
(Wahlfach)
- Masterstudium Angewandte Informatik
(SKZ: 911, Version: 13W.1)
-
Fach: Vertiefung Informatik
(Pflichtfach)
-
Algorithmen und Komplexitätstheorie (
2.0h UE / 4.0 ECTS)
- 622.102 Algorithmen und Komplexitätstheorie (2.0h UE / 4.0 ECTS)
-
Algorithmen und Komplexitätstheorie (
2.0h UE / 4.0 ECTS)
-
Fach: Vertiefung Informatik
(Pflichtfach)
- Masterstudium Mathematics
(SKZ: 401, Version: 18W.1)
-
Fach: Discrete Mathematics
(Wahlfach)
-
6.2 Algorithms and Complexity (
2.0h UE / 4.0 ECTS)
- 622.102 Algorithmen und Komplexitätstheorie (2.0h UE / 4.0 ECTS)
-
6.2 Algorithms and Complexity (
2.0h UE / 4.0 ECTS)
-
Fach: Discrete Mathematics
(Wahlfach)
- Masterstudium Mathematics
(SKZ: 401, Version: 18W.1)
-
Fach: Applied Mathematics
(Wahlfach)
-
Lehrveranstaltungen aus den Vertiefungsfächern (
0.0h XX / 12.0 ECTS)
- 622.102 Algorithmen und Komplexitätstheorie (2.0h UE / 4.0 ECTS)
-
Lehrveranstaltungen aus den Vertiefungsfächern (
0.0h XX / 12.0 ECTS)
-
Fach: Applied Mathematics
(Wahlfach)
Gleichwertige Lehrveranstaltungen im Sinne der Prüfungsantrittszählung
-
Sommersemester 2021
- 622.102 UE Algorithmen und Komplexitätstheorie (2.0h / 4.0ECTS)
-
Sommersemester 2020
- 622.102 PR Algorithmen und Komplexitätstheorie (2.0h / 4.0ECTS)
-
Wintersemester 2019/20
- 622.102 PR Algorithmen und Komplexitätstheorie (2.0h / 4.0ECTS)
-
Wintersemester 2018/19
- 622.102 PR Algorithmen und Komplexitätstheorie (2.0h / 4.0ECTS)
-
Wintersemester 2017/18
- 622.102 PR Algorithmen und Komplexitätstheorie (2.0h / 4.0ECTS)
-
Wintersemester 2016/17
- 622.102 PR Algorithmen und Komplexitätstheorie (2.0h / 4.0ECTS)
-
Wintersemester 2015/16
- 622.102 PR Algorithmen und Komplexitätstheorie (2.0h / 4.0ECTS)
-
Wintersemester 2014/15
- 622.102 PR Algorithmen und Komplexitätstheorie (2.0h / 4.0ECTS)
-
Wintersemester 2013/14
- 622.102 PR Algorithmen und Komplexitätstheorie (2.0h / 4.0ECTS)
-
Wintersemester 2012/13
- 622.102 PR Algorithmen und Komplexitätstheorie (2.0h / 4.0ECTS)
-
Wintersemester 2011/12
- 622.102 PR Algorithmen und Komplexitätstheorie (2.0h / 4.0ECTS)
-
Wintersemester 2010/11
- 622.102 PR Algorithmen und Komplexitätstheorie (2.0h / 4.0ECTS)
-
Wintersemester 2009/10
- 622.101 PR Algorithmen und Komplexitätstheorie (2.0h / 4.0ECTS)