Комбинаторные конструкции в теоретической информатике

2026/2027

Учебный год

RUS

Обучение ведется на русском языке

6

Кредиты

Кто читает:

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

Статус:

Курс по выбору

Когда читается:

1-й курс, 3, 4 модуль

Программа дисциплины

Аннотация

Графы-экспандеры являются одним из самых важных инструментов в теоретической информатики. Они используются при построении множества современных эффективных алгоритмов (например, алгоритма Рейнгольда поиска пути в графе), а также в доказательстве теорем (например, PCP-теорема). То же самое относится к кодам с исправлением ошибок - они используются при передаче информации по ненадежному каналу и, например, в построении односторонних функций. Овладение этими двумя техниками является необходимым умением современных специалистов в теоретической информатике.