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

УТВЕРЖДАЮ
декан факультета вычислительной математики и кибернетики
______________/И.А. Соколов /
«___» ________________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.Б Способность понимать и применять в научно-исследовательской деятельности современный математический аппарат
•	ПК-4.Б Способность применять в профессиональной деятельности современные средства разработки программного обеспечения и методы параллельной обработки данных, реализовывать отдельные этапы разработки системного и прикладного программного обеспечения, систем обработки и анализа данных, сетевых технологий
Планируемые результаты обучения по дисциплине (модулю):
Знать:
1.	основные понятия и классы задач теории математического программирования и теории расписаний,
2.	современные архитектуры центров обработки данных и вычислительных систем реального времени,
3.	задачи планирования вычислений в центрах обработки данных и вычислительных системах реального времени,
4.	принципы построения алгоритмов имитации отжига, муравьиных алгоритмов, генетических и эволюционных алгоритмов, жадных алгоритмов, алгоритмов сочетающих жадные стратегии и ограниченный перебор,
5.	задачи, которые необходимо решить при построении алгоритма для конкретной прикладной задачи оптимизации и методы их решения.
Уметь:
1.	математически формулировать задачи условной оптимизации и планирования вычислений,
2.	разрабатывать алгоритмы решения этих задач,
3.	проводить теоретическое и экспериментальное исследование свойств алгоритмов.
Владеть:
1.	методами оценки класса сложности задачи,
2.	методами доказательства корректности алгоритмов,
3.	методами оценки вычислительной сложности алгоритмов. 
4. Формат обучения: лекции и семинарские занятия проводятся с использованием слайдов лекций MS PowerPoint и меловой доски.

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

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

В курсе рассматриваются алгоритмы, опирающиеся на метод проб и ошибок: генетические и эволюционные алгоритмы, алгоритмы имитации отжига, муравьиные алгоритмы, алгоритмы случайного поиска (ненаправленного, направленного, направленного с самообучением). Рассматриваются теоретические основы построения алгоритмов, применение алгоритмов для решения классических задач комбинаторной оптимизации и для решения задач планирования вычислений в распределенных системах реального времени и центрах обработки данных. 

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

форма промежуточной аттестации по дисциплине (модулю)	Всего
(часы)	В том числе	
		Контактная работа (работа во взаимодействии с преподавателем), часы
из них	Самостоятельная работа обучающегося, часы
	
		Занятия лекционного  типа 	Занятия семинарского типа 	  Всего 		
Тема 1. Классификация задач и алгоритмов математического программирования.
•	Задачи условной оптимизации и их классификация.
•	«Сложные» задачи условной оптимизации. 
•	Пояснение использование априорной информации о целевой функции и функциях ограничениях для построения алгоритма (на примере задач линейного программирования, симплекс метод).
•	Задачи комбинаторной оптимизации. Задача коммивояжера.
•	Задача о рюкзаке: содержательная и математическая формулировка, частные задачи, пример жадного алгоритма оптимального для непрерывной задачи и приближенного для дискретной задачи.	18	6	6	12	6	
Тема 2. Задачи планирования вычислений в ЦОД и ВСРВ.
Архитектура ЦОД.
Характеристики физических ресурсов.
Типы виртуальных ресурсов и их характеристики.
Модели обслуживания.
Жизненный цикл виртуального ресурса.
Соглашения об уровне обслуживания (Service Level Agreement (SLA)).
Политики размещения виртуальных ресурсов.
Задача размещения виртуальных ресурсов для модели обслуживания IaaS (содержательная формулировка).

Примеры архитектур ИУС РВ:
Комплекс бортового оборудования (КБО) самолета F-22.
КБО МКС.
Режим работы КБО, требования к выполнению задач в реальном времени, большой цикл.
Предобработка информации, первичная и вторичная обработка информации.
Федеративные архитектуры. 
Цель разработки новых архитектур и технологий построения КБО.
ИМА: подходы к достижению целей и стандарты.
Задачи планирования вычислений в КБО с архитектурой ИМА. 
Проблемы переноса программ первичной обработки информации в единый вычислитель (на примере локационных систем).	12	4	4	8	4	
Тема 3. Алгоритмы имитации отжига.
Вероятностный закон принятия нового решения текущим. Общая схема алгоритма. Законы понижения температуры.
Скорость сходимости. Динамический закон понижения температуры.
Алгоритм ИО для построения многопроцессорных расписаний:
	• Математическая формулировка задачи построения многопроцессорных расписаний.
	• Ярусная форма представления расписаний.
	• Система операций преобразование расписаний, теорема о ее замкнутости  и полноте, доказательство теоремы.
	• Метрика в пространстве корректных расписаний.
	• Направленные стратегии применения операций преобразования расписаний.

Параллельный алгоритм имитации отжига.
1. Способы распараллеливания алгоритмов ИО.
2. Параллельный алгоритм ИО для построения многопроцессорных расписаний: 
•	разбиение пространства расписаний на области, 
•	модификация операций преобразования расписаний, 
•	распределение областей по вычислительным узлам и схема отсечения областей.
•	эффективность параллельного алгоритма по критериям точность и вычислительная сложность.
•	Эффективность псевдопараллельного алгоритма по критериям точность и вычислительная сложность.	24	8	8	16	8	
Тема 4. Алгоритмы случайного поиска.
1. Основы методов случайного поиска, общая схема алгоритма и ее параметры.
2. Алгоритмы направленного случайного поиска: 
•	алгоритм наилучшей пробы, 
•	алгоритм с парной пробой, 
•	алгоритм с возвратом при неудачном шаге, алгоритм с линейной  экстраполяцией.
3. Алгоритмы случайного направленного поиска с самообучением: 
•	принципы построения алгоритмов, 
•	способы самообучения,
•	устранение положительной обратной связи.	18	6	6	12	6	
Тема 5. Генетические и эволюционные алгоритмы (ГА). 
Муравьиные алгоритмы (МА).
 Области успешного применения ГА.
 Генетический алгоритм Холланда.
Теорема схем и гипотеза строительных блоков.
Примеры модификации операций генетического алгоритма и объяснение целей их введения с точки зрения теоремы схем и гипотезы строительных блоков.
ГА с самообучением.

 Биологическая модель МА.
 МА для решения задачи коммивояжера.
Использование МА для построения расписаний.
Недостатки базового МА и его модификации.
МА построения расписания обменов по каналу с централизованным управлением на основе схемы муравьиных колоний. 
МА построения многопроцессорного расписания.
МА минимизации суммарного запаздывания работ.	36	12	12	24	12	
6. Промежуточная аттестация – устный экзамен	36		36	
Итого 	144	72	72	

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

7.1. Типовые контрольные задания или иные материалы для проведения текущего контроля успеваемости.
1. Построить, обосновать корректность и завершимость, реализовать и протестировать алгоритм имитации отжига для решения задачи определения минимально необходимого числа процессоров и построения расписания выполнения функциональных задач со временем выполнения не превышающим заданный директивный срок. Процессоры одинаковые по производительности и по функциональным возможностям, прерывания недопустимы, отношение частичного порядка на множестве работ произвольное, времена выполнения работ различные.
2. Реализовать и провести исследование свойств алгоритма имитации отжига для решения задачи построения статических многопроцессорных расписаний с минимальным временем выполнения на заданном числе процессоров. Алгоритм приведен в лекции. Для исследования свойств алгоритма использовать метод проверки статистических гипотез.
Вопросы к экзамену.
1.	Классификация задач условной оптимизации. Понятие комбинаторных задач условной оптимизации и проблемы применения для их решения оптимальных и эвристических алгоритмов, использующих априорно известные свойства о целевой функции и функциях ограничений. 
2.	Классические задачи комбинаторной оптимизации: задача о рюкзаке и задача коммивояжера (симметричная задача коммивояжера, асимметричная задача коммивояжера, метрическая задача коммивояжера). 
3.	Задачи построения расписаний и их классификация.
4.	Задача построения статико-динамических расписаний.
5.	Задача построения расписания обменов по шине с централизованным управлением для схемы с подциклами (на примере стандарта MIL-STD 1533В).
6.	Задача построения расписания обменов по шине с централизованным управлением для схемы без подциклов (на примере стандарта MIL-STD 1533В).
7.	Алгоритм направленного случайного поиска с парной пробой. Алгоритм наилучшей пробы.
8.	Алгоритм направленного случайного поиска с возвратом при неудачном шаге.
9.	Алгоритм направленного случайного поиска с пересчетом при неудачном шаге.
10.	Алгоритм направленного случайного поиска с линейной экстраполяцией.
11.	Алгоритм статистического градиента.
12.	Принципы построения алгоритмов случайного направленного поиска с самообучением. Самообучение методом исключения. Покоординатное экспоненциальное обучение. Алгоритм покоординатного самообучения с произвольным законом изменения вероятности.
13.	Принципы построения алгоритмов случайного направленного поиска с самообучением. Способы решения проблемы передетерминирования алгоритма, повышения чувствительности алгоритма к выбору наилучшего направления, способы устранения положительной обратной связи.
14.	Концепция построения алгоритмов имитации отжига. Общая схема алгоритмов и проблемы построения алгоритмов для решения задач условной оптимизации.
15.	Асимптотическая сходимость алгоритмов имитации отжига: описание поведения алгоритма имитации отжига цепью Маркова, теоремы о сходимости, скорость сходимости.
16.	Методы распараллеливания алгоритмов имитации отжига: асинхронный параллельный алгоритм, параллельный алгоритм с синхронизацией, алгоритм, основанный на декомпозиции целевой функции, подходы, основанные на декомпозиции пространства решений.
17.	Алгоритм имитации отжига для решения задачи построения статических многопроцессорных расписаний с минимальным временем выполнения на заданном числе процессоров: математическая формулировка задачи, способы представления расписания и операций его преобразования, стратегии применения операций преобразования текущего решения.
18.	Параллельный алгоритм имитации отжига для построения статических многопроцессорных расписаний: разбиение исходного пространства решений на области, операции преобразования расписания внутри области, распределение областей по узлам вычислительной системы.
19.	 Простой генетический алгоритм (алгоритм Холланда).
20.	Теория схем. Гипотеза строительных блоков.
21.	Генетический алгоритм для решения задачи определения минимально необходимого числа процессоров и построения расписания выполнения функциональных задач со временем выполнения не превышающим заданный директивный срок: математическая формулировка задачи, кодирование решений, операции генетического алгоритма, функция выживаемости и критерий останова. 
22.	Муравьиные алгоритмы: концепция построения алгоритмов (биологическая модель), общая схема работы муравьиных алгоритмов. 
23.	Модификации муравьиных алгоритмов: максиминный алгоритм, алгоритм с поглощением феромона, совместное использование с алгоритмами локального поиска, элитные муравьи, ранговый алгоритм, список кандидатов.
24.	Муравьиный алгоритм для решения задачи построения статико-динамических расписания.
25.	Муравьиный алгоритм для решения задачи построения расписания обменов по шине с централизованным управлением (схема с подциклами).
26.	Жадные алгоритмы: общая схема, оптимальный алгоритм построение расписания выполнения работ в одноприборном устройстве, доказательство оптимальности алгоритма. 
27.	Алгоритмы, сочетающие жадные стратегии и стратегии ограниченного перебора: общая схема, процедуры ограниченного перебора.
28.	Самоорганизующаяся облачная платформа: архитектура и язык описания запросов для создания виртуальных сетей. 
29.	Методика статистической обработки результатов экспериментов по исследованию свойств алгоритмов.

Типовые задачи для экзамена.
1.	Построить алгоритм направленного случайного поиска с возвратом при неудачном шаге и обосновать его свойства для решения задачи о рюкзаке.
2.	Построить алгоритм направленного случайного поиска с возвратом при неудачном шаге и обосновать его свойства для решения симметричной задачи коммивояжера. 
3.	Построить генетический алгоритм и обосновать его свойства для решения задачи о рюкзаке. 
4.	Построить генетический алгоритм и обосновать его свойства для решения симметричной задачи коммивояжера.
5.	Построить генетический алгоритм и обосновать его свойства для решения асимметричной задачи коммивояжера.
6.	Построить генетический алгоритм и обосновать его свойства симметричной метрической задачи коммивояжера.
7.	Построить алгоритм имитации отжига и обосновать его свойства для решения задачи о рюкзаке.
8.	Построить алгоритм имитации отжига и обосновать его свойства для решения симметричной задачи коммивояжера.

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

Уметь:
1.	математически формулировать задачи условной оптимизации и планирования вычислений,
2.	разрабатывать алгоритмы решения этих задач,
3.	проводить теоретическое и экспериментальное исследование свойств алгоритмов.

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

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

Основная литература:
1.	  М. Мину. Математическое программирование. Теория и алгоритмы.- М.: Наука, 1990.
2.	Т. Кормен, Ч. Лейзерсон¸ Р. Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.-960с.
3.	Л.А. Растригин. Статистические методы поиска.- М.: Наука, 1968.
4.	Holland J.N. Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan: Univ. of Michigan Press, 1975.
5.	Dorigo M. Optimization, Learning and Natural Algorithms. // PhD Thesis. Dipartimento di Elettronica, Politechnico Di Milano, Milano. 1992.
6.	Уоссермен Ф. Нейрокомпьютерная техника. Теория и практика.- М.: Мир, 1992. – 240с.
7.	Теория расписаний и вычислительные машины. Под ред. Э.Г. Коффмана. М.: Наука, 1984. 334 с. 
8.	Смелянский Р.Л. Модель функционирования распределенных вычислительных систем. // Вестн. Моск. Ун-та. сер 15, Вычисл. Матем. и Кибернетика. 1990, No. 3, стр. 3-21.
9.	Костенко В.А. Алгоритмы построения расписаний для вычислительных систем реального времени, допускающие использование имитационных моделей // Программирование - 2013. - №5 - С.53-71.
10.	Калашников А.В., Костенко В.А. Параллельный алгоритм имитации отжига для построения многопроцессорных расписаний // Известия РАН. Теория и системы управления. - 2008. -№ 3 - С.133-142.
11.	Вдовин, П.М. Зотов И.А, Костенко В.А., Плакунов А.В., Смелянский Р.Л. Сравнение различных подходов к распределению ресурсов в центрах обработки данных // Известия РАН. Теория и системы управления, 2014., № 4.
12.	Вдовин, П.М., Костенко В.А. Алгоритм распределения ресурсов в центрах обработки данных с раздельными планировщиками для различных типов ресурсов // Известия РАН. Теория и системы управления, 2014., № 5.

Дополнительная литература:
1.	Костенко В.А. Алгоритмы построения расписаний для одноприборных систем, входящих в состав систем реального времени // Методы и средства обработки информации. Труды третьей Всероссийской научной конференции. - М.: Издательский отдел факультета ВМиК МГУ имени М.В. Ломоносова; МАКС Пресс, 2009. - С.245-258.
2.	Штовба С.Д. Муравьиные алгоритмы: теория и применение// Программирование. 2005. №4.
3.	Arinc Specification 653. Airlines Electronic Engineering Committee. [PDF] (http://www.arinc.com).
4.	Государственный стандарт СССР «Интерфейс магистральный последовательный системы электронных модулей» ГОСТ 26765.52-87.
5.	Костенко В.А., Гурьянов Е.С. Алгоритм построения расписаний обменов по шине с централизованным управлением и исследование его эффективности// Программирование, 2005., N6. - С.67-76.
6.	Z. J. Czech. Parallel Simulated Annealing for the Delivery Problem. // Ninth Euromicro Workshop on Parallel and Distributed Processing. 2001. Mantova Italy. P 219-226.
7.	Z. J. Czech. Parallel Simulated Annealing for the Delivery Problem. // Ninth Euromicro Workshop on Parallel and Distributed Processing. 2001. Mantova Italy. P 219-226.
8.	Stefka Fidanova, Simulated Annealing for Grid Scheduling Problem //. IEEE John Vincent Atanasoff 2006 International Symposium on Modern Computing (JVA'06). 2006. P 41-45.
9.	D.Janaki Ram, T.H.Sreenivas, K.Ganapathy Subramaniam. Parallel Simulated Annealing Algorithms // Journal of parallel and distributed computing. 1996. №37. P 207-212.
10.	Golberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, Mass., 1989.
11.	Скобцов Ю.А. Основы эволюционных вычислений. Донецк.: ДонНТУ, 2008.- 326с.
12.	Костенко В.А., Смелянский Р.Л., Трекин А.Г. Синтез структур вычислительных систем реального времени с использованием генетических алгоритмов// Программирование, 2000., №5, С.63-72.
13.	Storn R., Price K. Minimizing the real functions of the ICEC'96 contest by differential evolution // IEEE Conference on Evolutionary Computation, Nagoya,  1996, pp. 842-844.
14.	Kalyanmoy Deb and Mayank Goyal. A Combined Genetic Adaptive Search GeneAS for Engineering Design. Computer Science and Informatics, 26(4):30--45, 1996.
15.	Костенко В. А., Плакунов А. В. Алгоритм построения одноприборных расписаний, основанный на схеме муравьиных колоний // Известия РАН. Теория и системы управления, 2013,. № 6, С.87-96.
16.	Д.А.Зорин, В.А.Костенко. Алгоритм синтеза архитектуры вычислительной системы реального времени с учетом требований к надежности // Известия РАН. Теория и системы управления. - 2012. –  № 3 - С.76–83. 

Информационные справочные системы: 	 https://istina.msu.ru  
http://elibrary.ru	
www.scopus.com	

Материально-техническкое обеспечение:
			Программное обеспечение для подготовки слайдов лекций MS PowerPoint
			Программное обеспечение для создания и просмотра pdf-документов Adobe Reader
			Для преподавания дисциплины требуется класс, оборудованный маркерной или меловой доской и проектором.

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

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

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