Title:

Complexity

Code:SLO
Ac.Year:2010/2011
Term:Summer
Curriculums:
ProgrammeFieldYearDuty
IT-MSC-2MBI-Elective
IT-MSC-2MBS-Elective
IT-MSC-2MGM-Elective
IT-MSC-2MGM.-Elective
IT-MSC-2MIN-Compulsory-Elective - group B
IT-MSC-2MIN.2ndElective
IT-MSC-2MIS1stElective
IT-MSC-2MIS.1stElective
IT-MSC-2MMI-Elective
IT-MSC-2MMM-Compulsory-Elective - group L
IT-MSC-2MPS-Elective
IT-MSC-2MPV-Elective
IT-MSC-2MSK-Elective
IT-MSC-2EITE2ndElective
Language of Instruction:Czech, English
Private info:http://www.fit.vutbr.cz/study/courses/SLO/private/
Credits:5
Completion:examination (written&verbal)
Type of
instruction:
Hour/semLecturesSem. ExercisesLab. exercisesComp. exercisesOther
Hours:2600026
 ExaminationTestsExercisesLaboratoriesOther
Points:6800032
Guarantor:Vojnar Tomáš, prof. Ing., Ph.D., DITS
Lecturer:Rogalewicz Adam, doc. Mgr., Ph.D., DITS
Instructor:Rogalewicz Adam, doc. Mgr., Ph.D., DITS
Faculty:Faculty of Information Technology BUT
Department:Department of Intelligent Systems FIT BUT
Prerequisites: 
Theoretical Computer Science (TIN), DITS
Follow-ups:
Cryptography (KRY), DITS
Formal Analysis and Verification (FAV), DITS
Parallel and Distributed Algorithms (PRL), DITS
Substitute for:
Computability and Complexity (VSL), DITS
 
Learning objectives:
  To learn mathematical models of computation and complexity theory.
Description:
  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.
Learning outcomes and competences:
  Understanding theoretical and practical limits of arbitrary computational systems.
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.
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
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
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.