Faculty of Information Technology, BUT

Course details

Complexity

SLO Acad. year 2009/2010 Summer semester 5 credits

This course covers the following themes: Matematical models of computation ( skeleton language, RAM, RASP models and their connection with Turing machines), time complexity, complexity classes, P and NP, NP-completness, important NP-complete problems, satisfability problem and its variants, other NP-problems, NP and co-NP languages, space complexity, PS and NPS languages, PS-complete languages, language classes based on randomization, applications of computational complexity theory - cryptography and one-way functions.

Guarantor

Language of instruction

Czech, English

Completion

Examination (written+oral)

Time span

26 hrs lectures, 26 hrs projects

Assessment points

70 exam, 30 projects

Department

Lecturer

Instructor

Subject specific learning outcomes and competences

Understanding theoretical and practical limits of arbitrary computational systems.

Learning objectives

To learn mathematical models of computation and complexity theory.

Study literature

  • Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
  • Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1

Fundamental literature

  • Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
  • Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1

Syllabus of lectures

  • Introduction. Complexity, time and space complexity.
  • Matematical models of computation. Skeleton language.
  • RAM, RASP machines and their relation with Turing machines.
  • Nondeterminism. Oracle machines. Reducibility.
  • P and NP. Examples: Kruskal, Traveling Salesman.
  • NP-completness. NP-complete problems.
  • Satisfability problem and its variants.
  • Other NP-problems.
  • NP and co-NP languages.
  • Space complexity, PS and NPS languages.
  • PS-complete languages.
  • Language classes based on randomization - classes RP and ZPP.
  • Applications: Cryptography and one-way functions.

Syllabus - others, projects and individual work of students

  • Project on Mathematical models of computation.
  • Project on Complexity.

Progress assessment

  • Projects: max. 32 points
  • Final exam: max. 68 points

Exam prerequisites

The minimal total score of 15 points gained out of the projects.
Back to top