ПРОГРАММА

экзамена кандидатского минимума по специальности 05.13,18 "Математическое моделирование, численные методы и комплексы программ» (физико-математические науки).

* ФУНКЦИОНАЛЬНЫЙ АНАЛИЗ

1. Метрические, нормированные, гильбертовы пространства,

2. Линейные функционалы и операторы.

Обыкновенные дифференциальные уравнения и дифференциальные уравнения в частных производных первого порядка.

* ФУНКЦИОНАЛЬНЫЙ АНАЛИЗ

1. Метрические, нормированные, гильбертовы пространства,

Метрические пространства. Полнота. Непрерывные отображения, Компактные множества. Принцип сжимающих отображений, метод последовательных приближений и их приложения. Линейные, нормированные, банаховы и гильбертовы пространства. Сильная и слабая сходимость. Задача о наилучшем приближении. Наилучшее равномерное приближение. Минимальное свойство коэффициентов Фурье ([1], гл. I, V , VII; [2], гл. III - VI; [3] гл. II; [4], гл.IV).

2. Линейные функционалы и операторы.

Непрерывные  линейные  операторы.  Норма и спектральный  радиус  оператора.

Сходимость операторов. Обратимость. Ряд Неймана Σ А^k и условия его сходимости. Теоремы о существовании обратного оператора. Мера обусловленности линейного оператора и ее применение при замене точного уравнения (решения) приближенным. Линейные функционалы. Сопряженное пространство. Принцип равномерной ограниченности, теорема Баиаха-Штейнгауза и ее приложения. Теорема Рисса (для гильбертова пространства). Спектр оператора. Сопряженные, самосопряженные, симметричные, положительно определенные, вполне непрерывные операторы и их спектральные свойства. Вариационные методы минимизации квадратичных функционалов, решения уравнений и нахождения собственных значений (методы Ритца, Бубнова-Галеркнна, наименьших квадратов). Дифференцирование нелинейных операторов, производные Фреше и Гато. Метод Ньютона, его сходимость и применение. Теоремы Фредгольма для уравнений с вполне непрерывным оператором. Теорема Гильберта-Шмидта.

([1], гл. III - VII; [2], гл. VIII - XII; [3], гл. II: [4], гл. VI, VII; [5]. гл. I, IV; [б], гл. II; [7] гл. XII).

Обыкновенные дифференциальные уравнения и дифференциальные уравнения в частных производных первого порядка.

Теорема существования и единственности решения задачи Кощи для линейных и нелинейных систем первого порядка. Линейные уравнения и системы с постоянными коэффициентами. Лцрейные уравнения и системы с переменными коэффициентами. Многообразие решений. Формула Лиувилля -Остроградcкого.; Теоремы о непрерывной зависимости решения от начальных условий и от параметров. Гладкость решения по начальным данным и параметрам. Автономные системы. Классификация особых точек. Устойчивость по Ляпунову. Теорема Ляпунова об устойчивости по первому приближению. Предельные циклы. Дифференциальные уравнения в частных производных первого порядка ([8], §3,7,8.10,12,14 - 18,21,23,24,26,28; [9], часть II, гл. I, §1)

ЧИСЛЕННЫЕ МЕТОДЫ

1. Численные методы алгебры

Прямые и итерационные методы решения систем линейных уравнений, с полными матрицами и матрицами специального вида. Одношаговые итерационные методы. Чебышевские одношаговые итерационные методы. Оптимальный набор чебышевских параметров и вычислительная устойчивость. Трехчленные (двушаговые) чебышевские итерационные методы. Методы сопряженных градиентов решения линейных систем и спектральных задач. Применение методов регуляризации, минимизации сглаживающего функционала и итерационных методов для решения вырожденных, несовместных и плохо обусловленных систем линейных алгебраических уравнений и интегральных уравнений 1-го рода ([I], гл. V: [4], гл. VI; [6], гл. IV, VII; [7], гл. XI; [10], гл. X; [11], гл. II, VI, VII, IX).

2. Приближение функций

Общие свойства ортогональных систем многочленов. Многочлены Лежандра и Чебышева; их свойства и приложения. Быстрое дискретное преобразование Фурье и его применение в теории приближений и методах решения задач математической физики, интерполяция сплайнами. Методы спуска для экстремума функционалов ([1], гл. VII; [4], гл. II, IV, VII: [5], гл. V; [6], гл. I -IV; [10], гл. X).

Дискретная математика 

1. Графы

1. Способы задания графов. Необходимое и достаточное условие существования Эйлерова цикла. Гамильтоновы циклы и цепи. Теорема Оре. Теорема о характеризации деревьев.

2.     Задача поиска минимального остовного дерева, алгоритмы Краскала и Прима. Задача о кратчайшем пути. Алгоритм Дейкстры.

3.     Потоки в сетях. Теорема Форда - Фалкерсона. Метод расстановки пометок.

4..  Дизъюнктивные  нормальные  формы  (ДНФ).   Машина  Тьюринга.   Элементы теории сложности. Классы Р и NP. ([12], [13], [14], [15], [16], [17])

** Математическое программирование и теория игр

1. Линейное программирование (ЛП).

1. Общая, стандартная и каноническая задачи ЛП. Теорема эквивалентности. Теорема о выпуклости допустимого множества.

2.     Специальная задача ЛП. Симплекс-метод. Критерий остановки симплекс-метода. Конечность симплекс-метода. Метод искусственного базиса для канонической задачи ЛП.

4. Транспортная задача, метод потенциалов. ([13], [14], [18])

2.  Выпуклое программирование.

Критерий оптимальности задачи ВП. Совпадение локального и глобального минимума в задаче ВП. Критерий оптимальности задачи ВП. Метод возможных направлений. Теорема Куна-Таккера. ([19])

3.  Динамическое программирование.

Динамические процессы, уравнение Беллмана. Сетевая модель планирования и управления. Алгоритмы Форда. Раннее и позднее расписание. ([14])

4.  Теория игр.

Определение игры. Антагонистические игры. Теорема о минимаксе для матричных игр. Нахождение минимальных смешанных стратегий. Игра N лиц в форме характеристической функции. ([20])

5.  Многокритериальные задачи, оптимальность по Парето. Свертки критериев

6. Дискретное программирование.

1. Задачи   целочисленного   программирования   (ЦП),   булево   программирование.   Примеры задач ЦП (задачи о покрытии, размещении, о рюкзаке, задача коммивояжера). Метод отсечения (двойственные дробные алгоритмы отсечения, отсечения Данцига, Гомори). Метод ветвей и границ (алгоритм Литота и др., схема Лэнд и Дойг). Метод регулярных разбиений в ЦП. ([14], [15]. [21]).

Математическое моделирование. Техническое и программное обеспечение

научных исследований

1.      Основные виды научных исследований. Значение математики и вычислительной техники в научных исследованиях.

2.      Основные этапы моделирования. Предварительное исследование моделируемого объекта. Постановка задач и определение типа модели. Требования к модели. Построение математической, алгоритмической и программной модели исследуемой системы. ([22], [23], [24])

3.      Базы данных.

 1. Основные определения и требования к базам данных. Три уровня описания и представления данных в базах данных. Реализация принципа независимости данных. Три классических модели описания данных. Их достоинства и недостатки.

2.      Нормализация отношений - основа проектирования структуры базы данных. Требования к третьей нормальной форме.

3.      Физическая организация баз данных. Классификация методов доступа. Методы доступа: В - дерево и инвертированные файлы. ([25], [26], [27])

4.    Прикладное программное обеспечение научных исследований. Формы
представления комплексов прикладных программ (ППП), диалоговая система, примеры
библиотек и ППП общематематического назначения. Архитектура ППП и процесс
обработки входного задания. Архитектура диалоговой системы. Способы организации диалогового процесса исследований. Достоинства и недостатки использования проблемно-ориентированных языков моделирования. Факторы, влияющие на выбор языка. Пакеты и системы дискретного, непрерывного и дискретно-непрерывного моделирования. ([28]).

Планирование экспреримента, математические методы статистики, анализ данных.

1.                                     Цели и методы планирования экспериментов. Математическая теория эксперимента: формулировка проблемы, классификация методов. Планирование регрессионных экспериментов, критерии оптимальности регрессионных планов. Планы 1-го и II-го порядков. Последовательные методы планирования эксперимента. Планирование эксперимента при поиске оптимальных условий. Задачи и планирование эксперимента при исследовании динамических объектов. ([29] - [33])

2.                                     Основные характеристики и особенности массивов информации в научных исследованиях. Размерность, качественные количественные признаки, способы представления, механизмы и модели порождения данных, общая схема и основные этапы анализа данных. ([34])

3.                                     Задача статистического оценивания параметров. Свойства статистических оценок. Методы статистического оценивания. Использование априорной информации (байесовский подход). ([35], [36])

4.                                     Статистическая проверка гипотез. Основные типы гипотез, проверяемых в ходе статистической обработки данных. Общая схема статистического критерия. Построение статистического критерия, принципы отношения правдоподобия. Характеристики качества статистического критерия. Последовательная схема принятия решения. ([35], [36])

5.                                     Методы структуризации данных. Задача классификации, механизмы порождения классификаций. Задача классификации объектов с "учителем", различные модели распознавания образов. Задача автоматической классификации (кластер -анализ), вариационный и статистический подходы, основные типы алгоритмов, проблема выбора числа классов. ([34], [37])

6.                                     Методы структуризации параметров модели и методы факторного анализа, алгоритмы экстремальной группировки, выбор числа групп, нелинейные модели, особенности методов структурирования качественных признаков. ([34]).

7.                                     Методы отображения и визуализации многомерных данных, методы и модели многомерного шкалирования, особенности использования алгоритмов для различных типов данных, связь методов многомерного шкалирования и методов классификации. ([34]).

8.           Методы  аппроксимации        сложных        зависимостей, построение прогностических и нормативных моделей. Регрессионные линейные и нелинейные модели. Методы кусочной аппроксимации зависимостей. Структурные регрессионные уравнения. Методы структурной минимизации эмпирического риска в задаче аппроксимации зависимостей. ([30], [34] ,[35], [36]).

Литература

1. Треногий В.А. Функциональный анализ. М: Наука, 1980.

2.      Вулих Б.З. Введение в функциональный анализ. М.: Физматгиз, 1958.

3.   Михайлов  В.П.  Дифференциальные уравнения в частных  производных.  М.:
Наука, 1976.

4.      Бахвалов Н.С. Численные методы, М.: Наука, 1973.

5.      Владимиров B.C. Уравнения математической физики. М.: Наука, 1961.

6.      Марчук Г.И. Методы вычислительной математики. М.: Наука, 1980.

7.      Годунов С.К., Рябенький B.C. Разностные схемы. М.: Наука, 1977.

8.      Понтрягин Л.С. Обыкновенные дифференциальные уравнения. М: Наука, 1974.

9.      Смирнов В.И. Курс высшей математики. t.IV, части I и II. М.: Наука, 1981.

10.     Самарский А.А. Теория разностных схем. М.: Наука, 1977.

11.     Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. М.: Физматгиз, 1960.

12.     Харари Ф. Теория графов. - М. Мир, 1973.

13.     Ху.Т. Целочисленное программирование и потоки в сетях. М.:Мир, 1974.

14.  Пападимитриу X., Стайглиц К. Комбинаторная Оптимизация. Алгоритмы и
сложность. М.: Мир, 1985.

15.       М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

16.       Липский. В. Комбинаторика для программистов. М.: Мир, 1987.

17.       Оре О. Теория графов. М.:Наука, 1980.

18.       Юдин Д.Б., Голынтейн Е.Г. Задачи и методы линейного программирования. М.: Советское радио, 1961.

19.       Карманов В. Г. Математическое программирование. М.: Наука, 1980.

20.       Оуэн. Г. Теория игр. М.: Мир, 1971.

21.       Колоколов А.А. Методы дискретной оптимизации. Омск, 1984.

22.       Кузмичев      Д. А.,      Радкевич      И. А.,      Смирнов      А. Д.      Автоматизация
экспериментальных исследований. Учебное пособие для вузов. М.:Наука,1983.

23.  Быков  В.В.  Цифровое моделирование в  статистической радиотехнике.  М.: Советское радио. 1971.

24.  Шеннон Р. Имитационное моделирование систем - искусство и наука. М.: Мир, 1978.

25.       Мартин Дж. Организация баз данных в вычислительных системах. М.: Мир, 1980.

26.       Тиори Т., Фрай Дж. Проектирование структур баз данных. Т.2. М.:Мир, 1985.

27.       Ульман Дж. Основы систем баз данных. М.:Финансы и статистика, 1983.

28.       Шураков В.В., Алферова Э.В., Лихачева Р.Н. Программное обеспечение ЭВМ. Учебное пособие для вузов. М.:Статистика, 1979.