МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. ЛОМОНОСОВА
Факультет вычислительной математики и кибернетики
ПРОГРАММА
вступительного экзамена в аспирантуру по направлению 09.06.01 – информатика и вычислительная
техника,
направленность 05.13.15 – «вычислительные машины, комплексы и компьютерные сети»
От экзаменующегося требуется: знание материала, предусмотренного в общей и дополнительной частях; умение кратко изложить содержание работы, представленной в качестве реферата, и владение всем кругом вопросов связанных с узкой областью, к которой относится реферат.
1. Общая часть.
1.	Непрерывные функции одной переменной и их свойства. Равномерная непрерывность. Равностепенная непрерывность семейства функций. Теорема Арцела.
2.	Функции многих переменных. Полный дифференциал, и его геометрический смысл. Достаточные условия дифференцируемости. Градиент.
3.	Определенный интеграл. Интегрируемость непрерывной функции. Первообразная непрерывной функции. Приближенное вычисление определенных интегралов. Формулы трапеций и Симпсона, оценки погрешностей. Понятие о методе Гаусса.
4.	Числовые ряды. Сходимость рядов. Критерий Коши. Достаточные признаки сходимости (Коши, Деламбера, интегральный, Лейбница).
5.	Абсолютная и условная сходимость ряда. Свойства абсолютно сходящихся рядов. Перестановка членов ряда. Теорема Римана. Умножение рядов.
6.	Ряды и последовательности функций. Равномерная сходимость. Признак Вейерштрасса. Свойства равномерно сходящихся рядов (непрерывность суммы, почленное интегрирование и дифференцирование).
7.	Собственные и несобственные интегралы, зависящие от параметра. Равномерная сходимость по параметрам и ее признаки. Непрерывность, интегрирование и дифференцирование интегралов по параметру.
1.	
8.	Мера множества. Измеримые функции. Интеграл Лебега и его основные свойства.
9.	Степенные ряды в действительной и комплексной области. Радиус сходимости. Теорема Коши-Адамара. Теорема Абеля. Свойства степенных рядов (почленное интегрирование и дифференцирование). Разложение элементарных функций.
10.	Функции комплексного переменного. Условия Коши-Римана. Геометрический смысл аргумента и модуля производной.

11.	Элементарные функции комплексного переменного  ,    , , и
даваемые ими конформные отображения. Простейшие многозначные функции , Ln(z).
12.	Теорема Коши об интеграле по замкнутому контуру. Интеграл Коши. Ряд Тейлора.
13.	Ряд Лорана. Полюс и существенно особая точка. Вычеты. Основная теорема о вычетах и ее применение.
14.	Линейные преобразования. Квадратичные формы. Приведение их к каноническому виду линейными преобразованиями в комплексной и действительной областях. Закон инерции.
15.	Линейная зависимость и независимость векторов. Ранг матрицы. Системы линейных алгебраических уравнений, теорема Кронекера-Капелли. Общее решение системы линейных алгебраических уравнений.
16.	Ортогональные преобразования в евклидовом пространстве и ортогональные матрицы. Свойства ортогональных матриц.
17.	Характеристический многочлен линейного преобразования векторного пространства. Собственные числа и собственные векторы. Свойства собственных чисел и векторов симметрических матриц. Понятие о методе ортогональных вращений решения полной проблемы собственных значений.
18.	Итерационные методы решения уравнения f(x) = 0 (хорд, Ньютона). Принцип сжатых отображений в полных метрических пространствах и его применение.
19.	Линейные операторы, норма линейного оператора. Итерационные методы решения систем линейных алгебраических уравнений (методы простой итерации и Зейделя).
12.	
20.	Гильбертово пространство. Линейные и билинейные функционалы в гильбертовом пространстве. Линейные уравнения с вполне непрерывным оператором.
21.	Интегральные уравнения Фредгольма 2-ого рода. Теорема Фредгольма. Интегральные уравнения с симметричным ядром.
22.	Ортогональные системы функций. Ряды Фурье по ортогональной системе функций, неравенство Бесселя, сходимость ряда Фурье. Достаточные условия равномерной сходимости рядов Фурье по тригонометрической системе функций. Влияние гладкости функции на порядок коэффициентов Фурье.
23.	Теорема существования и единственности решения задачи Коши для
уравнения, системы уравнений первого порядка и уравнения n-ого
порядка.
24.	Линейные дифференциальные уравнения n-ого порядка. Линейное однородное уравнение. Линейная независимость функций. Фундаментальная система решений. Определитель Вронского. Общее решение неоднородного уравнения.
25.	Линейные обыкновенные дифференциальные уравнения с постоянными коэффициентами (однородные и неоднородные).
26.	Устойчивость по Ляпунову решений обыкновенных дифференциальных уравнений. Теорема об устойчивости по первому приближению. Второй метод Ляпунова.
27.	Простейшая задача вариационного исчисления. Уравнение Эйлера. Вариационная задача с подвижными концами. Условия трансверсальности.
28.	Градиентные методы поиска экстремума.
29.	Формализация понятия алгоритма (машины Тьюринга, нормальные алгоритмы Маркова). Алгоритмическая неразрешимость.
30.	Структура и состав вычислительной системы (аппаратура + программное обеспечение). Физические и виртуальные ресурсы. Управление ресурсами в вычислительной системе. Потоки управляющей информации и данных в вычислительной системе. Проблемы дисбаланса производительности компонентов вычислительной системы и аппаратно-программные решения, предназначенные для сглаживания этого дисбаланса. Кеширование информационных потоков в вычислительной системе.
31.	Архитектура многопроцессорных вычислительных систем. Графовая модель представления параллельных алгоритмов. Принципы построения параллельных программ с использованием технологий MPI и OpenMP.
29.	
Показатели   качества    параллельных   программ.   Закон    Амдала,    его следствия.
32.	Операционные системы, основные функции. Типы операционных систем. Организация управления и взаимодействия процессов в Операционной системе. Модели и средства синхронизации. Программирование взаимодействующих процессов. Модели организации и управления ОЗУ.
33.	Парадигмы программирования (функциональное, императивное, объектно-ориентированное программирование).
34.	Базы данных. Основные понятия реляционной модели данных. Реляционная алгебра. Средства языка запросов SQL.
35.	Функции алгебры логики. Реализация их формулами. Совершенная
дизъюнктивная нормальная форма.
36.	Схемы из функциональных элементов и простейшие алгоритмы их
синтеза. Оценка сложности схем, получаемых по методу Шеннона.
ЛИТЕРАТУРА
1.	Ильин В.А., Позняк Э.Г. Основы математического анализа, часть 1 и часть 2. М.: Физматлит, 2005 (часть 1) и 2002 (часть 2).
2.	Кудрявцев Л.Д. Математический анализ, часть 1 и часть 2. М.: Дрофа, 2003 (часть 1) и 2004 (часть 2).
3.	Александров   П.С.   Лекции   по   аналитической   геометрии.   М.: Наука, 1968.
4.	Воеводин В.В. Линейная алгебра. М.: Наука, 1980.
5.	Привалов    И.И.    Введение    в    теорию    функций    комплексного переменного. СПб.: Лань, 2009.
6.	Свешников  А.Г., Тихонов А.Н. Теория функций  комплексного переменного. М.: Физматлит, 2008.
7.	Гельфанд И.М. Лекции по линейной алгебре. Изд-во МЦНМО, 1998.
8.	Курош А.Г. Курс высшей алгебры. СПб.: Лань, 2006.
9.	Колмолгоров   А.Н.,   Фомин   С.В.   Элементы   теории   функций   и функционального анализа. М.: Физматлит, 2004.
10.	Шилов   Г.Е.   Введение   в   теорию   линейных   пространств.   М.: ГИТТЛ, 1956.
11.	Понтрягин   Л.С.   Обыкновенные   дифференциальные   уравнения. М.: Наука, 1982.
12.	Степанов     В.В.     Курс     дифференциальных     уравнений.     М.: Эдиториал УРСС, 2004.
13.	Петровский И.Г. Лекции по обыкновенным дифференциальным уравнениям. М.: Физматлит, 2009.
1.	

14.	Эльсгольц Л.З. Дифференциальные уравнения и вариационное исчисление. М.: Наука, 1969.
15.	Тихонов А.Н., Самарский А.А. Уравнения математической физики. М.: Наука, 2004.
16.	Соболев C.Л. Уравнения математической физики. М.: Наука, 1966.
17.	Петровский И.Г. Лекции об уравнениях с частными производными. М.: Физматлит, 2009.
18.	Березин И.С., Жидков Н.П. Методы вычислений, том 1 и том 2. М.: ГИФМЛ, 1962 (том 1) и 1959 (том 2).
19.	Бахвалов Н.С. Численные методы. М.: Наука, 1975.
20.	Самарский А.А. Введение в теорию разностных схем. М.: Наука, 1971.
21.	Феллер В. Введение в теорию вероятностей и ее приложения, том 1 и том 2. М.: Мир, 1964 (том 1) и 1967 (том 2).
22.	Крамер Г. Математические методы статистики. М.: Мир, 1975.
23.	Яблонский С.В. Введение в дискретную математику. М.: Высшая
Школа, 2010.
24.	Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
25.	Ложкин С.А. Лекции по основам кибернетики. М.: Издательский отдел ф-та ВМК МГУ, 2004.

26.	Мальцев А.И. Алгоритмы и вычислимые функции. М.: Наука, 1986.
27.	Карлин С. Математические методы в теории игр, программировании и экономике. М.: Мир, 1964.
28.	Васильев Ф.П. Методы оптимизации. М.: Факториал пресс, 2002.
29.	Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.
30.	Корухова Л.С., Шура-Бура М.Р. Введение в алгоритмы. Учебное
пособие для студентов I курса, 2-е исправленное издание. — М.
Издательский отдел факультета ВМиК МГУ (лицензия ИД № 05899 от
24.09.2001 г.); МАКС Пресс, 2010, http://sp.cmc.msu.ru/info/1/vvedalg.pdf
31.	Э. Таненбаум, Т. Остин, Архитектура компьютера. 6-е издание, СПб: Питер, 2013.
32.	Операционные системы. У. Столингс. Вильямс. 2002.
33.	Э. Таненбаум, Х. Бос Современные операционные системы. 4-е
издание, СПб: Питер, 2015.
34.	Т. Пратт. М. Зелкович. Языки программирования. Разработка и
реализация 4-е издание, СПб: Питер, 2002.
35.	В. Ш. Кауфман. Языки программирования. Концепции и принципы. -
М.: ДМК-Пресс, 2010.
36.	К. Дейт. Введение в системы баз данных. М: Вильямс, 2006.
37.	В.В. Воеводин, Вл.В. Воеводин "Параллельные вычисления", БХВ-Петербург, 2002, 608с.
38.	А.С. Антонов Технологии параллельного программирования MPI и
OpenMP: Учеб пособие. Предисл. : В.А. Садовничий - М.: Изд-во Моск.
ун-та, 2012. – 344 с. - (Серия "Суперкомпьютерное образование").

2. Дополнительная часть.

1.	Последовательная и параллельная сложность алгоритмов, информационный граф и ресурс параллелизма алгоритмов. Закон Амдала.
2.	Основные принципы построения и архитектура сети Интернет. Алгоритмы и протоколы внешней и внутренней маршрутизации. Явление перегрузки и методы борьбы с ней.
3.	Основные принципы организации оптических и беспроводных систем передачи данных (OTN, IEEE 802.11, 4G LTE, 5G).
4.	Сети хранения данных – архитектура и основные сервисы.
5.	Принципы организации и основные достоинства MPLS технологии.
6.	Программно-конфигурируемые сети (SDN). Основные принципы, архитектура и протоколы. Устройство OpenFlow контроллера и коммутатора. Примеры применения.
7.	Виртуализация сетевых сервисов (NFV). Основные принципы, этапы развития, архитектура, преимущества. Примеры применения.
8.	Качество сервиса в компьютерных сетях: модели распределения ресурсов сети и методы борьбы с перегрузками.
9.	Основные подходы математического моделирования компьютерных сетей. Прототипирование компьютерных сетей: преимущества, недостатки, ограничения применимости.
10.	Динамическое планирование задач в ИУС РВ. Схемы планирования Rate Monotonic (фиксированные приоритеты) и Earliest Deadline First (динамические приоритеты). Оценка времени отклика задач для схемы Rate Monotonic.
11.	 Понятие наихудшего времени выполнения программы (WCET). Факторы, влияющие на WCET. Фазы анализа WCET. Использование абстрактной интерпретации для выявления недопустимых путей. Анализ влияния конвейера на время выполнения программы.
12.	 Интегрированная модульная архитектура (ИМА) встроенных систем. Статико-динамическая схема планирования. Понятия жёсткого и мягкого реального времени.
13.	 Коммуникационные протоколы. Ошибки, возникающие при передаче сообщений. Задача надежного обмена сообщениями. Симметричные протокол скользящего (раздвижного) окна: устройство протокола и обоснование его корректности. Протокол альтернирующего бита.
14.	 Временные автоматы как формальные модели распределенных систем реального времени. Темпоральные логики и примеры их применения. Примеры использования временных автоматов для моделирования встроенных систем. Задача верификации моделей программ реального времени. 
15.	 Понятия пространственной и временной сложности алгоритмов. Примеры оценок для классов алгоритмов сортировки и поиска. Классы Р и NP алгоритмов распознавания языков. Проблема соотношения классов  P и NP. Полиномиальная сводимость; NP -полные задачи (формулировка основных фактов, примеры).
16.	Задачи условной оптимизации и их классификация. Задача о рюкзаке: содержательная и математическая формулировка, пример жадного алгоритма оптимального для непрерывной задачи и приближенного для дискретной задачи.
17.	Эвристические алгоритмы условной оптимизации. Алгоритмы имитации отжига, генетические и эволюционные алгоритмы, муравьиные алгоритмы, алгоритмы направленного случайного поиска с самообучением.
18.	Принципы, методы и средства синхронизации и взаимодействия параллельных процессов в информационных системах. Задачи взаимоисключающего доступа: Читатели – Писатели, Поставщик – Потребитель. Синхронизация времени. Логические часы.
19.	Понятие неисправности, ошибки, отказа. Отказоустойчивость в распределенных системах. Типы отказов. Фиксация контрольных точек и восстановление после отказа. Репликация и протоколы голосования. Надежная групповая рассылка.
20.	Коды Боуза-Чоудхури-Хоквингема: определение, алгоритмы кодирования и декодирования.
21.	Вероятностное пространство. Случайные величины и их распределения. свойства. Закон больших чисел. Теорема Пуассона. Центральная предельная теорема. Пуассоновский процесс.
22.	Методы статистической обработки результатов экспериментов. Визуализация данных. Методы точечного оценивания неизвестных параметров. Доверительные интервалы. Проверка статистических гипотез. Критерии согласия Колмогорова и хи-квадрат.
23.	Дискретные цепи Маркова. Метод вложенных цепей Маркова при исследовании систем массового обслуживания.
ЛИТЕРАТУРА
1.	Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М.: МЦНМО. 2000. - 960 с. ISBN 5-900916-37-5.
2.	Столлингс В. Операционные системы. Внутреннее устройство и принципы проектирования. 4 изд. - М.: Изд. дом «Вильяме», 2002. - 843 с. ISBN 5-8459-03 10-6.
3.	Таненбаум Э. Современные операционные системы. - СПб.: Питер, 2002. - 1040 с. ISBN 5-318-00299-4.

4.	Операционные системы: взаимодействие процессов. Вдовикина Н.В., Машечкин И.В., Терехин А.Н., Томилин А.Н. МАКС Пресс Москва, 216 с. Москва 2008 г.

5.	Таненбаум Э., Стеен М. ван. Распределенные системы. Принципы и парадигмы. - СПб.: Питер, 2003. - 887 с. ISBN 5-272-00053-6.
6.	Крюков В. А. Конспект лекций по курсу «Распределённые операционные системы» - http://sp.cs.msu.ru/courses/os/
7.	 Ж. Тель. Введение в распределенные алгоритмы, изд-во МЦНМО, 2009 г., 616 с.
8.	Э.М. Кларк, О. Грамберг, Д. Пелед. Верификация моделей программ: Model Checking. Изд-во МЦНМО, 2002. 417 c.
9.	Ю.Г. Карпов. Model Checking: верификация параллельных и распределенных программных систем. Изд-во БХВ-Петербург, 2010. 
10.	Смелянский Р. Л. Компьютерные сети: в 2 т. т.1 Системы передачи данных. - Издательский центр "Академия" г.Москва, 2011. - С. 304.
11.	Смелянский Р. Л. Компьютерные сети: в 2 т. т.2. Сети ЭВМ. - Издательский центр "Академия" г.Москва, 2011. - С. 240.
12.	Таненбаум Э. Компьютерные сети. 4-е изд. - СПб.: Питер 2003. - 992 с. ISBN 5-318- 00492-Х.
13.	Давыдов Э.Г. Исследование операций. М.: Высшая школа, 1990.
14.	Морозов В.В. Основы теории игр. М.: МГУ, 2002.
15.	Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.
16.	Мину М. Математическое программирование. Теория и алгоритмы. – М.: Наука, 1990. – 488с.
17.	Растригин Л.А. Статистические методы поиска // М.: Наука, 1968. 
18.	Калашников А.В., Костенко В.А. Параллельный алгоритм имитации отжига для построения многопроцессорных расписаний// Известия РАН. Теория и системы управления, 2008., N.3, С.133-142. 
19.	Holland J.N. Adaptation in Natural and Artificial Systems // Ann Arbor, Michigan: Univ. of Michigan Press, 1975. 
20.	Dorigo M. Optimization, Learning and Natural Algorithms // PhD Thesis. Dipartimento di Elettronica. Milano: Politechnico Di Milano, 1992. 
21.	Штовба С.Д. Муравьиные алгоритмы: теория и применение // Программирование. 2005. № 4, С. 1–15.
22.	Гнеденко Б.В. Курс теории вероятностей. - М.: Наука, 1990.
23.	Ивченко Г.И., Медведев Ю.И. Введение в математическую статистику. -- М.: URSS, 2010.