Аспирантура
2020/2021
Теоретическая инфоpматика
Статус:
Курс по выбору
Направление:
09.06.01. Информатика и вычислительная техника
Где читается:
Факультет компьютерных наук
Когда читается:
2-й курс, 1 семестр
Формат изучения:
без онлайн-курса
Преподаватели:
Баувенс Бруно Фредерик Л.
Язык:
английский
Кредиты:
5
Контактные часы:
38
Course Syllabus
Abstract
The course teaches basic concepts from computability theory and comutational complexity, as well as a few advanced topics of interest. The course is intended for students with a diverse background (not necessarily in computer science), who already have some mathematical maturity after studying.
Learning Objectives
- students are familiar with basic concepts in the theory of computation: finite state machines, regular expressions, Turing machines, computable functions, Godel-incompleteness, polynomial time and space complexity, NP-hardness, probabilistic computation, hardness of approximation
- to train the ability of mathematical problem solving
- to improve English writing and presentation skills
Expected Learning Outcomes
- The ability to carry out research in the field of professional activity using current research methods and information and communication technologies
- The ability to carry out theoretical analysis and design of programming languages and systems, to use methods for analysing program semantics
- The ability to develop and use methods for improving the efficiency and reliability of data and knowledge processing and transmission in computing machinery, systems, and networks
- The ability to do research in transformation of information into data and knowledge, models of data and knowledge representation, methods for knowledge processing, machine learning and knowledge discovery methods, principles of building and operating software for automation of these processes
Course Contents
- Automata and regular languagesDiscrete finite automata: deterministic, non-deterministic, equivalence and pumping lemma. Regular expressions and equivalence with finite automata.
- Computability theoryTuring machines: expressive power, equivalence with register machines, tag-systems. Halting problem, undecidability of tilings and a few other problems.
- Godel incompletenessProof systems: decidability of arithmetic with addition, undecidability of number theory, and Godel incompleteness.
- Computational complexityClasses P and NP, dynamic programming, the Levin-Cook theorem, NP-completeness of Hamiltonian path, vertex cover, etc. Classes L, PSPACE, NPSPACE, EXPSPACE, Savitch theorem, completeness of: formula game, generalized geography, testing equivalence of regular expressions. Oracle computation and oracles A and B for which P^A = NP^A and P^B != NP^B.
Assessment Elements
- Intermediate exam
- Final assessmentStudents with a decent background in mathematics and theoretical computer science have the option to do a project, instead of the 2 exams. They should read 1 or more theoretical research papers, rewrite in a self-contained form intended for a general audience in computer science, and give a lecture.
- Intermediate exam
- Final assessmentStudents with a decent background in mathematics and theoretical computer science have the option to do a project, instead of the 2 exams. They should read 1 or more theoretical research papers, rewrite in a self-contained form intended for a general audience in computer science, and give a lecture.
Bibliography
Recommended Core Bibliography
- Arora, S., & Barak, B. (2009). Computational Complexity : A Modern Approach. Cambridge: Cambridge eText. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=304712
Recommended Additional Bibliography
- Introduction to the theory of computation, Sipser, M., 2013