Main page | Study Branches/Specializations | Groups of Courses | All Courses | Roles                Instructions

A course is the basic teaching unit, it's design as a medium for a student to acquire comprehensive knowledge and skills indispensable in the given field. A course guarantor is responsible for the factual content of the course.
For each course, there is a department responsible for the course organisation. A person responsible for timetabling for a given department sets a time schedule of teaching and for each class, s/he assigns an instructor and/or an examiner.
Expected time consumption of the course is expressed by a course attribute extent of teaching. For example, extent = 2 +2 indicates two teaching hours of lectures and two teaching hours of seminar (lab) per week.
At the end of each semester, the course instructor has to evaluate the extent to which a student has acquired the expected knowledge and skills. The type of this evaluation is indicated by the attribute completion. So, a course can be completed by just an assessment ('pouze zápočet'), by a graded assessment ('klasifikovaný zápočet'), or by just an examination ('pouze zkouška') or by an assessment and examination ('zápočet a zkouška') .
The difficulty of a given course is evaluated by the amount of ECTS credits.
The course is in session (cf. teaching is going on) during a semester. Each course is offered either in the winter ('zimní') or summer ('letní') semester of an academic year. Exceptionally, a course might be offered in both semesters.
The subject matter of a course is described in various texts.

MI-PAA Problems and Algorithms Extent of teaching: 2P+1R+1C
Instructor: Completion: Z,ZK
Department: 18103 Credits: 5 Semester: Z

Annotation:
Students are able to evaluate discrete problems by complexity and by the purpose of optimisation (on-line tasks, multicriterial optimisation). They understand principles and properties of heuristics and exact algorithms and, therefore, are able to select, apply, and experimentally evaluate a suitable heuristics for a practical problem.

Lecture syllabus:
1. Discrete optimization, examples of practical tasks. Combinatorial problems. Algorithm complexity, problem complexity.
2. Models of computation. The classes P and NP. Polynomial hierarchy.
3. The notion of completeness. Complexity comparison techniques. The classes NP-complete, NP-hard and NPI.
4. The classes PO and NPO and their structure. Deterministic approximation algorithms. Classification of approximative problems. Pseudopolynomial algorithms. Randomization and randomized algorithms.
5. Communication and circuit complexity
6. Practical deployment of heuristic and exact algorithms. Experimental evaluation.
7. Local methods: state space and search space, exact methods, heuristics.
8. Simulated annealing.
9. Simulated evolution: taxonomy, genetic algorithms.
10. Advanced genetic algorithms: competent GA, fast messy GA, Stochastic optimization: models and applications. Bayesian optimization.
11. Tabu search.
12. Global methods, taxonomy of decomposition-based methods. Exact and heuristic global methods, the Davis-Putnam procedure seen as a global method.
13. Reserved

Seminar syllabus:
1. Seminar: terminology, examples of complexity.
2. Seminar: examples of state space.
3. Homework consultation when required, self-study: dynamic programming revision.
4. Solved problems session: the classes P and NP, complexity proofs, problems beyond NP.
5. Solved problems session: completeness, reductions.
6. Homework consultation when required.
7. Homework consultation when required.
8. Homework consultation when required.
9. Midterm test.
10. Homework consultation when required.
11. Solved problems session: advanced heuristics, applications.
12. Homework consultation when required.
13. Homework consultation when required.
14. Backup test term, evaluation.

Literature:
1. Garey, M. R., Johnson, D. S. ''Computers and Intractability: A Guide to the Theory of NP-Completeness''. W. H. Freeman, 1979. ISBN 0716710455.
2. Ausiello, G., Crescenzi, P., Kann, V., Gambosi, G., Spaccamela, A. M. ''Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties''. Springer, 2003. ISBN 3540654313.

Requirements:
The notion of complexity, asymptotic complexity bounds. Basic graph theory. Programming in any imperative language using queues, stacks, and lists.

Předmět je nahrazen ekvivalentním NI-KOP // Informace o předmětu a výukové materiály naleznete na https://moodle-vyuka.cvut.cz/course/view.php?id=2217

The course is also part of the following Study plans:
Study Plan Study Branch/Specialization Role Recommended semester
MI-ZI.2016 Knowledge Engineering PP 1
MI-ZI.2018 Knowledge Engineering PP 1
MI-SP-TI.2016 System Programming PP 1
MI-SP-SP.2016 System Programming PP 1
MI-SPOL.2016 Unspecified Branch/Specialisation of Study PP 1
MI-WSI-WI.2016 Web and Software Engineering PP 1
MI-WSI-SI.2016 Web and Software Engineering PP 1
MI-WSI-ISM.2016 Web and Software Engineering PP 1
MI-NPVS.2016 Design and Programming of Embedded Systems PP 1
MI-PSS.2016 Computer Systems and Networks PP 1
MI-PB.2016 Computer Security PP 1


Page updated 28. 3. 2024, semester: Z/2023-4, L/2019-20, L/2022-3, Z/2019-20, Z/2022-3, L/2020-1, L/2023-4, Z/2020-1, Z,L/2021-2, Send comments to the content presented here to Administrator of study plans Design and implementation: J. Novák, I. Halaška