Faculty of Information Technology, BUT

Course details

Complexity

SLO Acad. year 2007/2008 Summer semester 5 credits

Course is not open in this year
Close
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)

Time span

26 hrs lectures, 26 hrs projects

Assessment points

70 exam, 30 projects

Department

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.

Back to top