• A
• A
• A
• АБB
• АБB
• АБB
• А
• А
• А
• А
• А
Обычная версия сайта
Бакалавриат 2020/2021

# Методы теоретической информатики

Направление: 01.03.02. Прикладная математика и информатика
Когда читается: 4-й курс, 3 модуль
Формат изучения: с онлайн-курсом
Язык: английский
Кредиты: 4

### Course Syllabus

#### Abstract

The goal of the course "Theorist’s Toolkit" is to give learners understanding of basic techniques and methods for solving and analyzing problems in theoretical computer science. The target audience of this course is students of the specialization "Theoretical Computer Science". Among all the various methods of theoretical computer science, we cover the most actively used in modern research in this area.

#### Learning Objectives

• The main goal of this course is to give students understanding of the basic methods and techniques used in research of theoretical computer science.
• It is suggested that students will be able to formulate theoretical computer science problems.
• It is expected to develop students' ability to solve problems by using the methods of theoretical computer science.
• Students are expected to master the basic definitions and facts of mathematics and theoretical computer science covered in the course.
• It is expected that students will know how to use basic methods of theoretical computer science.
• It is planned to develop students' skills of transition from discussing practical problems to their mathematical formulations and further analysis of the formulated mathematical problems.

#### Course Contents

• Probabilistic methods.
Chernoff bound and applications. Generalization to dependent random variables.
• Boolean Fourier analysis.
Basic notions, results and applications.
• Polynomial method.
Representation of boolean functions by polynomials, applications to decision trees, boolean circuits and communication complexity.

#### Assessment Elements

• Homeworks
• Colloquium
There is no exam. The course grade is given according to the cumulative assessment.
• Test

#### Interim Assessment

• Interim assessment (3 module)
0.5 * Colloquium + 0.35 * Homeworks + 0.15 * Test

#### 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