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

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

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

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

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

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

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

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

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

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

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

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

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

Кредиты: 6

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

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

Аннотация

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

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

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

Содержание учебной дисциплины

Тема 1. Разрешимость логических теорий.
Тема 2. Графы-экспандеры и их применения.
Тема 3. Сложность разрешающих деревьев
Тема 4. Нижние оценки схемной сложности

Элементы контроля

Домашнее задание
Коллоквиум
Экзамен
Экзамен проводится в письменной форме. Экзамен проходит с прокторингом. Студенты загружают задание с сайта по ссылке, решают на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com. Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена. Экзамен длится 90 минут. Во время экзамена разрешено смотреть на условия задач и на конспекты лекций: https://www.dropbox.com/s/1fl4vg99nblb9yo/vereshchagin-revised.pdf?dl=0https://www.dropbox.com/s/4eakm5abultga7x/DecisionTrees.pdf?dl=0, https://www.dropbox.com/s/2uw24ocj405b3yu/main.pdf?dl=0, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать конспекты лекций и условия задач.

Промежуточная аттестация

2021/2022 учебный год 4 модуль
0.4 * Коллоквиум + 0.4 * Экзамен + 0.2 * Домашнее задание

Список литературы

Авторы

Верещагин Николай Константинович

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