| Course title | Computability and Complexity |
|---|---|
| Course code | KMI/VYSLO |
| Organizational form of instruction | Lecture + Exercise |
| Level of course | Bachelor |
| Year of study | not specified |
| Semester | Winter |
| Number of ECTS credits | 4 |
| Language of instruction | Czech |
| Status of course | Compulsory |
| Form of instruction | Face-to-face |
| Work placements | This is not an internship |
| Recommended optional programme components | None |
| Lecturer(s) |
|---|
|
| Course content |
|
Introduction to computability: Turing machine (TM) definition, concept of computation, language recognized by TM (configuration, etc.), language decided by TM, TM computable function, Church-Turing thesis. Variants of TM: TM with two-way infinite tape, multiple-tape TM, equivalences with basic TM. Universal TM: definition, description of computation. Languages and problems: Partial recursive and recursive languages, decision problems, reducibility of decision problems to languages, existence of languages which are not partially recursive. Non-recursive languages, non-computable problems: Halting problem, reducibility, equivalence of context-free grammars, Rice's theorem and its applications. Complexity: complexity of algorithms and problems. Basic complexity classes: class PTIME, nondeterministic TM and class NPTIME. NP-complete problems, selected NP-complete problems, proving NP-completeness. Space complexity, classes PSPACE and NPSPACE, Savitch's theorem, PSPACE-complete problems. Introduction to the area of approximation algorithms and probabilistic algorithms.
|
| Learning activities and teaching methods |
| Lecture, Demonstration |
| Learning outcomes |
|
The students become familiar with basic concepts of computability and complexity.
1. Knowledge Identify unsolvable problems and solvable problems and their computational complexity. |
| Prerequisites |
|
unspecified
|
| Assessment methods and criteria |
|
Oral exam, Written exam
Active participation in class. Completion of assigned homeworks. Passing the oral (or written) exam. |
| 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 | 3 | Recommended year of study:3, Recommended semester: Winter |
| Faculty: Faculty of Science | Study plan (Version): Computer Science for Education (2024) | Category: Informatics courses | 3 | Recommended year of study:3, Recommended semester: Winter |
| Faculty: Faculty of Science | Study plan (Version): Bioinformatics (2021) | Category: Informatics courses | 3 | Recommended year of study:3, Recommended semester: Winter |
| Faculty: Faculty of Science | Study plan (Version): Computer Science - Specialization in Programming and Software Development (2021) | Category: Informatics courses | 3 | Recommended year of study:3, Recommended semester: Winter |
| Faculty: Faculty of Science | Study plan (Version): Computer Science - Specialization in General Computer Science (2021) | Category: Informatics courses | 3 | Recommended year of study:3, Recommended semester: Winter |