Кандаминимум 010109 - программа основной специальности

ПРОГРАММА-МИНИМУМ
кандидатского экзамена по специальности
01.01.09 «Математическая кибернетика и дискретная математика»
по физико-математическим наукам

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

Программа разработана экспертным советом Высшей аттестационной комиссии Министерства образования Российской Федерации по математике и механике при участии Московского государственного университета им. М. В. Ломоносова.

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

• Теоремы о достижении нижней грани функции (функционала) на множестве (в Е^N, в метрических пространствах, в гильбертовых пространствах).
• Выпуклые множества, выпуклые функции, сильно выпуклые функции, их свойства.
• Критерии оптимальности в гладких выпуклых задачах минимизации (в форме вариационного неравенства <f'(x_*), x — x_* > ? 0 " x из X).
• Правило множителей Лагранжа.
• Теорема Куна-Таккера, двойственная задача, ее свойства.
• Метод проекции градиента (в Е^N, в гильбертовом пространстве).
• Метод Ньютона.
• Метод покоординатного спуска.
• Метод штрафных функций.
• Метод барьерных функций.
• Метод динамического программирования.
• Устойчивость задач оптимизации. Метод стабилизации (регуляризация по Тихонову).
• Линейное программирование. Симплекс-метод. Двойственные задачи линейного программирования.

Исследование операций, теория игр

• Антагонистические игры. Матричные игры, теорема о минимаксе.
• Выпукло-вогнутые антагонистические игры. Теорема существования седловой точки.
• Бескоалиционные игры n лиц. Равновесие по Нэшу.
• Принцип гарантированного результата. Минимаксные задачи.
• Многокритериальная оптимизация. Оптимальность по Парето. Лексикографический подход.
• Кооперативные игры (с-ядро, вектор Шепли).
• Задача распределения ресурсов (модель Гросса, принцип уравнивания Гермейера).
• Иерархические игры.
• Потоки в сетях (теорема Форда-Фалкерсона, задача и алгоритмы поиска кратчайшего пути в графе, задача составления расписаний, транспортная задача).

Оптимальное управление

• Постановка задач оптимального управления, их классификация.
• Принцип максимума Понтрягина. Краевая задача принципа максимума.
• Линейная задача быстродействия, ее свойства (существование решения, число переключений).
• Принцип максимума и вариационное исчисление.
• Управляемость и наблюдаемость в линейных системах, их взаимосвязь (взаимодвойственность). Теоремы Калмана, Красовского.
• Метод динамической регуляризации в задаче наблюдения.
• Дифференциальные игры.

Дискретная оптимизация

• Целочисленное линейное программирование (метод Гомори, свойства унимодулярности матрицы ограничений).
• Метод ветвей и границ (на примере задач целочисленного или булева линейного программирования).
• Временная сложность решения задач дискретной оптимизации. Основные классы сложности (P, NP, NPC).
• NP-трудные задачи (задача о рюкзаке, задача коммивояжера).

Теория функциональных систем

• Проблема полноты. Теорема о полноте систем функций двузначной логики P₂.
• Алгоритм распознавания полноты систем функций k-значной логики P_k.
• Теорема Слупецкого.
• Особенности k-значных логик.
• Автоматы. Регулярные события и их представление в автоматах.
• Эксперименты с автоматами.
• Алгоритмическая неразрешимость проблемы полноты для автоматов.
• Вычислимые функции. Эквивалентность класса рекурсивных функций и класса функций, вычислимых на машинах Тьюринга.
• Алгоритмическая неразрешимость проблемы эквивалентности слов в ассоциативных исчислениях.

Комбинаторный анализ и теория графов

• Основные комбинаторные числа.
• Оценки и асимптотики для комбинаторных чисел.
• Графы и сети. Оценки числа графов и сетей различных типов.
• Плоские и планарные графы. Формула Эйлера для плоских графов. Необходимые условия планарности в теореме Понтрягина—Куратовского (без доказательства достаточности).
• Экстремальная теория графов. Теорема Турана.
• Теорема Рамсея.

Теория кодирования

• Алфавитное кодирование. Критерии однозначности декодирования. Неравенство Крафта—Макмиллана.
• Оптимальное кодирование. Построение кодов с минимальной избыточностью.
• Самокорректирующиеся коды. Граница упаковки. Коды Хемминга, исправляющие единичную ошибку.
• Конечные поля и их основные свойства.
• Коды Боуза—Чоудхури—Хоквингема.

Управляющие системы

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

Дизъюнктивные нормальные формы

• Проблема минимизации булевых функций. Дизъюнктивные нормальные формы (ДНФ). Постановка задачи в геометрической форме.
• Локальные алгоритмы построения ДНФ. Построение ДНФ ∑Т (сумма тупиковых) с помощью локального алгоритма.
• Невозможность построения ДНФ ∑М (сумма минимальных) в классе локальных алгоритмов.

Синтез и сложность управляющих систем

• Асимптотически оптимальный метод синтеза схем из функциональных элементов.
• Асимптотически оптимальный метод синтеза контактных схем.
• Инвариантные классы и их свойства.
• Синтез схем для функций из некоторых инвариантных классов.
• Нижние оценки сложности реализации булевых функций параллельно-последовательными контактными схемами.
• Нижние оценки сложности реализации булевых функций формулами в произвольном базисе.

Эквивалентные преобразования управляющих систем

• Эквивалентные преобразования формул двузначной логики Р₂.
• Эквивалентные преобразования контактных схем.
• Эквивалентные преобразования операторных алгоритмов.
• Пример Линдона.

Надежность и контроль функционирования управляющих систем

• Построение надежных контактных схем из ненадежных контактов.
• Логический подход к контролю исправности и диагностике неисправностей управляющих систем. Тесты.

Математическая экономика

• Модель межотраслевого баланса В. В. Леонтьева. Продуктивные матрицы. Критерии продуктивности. Теорема Фробениуса—Перрона. Свойства числа Фробениуса—Перрона. Теорема об устойчивости примитивных матриц.
• Динамическая модель В. В. Леонтьева. Теорема о магистрали Моришимы. Экономическая интерпретация вектора Фробениуса — Перрона.
• Линейные задачи оптимального распределения ресурсов. Экономическая интерпретация двойственности в задачах линейного программирования.
• Модель Кокса—Росса—Рубинштейна. Оценка стоимости опциона.
• Модель олигополистической конкуренции Курно. Теорема Нэша.
• Модель Эрроу—Дебре. Конкурентное равновесие. Сведение вопроса о существовании конкурентного равновесия к решению задачи дополнительности. Замкнутость отображений спроса и предложения. Теорема Эрроу—Дебре.
• Неподвижные точки. Теоремы Брауэра и Какутани. Лемма Гейла — Никайдо — Дебре. Теорема Фань-Цзы.
• Оптимальность по Парето конкурентного равновесия (первая теорема теории благосостояния). Теорема Дебре (вторая теорема теории благосостояния). Сравнительная статика в моделях конкурентного равновесия.
• Проблемы коллективного выбора. Парадокс Эрроу.
• Индексы неравенства и кривая Лоренца. Теорема мажоризации.

Основная литература

• Яблонский С. В. Введение в дискретную математику. М.: Высш. школа, 2001.
• Кудрявцев В.В, Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М.: Наука, 1985.
• Мальцев А. И. Алгоритмы и вычислимые функции. М.: Наука, 1986.
• Оре О. Теория графов. М.: Наука, 1980.
• Кибернетический сборник. 1960—1990. Вып. 1—9; вып. 1—28 (новая серия). М.: Мир.
• Дискретная математика и математические вопросы кибернетики. Т. 1. / Под общ. ред. С. В. Яблонского и О. Б. Лупанова. М.: Наука, 1974.
• Нигматуллин Р. Г. Сложность булевых функций. М.: Наука, 1991.
• Проблемы кибернетики. 1959—1984. Вып. 1—41. М.: Наука.
• Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. М.: Наука, 1990.
• Труды Математического института им. В. А. Стеклова. Т. 51. М.: Изд-во АН СССР, 1958.
• Математические вопросы кибернетики. 1988—2001. Вып. 1—10. М.: Наука.
• Гермейер Ю. Б. Введение в теорию исследования операций. М.: Наука, 1969.
• Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. М.: Наука, 1986.
• Васильев Ф. П. Методы оптимизации. М.: Факториал, 2002.
• Карманов В. Г. Математическое программирование. М.: Наука, 2000.
• Понтрягин Л. Избранные научные труды. Т. 2. М.: Наука, 1988.
• Тихомиров В. М., Фомин С. В., Алексеев В. М. Оптимальное управление. М.: Наука, 1979.
• Краснощеков П. С., Петров А. А. Принципы построения моделей. М.: Фазис, 2002.
• Подиновский В. В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1981.
• Морозов В. В. Основы теории игр. М.: Изд-во МГУ, 2002.
• Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. М.: Наука, 198 .
• Никайдо Х. Выпуклые структуры и математическая экономика. М.: Мир, 1972.
• Ашманов С. А. Введение в математическую экономику. М.: Наука, 1984.
• Экланд И. Элементы математической экономики. М.: Мир, 1983.
• Обен Ж.-П. Нелинейный анализ и его экономические приложения. М.: Мир, 1988.
• Маршалл А., Олкин И. Неравенства, теория мажоризации и ее приложения. М.: Мир, 1983.
• Мельников А. В. Стохастический анализ и расчет производных ценных бумаг. М.: ТВП, 1997.

Дополнительная литература

• МакВильмс Ф. Дж., Слоэн Н. Дж. Теория кодов, исправляющих ошибки. М.: Связь, 1979.
• Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984.
• Сэведж Дж. Э. Сложность вычислений. М.: Факториал, 1998.
• Марков А. А. Введение в теорию кодирования. М.: Наука, 1982.
• Орлов В. А. Простое доказательство алгоритмической неразрешимости некоторых задач о полноте автоматных базисов. //Кибернетика. 1973. № 4. С. 109—113.
• Редькин Н. П. Надежность и диагностика схем. М.: Изд-во МГУ, 1992.
• Соловьев Н. А. Тесты (теория, построение, применения). Новосибирск: Наука, 1978.
• Поляк Б. Т. Введение в оптимизацию. М.: Наука, 1984.