Бакалавриат 2023/2024

Теория сложности вычислений

Статус: Курс по выбору (Программная инженерия)

Направление: 09.03.04. Программная инженерия

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет компьютерных наук

Когда читается: 4-й курс, 1-3 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Преподаватели: Баувенс Бруно Фредерик Л., Лукьяненко Никита Сергеевич

Язык: английский

Кредиты: 10

Контактные часы: 60

Course Syllabus

Abstract

This course teaches a mathematical theory that helps to invent better algorithms. With “better” we mean that the algorithms use fewer resources such as time or memory. We also consider parallel computation, distributed systems and learning problems. In these settings we might also optimize other types of resources. For example, in distributed systems we might want to minimize the amount of communication. We focuss on worst case guarantees. A large part of our time is devoted to the study of what is not possible. In other words, we study fundamental barriers for the existence of programs that use fewer resources than a given bound.