Computability and computational complexity

Lectures:
Introduction: Algorithm intuitively.
History: Foundational crisis in 20th century mathematics. Solving the crisis. Formal systems. Hilbert’s program. Godel’s theorems.
Introduction to computability: What is algorithm and computation? Models of comp. Church-Turing thesis. Turing machine and versions. Nondeterminism.
Universal TM. RAM model and general purpose computers. Recursion theorem, recursive definitions and execution.
Incomputability. Sets vs. languages. Decision problems. Incomputable problems exist. Methods of proving incomputability (diagonalization, reductions, Rice’s theorem). Examples of incomputable problems and consequences in various fields. (Basics of relative computability and hierarchies.)
Automata, grammars, languages: Finite automata, regular grammars, expressions and languages. Pushdown automata, context-free grammars and languages. Linear bounded automata, context-sensitive grammars and languages. Examples and application.
Introduction to computational complexity: Time, space, and other complexities. Easy and hard problems. Classes P, NP, EXP and other complexity classes. NP-completeness/hardness and methods of proving it. Examples and applications.
Coping with hard problems: Basics of randomized, approximation, and parallel computing. Basics of interactive proving. Examples and application.
Recent approaches: Basics of quantum computing.

Home works and seminars:

B. Robič: The Foundations of Computability Theory, Springer, 2014 (to appear)
S.Arora, B.Barak Computational Complexity: A modern approach, Cambridge Univ Press (2009)
Dodatna literatura:
M. Sipser: Introduction to the Theory of Computation, Course Technology (2006)
B. Robič: Aproksimacijski algoritmi, Založba FE in FRI, 2. izd. (2009)

Major part of the course is devoted to computability and computational complexity theory emphasizing on application on various disciplines of computer science. In part the course covers the historical development of the field as well as its recent achievements, again focusing on practical problem solving.

Knowledge and understanding:
Student will posess knowledge and skills in computability and computational complexity theory.
Application:
Computability and computational complexity theory is fundamental to efficient problem solving, algorithm design and analysis, and design of complex software.
Reflection:
Learning deep and intricate facts of the computability and computation complexity theory and their use in various disciplines in computer science.
Transferable skills:
We will treat the topics with as much of mathematical rigor as necessary for clear and develop a birds-eye look at the theory by explaining the motivation and intuition behind the various notions and facts of this theory .

Lectures and exercise groups, homework assignemnts.
Frequent homework assignemts shall not be time consuming. Some of the homework assignments will be more demanding – projects – which may be distibuted to students divided in groups.

Continuing (homework, midterm exams, project work)
Final (written and oral exam)

ROBIČ, Borut. The foundations of computability theory. Heidelberg [etc.]: Springer, cop. 2015. XX, 331 str., ilustr. ISBN 978-3-662-44807-6. ISBN 978-3-662-44808-3, doi: 10.1007/978-3-662-44808-3. [COBISS-SI-ID 1536557251]
BEZENŠEK, Mitja, ROBIČ, Borut. A survey of parallel and distributed algorithms for the Steiner tree problem. International journal of parallel programming, ISSN 0885-7458. [Print ed.], 2014, vol. 42, no. 2, str. 287-319. [COBISS-SI-ID 9891924]
MIHELIČ, Jurij, MAHJOUB, Amine, RAPINE, Christophe, ROBIČ, Borut. Two-stage flexible-choice problems under uncertainty. European journal of operational research, ISSN 0377-2217. [Print ed.], Mar. 2010, vol. 201, no. 2, str. 399-403, ilustr. [COBISS-SI-ID 7087444]
MIHELIČ, Jurij, ROBIČ, Borut. Flexible-attribute problems. Computational optimization and applications, ISSN 0926-6003. [Print ed.], 2010, vol. 47, no. 3, str. 553-566, ilustr. [COBISS-SI-ID 7087700]
TROBEC, Roman, ŠTERK, Marjan, ROBIČ, Borut. Computational complexity and parallelization of the meshless local Petrov-Galerkin methods. Computers & Structures, ISSN 0045-7949. [Print ed.], 2009, vol. 87, no. 1/2, str. 81-90. [COBISS-SI-ID 21895463]