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

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

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

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

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

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

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

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

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

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

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

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

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

Кредиты: 6

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

Полная версия программы учебной дисциплины

Аннотация

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

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

Целями освоения дисциплины «Сложность вычислений и логика в теоретической информатике» являются овладение студентами основными концепциями и результатами сложности вычислений и математической логики, применяемыми в теоретической информатике.

Планируемые результаты обучения

В результате освоения дисциплины студент должен знать: • основные понятия и теоремы сложности вычислений; • основные понятия и теоремы математической логики; • методы доказательства разрешимости логических теорий; • основные понятия дискретной математики, линейной алгебры и математического анализа. • способы построения графов-экспандеров и их применения в сложности вычислений.
В результате освоения дисциплины студент должен уметь: • пользоваться основными методами построения экспандеров; • пользоваться методами элиминации кванторов и игр Эренфойхта; • пользоваться понятиями чуствительности и блочной чуствительности; владеть: • навыками доказательства нижних оценок в сложности вычислений; • навыками доказательства верхних оценок в сложности вычислений; • методом дерандомизации вероятностных алгоритмов с попощью графов-экспандеров.

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

Тема 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.2 * Домашнее задание + 0.4 * Экзамен

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

Авторы

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

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