|
|
Main menu for Browse IS/STAG
Course info
KMA / AVS
:
Course description
Department/Unit / Abbreviation
|
KMA
/
AVS
|
Academic Year
|
2023/2024
|
Academic Year
|
2023/2024
|
Title
|
Algorithms and Complexity
|
Form of course completion
|
Exam
|
Form of course completion
|
Exam
|
Accredited / Credits
|
Yes,
5
Cred.
|
Type of completion
|
-
|
Type of completion
|
-
|
Time requirements
|
Lecture
3
[Hours/Week]
Tutorial
1
[Hours/Week]
|
Course credit prior to examination
|
Yes
|
Course credit prior to examination
|
Yes
|
Automatic acceptance of credit before examination
|
No
|
Included in study average
|
YES
|
Language of instruction
|
-
|
Occ/max
|
|
|
|
Automatic acceptance of credit before examination
|
No
|
Summer semester
|
1 / -
|
1 / -
|
0 / -
|
Included in study average
|
YES
|
Winter semester
|
0 / -
|
0 / -
|
0 / -
|
Repeated registration
|
NO
|
Repeated registration
|
NO
|
Timetable
|
Yes
|
Semester taught
|
Winter + Summer
|
Semester taught
|
Winter + Summer
|
Minimum (B + C) students
|
1
|
Optional course |
Yes
|
Optional course
|
Yes
|
Language of instruction
|
-
|
Internship duration
|
0
|
No. of hours of on-premise lessons |
|
Evaluation scale |
1|2|3|4 |
Periodicity |
každý rok
|
Evaluation scale for credit before examination |
S|N |
Periodicita upřesnění |
|
Fundamental theoretical course |
No
|
Fundamental course |
No
|
Fundamental theoretical course |
No
|
Evaluation scale |
1|2|3|4 |
Evaluation scale for credit before examination |
S|N |
Substituted course
|
None
|
Preclusive courses
|
N/A
|
Prerequisite courses
|
N/A
|
Informally recommended courses
|
KMA/TGD1
|
Courses depending on this Course
|
KMA/DM, KMA/DMI, KMA/TIS
|
Histogram of students' grades over the years:
Graphic PNG
,
XLS
|
Course objectives:
|
The aim is to provide a deeper insight into complexity classes and their relations based on the Turing machine computational model.
|
Requirements on student
|
Credit: project.
Exam: oral part.
|
Content
|
1. Languages. Reducibility. Computational models. Grammars.
2. Turing machines. Complexity measures.
3. Time-complexity classes. Class P.
4. Class NP and its structure.
5. Parametrized complexity.
6. Nonuniform complexity.
7. Complexity of optimisation problems. Approximability.
8. Boolean and polynomial hierarchy.
9. Space-complexity classes.
10. Probabilistic algorithms and complexity classes.
11. Interactive proof systems. PCP classes.
12. Parallel complexity.
13. Complexity of logical theories. Basics of Kolmogorov complexity.
14. Quantum computing.
|
Activities
|
|
Fields of study
|
|
Guarantors and lecturers
|
|
Literature
|
-
Basic:
Papadimitriou. Computational Complexity. 1995.
-
Basic:
Bovet, D.P.; Crescenzi, P. Introduction to the theory of complexity. Prentice Hall International Series in Computer Science, 2004. ISBN 978-0139153808.
-
Basic:
Sipser, Michael. Introduction to the theory of computation. 2nd ed. Boston : Thomson Course Technology, 2006. ISBN 0-534-95097-3.
-
Basic:
Kučera, Luděk. Kombinatorické algoritmy. 2. nezm. vyd. Praha : SNTL, 1989.
-
Extending:
Fiat, Woeginger (eds.). Online Algorithms. 1998.
-
Extending:
Williamson, D.P.; Shmoys, D.B. The Design of Approximation Algorithms. Cambridge University Press, 2011. ISBN 978-0521195270.
-
Recommended:
Hromkovič, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. 2nd ed. Berlin : Springer, 2003. ISBN 3-540-44134-4.
-
Recommended:
Sedgewick, Robert; Flajolet, Philippe. An introduction to the analysis of algorithms. Boston : Addison-Wesley, 1996. ISBN 0-201-40009-X.
-
Recommended:
Vazirani, V.V. Approximation Algorithms. Springer International Publishing AG, part of Springer Nature, 2013. ISBN 978-8181283856.
-
Recommended:
Rothe, J. Complexity Theory and Cryptology. Springer-Verlag Berlin Heidelberg, 2005. ISBN 978-3-642-06054-0.
-
On-line library catalogues
|
Time requirements
|
All forms of study
|
Activities
|
Time requirements for activity [h]
|
Contact hours
|
52
|
Preparation for comprehensive test (10-40)
|
35
|
Preparation for an examination (30-60)
|
56
|
Total
|
143
|
|
Prerequisites
|
Knowledge - students are expected to possess the following knowledge before the course commences to finish it successfully: |
popsat výpočetní model počítače s libovolným přístupem (RAM) |
formulovat základní polynomiálně řešitelné úlohy |
formulovat základní úlohy řešitelné nedeterministicky v polynomiálním čase |
Skills - students are expected to possess the following skills before the course commences to finish it successfully: |
aplikovat algoritmy pro základní polynomiálně řešitelné úlohy |
vyřešit jednoduchou úlohu lineárního programování |
Competences - students are expected to possess the following competences before the course commences to finish it successfully: |
N/A |
N/A |
N/A |
|
Learning outcomes
|
Knowledge - knowledge resulting from the course: |
definovat složitostní třídy optimalizačních úloh |
popsat pravděpodobnostní třídy výpočetní složitosti |
popsat výpočetní model Turingova stroje |
vysvětlit aproximační algoritmy pro standardní úlohy |
Skills - skills resulting from the course: |
odhadnout výpočetní složitost dané úlohy |
odhadnout aproximovatelnost dané optimalizační úlohy |
navrhnout jednoduchý pravděpodobnostní algoritmus pro danou úlohu |
Competences - competences resulting from the course: |
N/A |
N/A |
|
Assessment methods
|
Knowledge - knowledge achieved by taking this course are verified by the following means: |
Oral exam |
Test |
Individual presentation at a seminar |
Skills - skills achieved by taking this course are verified by the following means: |
Skills demonstration during practicum |
Competences - competence achieved by taking this course are verified by the following means: |
Oral exam |
|
Teaching methods
|
Knowledge - the following training methods are used to achieve the required knowledge: |
Lecture |
Interactive lecture |
Practicum |
Skills - the following training methods are used to achieve the required skills: |
Practicum |
Competences - the following training methods are used to achieve the required competences: |
Interactive lecture |
|
|
|
|