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

УТВЕРЖДАЮ
декан факультета вычислительной математики и кибернетики
______________/И.А. Соколов /
«___» ________________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.	Основные теоремы о сводимости задач.

Уметь:
1.	Оценивать число шагов алгоритма;
2.	Пользоваться рекуррентными соотношениями для анализа сложности алгоритмов;
3.	Выводить асимптотические оценки сложности алгоритмов.
  
Владеть:
1.	Навыками применения рекуррентных соотношений.
2.	Навыками решения практических задач анализа алгоритмов;
3.	Навыками анализа сложности алгоритмов  
4. Формат обучения: лекции проводятся с использованием меловой доски.

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

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

Форма промежуточной аттестации по дисциплине (модулю)	Всего
(часы)	В том числе	
		Контактная работа 
(работа во взаимодействии с преподавателем)
Виды контактной работы, часы	Самостоятельная работа обучающегося,
 часы 
	
		Занятия лекционного типа*	Занятия семинарского типа*	Всего		
1.	Сложность алгоритма как функция одного или нескольких числовых аргументов. Сложность в худшем случае	12	8	0	8	4	
2.	Сложность в среднем	12	8	0	8	4	
3.	Текущий контроль успеваемости: контрольная работа № 1 	2	0	0	0	2	
4.	Оценивание числа шагов (итераций) алгоритма	6	2	0	2	4	
5.	Нижняя граница сложности алгоритмов некоторого класса. Оптимальные алгоритмы	12	8	0	8	4	
6.	Битовая сложность	12	8	0	8	4	
7.	Рекуррентные соотношения как средство анализа сложности	12	8	0	8	4	
8.	Сводимость	10	6	0	6	4	
9.	Текущий контроль успеваемости: контрольная работа № 2	2	0	0	0	2	
Промежуточная аттестация: письменный экзамен	28	0	0	0	28	
Итого	108	48	0	48	60	

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

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

Контрольная работа № 1	
Вариант 1	Вариант 2	

1. Указать все вещественные значения δ при которых справедлива оценка
а) TTD(n) = O(nδ),
б) TTD(n) = Ω(nδ),
в) TTD(n) = Θ(nδ),
где TTD(n) – сложность алгоритма пробных делений.

2. Верно ли, что для рассмотрения сложности в среднем некоторого алгоритма требуется задание распределения вероятностей
а) на множестве всех допустимых входов?
б) на каждом из множеств всех входов фиксированного размера?

3.  При некоторых значениях  n число сравнений, затрачиваемых
при бинарном поиске, не определяется однозначно исходя лишь из
значения n (например, зная лишь, что n = 6, мы не можем указать
точное число сравнений). Но существует бесконечно много n таких,
для которых это значение определяется единственным образом и рав-
но ⌊log2 n ⌋+1. Доказать.
4. Пусть  QS (n) и  opt (n) – сложности в среднем быстрой сортировки и оптимальной в среднем сортировки. Верно ли, что QS (n) ∼ opt (n)? Если нет, то можно ли подобрать константу c такую, что  QS (n) ∼ c opt (n)? 	
1. Известно, что мультипликативная сложность метода
Гаусса решения системы n линейных уравнений с n неизвестными
допускает оценки
1) O(n3),     2)  + O(n2),      3) Θ(n3).
а) Из какой оценки (указать номер) следуют две остальные?
б) Можно ли из приведенных оценок выбрать такую, которая является следствием любой из остальных?
в) Является ли оценка Ω(n3) следствием какой-либо из оценок 1, 2, 3?
 
2. Верно ли, что определение усредненных затрат некоторого
рандомизированного алгоритма требует задания распределения вероятностей
а) на множестве всех допустимых входов?
б) на каждом из множеств всех входов фиксированного размера?

3. Верно ли, что сложность по числу сравнений сортировки массива из n элементов бинарными вставками есть n log2 n+ O(1)?

4. Может ли сортировка со сложностью в худшем случае Ω(n log n) по числу перемещений элементов быть оптимальной по порядку сложности по числу сравнений?

Контрольная работа № 2	
Вариант 1	Вариант 2	

1.Исследовать битовую сложность вычисления величины 1 +2+ ... +n последовательными сложениями. Размером входа считать битовую длину m целого числа n.

2. Определить сложность алгоритма перекладывания дисков в игре «Ханойские башни» при условии, что затраты на перекладывание со столбика на столбик i-го по величине диска равны i2.

3. Здесь речь идет о линейной сводимости P ≤ Q задач, связанных с мультипликативными операциями над квадратными числовыми матрицами порядка n. Рассматриваются лишь такие алгоритмы решения задачи Q, для сложности по числу арифметических операций каждого из которых выполняется соотношение T(kn)  = O(T(n)), k =2, 3.
Требуется показать, что задача умножения произвольных квадратных матриц линейно сводится к задаче умножения симметричных квадратных матриц.	
1. Из определения чисел Фибоначчи видно, что можно  вычислить Fn, выполнив n−1 сложение. Доказать, что битовая сложность этого алгоритма допускает оценку O(n2) при рассмотрении n в качестве размера входа.

2. Определить сложность алгоритма перекладывания дисков в игре «Ханойские башни» при условии, что затраты на перекладывание со столбика на столбик i-го по величине диска равны 2i .

3. Здесь речь идет о линейной сводимости P ≤ Q задач, связанных с мультипликативными операциями над квадратными числовыми матрицами порядка n. Рассматриваются лишь такие алгоритмы решения задачи Q, для сложности по числу арифметических операций каждого из которых выполняется соотношение T(kn)  = O(T(n)), k =2, 3.
Требуется показать, что задача умножения произвольных квадратных матриц линейно сводится к задаче умножения верхних треугольных матриц.	

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

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

Уметь:
1.	Оценивать число шагов алгоритма;
2.	Пользоваться рекуррентными соотношениями для анализа сложности алгоритмов
3.	Выводить асимптотические оценки сложности алгоритмов;
  
Владеть:
1.	Навыками применения рекуррентных соотношений.
2.	Навыками решения практических задач анализа алгоритмов;
3.	Навыками анализа сложности алгоритмов.	

ПК-2.Б 

ОПК-2.Б

ОПК-1.Б	

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

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

1. Абрамов С.А.  Лекции о сложности алгоритмов.  Издание второе переработанное. M:  МЦНМО. 2012.  
2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.  М.: Мир. 1979. 
3. Кормен Т., Лейзерсон Ч., Ривест Р.  Алгоритмы: построение и анализ. M: МЦНМО. 2000. 
  
Дополнительная литература:

. 1. Алексеев  В.Б. Введение в теорию сложности алгоритмов (учебное пособие для студентов), M:  ВМК МГУ. 2002. 
2. Гэри  М.,  Джонсон Д.   Вычислительные машины и труднорешаемые задачи. М: Мир. 1982. 
3. Вялый М.Н.  Сложность вычислительных задач. Математическое просвещение. Вып. 4.  M:  МЦНМО. 2000. 
4.Montwani R., Raghavan P.  Randomized algorithms. Cambridge University Press.1975.

Информационные справочные системы:  https://www.ccas.ru/ca/doku.php/essay

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

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

10. Преподаватели:  	профессор факультета ВМК МГУ С.А. Абрамов, 
			доцент факультета ВМК МГУ Е.А. Бордаченкова, 
			ассистент факультета ВМК МГУ А.А. Панферов.

11. Авторы программы:  профессор факультета ВМК МГУ С.А. Абрамов, доцент факультета ВМК МГУ Е.А. Бордаченкова.