622.102 (22S) Algorithms and Complexity Theory

Sommersemester 2022

Registration deadline has expired.

First course session
07.03.2022 08:30 - 10:00 S.2.42 On Campus
... no further dates known

Overview

Due to the COVID-19 pandemic, it may be necessary to make changes to courses and examinations at short notice (e.g. cancellation of attendance-based courses and switching to online examinations).

For further information regarding teaching on campus, please visit: https://www.aau.at/en/corona.
Lecturer
Course title german Algorithmen und Komplexitätstheorie
Type Practical class (continuous assessment course )
Course model Attendance-based course
Hours per Week 2.0
ECTS credits 4.0
Registrations 7 (25 max.)
Organisational unit
Language of instruction German
possible language(s) of the assessment German , English
Course begins on 07.03.2022
eLearning Go to Moodle course
Seniorstudium Liberale Yes

Time and place

Please note that the currently displayed dates may be subject to change due to COVID-19 measures.
List of events is loading...

Course Information

Intended learning outcomes

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.

Teaching methodology

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".

Course content

  • 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

Prior knowledge expected

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

Curricular registration requirements

keine

Literature

  • 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.

Examination information

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.

Modified examination information (exceptional COVID-19 provisions)

Bei Bedarf findet die LV und damit auch die immanente Beurteilung on-line statt.

Examination methodology

Beurteilung der laufenden Mitarbeit (Ausarbeitung und Vortrag von Übungsbeispielen), Ergänzt durch optionale Beiträge (Wettbewerbe, Ausarbeitung von Themen etc.)

Examination topic(s)

Die Beispiele und Themen orientieren sich am Stoff der Vorlesung.

Assessment criteria / Standards of assessment for examinations

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.

Grading scheme

Grade / Grade grading scheme

Position in the curriculum

  • Teacher training programme Computer Sciences and Computer Sciences Management (Secondary School Teacher Accreditation) (SKZ: 884, Version: 04W.7)
    • Stage two
      • Subject: Angewandte Informatik (LI 2.3) (Compulsory subject)
        • Algorithmen und Komplexitätstheorie ( 2.0h PR / 4.0 ECTS)
          • 622.102 Algorithms and Complexity Theory (2.0h UE / 4.0 ECTS)
  • Bachelor's degree programme Applied Informatics (SKZ: 511, Version: 19W.2)
    • Subject: Vertiefung Informatik (Compulsory elective)
      • 7.1 Algorithmen und Komplexitätstheorie ( 2.0h UE / 4.0 ECTS)
        • 622.102 Algorithms and Complexity Theory (2.0h UE / 4.0 ECTS)
          Absolvierung im 4., 5., 6. Semester empfohlen
  • Bachelor's degree programme Applied Informatics (SKZ: 511, Version: 17W.1)
    • Subject: Mathematics and Statistics (Compulsory elective)
      • 3.1 Algorithmen und Komplexitätstheorie ( 2.0h UE / 4.0 ECTS)
        • 622.102 Algorithms and Complexity Theory (2.0h UE / 4.0 ECTS)
          Absolvierung im 5. Semester empfohlen
  • Bachelor's degree programme Applied Informatics (SKZ: 511, Version: 12W.1)
    • Subject: Mathematics and Statistics (Compulsory elective)
      • Algorithmen und Komplexitätstheorie ( 2.0h UE / 4.0 ECTS)
        • 622.102 Algorithms and Complexity Theory (2.0h UE / 4.0 ECTS)
  • Master's degree programme Applied Informatics (SKZ: 911, Version: 13W.1)
    • Subject: Vertiefung Informatik (Compulsory subject)
      • Algorithmen und Komplexitätstheorie ( 2.0h UE / 4.0 ECTS)
        • 622.102 Algorithms and Complexity Theory (2.0h UE / 4.0 ECTS)
  • Masterstudium Mathematics (SKZ: 401, Version: 18W.1)
    • Subject: Discrete Mathematics (Compulsory elective)
      • 6.2 Algorithms and Complexity ( 2.0h UE / 4.0 ECTS)
        • 622.102 Algorithms and Complexity Theory (2.0h UE / 4.0 ECTS)
  • Masterstudium Mathematics (SKZ: 401, Version: 18W.1)
    • Subject: Applied Mathematics (Compulsory elective)
      • Lehrveranstaltungen aus den Vertiefungsfächern ( 0.0h XX / 12.0 ECTS)
        • 622.102 Algorithms and Complexity Theory (2.0h UE / 4.0 ECTS)

Equivalent courses for counting the examination attempts

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)