2026/2027
Комбинаторные конструкции в теоретической информатике
Статус:
Маго-лего
Где читается:
Факультет компьютерных наук
Когда читается:
3, 4 модуль
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
6
Контактные часы:
80
Программа дисциплины
Аннотация
Графы-экспандеры являются одним из самых важных инструментов в теоретической информатики. Они используются при построении множества современных эффективных алгоритмов (например, алгоритма Рейнгольда поиска пути в графе), а также в доказательстве теорем (например, PCP-теорема). То же самое относится к кодам с исправлением ошибок - они используются при передаче информации по ненадежному каналу и, например, в построении односторонних функций. Овладение этими двумя техниками является необходимым умением современных специалистов в теоретической информатике.