| Course title | Selected Topics in Algorithms |
|---|---|
| Course code | KMI/VYTAL |
| Organizational form of instruction | Seminar |
| Level of course | Bachelor |
| Year of study | 2 |
| Semester | Summer |
| Number of ECTS credits | 3 |
| Language of instruction | Czech |
| Status of course | Compulsory-optional |
| Form of instruction | Face-to-face |
| Work placements | This is not an internship |
| Recommended optional programme components | None |
| Lecturer(s) |
|---|
|
| Course content |
|
The satisfiability problem for propositional logic formulas (SAT), its hardness, applications, and theoretical significance. Resolution, the resolution theorem, algorithms derived from resolution, lower bounds on the length of resolution refutations. Variants solvable in polynomial time. The family of algorithms based on DPLL, the main ideas behind CDCL solvers. The Paturi-Pudlák-Zane algorithm. Combinatorial considerations concerning satisfiability.
|
| Learning activities and teaching methods |
| Work with Text (with Book, Textbook), Demonstration, Laboratory Work |
| Learning outcomes |
|
The aim is to acquaint students with an important algorithmic problem, the algorithms for solving it, their implementation aspects, and the relevant theoretical topics. The satisfiability of propositional logic formulas has been chosen as the model problem.
|
| Prerequisites |
|
unspecified
|
| Assessment methods and criteria |
|
Student performance, Analysis of Activities ( Technical works)
|
| Recommended literature |
|
| Study plans that include the course |
| Faculty | Study plan (Version) | Category of Branch/Specialization | Recommended semester | |
|---|---|---|---|---|
| Faculty: Faculty of Science | Study plan (Version): Computer Science (2020) | Category: Informatics courses | 2 | Recommended year of study:2, Recommended semester: Summer |
| Faculty: Faculty of Science | Study plan (Version): Computer Science - Specialization in Programming and Software Development (2021) | Category: Informatics courses | 2 | Recommended year of study:2, Recommended semester: Summer |
| Faculty: Faculty of Science | Study plan (Version): Computer Science - Specialization in General Computer Science (2021) | Category: Informatics courses | 2 | Recommended year of study:2, Recommended semester: Summer |