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

2022/2023

Учебный год

RUS

Обучение ведется на русском языке

6

Кредиты

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

Кто читает:

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

Статус:

Курс по выбору

Когда читается:

3-й курс, 3, 4 модуль

Преподаватели

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

Милованов Алексей Сергеевич

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

Аннотация

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

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

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

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

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

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

• Домашнее задание
  домашнее задание
• Коллоквиум
• экзамен
  экзамен

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

• 2022/2023 учебный год 4 модуль
  0.1 * Домашнее задание + 0.1 * Домашнее задание + 0.4 * Коллоквиум + 0.4 * экзамен

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

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

• Верещагин, Н. К. Языки и исчисления : учебное пособие / Н. К. Верещагин, А. Х. Шень. — 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

Авторы

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