Course: Complexity and Computability

» List of faculties » FP » NTI
Course title Complexity and Computability
Course code NTI/SVA
Organizational form of instruction Lecture + Lesson
Level of course Master
Year of study not specified
Semester Winter and summer
Number of ECTS credits 2
Language of instruction Czech
Status of course Compulsory
Form of instruction Face-to-face
Work placements Course does not contain work placement
Recommended optional programme components None
Lecturer(s)
  • Kosková Třísková Lenka, Ing. Ph.D.
Course content
Lecture: 1. Mathematical models of computation, Turing machine. 2. Decidability, halting problem, Post correspondence problem. 3. Computability, recursive functions, Turing and Church thesis. 4. Algorithmical complexity. 5. Asymptotical complexity. 6. Polynomial decidability. 7. NP-languages, NP-problems, NP-complexity.

Learning activities and teaching methods
Monological explanation (lecture, presentation,briefing)
  • Class attendance - 14 hours per semester
Learning outcomes
Complexity of algorithms, polynomial, NP, exponential, NP-complete problems. Primality. Cryptography. Computability: Turing machines, primitive recursive functions, Kleene Normal Form Theorem, unsolvable problems, recursive sets, recursively enumerable sets.
The students gain overview of main terms related to theoretical decidability and complexity of algorithms.
Prerequisites
Unspecified

Assessment methods and criteria
Combined examination

Requirements for getting a credit are activity at the practicals /seminars and successful passing the tests.
Recommended literature
  • Hopcroft, J. E., Ullman, J. D. Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979.
  • Jiří Vaníček. Teoretické základy informatiky. Praha, 2007. ISBN 9788090396241.


Study plans that include the course
Faculty Study plan (Version) Category of Branch/Specialization Recommended year of study Recommended semester
Faculty: Faculty of Science, Humanities and Education Study plan (Version): Teacher Training for Lower and Upper Secondary Schools - Informatics (20) Category: Pedagogy, teacher training and social care - Recommended year of study:-, Recommended semester: Winter
Faculty: Faculty of Science, Humanities and Education Study plan (Version): Teacher Training for Lower and Upper Secondary Schools - Informatics (20) Category: Pedagogy, teacher training and social care - Recommended year of study:-, Recommended semester: Winter