622.100 (21S) Algorithms and Complexity Theory

Sommersemester 2021

Time for applications expired.

First appointment of the course
02.03.2021 08:00 - 10:00 online Off Campus
Next Appointment:
18.05.2021 08:00 - 10:00 online Off Campus

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
Lecture
Course model
Online course
Hours per Week
2.0
ECTS-credits
2.0
Registrations
14
Organisational Unit
Language of Instruction
German
Course begins on (set in LVOnline)
02.03.2021
eLearning
go to Moodle-Course

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

Learning Outcome

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 including the use of eLearning tools

Vorlesung

Course overview

  • 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

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.

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.

Link to further information

https://www.syssec.at/de/lehre/ss-2021/algorithmen-und-komplexitaetstheorie

Exam information

Modified examination information (exceptional COVID-19 provisions)

SPU, ggf. online (ROPE).

Exam methodology

Schriftliche Prüfung (SPU, ggf. ROPE) am Ende des Semesters.

Exam topics

Siehe Inhalte oben.

Exam mode

https://www.syssec.at/de/lehre/ss-2021/algorithmen-und-komplexitaetstheorie

Grading scheme

Grade / Grade grading scheme

Degree programmes

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

Equivalent Courses for counting the exam attempts

Sommersemester 2020
  • 622.100 VO Algorithmen und Komplexitätstheorie (2.0h / 2.0ECTS)
Wintersemester 2019/20
  • 622.100 VO Algorithmen und Komplexitätstheorie (2.0h / 2.0ECTS)
Wintersemester 2018/19
  • 622.100 VO Algorithmen und Komplexitätstheorie (2.0h / 2.0ECTS)
Wintersemester 2017/18
  • 622.100 VO Algorithmen und Komplexitätstheorie (2.0h / 2.0ECTS)
Wintersemester 2016/17
  • 622.100 VO Algorithmen und Komplexitätstheorie (2.0h / 2.0ECTS)
Wintersemester 2015/16
  • 622.100 VO Algorithmen und Komplexitätstheorie (2.0h / 2.0ECTS)
Wintersemester 2014/15
  • 622.100 VO Algorithmen und Komplexitätstheorie (2.0h / 2.0ECTS)
Wintersemester 2013/14
  • 622.100 VO Algorithmen und Komplexitätstheorie (2.0h / 2.0ECTS)
Wintersemester 2012/13
  • 622.100 VO Algorithmen und Komplexitätstheorie (2.0h / 2.0ECTS)
Wintersemester 2011/12
  • 622.100 VO Algorithmen und Komplexitätstheorie (2.0h / 2.0ECTS)
Wintersemester 2010/11
  • 622.100 VO Algorithmen und Komplexitätstheorie (2.0h / 2.0ECTS)
Wintersemester 2009/10
  • 622.100 VO Algorithmen und Komplexitätstheorie (2.0h / 2.0ECTS)