622.100 (19W) Algorithms and Complexity Theory
Overview
- Lecturer
- Course title german Algorithmen und Komplexitätstheorie
- Type Lecture
- Hours per Week 2.0
- ECTS credits 2.0
- Registrations 20
- Organisational unit
- Language of instruction German
- Course begins on 01.10.2019
- eLearning Go to Moodle course
Time and place
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 including the use of eLearning tools
Vorlesung
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.
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/ws-2019/algorithmen-und-komplexitaetstheorie
Examination information
Examination methodology
Online-Klausur am Ende des Semesters
Examination topic(s)
Stoff der gesamten Vorlesung
Assessment criteria / Standards of assessment for examinations
siehe https://www.syssec.at/de/lehre/ws-2019/algorithmen-und-komplexitaetstheorie/modalitaeten
Grading scheme
Grade / Grade grading schemePosition 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 VO / 2.0 ECTS)
- 622.100 Algorithms and Complexity Theory (2.0h VO / 2.0 ECTS)
-
Algorithmen und Komplexitätstheorie (
2.0h VO / 2.0 ECTS)
-
Subject: Angewandte Informatik (LI 2.3)
(Compulsory subject)
-
Stage two
- Bachelor's degree programme Applied Informatics
(SKZ: 511, Version: 19W.2)
-
Subject: 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
-
7.1 Algorithmen und Komplexitätstheorie (
2.0h VO / 2.0 ECTS)
-
Subject: Vertiefung Informatik
(Compulsory elective)
- 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 VO / 2.0 ECTS)
- 622.100 Algorithms and Complexity Theory (2.0h VO / 2.0 ECTS) Absolvierung im 5. Semester empfohlen
-
3.1 Algorithmen und Komplexitätstheorie (
2.0h VO / 2.0 ECTS)
-
Subject: Mathematics and Statistics
(Compulsory elective)
- Bachelor's degree programme Applied Informatics
(SKZ: 511, Version: 12W.1)
-
Subject: 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)
-
Algorithmen und Komplexitätstheorie (
2.0h VO / 2.0 ECTS)
-
Subject: Mathematics and Statistics
(Compulsory elective)
- Master's degree programme Applied Informatics
(SKZ: 911, Version: 13W.1)
-
Subject: 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)
-
Algorithmen und Komplexitätstheorie (
2.0h VO / 2.0 ECTS)
-
Subject: Vertiefung Informatik
(Compulsory subject)
- Master's degree programme Mathematics
(SKZ: 401, Version: 18W.1)
-
Subject: 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)
-
6.2 Algorithms and Complexity (
2.0h VO / 2.0 ECTS)
-
Subject: Discrete Mathematics
(Compulsory elective)
- Master's degree programme Mathematics
(SKZ: 401, Version: 18W.1)
-
Subject: 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)
-
Lehrveranstaltungen aus den Vertiefungsfächern (
0.0h XX / 12.0 ECTS)
-
Subject: Applied Mathematics
(Compulsory elective)
- Master's degree programme Technical Mathematics
(SKZ: 401, Version: 13W.1)
-
Subject: 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)
-
Algorithmen und Komplexitätstheorie (
2.0h VO / 2.0 ECTS)
-
Subject: Diskrete Mathematik
(Compulsory elective)
Equivalent courses for counting the examination attempts
-
Sommersemester 2022
- 622.100 VO Algorithmen und Komplexitätstheorie (2.0h / 2.0ECTS)
-
Sommersemester 2021
- 622.100 VO Algorithmen und Komplexitätstheorie (2.0h / 2.0ECTS)
-
Sommersemester 2020
- 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)