Федеральное государственное бюджетное образовательное
учреждение высшего образования 
Московский государственный университет имени М.В. Ломоносова
Факультет вычислительной математики и кибернетики

УТВЕРЖДАЮ
декан факультета вычислительной математики и кибернетики
______________/И.А. Соколов /
«___» ________________20___г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Наименование дисциплины:
Введение в теорию сложности вычислений
Уровень высшего образования:
бакалавриат
Направление подготовки / специальность:
01.03.02 «Прикладная математика и информатика» (3++)
Направленность (профиль):
Математические методы обработки информации и принятия решений
Форма обучения:
очная

Москва 2023

Рабочая программа дисциплины (модуля) разработана в соответствии с самостоятельно установленным МГУ образовательным стандартом (ОС МГУ) для реализуемых основных профессиональных образовательных программ высшего образования по направлению подготовки 01.03.02, 01.04.02 "Прикладная математика и информатика" программы бакалавриата  Утвержден приказом МГУ от 30 августа 2019 года № 1041 (в редакции приказов МГУ от 11 сентября 2019 года № 1109, от 10 июня 2021 года № 609, от 7 октября 2021 года № 1048, от 21 декабря 2021 года № 1404, от 2 ноября 2022 года № 1299)

1. Дисциплина относится к базовой части ОПОП ВО.

2. Входные требования для освоения дисциплины (модуля): учащиеся должны владеть знаниями по алгебре, теории вероятности и дискретной математике в объеме, соответствующем программе третьего года обучения основных образовательных программ бакалавриата по укрупненным группам направлений и специальностей 01.00.00 «Математика и механика», 02.00.00 «Компьютерные и информационные науки».

3. Результаты обучения по дисциплине (модулю), соотнесенные с требуемыми компетенциями выпускников.

Компетенции выпускников, частично формируемые при реализации дисциплины (модуля):

●	ОПК-1.Б Способность применять и адаптировать существующие математические и компьютерные методы для разработки и реализации алгоритмов решения актуальных задач в области фундаментальной и прикладной математики
●	ОПК-2.Б Способность применять и модифицировать математические модели, а также интерпретировать полученные математические результаты при решения задач в области профессиональной деятельности 
●	ПК-2.Б Способность понимать и применять в научно-исследовательской деятельности современный математический аппарат

Планируемые результаты обучения по дисциплине (модулю):

Знать:
1.	основные подходы к формализации понятия “сложность”;
2.	основные подходы к постановке вычислительных задач в терминах задач распознавания языков и задач поиска;
3.	основные модели вычислений и принципиальные различия между ними;
4.	основные классы языков, определяемых различными моделями вычислений;
5.	соотношения между различными классами языков;
6.	методы теории сложности для получения соотношений между классами языков;
7.	открытые проблемы теории сложности; 
8.	понятия, определения и факты теории сложности вычислений;
Уметь:
1.	применять на практике общую теорию и методы теории сложности;
2.	сопоставлять математическим задачам их вычислительные аналоги;
3.	выбирать релевантную модель вычислений для анализа сложности вычислительных задач;
4.	классифицировать языки с помощью техники сведений;
5.	исследовать принадлежность языка известным классам;
6.	представлять математические знания в устной форме;
Владеть:
1.	навыками формализации вычислительных задач;
2.	навыками использования аппарата дискретной математики, алгебры и теории вероятности для построения сведений между классами языков;

4. Формат обучения: занятия проводятся с использованием меловой или маркерной доски, интерактивные материалы демонстрируются с помощью ноутбука и проектора.

5. Объем дисциплины (модуля) составляет 2 з.е., в том числе 36 академических часа, отведенных на контактную работу обучающихся с преподавателем,  36 академических часов на самостоятельную работу обучающихся. 

6. Содержание дисциплины (модуля), структурированное по темам (разделам) с указанием отведенного на них количества академических часов и виды учебных занятий.

Наименование и краткое содержание разделов и тем дисциплины (модуля),

Форма промежуточной аттестации по дисциплине (модулю)	Всего
(часы)	В том числе	
		Контактная работа 
(работа во взаимодействии с преподавателем)
Виды контактной работы, часы	Самостоятельная работа обучающегося,
 часы 
	
		Занятия лекционного  типа*	Занятия семинарского типа*	Всего		
1.	Вычислительная задача, трудоёмкость алгоритма, вычислительная сложность задачи. Задача распознавания языка. Задача поиска.	3	2		2	1	
2.	Однородная и неоднородная модели. Тезис Тьюринга. Универсальные машины Тьюринга.	3	2		2	1	
3.	Теоремы об иерархии и ускорении.	8	6		6	2	
4.	Понятие эффективного вычисления. Тезис Эдмондса (полиномиальный тезис Тьюринга). Классы P и P∕poly	4	2		2	2	
5.	Вычисление с оракулом. Релятивизация. Самосводимость.	4	2		2	2	
6.	Недетерминированные вычисления. Класс NP и задача поиска. 	3	2		2	1	
7.	Сводимость по Карпу. Сводимость по Куку. Полные задачи.	3	2		2	1	
8.	Класс PSPACE.	4	2		2	2	
9.	Вероятностная машина Тьюринга. Классы RP, BPP. Рандомизированнаясамосводимость.	8	6		6	2	
10.	Интерактивные доказательства	6	4		4	2	
11.	Полиномиальная иерархия.	8	6		6	2	
Промежуточная аттестация: устный экзамен	18	0		0	18	
Итого	72	36		36	36	

7. Фонд оценочных средств (ФОС) для оценивания результатов обучения по дисциплине (модулю)

7.1. Типовые контрольные задания или иные материалы для проведения текущего контроля успеваемости.

Самостоятельные работы, коллоквиумы и дополнительные задания не предусмотрены учебным планом.

7.2. Типовые контрольные задания или иные материалы для проведения промежуточной аттестации.

Вопросы к экзамену.

1.	Математические и вычислительные задачи (задачи поиска и распознавания, примеры, нижние и верхние оценки)
2.	Детерминированная машина Тьюринга и класс DTIME, теорема о линейном ускорении (идея доказательства)
3.	Теорема об иерархии (с доказательством, диагональный метод)
4.	Теорема о пропуске в иерархии (с доказательством), теорема о сверхэкспоненциальном ускорении (формулировка)
5.	Нерелятивизируемые утверждения (нельзя доказать P <> NP методом диагонализации)
6.	Недетерминированная машина Тьюринга, класс NP, эквивалентность двух определений
7.	Классы P, EXP, PSPACE (соотношения между ними)
8.	Машина Тьюринга с оракулом, сводимость по Куку, эффективные вычисления, незамкнутость классов DTIME(n^k)
9.	Замкнутость класса P по Куку, Самосводимость
10.	Сводимость по Карпу, NP-трудность и NP-полнота, замкнутость классов P, NP
11.	Класс RP, RP_weak, RP_strong (определение, доказательство их равенства)
12.	Класс BPP, BPP_weak, BPP_strong (определение, доказательство их равенства)
13.	Вероятностная машина тьюринга, классы PP, ZPP (определения, соотношение с другими классами)
14.	Однородная и неоднородная модель вычислений, класс SIZE
15.	Класс P/Poly (определение, соотношения с классом SIZE и BPP)
16.	Полиномиальная иерархия
17.	Интерактивные доказательства

Типовые задачи для экзамена.

1.	Привести пример оракулов, относительно которых классы P и NP совпадают и не совпадают.
2.	Привести пример полной относительно сводимости по Карпу в PSPACE задачи, доказать полноту этой задачи.
3.	Привести пример семейства графов, для которых задача распознаваниягамильтоновости графа не сложнее, чем задача распознавания эйлеровости.
4.	Доказать следующее утверждение: пусть из двух функций f, g : N → N первая не превосходит вторую начиная с некоторого n. Тогда DTIME(f) ⊆ DTIME(g).
5.	Определите класс Exp^Exp . Верно ли, что Exp = Exp^Exp? Дайте явное описание класса Exp^Exp через классы DTIME 
6.	Докажите, что язык гамильтоновых графов лежит в классе NP.
7.	Докажите, что из замкнутости относительно сводимости по карпу класса K следует замкнутость класса coK. 

Экзаменационный билет состоит из одного вопроса и задачи, например

1.	Сводимость по Карпу, NP-трудность и NP-полнота, замкнутость классов P, NP
2.	Привести пример полной в PSPACE задачи, доказать полноту этой задачи.

ШКАЛА И КРИТЕРИИ ОЦЕНИВАНИЯ результатов обучения (РО) по дисциплине (модулю)  
	
Оценка
РО и
соответствующие виды оценочных средств 	2	3	4	5	
Знания
Экзамен	Отсутствие знаний	Фрагментарные знания	Общие, но не структурированные знания	Сформированные систематические знания	
Умения
Контрольная задача на экзамене	Отсутствие умений	В целом успешное, но не систематическое умение	В целом успешное, но содержащее отдельные пробелы умение (допускает неточности непринципиального характера)
	Успешное и систематическое умение	
Навыки 
(владения, опыт деятельности)
Экзамен
	Отсутствие навыков (владений, опыта)	Наличие отдельных навыков (наличие фрагментарного опыта)	В целом, сформированные навыки (владения), но используемые не в активной форме	Сформированные навыки (владения), применяемые при решении задач	
Соответствие результатов обучения и компетенций, в развитии которых участвует дисциплина (модуль)
	
Результаты обучения	Компетенция, с частичным формированием которой связано достижение результата обучения	
Знать:
1.	основные подходы к формализации понятия “сложность”;
2.	основные подходы к постановке вычислительных задач в терминах задач распознавания языков и задач поиска;
3.	основные модели вычислений и принципиальные различия между ними;
4.	понятия, определения и факты теории сложности вычислений;

Уметь:
1.	применять на практике общую теорию и методы теории сложности;
2.	сопоставлять математическим задачам их вычислительные аналоги;
3.	выбирать релевантную модель вычислений для анализа сложности вычислительных задач;

Владеть:
1.	навыками формализации вычислительных задач;

ОПК-1.Б	
Знать:
1.	основные классы языков, определяемых различными моделями вычислений;
2.	соотношения между различными классами языков;
3.	методы теории сложности для получения соотношений между классами языков;
4.	открытые проблемы теории сложности; 

Уметь:
1.	классифицировать языки с помощью техники сведений;
2.	исследовать принадлежность языка известным классам;

ОПК-2.Б	
Владеть:
1.	навыками использования аппарата дискретной математики, алгебры и теории вероятности для построения сведений между классами языков;

ПК-2.Б	

8. Ресурсное обеспечение:

Основная литература:

1.	Кузюрин Н. Н., Фомин С. А. Эффективные алгоритмы и сложность вычислений: Учебное пособие. - М.: МФТИ, 2007. - 312 с.
2.	Гэри М., Джонсон Д. Вычислительные машины и трудноразрешаемые задачи: Пер. с англ. - М.: Мир, 1982. - 416 с.
3.	А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. -  М.: МЦНМО, 1999. - 192 с.

Дополнительная литература:

1.	Н. К. Верещагин, В.А. Успенский, and А. А. Шень. Колмогоровская сложность и алгоритмическая случайность. МЦНМО, 1-е издание, 2013. 
2.	В. Б. Алексеев. Введение в теорию сложности алгоритмов. Издательский отдел ф-та ВМиК МГУ Москва, 2002.

Информационные справочные системы:

http://cryptography.ru/info/

Материально-техническое обеспечение:

аудитория с партами, меловой или маркерной доской.

9. Язык преподавания - русский.

10. Преподаватели:		с.н.с. ИПИБ МГУ Н.П. Варновский, 
				аспирант факультета ВМК МГУ Л. Р. Ахметзянова.

11. Авторы программы:	Доцент кафедры ИБ ВМК МГУ И. В. Чижов,
				с.н.с. ИПИБ МГУ Н.П. Варновский.