• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 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 * Экзамен
Список литературы

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

Рекомендуемая основная литература

  • Верещагин, Н. К. Лекции по математической логике и теории алгоритмов : учебное пособие / Н. К. Верещагин, А. Шень. — 3-е изд., доп. — Москва : МЦНМО, [б. г.]. — Часть 2 : Языки и исчисления — 2008. — 288 с. — ISBN 978-5-94057-322-7. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9307 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
  • Верещагин, Н. К. Языки и исчисления : учебное пособие / Н. К. Верещагин, А. Х. Шень. — 2-е изд. — Москва : ИНТУИТ, 2016. — 278 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100547 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.

Рекомендуемая дополнительная литература

  • MOSER, R. A., & TARDOS, G. (2010). A Constructive Proof of the General Lovász Local Lemma. Journal of the ACM, 57(2), 11–11:15. https://doi.org/10.1145/1667053.1667060

Авторы

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