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

УТВЕРЖДАЮ
декан факультета вычислительной математики и кибернетики
______________/И.А. Соколов /
«___» ________________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.	некоторые приближенные алгоритмы для задач оптимизации с оценками их сложности.
Уметь:
1.	применять на практике методы анализа сложности алгоритмов и задач;
2.	применять на практике методы и подходы для построения быстрых алгоритмов;
3.	доказывать труднорешаемость задач.
Владеть:
1.	методами построения быстрых алгоритмов;
2.	методами доказательства утверждений о сложности алгоритмов.

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

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

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

Форма промежуточной аттестации по дисциплине (модулю)	Всего
(часы)	В том числе	
		Контактная работа 
(работа во взаимодействии с преподавателем)
Виды контактной работы, часы	Самостоятельная работа обучающегося,
 часы 
	
		Занятия лекционного типа*	Занятия семинарского типа*	Всего		
1.	Основные понятия теории сложности алгоритмов. Примеры алгоритмов поиска и сортировки с анализом сложности.	9	6	0	6	3	
2.	Рекуррентные методы построения алгоритмов. Метод динамического программирования. Метод «разделяй и властвуй». Алгоритмы Карацубы и Тоома для умножения чисел. Метод Штрассена для умножения матриц.	21	14	0	14	7	
3.	Метод расширения модели. Алгоритмы умножения 0-1 матриц. Алгоритм транзитивного замыкания графов. Ускоренные алгоритмы распознавания свойств дискретных функций.	18	12	0	12	6	
4.	Общая теория сложности задач. Существование сколь угодно сложных задач. Метод следов для получения нижних оценок сложности. Сложность распознавания симметрии на машинах Тьюринга. Классы P и NP. Теорема Кука. Некоторые NP-полные задачи на графах. 	36	24	0	24	12	
5.   Задачи оптимизации. Приближенные алгоритмы. Задача коммивояжера. Сложность точных и приближенных алгоритмов для различных вариантов задачи коммивояжера.	12	8	0	8	4	
6.  Классы PSPACE и DLOG. Терема об иерархии по памяти.	12	8	0	8	4	
7.  Промежуточная аттестация: устный экзамен	36	0	0	0	36	
Итого	144	72	0	72	72	

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

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

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

Зачет учебным планом не предусматривается.
ВОПРОСЫ К ЭКЗАМЕНУ
В билете 2 вопроса – один из части А и один из части В.
Часть А – ответ без подготовки, но по любым материалам (конспекты, книжки и т.д.). Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки утверждений – без конспектов.
1.	Метод «разделяй и властвуй». Теорема о скорости роста функции, заданной рекуррентным неравенством.
2.	Алгоритм Тоома для умножения чисел.
3.	Алгоритм Штрассена для умножения матриц.
4.	Алгоритмы обычного и булевского умножения матриц с битовыми операциями.
5.	Сложность распознавания принадлежности функции, заданной векторно, классам, определяемым двухместными предикатами.
6.	Сложность распознавания принадлежности булевой функции, заданной векторно, классу FmU(Rm).
7.	Вычислимые функции, их нумерация. Теоремы о существовании трудно вычислимой общерекурсивной функции.
8.	Теорема Барздиня о распознавании симметрии.
9.	Теорема о регулярности языка, распознаваемого со следом константной длины.
10.	Теорема о регулярности языка, распознаваемого со слаборастущими длиной следа или временем.
11.	Теорема Кука.
12.	Теорема об NP-полноте языка ГАМИЛЬТОНОВ ЦИКЛ.
13.	Задача коммивояжера, ее NP-трудность, теоремы о приближенных алгоритмах     для нее.
14.	Теорема о PSPACE-полноте задачи о квантифицированных булевских формулах.
15.	Теорема об иерархии по памяти. Несовпадение классов  DLOG  и  PSPACE.

Часть В – ответ без конспектов и почти без подготовки (с доказательствами).

16.	Сложность алгоритма бинарного поиска в упорядоченном массиве.
17.	Нижние оценки сложности поиска в упорядоченном массиве.
18.	Нижняя оценка сложности сортировки. Сложность алгоритма сортировки вставкой.
19.	Сложность алгоритма сортировки слиянием.
20.	Алгоритм динамического программирования для задачи об оптимальном порядке умножения матриц.
21.	Алгоритм динамического программирования для поиска кратчайших путей между всеми парами вершин в графе.
22.	Алгоритм Карацубы для умножения чисел.
23.	Алгоритм транзитивного замыкания графа.
24.	Верхние оценки сложности распознавания принадлежности булевой функции, заданной векторно, предполным классам Поста T0, T1, S, L, M.
25.	Леммы о максимальной длине и сумме длин различных слов.
26.	Классы P и NP. Примеры языков из NP. Замкнутость класса P относительно полиномиального сведения.
27.	Теоремы об NP-полноте языков КЛИКА, Независимое Множество Вершин, Вершинное Покрытие.
28.	Полиномиальный алгоритм для построения эйлерова цикла.
29.	Задача о минимальном вершинном покрытии, ее NP-трудность, жадный и 1-приближенный алгоритмы для нее.
30.	Класс PSPACE. Соотношение между классами NP и PSPACE. Верхняя оценка времени работы для задач из PSPACE.
31.	Теорема о принадлежности задачи о квантифицированных булевских формулах классу PSPACE.
32.	Класс DLOG. Соотношение между классами DLOG и P.

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

1.	Теорема о регулярности языка, распознаваемого со следом константной длины.
2.	Алгоритм транзитивного замыкания графа.

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

Соответствие результатов обучения и компетенций, в развитии которых участвует дисциплина (модуль)	
Результаты обучения	Компетенция, с частичным формированием которой связано достижение результата обучения	
Знать:
1.	основные известные быстрые алгоритмы с оценками их сложности;
2.	основные методы и подходы для построения быстрых алгоритмов;
3.	некоторые приближенные алгоритмы для задач оптимизации с оценками их сложности.
Уметь:
4.	применять на практике методы анализа сложности алгоритмов и задач;
5.	применять на практике методы и подходы для построения быстрых алгоритмов.	

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

ОПК-2.Б	
Знать:
1.	некоторые классы сложности языков и задач.
Уметь:
2.	доказывать труднорешаемость задач.

Владеть:
3.	методами построения быстрых алгоритмов;
4.	методами доказательства утверждений о сложности алгоритмов.

ПК-2.Б	

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

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

1.	Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Изд. отдел ф-та ВМиК МГУ, 2002.

Дополнительная литература:
1.	Проблемы математической логики. Сложность алгоритмов и вычислимых функций. (Сб. переводов), М.: Мир, 1970, с. 311-314.
2.	Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., «Мир», 1979.
3.	Барздинь Я.М. Сложность распознавания симметрии на машинах Тьюринга. Сб. "Проблемы кибернетики", вып. 15 (1965), с. 245-248.
4.	Гэpи М., Джонсон Д. Вычислительные машины и тpудноpешаемые задачи. М.: Мир, 1982.
5.	Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М., «Мир», 1985.

Информационные справочные системы:  http://mk.cs.msu.ru

Материально-техническое обеспечение:  аудитория с партами и меловой доской.

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

10. Преподаватели:  		профессор факультета ВМК МГУ В.Б. Алексеев

11. Авторы программы:  	профессор факультета ВМК МГУ В.Б. Алексеев.