City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Introduction to theoretical computer science
Saint Petersburg / autumn 2020, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Это содержательный курс, который даст слушателям представление не только о различных областях теоретической информатики, но также и об основных методах и идеях. Мы поговорим про такие области: алгоритмическая неразрешимость, сложность вычислений, понятие доказательств в информатике (классические, интерактивные, вероятностно проверяемые, доказательства с нулевым разглашением), линейное программирование и принцип двойственности, вычисления с малой памятью, параллельные вычисления, вероятностные алгоритмы, теория информации (классическая и алгоритмическая), коммуникационная сложность, тестирование свойств и пр.

Курс не требует никаких предварительных знаний, выходящих за программу первых двух курсов ВУЗов, но существенно проще будет тем, кто уже прослушал курсы по дискретной математике, алгоритмам и структурам данных и теории вероятностей.

Похожий курс читался в 2013 и 2016 годах.