Федеральное государственное бюджетное образовательное учреждение высшего образования

«Московский государственный университет имени М.В.Ломоносова»

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

                                                           «УТВЕРЖДАЮ»
Декан механико-математического факультета,
член- корр. РАН, профессор А.И. Шафаревич
______________________________

«27» мая 2022 г.

ПРОГРАММА ВСТУПИТЕЛЬНОГО ЭКЗАМЕНА
(для осуществления приема на обучение по образовательным программам высшего образования - программам подготовки научных и научно-педагогических кадров в аспирантуре)

1. Естественные науки
1.1. Математика и механика

1.2.2. Математическое моделирование, численные методы 
и комплексы программ
(Физико-математические науки)

Программа утверждена
Приказом по факультету
№ _ от ____________ 2022 г.
/
Ученым советом факультета
(протокол № 4 от мая 2022 г.)

Москва-2022

I.	ОПИСАНИЕ ПРОГРАММЫ

Настоящая программа* по специальности «1.2.2 Математическое моделирование, численные методы и комплексы программ» предназначена для осуществления приема по образовательным программам высшего образования  программам подготовки научных и научно-педагогических кадров в аспирантуре, содержит основные темы и вопросы к вступительному экзамену по специальности, список основной и дополнительной литературы и критерии оценивания.

II. ОСНОВНЫЕ РАЗДЕЛЫ И ВОПРОСЫ К ЭКЗАМЕНУ
Общая часть
1. Непрерывность функций одной переменной, свойства непрерывных функций. 
2. Функции многих переменных, полный дифференциал и его геометрический смысл. Достаточные условия дифференцируемости. Градиент. 
3. Определенный интеграл. Интегрируемость непрерывной функции. Первообразная непрерывной функции. 
4. Неявные функции. Существование, непрерывность и дифференцируемость неявных функций. 
5. Числовые ряды. Сходимость рядов. Критерий сходимости Коши. Достаточные признаки сходимости. 
6. Абсолютная и условная сходимость ряда. Свойство абсолютно сходящихся рядов. Умножение рядов. 
7. Ряды функций. Равномерная сходимость. Признак Вейерштрасса. Свойства равномерно сходящихся рядов (непрерывность суммы, почленное интегрирование и дифференцирование). 
8. Степенные ряды в действительной и комплексной области. Радиус сходимости, свойства степенных рядов (почленное интегрирование, дифференцирование). Разложение элементарных функций. 
9. Несобственные интегралы и их сходимость. Равномерная сходимость интегралов, зависящих от параметра. Свойства равномерно сходящихся интегралов. 
10. Ряды Фурье. Достаточные условия представимости функции рядом Фурье. 
11. Теоремы Остроградского и Стокса. Дивергенция. Вихрь. 
12. Линейные пространства, их подпространства. Базис. Размерность. Теорема о ранге матрицы. Система линейных уравнений. Геометрическая интерпретация системы линейных уравнений. Фундаментальная система решений системы однородных линейных уравнений. Теорема Кронекера - Капелли. 
13. Билинейные и квадратичные функции и формы в линейных пространствах и их матрицы. Приведение к нормальному виду. Закон инерции. 
14. Линейные преобразования линейного пространства, их задания матрицами. Характеристический многочлен линейного преобразования. Собственные векторы и собственные значения, связь последних с характеристическими корнями. 
15. Евклидово пространство. Ортонормированные базисы. Ортогональные матрицы. Симметрические преобразования. Приведение квадратичной формы к главным осям. 
16. Группы, подгруппы, теорема Лагранжа. Порядок элемента. Циклические группы, факторгруппа. Теорема о гомоморфизмах. 
17. Аффинная и метрическая классификация кривых и поверхностей второго порядка. Проективная классификация кривых. 
18. Дифференциальное уравнение первого порядка. Теорема о существовании и единственности решения. 
19. Линейное дифференциальное уравнение второго порядка. Линейное однородное уравнение. Линейная зависимость функций. Фундаментальная система решений. Определитель Вронского. Линейное неоднородное уравнение. 
20. Линейное дифференциальное уравнение n-го порядка с постоянными коэффициентами: однородные и неоднородные задачи. 
21. Функции комплексного переменного. Условия Коши - Римана. Геометрический смысл аргумента и модуля производной. 
22. Элементарные функции комплексного переменного и задаваемые ими конформные отображения. Простейшие многозначные функции. Дробно-линейные преобразования. 
23. Интеграл Коши. Теорема Коши об интеграле по замкнутому контуру. Ряд Тейлора. 
24. Ряд Лорана. Полюс и существенно особая точка. Вычеты. 
25. Криволинейные координаты на поверхности. Первая квадратичная форма поверхности. 
26. Вторая квадратичная форма поверхности Нормальная кривизна линии на поверхности. Теорема Менье. 
27. Главные направления и главные кривизны. Формула Эйлера.

Специальная часть
1. Динамические структуры данных: стек, дек, очередь, последовательность, список, дерево, множество. Непрерывные и ссылочные реализации структур данных.
2. Реализации множеств. Хэширование. Совершенные, минимальные хеш-функции. Различные варианты хэш-реализаций множеств. Эффективность процедур поиска, включения и исключения элементов при различных реализациях.
3. Бинарные деревья.  Процедуры восходящего, нисходящего, горизонтального обхода бинарного дерева. Деревья поиска. Добавление и  удаление  элементов  в дерево поиска. Сбалансированные бинарные деревья. Алгоритмы балансировки дерева. Теорема о глубине сбалансированного дерева.
4. Красно-черные деревья. Сравнение эффективности поиска со сбалансированным деревом. Процедуры добавления и  удаления  элементов. Оценки их эффективности. Теорема о глубине красно-черного дерева.
5. B-деревья. Процедуры добавления и  удаления  элементов. Оценки их эффективности.
6. Контейнеры данных переменного и фиксированного размера. Методы реализации функций динамического выделения памяти.
7. Сортировки  обменом, линейной  вставкой,  выбором,  слиянием (Неймана). Сортировка Шелла. Сортировка с помощью дерева (heapsort). Быстрая сортировка. Теоремы об оценке снизу для трудоемкости сортировок. Теоремы о средней трудоемкости быстрой сортировки. Алгоритм сортировки с линейной оценкой трудоемкости.
8. Алгоритмы сжатия данных: RLE, Хаффмена, LZW, арифметического кодирования. Адаптивные алгоритмы. Теоремы об оптимальности кода Хаффмена. Теоремы о сжатии в методе арифметического кодирования.
9. Формальные грамматики. LR(1) разбор для арифметического выражения. Рекурсивный алгоритм построения дерева разбора арифметического выражения. Компилятор модельного языка программирования: проектирование системы команд стекового процессора, реализация операторов перехода в программе, организация вызовов подпрограмм и функций, передача параметров в функции.
10. Операционные системы (ОС). Определения операционных систем реального времени (ОСРВ). Определения основных объектов ОС. Программа, процессор, процесс. Основные составляющие процесса, состояния процесса. Стек, виртуальная память, механизмы трансляции адреса.
11. Ресурсы, приоритеты. Виды ресурсов: аппаратные, программные, активные, пассивные, локальные, разделяемые, постоянные, временные, не критичные, критичные.
12. Параллельные процессы. Многозадачные ОС. Типы взаимодействия процессов: сотрудничающие и конкурирующие процессы, взаимное исключение процессов. Проблемы, возникающие при синхронизации процессов и идеи их разрешения. Связывание. Статическое и динамическое связывание. Особенности реализации для ОСРВ.
13. Определение потока исполнения (thread). Сравнение с процессами: создание, планирование, управление. Состояния процесса, потока исполнения и механизмы перехода из одного состояния в другое.
14. Типы архитектур операционных систем. Монолитная и модульная архитектура. Общее строение ОС. Роли отдельных компонент: планировщика, диспетчера.
15. Механизмы взаимодействия процессов: разделяемая память. Примитивные операции. Особенности реализации для систем с виртуальной памятью. Особенности реализации для ОСРВ.
16. Механизмы взаимодействия процессов: семафоры. Примитивные операции. Особенности реализации для ОСРВ.
17. Механизмы взаимодействия процессов: сигналы, события, критические секции. Примитивные операции. Особенности реализации для ОСРВ.
18. Механизмы взаимодействия процессов: очереди сообщений (почтовые ящики). Примитивные операции. Особенности реализации для ОСРВ.
19. Синхронизация и взаимодействие потоков исполнения. Объекты типа mutex. Примитивные операции. Виды mutex. Особенности реализации для ОСРВ.
20. Синхронизация и взаимодействие потоков исполнения. Объекты типа condvar. Примитивные операции. Виды condvar. Особенности реализации для ОСРВ.
21. Планирование задач в ОС. Цели планирования в ОСРВ. Требования к планировщику задач в ОСРВ, его роль в ОСРВ.
22. Приоритеты. Схемы назначения приоритетов. Инверсия приоритетов и методы борьбы с ней. Стратегии планирования задач. Типичные схемы планирования в UNIX системах и ОСРВ.
23. Контекст задачи. Переключение контекста. Роль и задачи диспетчера. Прерывания. Процессы обработки прерывания и вызова подпрограмм. Время реакции на прерывание.
24. Файловые системы. Принципы  организации хранения файлов  на диске. Логическая структура диска.  Базовые  функции файловой системы. Принципы организации древовидной файловой системы. Организация файловых систем FAT, ext, NTFS. Процедуры поиска всех блоков файла, поиска свободного места, создания и удаления файла.
25. Внутренняя организация процессоров. Выделение независимо работающих устройств: IU, FPU, MMU, BU. CISC и RISC процессоры. Повышение производительности процессоров за счет конвейеризации. Условия оптимального функционирования конвейера. Суперконвейерные и суперскалярные процессоры. Методы уменьшения негативного влияния инструкций перехода на производительность процессора. Исполнение инструкций не по порядку.
26. Повышение производительности процессоров за счет введения кэш памяти. Кэши: единый, Гарвардский, с прямой записью, с обратной записью. Организация кэш-памяти. Алгоритмы замены данных в кэш памяти. Специальные кэши. Согласование кэшей в мультипроцессорных системах с общей памятью. Методы уменьшения времени реакции на прерывание.
27. Архитектуры системных шин. Синхронные и асинхронные шины. Мультиплексирование шины. Отображение ресурсов на память и пространство ввода-вывода. Мосты между шинами. Архитектуры шин PCI, VME, CompactPCI.
28. Виды многопроцессорных архитектур. Системы с общей и распределенной памятью. Поддержка многозадачности и многопроцессорности специальными инструкциями процессора. Организация данных во внешней памяти. Механизмы преобразования данных при обменах.
29. Программирование систем с распределенной памятью. Message Passing Interface (MPI). Общая структура MPI-программы. Сообщения и их виды. Группы и коммуникаторы. Попарный обмен сообщениями. Операции ввода-вывода в MPI программах. Примеры.
30. Коллективный обмен сообщениями. Учет архитектуры параллельной ЭВМ. Ограничение коллективного обмена на подмножество процессов. Время в MPI программах.
31. Пересылка структур данных. Создание нового MPI типа данных. Упаковка/распаковка разнородных данных. Пересылка структур данных в однородных параллельных ЭВМ. Пересылки строк и столбцов матриц.
32. Объектно-ориентированный подход в программировании. Объекты, их информационная структура, отношения между объектами. Инкапсуляция, сокрытие информации. Абстрактные типы данных. Их преимущества. Классы и представители. Полиморфизм.
33. Объектно-ориентированный подход в программировании. Наследование. Переопределение информационных и/или поведенческих структур при наследовании. Цели использования наследования. Классический и объектно-ориентированный подходы к построению программ.
34. Понятие о сетях с коммутацией каналов и пакетов. Достоинства и недостатки каждого из подходов. Базовые топологии локальных сетей: линия, кольцо, звезда. Структурные элементы локальных и глобальных сетей. Повторитель, разветвитель, мост, шлюз.
35. Логика функционирования сетей Ethernet. Адресация. Дисциплина передачи данных. Разрешение коллизий.
36. Иерархия сетевых протоколов в модели TCP/IP (Internet) IP адресация. Классы адресов. Широковещательные и другие специальные адреса. Маска подсети. Протоколы  ARP, RARP, ICMP, назначение, принципы работы.
37. Протокол IP, назначение, принципы работы. Функции IP протокола, фрагментация и сборка. Уничтожение пакетов. Маршрутизация. 
38. Протокол UDP, назначение, принципы работы. Адресация транспортного уровня. Контроль правильности передачи. Протокол TCP, назначение, принципы работы. Обеспечение надежности передачи. Сегментация данных при отправлении и сборка при получении. Процедуры установления и разрыва соединения. Механизм подтверждений. Таймеры.
39. Протокол и система DNS, назначение, принципы работы. Структура доменных имен. Классификация DNS серверов. Формат запроса и ответа. Ресурсная запись. Итеративная, рекурсивная и смешанная процедуры. Поддержка распределенной базы данных DNS.
40. Протокол FTP, назначение, принципы работы. Вид запроса и отклика. Процесс передачи файлов. Классификация кодов откликов. 
41. Протокол HTTP, назначение, принципы работы. Формат запроса и отклика. Процесс передачи файлов. Структура и назначение строк-заголовков (header-lines). Виды соединений. Отличие HTTP/1.0 и HTTP/1.1. Классификация кодов откликов.
42. Socket-интерфейс. Основные функции и их назначение. Последовательность действий программы - клиента и программы - сервера.

От сдающих государственный экзамен требуется знание основных этапов развития математики в России и за рубежом.

III. РЕФЕРАТ ПО ИЗБРАННОМУ НАПРАВЛЕНИЮ ПОДГОТОВКИ

Реферат по избранному направлению подготовки представляет собой обзор литературы по теме будущего научного исследования и позволяет понять основные задачи и перспективы развития темы будущей диссертационной работы. Реферат включает титульный лист, содержательную часть, выводы и список литературных источников. Объем реферата 10-15 страниц машинописного текста. В отзыве к реферату предполагаемый научный руководитель дает характеристику работы и рекомендуемую оценку, входящую в общий экзаменационный балл.

IV. ПРИМЕР ЭКЗАМЕНАЦИОННОГО БИЛЕТА

Вопрос 1. Ряды Фурье. Достаточные условия представимости функции рядом Фурье.
Вопрос 2. Определение потока исполнения (thread). Сравнение с процессами: создание, планирование, управление. Состояния процесса, потока исполнения и механизмы перехода из одного состояния в другое.
Вопрос 3. Содержание реферата по теме диссертационного исследования (с приложением реферата и отзыва на реферат с отметкой предполагаемого научного руководителя).

V. РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

ОСНОВНАЯ:
1. Кострикин А.И. Введение в алгебру, ч. I,II,III Основы алгебры.
2. Курош А.Г. Курс высшей алгебры.
3. Александров П.С. Курс по аналитической геометрии и линейной алгебре.
4. Гельфанд И.И. Лекции по линейной алгебре.
5. Шилов Г.Е. Введение в теорию линейныхпростанств.
6. Кудрявцев Л.Д. Математический анализ.
7. Фихтенгольц Г.И. Основы математического анализа, тт. 1,2,3.
8. Рудин У.Л. Основы математического анализа.
9. Никольский С.М. Математический анализ.
10. Степанов В.В. Курс дифференциальных уравнений.
11. Петровский И.Г. Лекции по обыкновенным дифференциальным уравнениям.
12. Понтрягин Л.С. Обыкновенные дифференциальные уравнения.
13. Арнольд В.И. Обыкновенные дифференциальные уравнения.
14. Привалов Н.Н. Введение в теорию функции комплексных переменных.
15. Маркушевич А.И. Теория аналитических функций.
16. Шабат Б.В. Введение в комплексный анализ.
17. Рашевский П.К.Дифференциальная геометрия.
18. Дубровин Б.А., Новиков С.П., Фоменко А.Т.Современная геометрия.
19.Гнеденко Б.В. Очерк по истории математики в России и СССР.
20. Рыбников К.А. История математики.
ДОПОЛНИТЕЛЬНАЯ:
1. Валединский В.Д., Пронкин Ю.Н. Вычислительные системы и программирование. Системы хранения данных. М.: Изд-во ЦПИ при механико-математическом ф-те МГУ им. М.В.Ломоносова, 2006.
2. Валединский В.Д., Пронкин Ю.Н. Вычислительные системы и программирование. Организация вычислительных систем.: Изд-во ЦПИ при механико-математическом ф-те МГУ им. М.В.Ломоносова, 2006.
3. Богачев К.Ю. Операционные системы реального времени. М.: Изд-во ЦПИ при механико-математическом ф-те МГУ им. М.В.Ломоносова, 2001.
4. Богачев К.Ю. Основы параллельных вычислений. Том 1. М.: Изд-во ЦПИ при механико-математическом ф-те МГУ им. М.В.Ломоносова, 2002, 152 с.
5. Богачев К.Ю. Основы параллельных вычислений. Том 2. М.: Изд-во ЦПИ при механико-математическом ф-те МГУ им. М.В.Ломоносова, 2002, 176 с.

VI. КРИТЕРИИ ОЦЕНИВАНИЯ

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

*Все темы и вопросы должны быть не выше ФГОС ВО магистратуры и специалитета.

VII. АВТОРЫ

профессор, д.ф.м.н. Кобельков Г.М. 
профессор, д.ф.м.н. Богачев К.Ю.
доцент, к.ф.м.н. Попов А.В.