Computational complexity
General data
Course ID: | WM-I-ZO |
Erasmus code / ISCED: | (unknown) / (unknown) |
Course title: | Computational complexity |
Name in Polish: | Złożoność obliczeniowa |
Organizational unit: | Faculty of Mathematics and Natural Sciences. School of Exact Sciences. |
Course groups: |
(in Polish) INFORMATYKA II stopnia - rozkład zajęć: II rok |
Course homepage: | https://e.uksw.edu.pl/ |
ECTS credit allocation (and other scores): |
3.00
|
Language: | Polish |
(in Polish) Dyscyplina naukowa, do której odnoszą się efekty uczenia się: | information and communication technology |
Subject level: | intermediate |
Learning outcome code/codes: | I2_W01, I2_W11, I2_U01, I2_U06 |
Preliminary Requirements: | logic, algorithms and data structures, discrete mathematics |
Full description: |
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. |
Efekty kształcenia i opis ECTS: |
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 methods and 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. |
Classes in period "Winter semester 2021/22" (past)
Time span: | 2021-10-01 - 2022-01-31 |
Navigate to timetable
MO TU W KON
TH FR |
Type of class: |
Conversatorium, 30 hours
|
|
Coordinators: | Dorota Dąbrowska | |
Group instructors: | Dorota Dąbrowska | |
Students list: | (inaccessible to you) | |
Examination: | graded credit | |
(in Polish) E-Learning: | (in Polish) E-Learning (pełny kurs) z podziałem na grupy |
|
(in Polish) Opis nakładu pracy studenta w ECTS: | 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. |
Classes in period "Winter semester 2022/23" (past)
Time span: | 2022-10-01 - 2023-01-31 |
Navigate to timetable
MO TU KON
W TH FR |
Type of class: |
Conversatorium, 30 hours
|
|
Coordinators: | Dorota Dąbrowska | |
Group instructors: | Dorota Dąbrowska | |
Students list: | (inaccessible to you) | |
Examination: |
Course -
graded credit
Conversatorium - graded credit |
|
(in Polish) E-Learning: | (in Polish) E-Learning (pełny kurs) z podziałem na grupy |
|
(in Polish) Opis nakładu pracy studenta w ECTS: | 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. |
Classes in period "Winter semester 2023/24" (past)
Time span: | 2023-10-01 - 2024-01-31 |
Navigate to timetable
MO TU KON
W TH FR |
Type of class: |
Conversatorium, 30 hours
|
|
Coordinators: | Dorota Dąbrowska | |
Group instructors: | Dorota Dąbrowska | |
Students list: | (inaccessible to you) | |
Examination: |
Course -
graded credit
Conversatorium - graded credit |
|
(in Polish) E-Learning: | (in Polish) E-Learning (pełny kurs) z podziałem na grupy |
|
(in Polish) Opis nakładu pracy studenta w ECTS: | 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. |
|
Type of subject: | obligatory |
|
(in Polish) Grupa przedmiotów ogólnouczenianych: | (in Polish) nie dotyczy |
Classes in period "Winter semester 2024/25" (future)
Time span: | 2024-10-01 - 2025-01-31 |
Navigate to timetable
MO TU W TH FR |
Type of class: |
Conversatorium, 30 hours
|
|
Coordinators: | (unknown) | |
Group instructors: | (unknown) | |
Students list: | (inaccessible to you) | |
Examination: |
Course -
graded credit
Conversatorium - graded credit |
|
(in Polish) E-Learning: | (in Polish) E-Learning |
|
Type of subject: | obligatory |
|
(in Polish) Grupa przedmiotów ogólnouczenianych: | (in Polish) nie dotyczy |
Copyright by Cardinal Stefan Wyszynski University in Warsaw.