Title:

Computability and Complexity

Code:VSL
Ac.Year:ukončen 2004/2005
Sem:Winter
Language of Instruction:Czech, English
Public info:http://www.fit.vutbr.cz/study/courses/VSL/public/
Credits:6
Completion:credit+exam (written)
Type of
instruction:
Hour/semLecturesSeminar
Exercises
Laboratory
Exercises
Computer
Exercises
Other
Hours:39120014
 ExamsTestsExercisesLaboratoriesOther
Points:7520005
Guarantor:Janoušek Vladimír, doc. Ing., Ph.D. (DITS)
Lecturer:Češka Milan, prof. RNDr., CSc. (DITS)
Janoušek Vladimír, doc. Ing., Ph.D. (DITS)
Instructor:Křivka Zbyněk, Ing., Ph.D. (DIFS)
Faculty:Faculty of Information Technology BUT
Department:Department of Intelligent Systems FIT BUT
Prerequisites: 
Theoretical Computer Science 1 (TI1), DITS
Follow-ups:
Parallel and Distributed Algorithms (PDA), DITS
 
Learning objectives:
  To learn mathematical models of computation and theory of computability and complexity.
Description:
  Mathematical models of computation and computing systems, Turing machines. Multi-tape and non-deterministic Turing machines. Turing machines as language acceptors. Decidability. Universal Turing machine. Halting problem, Post correspondence problem. Computability, primitive recursive functions, partial recursive functions. Turing-Church thesis. Algorithmic complexity, problem complexity. Asymptotic approximation of complexity. Complexity in the context of various model of computation, polynomilally bound models. Deterministic decidability in polynomial time. NP-languages, NP-problems. NP-completness.
Subject specific learning outcomes and competencies:
  Understanding basics of mathematical models of computation and theory of computability and complexity. Understanding theoretical and practical limits of arbitrary computational systems.
Generic learning outcomes and competencies:
  Understanding theoretical and practical limits of arbitrary computational systems.
Syllabus of lectures:
 
  • Mathematical models of computation and computing systems,
  • Turing machines.
  • Multi-tape and non-deterministic Turing machines.
  • Turing machines as language acceptors.
  • Decidability.
  • Universal Turing machine. Halting problem, Post correspondence problem.
  • Computability, primitive recursive functions, partial recursive functions.
  • Turing-Church thesis.
  • Algorithmic complexity, problem complexity.
  • Asymptotic aproximation of complexity.
  • Complexity in the context of various model of computation, polynomialy bound models.
  • Deterministic decidability in polynomial time.
  • NP-languages, NP-problems. NP-completness.
Syllabus - others, projects and individual work of students:
 
  • 5 homeworks during semester
Fundamental literature:
 
  • Martin, J.C.: Introduction to Languages and the Theory of Computation, McGraw-Hill, Inc., 1991.
  • Saloma, A.: Computation and Automata, Cambridge University Press, 1985.
Study literature:
 
  • Brookshear J.G.: Theory of Computation, The Benjamin/Cummings Publishing Company, Inc, Redwood City, California 1989.
Links:
 2004-09-22: Autumn/winter-term exam period will be expired on Fri 2005-02-04.
Miloš Eysselt, Assistant Manager of Study Affairs.
Progress assessment:
  Homeworks - 5 points.
Mid-term exam - 20 points.
Exam prerequisites:
  At least 50 precent of mid-term exam points (10 pionts).
 

Your IPv4 address: 54.198.92.22
Switch to https

DNSSEC [dnssec]