Computational complexity WM-I-ZO
The aim of the course is to provide knowledge of the basics of computational complexity: abstract machines, calculation models and classes of complexity. After completing the course the student should know and understand the practical consequences of belonging to a problem, e.g. P or NP classes and the differences between the algorithm solving a given task and the heuristic or approximation algorithm.
(in Polish) Dyscyplina naukowa, do której odnoszą się efekty uczenia się
(in Polish) E-Learning
Term 2023/24_Z: (in Polish) E-Learning (pełny kurs) z podziałem na grupy | Term 2019/20_Z: (in Polish) E-Learning (pełny kurs) | Term 2021/22_Z: (in Polish) E-Learning (pełny kurs) z podziałem na grupy | Term 2020/21_Z: (in Polish) E-Learning (pełny kurs) z podziałem na grupy | Term 2022/23_Z: (in Polish) E-Learning (pełny kurs) z podziałem na grupy | Term 2024/25_Z: (in Polish) E-Learning |
(in Polish) Grupa przedmiotów ogólnouczenianych
(in Polish) Opis nakładu pracy studenta w ECTS
Term 2023/24_Z: Estimated student workload:
- participation in classes 30 h,
- preparation for classes 10 h,
- preparation for verification 25 h,
- project 10 h,
- consultations with the teacher 1 h,
76 h in total, corresponding to 3 ECTS. | Term 2019/20_Z: LECTURE
Estimated student workload:
- participation in 15-hour classes,
- preparation for verification 30 h,
- consultations with the tutor for 2 hours,
47 h in total, corresponding to 2 ECTS.
LABORATORIES
Estimated student workload:
- participation in 15-hour classes,
- preparation for verification 10 h,
- 5 h project,
- consultations with the tutor for 1 hour,
31 h in total, corresponding to 1 ECTS. | Term 2021/22_Z: Estimated student workload:
- participation in classes 30 h,
- preparation for classes 10 h,
- preparation for verification 25 h,
- project 10 h,
- consultations with the teacher 1 h,
76 h in total, corresponding to 3 ECTS. | Term 2020/21_Z: LECTURE
Estimated student workload:
- participation in 15-hour classes,
- preparation for verification 30 h,
- consultations with the tutor for 2 hours,
47 h in total, corresponding to 2 ECTS.
LABORATORIES
Estimated student workload:
- participation in 15-hour classes,
- preparation for verification 10 h,
- 5 h project,
- consultations with the tutor for 1 hour,
31 h in total, corresponding to 1 ECTS. | Term 2022/23_Z: Estimated student workload:
- participation in classes 30 h,
- preparation for classes 10 h,
- preparation for verification 25 h,
- project 10 h,
- consultations with the teacher 1 h,
76 h in total, corresponding to 3 ECTS. | Term 2024/25_Z: Estimated student workload:
- participation in classes 30 h,
- preparation for classes 10 h,
- preparation for verification 25 h,
- project 10 h,
- consultations with the teacher 1 h,
76 h in total, corresponding to 3 ECTS. |
Subject level
Learning outcome code/codes
Type of subject
Preliminary Requirements
Course coordinators
Learning outcomes
Student"
W1 - knows and understands the concepts of computational and decision problems, abstract machines, undecidability, computational complexity classes and their interrelationships (I2_W01, I2_W11),
U1 - can construct abstract machines for moderately complex decision and computational problems, can analyze algorithms in terms of time and memory complexity, can provide examples of problems belonging to different complexity classes (I2_U01, I2_U06).
Assessment criteria
For all learning outcomes, the following assessment criteria are adopted for all forms of verification:
grade 5: fully achieved (no obvious shortcomings),
grade 4.5: achieved almost fully and criteria for awarding a higher grade are not met,
grade 4: largely achieved and the criteria for a higher grade are not met,
grade 3.5: largely achieved - with a clear majority of positives - and the criteria for granting a higher grade are not met,
grade 3: achieved for most of the cases covered by the verification and criteria for a higher grade are not met,
grade 2: not achieved for most of the cases covered by the verification.
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: