МИНОБРНАУКИ РОССИИ
федеральное государственное бюджетное образовательное учреждение высшего образования
«Омский государственный университет им. »
«Утверждаю»
Проректор по научной работе
_______________
«_____» _____________ 2017 г.
Программа вступительного испытания
в аспирантуру по направлению
09.06.01 Информатика и вычислительная техника
Дисциплина по профилю подготовки:
Математическое моделирование, численные методы и
комплексы программ (в т. ч. методы оптимизации)
Омск
2017
1. Вступительное испытание (экзамен) проводится специально утверждённой для данного вида вступительных испытаний предметной комиссией.
2. Каждому из поступающих проводящая экзамен предметная комиссия предлагает два вопроса по своему выбору.
3. На подготовку ответов испытуемым предоставляется 45 минут.
4. Конспект ответов испытуемые излагают на стандартном бланке листа устного ответа, предоставленном приёмной комиссией, после чего излагают свои ответы членам предметной комиссии, которые фиксируют своё мнение по каждому ответу на том же бланке в произвольном виде.
5. Члены комиссии имеют право задавать испытуемым дополнительные (уточняющие) вопросы.
6. По каждому из вопросов испытуемый может получить до 50 баллов и до 100 баллов включительно в сумме. Эта сумма является оценкой за собеседование.
7. Решения принимаются предметной комиссией коллегиально и закрепляются подписями членов комиссии в листе устного ответа.
ПРОГРАММА
вступительного экзамена в аспирантуру по специальности
05.13.18 - Математическое моделирование, численные методы и комплексы программ
(в том числе методы оптимизации)
1. Математический анализ
Предел последовательности. Критерий Коши. Существование предела монотонно возрастающей, ограниченной сверху последовательности. Теорема Больцано-Вейерштрасса. Числовые ряды. Критерий Коши сходимости числовых рядов. Признаки сходимости числовых рядов (признаки сравнения, признаки Даламбера и Коши, признак Лейбница, признак Абеля-Дирихле). Предел функции. Непрерывные функции. Свойства функций, непрерывных на отрезке (теорема Вейерштрасса об ограниченности и достижении точных верхней и нижней граней, теорема Коши о промежуточных значениях). Существование пределов у монотонных функций. Теорема о непрерывности функции, обратной к монотонной. Равномерная непрерывность функций. Теорема Кантора. Обобщения теорем Вейерштрасса и Кантора на многомерный случай. Дифференцируемые функции одной и нескольких переменных. Производные и дифференциал. Формула Тейлора для функций одной и нескольких переменных. Ряды Тейлора. Элементарные функции. Теорема о неявных функциях (без док-ва). Экстремумы функций одной и нескольких переменных. Необходимые условия экстремума. Достаточные условия экстремума. Интеграл Римана. Необходимые и достаточные условия интегрируемости функции по Риману. Интегрируемость монотонной и непрерывной функций. Теорема о среднем. Формула Ньютона-Лейбница. Несобственные интегралы. Признаки сходимости несобственных интегралов. Признак Абеля-Дирихле. Понятие кратного интеграла по Риману. Сведение кратного интеграла к повторному. Замена переменных в кратных интегралах. Функциональные последовательности и ряды. Равномерная сходимость. Критерий Коши равномерной сходимости. Признак Вейерштрасса. Непрерывность предела равномерно сходящейся последовательности функций. Теоремы о почленном интегрировании и дифференцировании функциональных рядов.2. Функциональный анализ
2.1. Конечномерные вещественные пространства. Характеризация открытых, замкнутых, компактных множеств.
2.2. Измеримые функции. Основные теоремы о сходимости последовательностей измеримых функций (теоремы Егорова).
Интеграл Лебега. Основные свойства интеграла Лебега. Нормированные пространства. Полнота, сепарабельность, критерий компактности, сильная и слабая сходимость. Гильбертовы пространства. Теорема Рисса-Фишера. Ряды и интеграл Фурье. Элементы теории линейных операторов. Теорема Банаха об обратном операторе. Теорема Хана-Банаха. Теоремы Фредгольма для вполне непрерывных операторов. Линейные функционалы. Теорема Банаха-Штейнгауза. Теорема Рисса о представлении. Теоремы о неподвижной точке. Принцип Банаха. Принцип Шаудера.3. Алгебра
3.1. Понятие линейного пространства. Определение линейной зависимости и независимости векторов. Размерность линейного пространства, базис, координаты вектора, формулы преобразования координат при переходе от одного базиса к другому.
3.2. Матрицы и действия над ними. Определитель квадратной матрицы. Ранг матрицы и способы его вычисления.
3.3. Системы n линейных уравнений с m неизвестными. Решение однородной системы. Решение неоднородной системы. Теорема Кронекера-Капелли.
3.4. Линейные преобразования в n мерном пространстве. Матрица линейного преобразования и ее смысл. Изменение матрицы линейного преобразования при замене базиса. Область значений линейного преобразования. Обратное преобразование и его матрица. Произведение линейных преобразований.
3.5. Собственные векторы и собственные числа линейного преобразования. Характеристический многочлен. Линейная независимость собственных векторов, отвечающих различным собственным значениям. Матрица линейного преобразования в базисе из собственных векторов. Понятие жордановой формы матрицы.
3.6. Скалярное произведение и евклидовы пространства. Координатное представление скалярного произведения. Ортонормированный базис. Процесс ортогонализации.
3.7. Ортогональные преобразования. Матрица ортогонального преобразования. Ортогональные матрицы. Переход от одного ортонормированного базиса к другому.
3.8. Билинейные и квадратичные формы. Приведение квадратичной формы к каноническому виду в ортонормированном базисе. Закон инерции для квадратичных форм. Понятие положительно определенной квадратичной формы. Критерий Сильвестра (без доказательства).
4. Обыкновенные дифференциальные уравнения
4.1 Методы интегрирования уравнений первого порядка (уравнения с разделяющимися переменными, однородные уравнения, линейные уравнения, уравнения в полных дифференциалах, уравнения Бернулли и Рикатти). Уравнения более высоких порядков, методы понижения порядка.
4.2. Теорема существования и единственности решения задачи Коши для уравнения первого порядка и системы n уравнений в нормальной форме. Теорема существования и единственности для системы линейных уравнений первого порядка, структура общего решения, случай простых и кратных (без доказательства) собственных чисел.
4.3. Линейные уравнения n-го порядка с переменными коэффициентами. Фундаментальная система решений однородного уравнения и ее существование. Определитель Вронского. Формула Лиувилля. Решение однородного и неоднородного уравнения. Метод вариации произвольных постоянных.
4.4. Задача Штурма-Лиувилля. Функция Грина краевой задачи для обыкновенного дифференциального уравнения. Сведение задачи Штурма-Лиувилля к интегральному уравнению.
4.5. Автономные системы. Положение равновесия. Фазовая плоскость и фазовые траектории. Классификация положений равновесия на плоскости. Понятие устойчивости положения равновесия по Ляпунову и асимптотической устойчивости. Теорема об устойчивости по первому приближению. Функции Ляпунова и их применение.
4.6. Первые интегралы автономной системы. Линейные однородные уравнения в частных производных первого порядка. Общий вид решения. Задача Коши. Понятие характеристики.
5. Уравнения математической физики
Линейные дифференциальные уравнения в частных производных второго порядка. Приведение к каноническому виду в точке. Классификация уравнений. Понятие корректной начально-краевой задачи для уравнений в частных производных. Пример Адамара. Постановки начально-краевых задач для уравнений гиперболического, параболического и эллиптического типов. Задача Коши для волнового уравнения. Формула Даламбера в случае уравнения колебания струны. Непрерывная зависимость решений от начальных данных. Негладкие начальные данные, обобщенное решение. Задача Гурса, существование и единственность решения. Смешанная задача для уравнения колебания струны. Метод Фурье. Достаточные условия сходимости рядов (существование решения). Задача Коши для уравнения теплопроводности. Фундаментальное решение и его смысл. Существование и единственность решения. Смешанная задача для уравнения теплопроводности. Метод Фурье. Достаточные условия сходимости рядов (существование решения). Принцип максимума для уравнений параболического типа. Уравнение Лапласа. Гармонические функции и их свойства. Теорема об интегральном представлении функций. Теорема о среднем для гармонических функций. Принцип максимума и минимума для гармонических функций. Задачи Дирихле и Неймана для уравнения Лапласа. Решение задачи Дирихле в круге и вне круга методом Фурье. Единственность решений задач Дирихле и Неймана.6. Численные методы
Погрешности результатов численного решения задач, классификация и методы оценки. Задача интерполяции многочленами, минимизация оценки остаточного члена. Задача наилучшего приближения. Интерполяция сплайнами. Квадратурные формулы Ньютона-Котеса и наивысшей алгебраической степени точности, оценка остаточного члена. Составные формулы и их оптимизация, апостериорные методы оценки погрешности. Прямые и итерационные методы решения систем линейных алгебраических уравнений и их сравнительная характеристика. Оценка погрешностей. Методы решения проблемы собственных значений. Решение систем нелинейных алгебраических уравнений и задач нелинейной оптимизации. Аппроксимация, устойчивость, сходимость. Одношаговые и многошаговые методы решения задачи Коши для обыкновенных дифференциальных уравнений. Численные методы решения краевой задачи для уравнения второго порядка.7. Математическое моделирование
7.1. Основные принципы моделирования. Универсальность математических моделей. Методы построения математических моделей.
7.2. Этапы построения математической модели. Основные типы математических моделей.
7.3. Методы исследования математических моделей. Устойчивость. Проверка адекватности модели.
7.4. Математические модели в научных исследованиях. Математические модели в экономике, биологии.
7.5. Математические модели физических задач, приводящие к уравнениям математической физики.
8. Методы оптимизации
8.1. Линейное программирование. Симплекс-метод. Теоремы двойственности.
8.2. Выпуклое программирование. Теорема Куна-Таккера. Метод возможных направлений.
8.3. Целочисленное программирование. Метод ветвей и границ. Задача коммивояжера.
8.4. Динамическое программирование. Уравнения Беллмана. Задача о рюкзаке.
8.5. Комбинаторные оптимизационные задачи на графах и сетях. Задачи о кратчайшей связывающей сети, о кратчайшем пути, о максимальном потоке и минимальном разрезе. Алгоритмы Прима, Дейкстры, Эдмондса-Карпа, их трудоемкость и обоснование.
8.6. Элементы теории сложности вычислений. Классы P и NP. Полиномиальная сводимость задач распознавания. Теорема Кука (без доказательства). Примеры NP–полных задач распознавания. Сводимость по Тьюрингу. Примеры NP-трудных оптимизационных задач.
ЛИТЕРАТУРА
Фихтенгольц дифференциального и интегрального исчисления. Т.1 – 3. М.: Наука, 1970. , Основы математического анализа. Т.1, 2. М.: Наука, 1982. Зорич В. А. Математический анализ. М.: Наука, 1984. , Фомин теории функций и функционального анализа. М.: Наука, 1976. Курош высшей алгебры. М.: Наука, 1975. Мальцев линейной алгебры. М.: Наука, 1975. ведение в теорию матриц. М.: Наука, 1976. Понтрягин дифференциальные уравнения. М.: Наука, 1974. Барбашин в теорию устойчивости. М.: Наука, 1971. Демидович по математической теории устойчивости. М.: Наука, 1967. Бицадзе теории аналитических функций. М.: Наука, 1984. , Самарский математической физики. М.: Наука, 1977. , Жаринов математической физики. М.: Физматлит, 2000. Краснов уравнения. М.: Наука, 1975. , , Кобельков методы: Учеб. пособие. М.: Наука, 1987. Калиткин методы. М.: Наука, 1978. , Гулин методы. М.: Наука. 1989. , Михайлов моделирование. М.: Физматлит, 1997. Математическое моделирование / Под ред. , и др. М.:Изд-во МГУ, 1993. Лебедев математического моделирования социально-экономических процессов. М.: ИЗОГРАФ, 1997. еория графов. Алгоритмический подход. М.: Мир, 1978. ычислительные машины и труднорешаемые задачи. М.: Мир, 1982. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974. Карманов программирование. М.: Наука, 1980. , Финкельштейн программирование. М.: Наука, 1969.
Программу подготовил д. ф.-м. н.
