01.01.09 – дискретная математика и математическая кибернетика

Приказ Высшей аттестационной комиссии Республики Беларусь от 23 августа 2007 г. № 138
 

Цель и задачи программы-минимум - определить базовый уровень подготовки аспирантов и соискателей, необходимый для проведения научных исследований, отвечающих современным требованиям, в разделах математики, соответствующих специальности «Дискретная математика и математическая кибернетика».

Для достижения данной цели аспиранты и соискатели должны:

  • освоить теоретические положения и методы дискретной математики и математической кибернетики, предусмотренные настоящей программой;
  • овладеть базовыми алгоритмами решения основных задач дискретной математики и математической кибернетики и иметь навыки их практического использования.

В соответствии с паспортом специальности 01.01.09 «Дискретная математика и математическая кибернетика» в программе кандидатского экзамена отражены такие важные направления, как:

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

I. ДИСКРЕТНАЯ МАТЕМАТИКА

Булевы функции. Проблема полноты. Теорема о полноте в Р2Функции k-значной логики. Теорема Кузнецова ([20], гл. I, 2).

ДНФ. Упрощение ДНФ. Геометрическая интерпретация. ДНФ типа ZT. Теорема Журавлёва ([20], ч. V, гл. 1).

Синтез схем из функциональных элементов. Нижняя оценка для функции Цп). Метод Шеннона. Метод Лупанова ([20], ч. V, гл. 2).

Кодирование. Алфавитное кодирование, критерий однозначности декодирования. Коды с минимальной избыточностью. Самокорректирующиеся коды. Коды Хэмминга ([20], гл. 4).

Принцип включения и исключения. Производящие функции и рекуррентные соотношения. Разбиения чисел и множеств. Матроиды и трансверсали. Теорема Холла и теорема Радо ([19], гл. 1-4; [9], гл. 3; [11], гл. 4).

Графы. Матричная теорема Кирхгофа. Оценки числа вершинной независимости. Паросочетания. Хроматическое число и хроматический индекс графа. Критерии планарности. Эйлеровы графы. Достаточные условия гамильтоновости графа ([9], гл. 2, 4, 6, 7, 9).

Автоматы. Регулярные языки и допускающие их автоматы ([2], гл. 9).

Вычислимые функции. Эквивалентность класса рекурсивных функций и функций, вычислимых на машинах Тьюринга ([12], §§ 1, 2, 3.1-3.4, 12.1-12.3).

Комбинаторные алгоритмы. Модели вычислений и сложность алгоритма. Алгоритмы сортировки. Поиск в графе. Кратчайшие пути. Минимальные остовные деревья. Наибольшие паросочетания. Алгоритм расстановки пометок для построения максимального потока. Классы Р и NP. Полиномиальная сводимость и JVP-полные задачи. Сильная NP -полнота ([2], гл.1, [8], гл. 1-4; [9], гл. 12; [11], гл. 2, 3,4).

II. ТЕОРИЯ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ

Основные понятия теории экстремальных задач. Глобальный и локальный минимум вещественнозначной функции. Задачи минимизации вещественнозначных функций без ограничений. Необходимые условия локального минимума первого и второго порядка. Достаточные условия строгого локального минимума. ([1], §3.1.1; [7], введение, § 2.1).

Задачи минимизации вещественнозначных функций с нефункциональными ограничениями. Необходимые условия локального минимума первого порядка. Достаточные условия строгого локального минимума ([6], гл. 3, § 5).

Задача нелинейного программирования. Необходимые условия Зойтендейка и условие Каруша-Джона. Достаточные условия оптимальности первого порядка в задаче нелинейного программирования. Условия оптимальности второго порядка. [18], гл. 4,§1;[7],§3;[6],гл. 3, §§ 1-4).

Задача выпуклого программирования. Условия оптимальности (необходимые и/или достаточные) для решений задачи выпуклого программирования. Условия регулярности Слейтера. Теорема Куна-Таккера. Двойственная задача выпуклого программирования. ([16], гл. 3, § 1; [18], гл. 4, §§ 2, 3; [7], § 2.3; [6], гл. 2).

Задача линейного программирования. Критерий оптимальности решений в задаче линейного программирования. Двойственная задача линейного программирования. Теоремы двойственности. Симплекс-метод. Метод эллипсоидов. ([15], гл. 2, 3, 8; [5], гл. 3; [18], гл. 4,§1;[7],§3;[6],гл. 1).

Целочисленное линейное программирование. Вполне унимодулярность. Алгоритм Гомори. Метод "ветвей и границ" ([15], гл. 13, 14, 18).

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

Динамическое программирование ([6], гл. 5).

Теория игр. Игры двух лиц. Матричные игры. Чистые и смешанные стратегии. Теорема о минимаксе для матричных игр. Некооперативные и кооперативные игры и-лиц. ([1], [13], гл. 7, 12, 13; [14]).

Элементы математической экономики. Модель Леонтьева. Модель Неймана-Гейла. Теория экономического равновесия. Отношения предпочтения и функции полезности. Неоклассическая теория спроса. Модель Вальраса. Модели динамического равновесия. ([3], ч. 1, II; [13], гл. 10,11).

III. ВАРИАЦИОННЫЕ ЗАДАЧИ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ

Простейшая вариационная задача с закрепленными концами. Понятие слабого и сильного локального минимума в простейшей вариационной задаче. Первое необходимое условие слабого локального минимума. Уравнения Эйлера. Второе необходимое условие слабого локального минимума. Условие Лежандра. Необходимое условие Якоби. Необходимое условие Вейерштрасса для сильного локального минимума. Достаточные условия слабого локального минимума. ([7], §§ 4, 5; [1], §§1.4, 4.1, 4.4; [6], гл. 6).

Терминальная задача оптимального управления. Принцип максимума ([7], § 6; [1], §§ 1.5, 4.2; [6], гл. 7; [17] ).

Динамическое программирование в теории оптимального управления ([4], [6], гл. 7).

Связь методов вариационного исчисления, принципа максимума и динамического программирования ([6], гл. 6; 7, § 2).

Проблема синтеза оптимальных систем ([17], гл. 1, § 5).

Основные понятия теории дифференциальных игр ([17], гл. 4, § 28; [6], гл.7, § 8, [10]).

ЛИТЕРАТУРА

  1. Алексеев В.М., Тихомиров В.М., Фомин СВ. Оптимальное управление. М.: Наука. 1979.
  2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир. 1979.
  3. Ашманов С.А. Введение в математическую экономику. М.: Наука. 1984.
  4. Беллман Р. Динамическое программирование. М.: Изд-во иностранной литературы. 1960.
  5. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука. 1980.
  6. Габасов Р., Кириллова Ф.М. Методы оптимизации. Минск: Изд-во БГУ. 1981.
  7. Галиев Э.М., Тихомиров В.М. Краткий курс теории экстремальных задач. М.: Изд-во МГУ. 1989.
  8. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир. 1982.
  9. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука. 1990.
  10. Красовский Н.Н. Теория управления движением. М.: Наука. 1968.
  11. И.Липский В. Комбинаторика для программистов. М.: Мир. 1988.
  12. Мальцев А.И. Алгоритмы и вычислимые функции. М.: Наука. 1965.
  13. Обен Ж.-П. Нелинейный анализ и его экономические приложения. М.: Мир. 1988.
  14. Оуэн Г. Теория игр. М.: Мир. 1971.
  15. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация.
  16. Алгоритмы и сложность. М.: Мир. 1985.
  17. Поляк Б.Т. Введение в теорию оптимизации. М.: Наука. 1983.
  18. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф.
  19. Математическая теория оптимальных процессов. М.: Наука. 1976. 18. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М.: Наука. 1980.
  20. Холл М. Комбинаторика. М.: Мир. 1970.
  21. Яблонский СВ. Введение в дискретную математику. М.: Наука. 1986.