622.102 (22S) Algorithmen und Komplexitätstheorie

Sommersemester 2022

Anmeldefrist abgelaufen.

Erster Termin der LV
07.03.2022 08:30 - 10:00 On Campus

... keine weiteren Termine bekannt

Überblick

Bedingt durch die COVID-19-Pandemie können kurzfristige Änderungen bei Lehrveranstaltungen und Prüfungen (z.B. Absage von Präsenz-Lehreveranstaltungen und Umstellung auf Online-Prüfungen) erforderlich sein.

Weitere Informationen zum Lehrbetrieb vor Ort finden Sie unter: https://www.aau.at/corona.

Lehrende/r

Univ.-Prof. Dipl.-Ing. Dr. Martin Hitz

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

Institut für Informatik-Systeme

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

Zeit und Ort

Beachten Sie bitte, dass sich aufgrund von COVID-19-Maßnahmen die derzeit angezeigten Termine noch ändern können.

Liste der Termine wird geladen...

LV-Beschreibung

Deutsch

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

Im Fall von online durchgeführten Prüfungen sind die Standards zu beachten, die die technischen Geräte der Studierenden erfüllen müssen, um an diesen Prüfungen teilnehmen zu können.

Deutsch

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 Benotungsschema

Position 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)

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

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

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)

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)

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)

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)

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)