622.102 (20S) Algorithmen und Komplexitätstheorie

Sommersemester 2020

Anmeldefrist abgelaufen.

Erster Termin der LV
11.03.2020 08:30 - 10:00 N.1.04 On Campus
... keine weiteren Termine bekannt

Überblick

Lehrende/r
LV-Titel englisch Algorithms and Complexity Theory
LV-Art Praktikum (prüfungsimmanente LV )
Semesterstunde/n 2.0
ECTS-Anrechnungspunkte 4.0
Anmeldungen 4 (25 max.)
Organisationseinheit
Unterrichtssprache Deutsch
LV-Beginn 11.03.2020
eLearning zum Moodle-Kurs

Zeit und Ort

Liste der Termine wird geladen...

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 inkl. Einsatz von eLearning-Tools

Bearbeitung von Übungsbeispielen (wöchentlich) und Programmieraufgaben (insgesamt 3 Abgaben verteilt über das gesamte Semester)

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.

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.

Link auf weitere Informationen

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

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.

Prüfungsmethode/n

Aktive Mitarbeit im Praktikum und Online-Klausur am Ende des Semesters

Prüfungsinhalt/e

gesamter Stoff des Praktikums (aufbauend auf der zugehörigen Vorlesung)

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 PR / 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 PR / 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 PR / 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 PR / 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 PR / 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 PR / 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 PR / 4.0 ECTS)
  • Masterstudium Technische Mathematik (SKZ: 401, Version: 13W.1)
    • Fach: Diskrete Mathematik (Wahlfach)
      • Algorithmen und Komplexitätstheorie ( 2.0h PR / 4.0 ECTS)
        • 622.102 Algorithmen und Komplexitätstheorie (2.0h PR / 4.0 ECTS)

Gleichwertige Lehrveranstaltungen im Sinne der Prüfungsantrittszählung

Sommersemester 2022
  • 622.102 UE Algorithmen und Komplexitätstheorie (2.0h / 4.0ECTS)
Sommersemester 2021
  • 622.102 UE 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)