622.102 (13W) Algorithms and Complexity Theory

Wintersemester 2013/14

Registration deadline has expired.

First course session
01.10.2013 12:00 - 14:00 S.2.42 On Campus
... no further dates known

Overview

Lecturer
Course title german Algorithmen und Komplexitätstheorie
Type Practical class (continuous assessment course )
Hours per Week 2.0
ECTS credits 4.0
Registrations 18 (25 max.)
Organisational unit
Language of instruction German
Course begins on 01.10.2013

Time and place

List of events is loading...

Course Information

Course content

Topics

  • 1 Einführung und Überblick
  • 2 Fundamentalsatz und Lösen von Rekursionen
  • 3 Zahlen- und Matrizenmultiplikation
  • 4 Greedy-Algorithmen und Matroide
  • 5 Deterministische Komplexitätsklassen
  • 6 Nichtdeterministische Komplexitätsklassen
  • 7 Reduktionen und Vollständigkeit
  • 8 NP-vollständige Probleme
  • 9 Approximationsalgorithmen
  • 10 Probabilistische Algorithmen und Komplexitätsklassen
  • 11 Orakel-Turingmaschinen und polynomiale Hierarchie
  • 12 Zero-Knowledge Proofs und die Klasse IP
  • 13 Schaltkreiskomplexität

Link to further information

http://www.syssec.at/auk13/

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.

Grading scheme

Grade / Grade grading scheme

Position in the curriculum

  • 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 PR / 4.0 ECTS)
  • Bachelorstudium Informatik (SKZ: 521, Version: 09W.3)
    • Subject: Algorithmen und Komplextheorie (Compulsory elective)
      • Algorithmen und Komplexitätstheorie ( 2.0h PR / 4.0 ECTS)
        • 622.102 Algorithms and Complexity Theory (2.0h PR / 4.0 ECTS)
  • Bachelor's degree programme Informatics (SKZ: 521, Version: 03W.1)
    • Subject: Algorithmen und Komplexitätstheorie (Compulsory subject)
      • Algorithmen und Komplexitätstheorie ( 2.0h PR / 4.0 ECTS)
        • 622.102 Algorithms and Complexity Theory (2.0h PR / 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 PR / 4.0 ECTS)
  • Masterstudium Informatik (SKZ: 921, Version: 09W.1)
    • Subject: Algorithmen und Komplexitätstheorie (Compulsory subject)
      • Algorithmen und Komplexitätstheorie ( 2.0h PR / 4.0 ECTS)
        • 622.102 Algorithms and Complexity Theory (2.0h PR / 4.0 ECTS)
  • Master's degree programme Informatics (SKZ: 921, Version: 03W.1)
    • Subject: Algorithmen und Komplexitätstheorie (Compulsory subject)
      • Algorithmen und Komplexitätstheorie ( 2.0h PR / 4.0 ECTS)
        • 622.102 Algorithms and Complexity Theory (2.0h PR / 4.0 ECTS)
  • Master's degree programme Technical Mathematics (SKZ: 401, Version: 13W.1)
    • Subject: Diskrete Mathematik (Compulsory elective)
      • Algorithmen und Komplexitätstheorie ( 2.0h PR / 4.0 ECTS)
        • 622.102 Algorithms and Complexity Theory (2.0h PR / 4.0 ECTS)
  • Master's degree programme Technical Mathematics (SKZ: 401, Version: 03W.2)
    • Subject: Datensicherheit und Kryptologie (Compulsory subject)
      • Höhere Kryptologie ( 3.0h VK / 6.0 ECTS)
        • 622.102 Algorithms and Complexity Theory (2.0h PR / 4.0 ECTS)
  • Master's degree programme Technical Mathematics (SKZ: 401, Version: 03W.2)
    • Subject: Operations Research (Compulsory subject)
      • Komplexitätstheorie ( 3.0h VK / 6.0 ECTS)
        • 622.102 Algorithms and Complexity Theory (2.0h PR / 4.0 ECTS)

Equivalent courses for counting the examination attempts

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