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

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

Лучший по критерию «Новизна полученных знаний»

Статус: Курс по выбору (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

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

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

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

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

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

Преподаватели: Верещагин Николай Константинович, Милованов Алексей Сергеевич

Язык: русский

Кредиты: 6

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

Дополнительные материалы в LMS Задать вопрос

Аннотация

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

Цель освоения дисциплины

Целями освоения дисциплины являются овладение студентами основными концепциями и результатами в области построения графов экспандеров и кодов с исправлением ошибок, применяемыми в теоретической информатике. Овладение основными кодами, применяемыми на практике и в теории.