Бакалавриат
2020/2021
Методы теоретической информатики
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
4-й курс, 3 модуль
Формат изучения:
с онлайн-курсом
Преподаватели:
Вялый Михаил Николаевич,
Милованов Алексей Сергеевич,
Подольский Владимир Владимирович
Язык:
английский
Кредиты:
4
Контактные часы:
44
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
- ColloquiumThere is no exam. The course grade is given according to the cumulative assessment.
- Test
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
- Ryan O’Donnell. (2012). Analysis of Boolean Functions. Http://Www.Cs.Mcgill.ca/%7Edenis/Barbados2012.Pdf.