13 534
правки
Изменения
Новая страница: «<center>ПРОГРАММА-МИНИМУМ<br></center> <center>кандидатского экзамена по специальности<br></center> <center>'''01...»
<center>ПРОГРАММА-МИНИМУМ<br></center>
<center>кандидатского экзамена по специальности<br></center>
<center>'''01.01.09 «Математическая кибернетика и дискретная математика»'''<br></center>
<center>по физико-математическим наукам</center>
В основу данной программы положены следующие разделы: математическое программирование, исследование операций, теория игр, оптимальное управление, дискретная оптимизация, теория функциональных систем, комбинаторный анализ, теория графов, теория кодирования, управляющие системы, дизъюнктивные нормальные формы, синтез и сложность управляющих систем, эквивалентные преобразования управляющих систем, надежность и контроль функционирования управляющих систем, математическая экономика.
Программа разработана экспертным советом Высшей аттестационной комиссии Министерства образования Российской Федерации по математике и механике при участии Московского государственного университета им. М. В. Ломоносова.
== Математическое программирование ==
* Теоремы о достижении нижней грани функции (функционала) на множестве (в ''Е<sup>N</sup>'', в метрических пространствах, в гильбертовых пространствах).
* Выпуклые множества, выпуклые функции, сильно выпуклые функции, их свойства.
* Критерии оптимальности в гладких выпуклых задачах минимизации (в форме вариационного неравенства <''f'''(''x''<sub>*</sub>), ''x — x''<sub>*</sub> > ? 0 " ''x'' из ''X'').
* Правило множителей Лагранжа.
* Теорема Куна-Таккера, двойственная задача, ее свойства.
* Метод проекции градиента (в ''Е<sup>N</sup>'', в гильбертовом пространстве).
* Метод Ньютона.
* Метод покоординатного спуска.
* Метод штрафных функций.
* Метод барьерных функций.
* Метод динамического программирования.
* Устойчивость задач оптимизации. Метод стабилизации (регуляризация по Тихонову).
* Линейное программирование. Симплекс-метод. Двойственные задачи линейного программирования.
== Исследование операций, теория игр ==
* Антагонистические игры. Матричные игры, теорема о минимаксе.
* Выпукло-вогнутые антагонистические игры. Теорема существования седловой точки.
* Бескоалиционные игры ''n'' лиц. Равновесие по Нэшу.
* Принцип гарантированного результата. Минимаксные задачи.
* Многокритериальная оптимизация. Оптимальность по Парето. Лексикографический подход.
* Кооперативные игры (''с''-ядро, вектор Шепли).
* Задача распределения ресурсов (модель Гросса, принцип уравнивания Гермейера).
* Иерархические игры.
* Потоки в сетях (теорема Форда-Фалкерсона, задача и алгоритмы поиска кратчайшего пути в графе, задача составления расписаний, транспортная задача).
== Оптимальное управление ==
* Постановка задач оптимального управления, их классификация.
* Принцип максимума Понтрягина. Краевая задача принципа максимума.
* Линейная задача быстродействия, ее свойства (существование решения, число переключений).
* Принцип максимума и вариационное исчисление.
* Управляемость и наблюдаемость в линейных системах, их взаимосвязь (взаимодвойственность). Теоремы Калмана, Красовского.
* Метод динамической регуляризации в задаче наблюдения.
* Дифференциальные игры.
== Дискретная оптимизация ==
* Целочисленное линейное программирование (метод Гомори, свойства унимодулярности матрицы ограничений).
* Метод ветвей и границ (на примере задач целочисленного или булева линейного программирования).
* Временная сложность решения задач дискретной оптимизации. Основные классы сложности (''P'', ''NP'', ''NPC'').
* ''NP''-трудные задачи (задача о рюкзаке, задача коммивояжера).
== Теория функциональных систем ==
* Проблема полноты. Теорема о полноте систем функций двузначной логики ''P''<sub>2</sub>.
* Алгоритм распознавания полноты систем функций ''k''-значной логики ''P<sub>k</sub>''.
* Теорема Слупецкого.
* Особенности ''k''-значных логик.
* Автоматы. Регулярные события и их представление в автоматах.
* Эксперименты с автоматами.
* Алгоритмическая неразрешимость проблемы полноты для автоматов.
* Вычислимые функции. Эквивалентность класса рекурсивных функций и класса функций, вычислимых на машинах Тьюринга.
* Алгоритмическая неразрешимость проблемы эквивалентности слов в ассоциативных исчислениях.
== Комбинаторный анализ и теория графов ==
* Основные комбинаторные числа.
* Оценки и асимптотики для комбинаторных чисел.
* Графы и сети. Оценки числа графов и сетей различных типов.
* Плоские и планарные графы. Формула Эйлера для плоских графов. Необходимые условия планарности в теореме Понтрягина—Куратовского (без доказательства достаточности).
* Экстремальная теория графов. Теорема Турана.
* Теорема Рамсея.
== Теория кодирования ==
* Алфавитное кодирование. Критерии однозначности декодирования. Неравенство Крафта—Макмиллана.
* Оптимальное кодирование. Построение кодов с минимальной избыточностью.
* Самокорректирующиеся коды. Граница упаковки. Коды Хемминга, исправляющие единичную ошибку.
* Конечные поля и их основные свойства.
* Коды Боуза—Чоудхури—Хоквингема.
== Управляющие системы ==
* Понятие управляющей системы. Основные модельные классы управляющих систем: дизъюнктивные нормальные формы, формулы, контактные схемы, схемы из функциональных элементов, автоматы, машины Тьюринга, операторные алгоритмы. Основные проблемы теории управляющих систем.
== Дизъюнктивные нормальные формы ==
* Проблема минимизации булевых функций. Дизъюнктивные нормальные формы (ДНФ). Постановка задачи в геометрической форме.
* Локальные алгоритмы построения ДНФ. Построение ДНФ ''∑Т'' (сумма тупиковых) с помощью локального алгоритма.
* Невозможность построения ДНФ ''∑М'' (сумма минимальных) в классе локальных алгоритмов.
== Синтез и сложность управляющих систем ==
* Асимптотически оптимальный метод синтеза схем из функциональных элементов.
* Асимптотически оптимальный метод синтеза контактных схем.
* Инвариантные классы и их свойства.
* Синтез схем для функций из некоторых инвариантных классов.
* Нижние оценки сложности реализации булевых функций параллельно-последовательными контактными схемами.
* Нижние оценки сложности реализации булевых функций формулами в произвольном базисе.
== Эквивалентные преобразования управляющих систем ==
* Эквивалентные преобразования формул двузначной логики ''Р''<sub>2</sub>.
* Эквивалентные преобразования контактных схем.
* Эквивалентные преобразования операторных алгоритмов.
* Пример Линдона.
== Надежность и контроль функционирования управляющих систем ==
* Построение надежных контактных схем из ненадежных контактов.
* Логический подход к контролю исправности и диагностике неисправностей управляющих систем. Тесты.
== Математическая экономика ==
* Модель межотраслевого баланса В. В. Леонтьева. Продуктивные матрицы. Критерии продуктивности. Теорема Фробениуса—Перрона. Свойства числа Фробениуса—Перрона. Теорема об устойчивости примитивных матриц.
* Динамическая модель В. В. Леонтьева. Теорема о магистрали Моришимы. Экономическая интерпретация вектора Фробениуса — Перрона.
* Линейные задачи оптимального распределения ресурсов. Экономическая интерпретация двойственности в задачах линейного программирования.
* Модель Кокса—Росса—Рубинштейна. Оценка стоимости опциона.
* Модель олигополистической конкуренции Курно. Теорема Нэша.
* Модель Эрроу—Дебре. Конкурентное равновесие. Сведение вопроса о существовании конкурентного равновесия к решению задачи дополнительности. Замкнутость отображений спроса и предложения. Теорема Эрроу—Дебре.
* Неподвижные точки. Теоремы Брауэра и Какутани. Лемма Гейла — Никайдо — Дебре. Теорема Фань-Цзы.
* Оптимальность по Парето конкурентного равновесия (первая теорема теории благосостояния). Теорема Дебре (вторая теорема теории благосостояния). Сравнительная статика в моделях конкурентного равновесия.
* Проблемы коллективного выбора. Парадокс Эрроу.
* Индексы неравенства и кривая Лоренца. Теорема мажоризации.
== Основная литература ==
* Яблонский С. В. Введение в дискретную математику. М.: Высш. школа, 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.
[[Категория:Учёба]]
<center>кандидатского экзамена по специальности<br></center>
<center>'''01.01.09 «Математическая кибернетика и дискретная математика»'''<br></center>
<center>по физико-математическим наукам</center>
В основу данной программы положены следующие разделы: математическое программирование, исследование операций, теория игр, оптимальное управление, дискретная оптимизация, теория функциональных систем, комбинаторный анализ, теория графов, теория кодирования, управляющие системы, дизъюнктивные нормальные формы, синтез и сложность управляющих систем, эквивалентные преобразования управляющих систем, надежность и контроль функционирования управляющих систем, математическая экономика.
Программа разработана экспертным советом Высшей аттестационной комиссии Министерства образования Российской Федерации по математике и механике при участии Московского государственного университета им. М. В. Ломоносова.
== Математическое программирование ==
* Теоремы о достижении нижней грани функции (функционала) на множестве (в ''Е<sup>N</sup>'', в метрических пространствах, в гильбертовых пространствах).
* Выпуклые множества, выпуклые функции, сильно выпуклые функции, их свойства.
* Критерии оптимальности в гладких выпуклых задачах минимизации (в форме вариационного неравенства <''f'''(''x''<sub>*</sub>), ''x — x''<sub>*</sub> > ? 0 " ''x'' из ''X'').
* Правило множителей Лагранжа.
* Теорема Куна-Таккера, двойственная задача, ее свойства.
* Метод проекции градиента (в ''Е<sup>N</sup>'', в гильбертовом пространстве).
* Метод Ньютона.
* Метод покоординатного спуска.
* Метод штрафных функций.
* Метод барьерных функций.
* Метод динамического программирования.
* Устойчивость задач оптимизации. Метод стабилизации (регуляризация по Тихонову).
* Линейное программирование. Симплекс-метод. Двойственные задачи линейного программирования.
== Исследование операций, теория игр ==
* Антагонистические игры. Матричные игры, теорема о минимаксе.
* Выпукло-вогнутые антагонистические игры. Теорема существования седловой точки.
* Бескоалиционные игры ''n'' лиц. Равновесие по Нэшу.
* Принцип гарантированного результата. Минимаксные задачи.
* Многокритериальная оптимизация. Оптимальность по Парето. Лексикографический подход.
* Кооперативные игры (''с''-ядро, вектор Шепли).
* Задача распределения ресурсов (модель Гросса, принцип уравнивания Гермейера).
* Иерархические игры.
* Потоки в сетях (теорема Форда-Фалкерсона, задача и алгоритмы поиска кратчайшего пути в графе, задача составления расписаний, транспортная задача).
== Оптимальное управление ==
* Постановка задач оптимального управления, их классификация.
* Принцип максимума Понтрягина. Краевая задача принципа максимума.
* Линейная задача быстродействия, ее свойства (существование решения, число переключений).
* Принцип максимума и вариационное исчисление.
* Управляемость и наблюдаемость в линейных системах, их взаимосвязь (взаимодвойственность). Теоремы Калмана, Красовского.
* Метод динамической регуляризации в задаче наблюдения.
* Дифференциальные игры.
== Дискретная оптимизация ==
* Целочисленное линейное программирование (метод Гомори, свойства унимодулярности матрицы ограничений).
* Метод ветвей и границ (на примере задач целочисленного или булева линейного программирования).
* Временная сложность решения задач дискретной оптимизации. Основные классы сложности (''P'', ''NP'', ''NPC'').
* ''NP''-трудные задачи (задача о рюкзаке, задача коммивояжера).
== Теория функциональных систем ==
* Проблема полноты. Теорема о полноте систем функций двузначной логики ''P''<sub>2</sub>.
* Алгоритм распознавания полноты систем функций ''k''-значной логики ''P<sub>k</sub>''.
* Теорема Слупецкого.
* Особенности ''k''-значных логик.
* Автоматы. Регулярные события и их представление в автоматах.
* Эксперименты с автоматами.
* Алгоритмическая неразрешимость проблемы полноты для автоматов.
* Вычислимые функции. Эквивалентность класса рекурсивных функций и класса функций, вычислимых на машинах Тьюринга.
* Алгоритмическая неразрешимость проблемы эквивалентности слов в ассоциативных исчислениях.
== Комбинаторный анализ и теория графов ==
* Основные комбинаторные числа.
* Оценки и асимптотики для комбинаторных чисел.
* Графы и сети. Оценки числа графов и сетей различных типов.
* Плоские и планарные графы. Формула Эйлера для плоских графов. Необходимые условия планарности в теореме Понтрягина—Куратовского (без доказательства достаточности).
* Экстремальная теория графов. Теорема Турана.
* Теорема Рамсея.
== Теория кодирования ==
* Алфавитное кодирование. Критерии однозначности декодирования. Неравенство Крафта—Макмиллана.
* Оптимальное кодирование. Построение кодов с минимальной избыточностью.
* Самокорректирующиеся коды. Граница упаковки. Коды Хемминга, исправляющие единичную ошибку.
* Конечные поля и их основные свойства.
* Коды Боуза—Чоудхури—Хоквингема.
== Управляющие системы ==
* Понятие управляющей системы. Основные модельные классы управляющих систем: дизъюнктивные нормальные формы, формулы, контактные схемы, схемы из функциональных элементов, автоматы, машины Тьюринга, операторные алгоритмы. Основные проблемы теории управляющих систем.
== Дизъюнктивные нормальные формы ==
* Проблема минимизации булевых функций. Дизъюнктивные нормальные формы (ДНФ). Постановка задачи в геометрической форме.
* Локальные алгоритмы построения ДНФ. Построение ДНФ ''∑Т'' (сумма тупиковых) с помощью локального алгоритма.
* Невозможность построения ДНФ ''∑М'' (сумма минимальных) в классе локальных алгоритмов.
== Синтез и сложность управляющих систем ==
* Асимптотически оптимальный метод синтеза схем из функциональных элементов.
* Асимптотически оптимальный метод синтеза контактных схем.
* Инвариантные классы и их свойства.
* Синтез схем для функций из некоторых инвариантных классов.
* Нижние оценки сложности реализации булевых функций параллельно-последовательными контактными схемами.
* Нижние оценки сложности реализации булевых функций формулами в произвольном базисе.
== Эквивалентные преобразования управляющих систем ==
* Эквивалентные преобразования формул двузначной логики ''Р''<sub>2</sub>.
* Эквивалентные преобразования контактных схем.
* Эквивалентные преобразования операторных алгоритмов.
* Пример Линдона.
== Надежность и контроль функционирования управляющих систем ==
* Построение надежных контактных схем из ненадежных контактов.
* Логический подход к контролю исправности и диагностике неисправностей управляющих систем. Тесты.
== Математическая экономика ==
* Модель межотраслевого баланса В. В. Леонтьева. Продуктивные матрицы. Критерии продуктивности. Теорема Фробениуса—Перрона. Свойства числа Фробениуса—Перрона. Теорема об устойчивости примитивных матриц.
* Динамическая модель В. В. Леонтьева. Теорема о магистрали Моришимы. Экономическая интерпретация вектора Фробениуса — Перрона.
* Линейные задачи оптимального распределения ресурсов. Экономическая интерпретация двойственности в задачах линейного программирования.
* Модель Кокса—Росса—Рубинштейна. Оценка стоимости опциона.
* Модель олигополистической конкуренции Курно. Теорема Нэша.
* Модель Эрроу—Дебре. Конкурентное равновесие. Сведение вопроса о существовании конкурентного равновесия к решению задачи дополнительности. Замкнутость отображений спроса и предложения. Теорема Эрроу—Дебре.
* Неподвижные точки. Теоремы Брауэра и Какутани. Лемма Гейла — Никайдо — Дебре. Теорема Фань-Цзы.
* Оптимальность по Парето конкурентного равновесия (первая теорема теории благосостояния). Теорема Дебре (вторая теорема теории благосостояния). Сравнительная статика в моделях конкурентного равновесия.
* Проблемы коллективного выбора. Парадокс Эрроу.
* Индексы неравенства и кривая Лоренца. Теорема мажоризации.
== Основная литература ==
* Яблонский С. В. Введение в дискретную математику. М.: Высш. школа, 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.
[[Категория:Учёба]]
