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

Материал из YourcmcWiki
Перейти к: навигация, поиск
(Новая страница: «<center>ПРОГРАММА-МИНИМУМ<br></center> <center>кандидатского экзамена по специальности<br></center> <center>'''01...»)
 
Строка 10: Строка 10:
 
== Математическое программирование ==
 
== Математическое программирование ==
  
* Теоремы о достижении нижней грани функции (функционала) на множестве (в ''Е<sup>N</sup>'', в метрических пространствах, в гильбертовых пространствах).
+
# Теоремы о достижении нижней грани функции (функционала) на множестве (в ''Е<sup>N</sup>'', в метрических пространствах, в гильбертовых пространствах).
* Выпуклые множества, выпуклые функции, сильно выпуклые функции, их свойства.
+
# Выпуклые множества, выпуклые функции, сильно выпуклые функции, их свойства.
* Критерии оптимальности в гладких выпуклых задачах минимизации (в форме вариационного неравенства <''f'''(''x''<sub>*</sub>), ''x — x''<sub>*</sub> > ? 0 " ''x'' из ''X'').
+
# Критерии оптимальности в гладких выпуклых задачах минимизации (в форме вариационного неравенства <''f'''(''x''<sub>*</sub>), ''x — x''<sub>*</sub> > ? 0 " ''x'' из ''X'').
* Правило множителей Лагранжа.
+
# Правило множителей Лагранжа.
* Теорема Куна-Таккера, двойственная задача, ее свойства.
+
# Теорема Куна-Таккера, двойственная задача, ее свойства.
* Метод проекции градиента (в ''Е<sup>N</sup>'', в гильбертовом пространстве).
+
# Метод проекции градиента (в ''Е<sup>N</sup>'', в гильбертовом пространстве).
* Метод Ньютона.
+
# Метод Ньютона.
* Метод покоординатного спуска.
+
# Метод покоординатного спуска.
* Метод штрафных функций.
+
# Метод штрафных функций.
* Метод барьерных функций.
+
# Метод барьерных функций.
* Метод динамического программирования.
+
# Метод динамического программирования.
* Устойчивость задач оптимизации. Метод стабилизации (регуляризация по Тихонову).
+
# Устойчивость задач оптимизации. Метод стабилизации (регуляризация по Тихонову).
* Линейное программирование. Симплекс-метод. Двойственные задачи линейного программирования.
+
# Линейное программирование. Симплекс-метод. Двойственные задачи линейного программирования.
  
 
== Исследование операций, теория игр ==
 
== Исследование операций, теория игр ==
  
* Антагонистические игры. Матричные игры, теорема о минимаксе.
+
# Антагонистические игры. Матричные игры, теорема о минимаксе.
* Выпукло-вогнутые антагонистические игры. Теорема существования седловой точки.
+
# Выпукло-вогнутые антагонистические игры. Теорема существования седловой точки.
* Бескоалиционные игры ''n'' лиц. Равновесие по Нэшу.
+
# Бескоалиционные игры ''n'' лиц. Равновесие по Нэшу.
* Принцип гарантированного результата. Минимаксные задачи.
+
# Принцип гарантированного результата. Минимаксные задачи.
* Многокритериальная оптимизация. Оптимальность по Парето. Лексикографический подход.
+
# Многокритериальная оптимизация. Оптимальность по Парето. Лексикографический подход.
* Кооперативные игры (''с''-ядро, вектор Шепли).
+
# Кооперативные игры (''с''-ядро, вектор Шепли).
* Задача распределения ресурсов (модель Гросса, принцип уравнивания Гермейера).
+
# Задача распределения ресурсов (модель Гросса, принцип уравнивания Гермейера).
* Иерархические игры.
+
# Иерархические игры.
* Потоки в сетях (теорема Форда-Фалкерсона, задача и алгоритмы поиска кратчайшего пути в графе, задача составления расписаний, транспортная задача).
+
# Потоки в сетях (теорема Форда-Фалкерсона, задача и алгоритмы поиска кратчайшего пути в графе, задача составления расписаний, транспортная задача).
  
 
== Оптимальное управление ==
 
== Оптимальное управление ==
  
* Постановка задач оптимального управления, их классификация.
+
# Постановка задач оптимального управления, их классификация.
* Принцип максимума Понтрягина. Краевая задача принципа максимума.
+
# Принцип максимума Понтрягина. Краевая задача принципа максимума.
* Линейная задача быстродействия, ее свойства (существование решения, число переключений).
+
# Линейная задача быстродействия, ее свойства (существование решения, число переключений).
* Принцип максимума и вариационное исчисление.
+
# Принцип максимума и вариационное исчисление.
* Управляемость и наблюдаемость в линейных системах, их взаимосвязь (взаимодвойственность). Теоремы Калмана, Красовского.
+
# Управляемость и наблюдаемость в линейных системах, их взаимосвязь (взаимодвойственность). Теоремы Калмана, Красовского.
* Метод динамической регуляризации в задаче наблюдения.
+
# Метод динамической регуляризации в задаче наблюдения.
* Дифференциальные игры.
+
# Дифференциальные игры.
  
 
== Дискретная оптимизация ==
 
== Дискретная оптимизация ==
  
* Целочисленное линейное программирование (метод Гомори, свойства унимодулярности матрицы ограничений).
+
# Целочисленное линейное программирование (метод Гомори, свойства унимодулярности матрицы ограничений).
* Метод ветвей и границ (на примере задач целочисленного или булева линейного программирования).
+
# Метод ветвей и границ (на примере задач целочисленного или булева линейного программирования).
* Временная сложность решения задач дискретной оптимизации. Основные классы сложности (''P'', ''NP'', ''NPC'').
+
# Временная сложность решения задач дискретной оптимизации. Основные классы сложности (''P'', ''NP'', ''NPC'').
* ''NP''-трудные задачи (задача о рюкзаке, задача коммивояжера).
+
# ''NP''-трудные задачи (задача о рюкзаке, задача коммивояжера).
  
 
== Теория функциональных систем ==
 
== Теория функциональных систем ==
  
* Проблема полноты. Теорема о полноте систем функций двузначной логики ''P''<sub>2</sub>.
+
# Проблема полноты. Теорема о полноте систем функций двузначной логики ''P''<sub>2</sub>.
* Алгоритм распознавания полноты систем функций ''k''-значной логики ''P<sub>k</sub>''.
+
# Алгоритм распознавания полноты систем функций ''k''-значной логики ''P<sub>k</sub>''.
* Теорема Слупецкого.
+
# Теорема Слупецкого.
* Особенности ''k''-значных логик.
+
# Особенности ''k''-значных логик.
* Автоматы. Регулярные события и их представление в автоматах.
+
# Автоматы. Регулярные события и их представление в автоматах.
* Эксперименты с автоматами.
+
# Эксперименты с автоматами.
* Алгоритмическая неразрешимость проблемы полноты для автоматов.
+
# Алгоритмическая неразрешимость проблемы полноты для автоматов.
* Вычислимые функции. Эквивалентность класса рекурсивных функций и класса функций, вычислимых на машинах Тьюринга.
+
# Вычислимые функции. Эквивалентность класса рекурсивных функций и класса функций, вычислимых на машинах Тьюринга.
* Алгоритмическая неразрешимость проблемы эквивалентности слов в ассоциативных исчислениях.
+
# Алгоритмическая неразрешимость проблемы эквивалентности слов в ассоциативных исчислениях.
  
 
== Комбинаторный анализ и теория графов ==
 
== Комбинаторный анализ и теория графов ==
  
* Основные комбинаторные числа.
+
# Основные комбинаторные числа.
* Оценки и асимптотики для комбинаторных чисел.
+
# Оценки и асимптотики для комбинаторных чисел.
* Графы и сети. Оценки числа графов и сетей различных типов.
+
# Графы и сети. Оценки числа графов и сетей различных типов.
* Плоские и планарные графы. Формула Эйлера для плоских графов. Необходимые условия планарности в теореме Понтрягина—Куратовского (без доказательства достаточности).
+
# Плоские и планарные графы. Формула Эйлера для плоских графов. Необходимые условия планарности в теореме Понтрягина—Куратовского (без доказательства достаточности).
* Экстремальная теория графов. Теорема Турана.
+
# Экстремальная теория графов. Теорема Турана.
* Теорема Рамсея.
+
# Теорема Рамсея.
  
 
== Теория кодирования ==
 
== Теория кодирования ==
  
* Алфавитное кодирование. Критерии однозначности декодирования. Неравенство Крафта—Макмиллана.
+
# Алфавитное кодирование. Критерии однозначности декодирования. Неравенство Крафта—Макмиллана.
* Оптимальное кодирование. Построение кодов с минимальной избыточностью.
+
# Оптимальное кодирование. Построение кодов с минимальной избыточностью.
* Самокорректирующиеся коды. Граница упаковки. Коды Хемминга, исправляющие единичную ошибку.
+
# Самокорректирующиеся коды. Граница упаковки. Коды Хемминга, исправляющие единичную ошибку.
* Конечные поля и их основные свойства.
+
# Конечные поля и их основные свойства.
* Коды Боуза—Чоудхури—Хоквингема.
+
# Коды Боуза—Чоудхури—Хоквингема.
  
 
== Управляющие системы ==
 
== Управляющие системы ==
  
* Понятие управляющей системы. Основные модельные классы управляющих систем: дизъюнктивные нормальные формы, формулы, контактные схемы, схемы из функциональных элементов, автоматы, машины Тьюринга, операторные алгоритмы. Основные проблемы теории управляющих систем.
+
# Понятие управляющей системы. Основные модельные классы управляющих систем: дизъюнктивные нормальные формы, формулы, контактные схемы, схемы из функциональных элементов, автоматы, машины Тьюринга, операторные алгоритмы. Основные проблемы теории управляющих систем.
  
 
== Дизъюнктивные нормальные формы ==
 
== Дизъюнктивные нормальные формы ==
  
* Проблема минимизации булевых функций. Дизъюнктивные нормальные формы (ДНФ). Постановка задачи в геометрической форме.
+
# Проблема минимизации булевых функций. Дизъюнктивные нормальные формы (ДНФ). Постановка задачи в геометрической форме.
* Локальные алгоритмы построения ДНФ. Построение ДНФ ''∑Т'' (сумма тупиковых) с помощью локального алгоритма.
+
# Локальные алгоритмы построения ДНФ. Построение ДНФ ''∑Т'' (сумма тупиковых) с помощью локального алгоритма.
* Невозможность построения ДНФ ''∑М'' (сумма минимальных) в классе локальных алгоритмов.
+
# Невозможность построения ДНФ ''∑М'' (сумма минимальных) в классе локальных алгоритмов.
  
 
== Синтез и сложность управляющих систем ==
 
== Синтез и сложность управляющих систем ==
  
* Асимптотически оптимальный метод синтеза схем из функциональных элементов.
+
# Асимптотически оптимальный метод синтеза схем из функциональных элементов.
* Асимптотически оптимальный метод синтеза контактных схем.
+
# Асимптотически оптимальный метод синтеза контактных схем.
* Инвариантные классы и их свойства.
+
# Инвариантные классы и их свойства.
* Синтез схем для функций из некоторых инвариантных классов.
+
# Синтез схем для функций из некоторых инвариантных классов.
* Нижние оценки сложности реализации булевых функций параллельно-последовательными контактными схемами.
+
# Нижние оценки сложности реализации булевых функций параллельно-последовательными контактными схемами.
* Нижние оценки сложности реализации булевых функций формулами в произвольном базисе.
+
# Нижние оценки сложности реализации булевых функций формулами в произвольном базисе.
  
 
== Эквивалентные преобразования управляющих систем ==
 
== Эквивалентные преобразования управляющих систем ==
  
* Эквивалентные преобразования формул двузначной логики ''Р''<sub>2</sub>.
+
# Эквивалентные преобразования формул двузначной логики ''Р''<sub>2</sub>.
* Эквивалентные преобразования контактных схем.
+
# Эквивалентные преобразования контактных схем.
* Эквивалентные преобразования операторных алгоритмов.
+
# Эквивалентные преобразования операторных алгоритмов.
* Пример Линдона.
+
# Пример Линдона.
  
 
== Надежность и контроль функционирования управляющих систем ==
 
== Надежность и контроль функционирования управляющих систем ==
  
* Построение надежных контактных схем из ненадежных контактов.
+
# Построение надежных контактных схем из ненадежных контактов.
* Логический подход к контролю исправности и диагностике неисправностей управляющих систем. Тесты.
+
# Логический подход к контролю исправности и диагностике неисправностей управляющих систем. Тесты.
  
 
== Математическая экономика ==
 
== Математическая экономика ==
  
* Модель межотраслевого баланса В. В. Леонтьева. Продуктивные матрицы. Критерии продуктивности. Теорема Фробениуса—Перрона. Свойства числа Фробениуса—Перрона. Теорема об устойчивости примитивных матриц.
+
# Модель межотраслевого баланса В. В. Леонтьева. Продуктивные матрицы. Критерии продуктивности. Теорема Фробениуса—Перрона. Свойства числа Фробениуса—Перрона. Теорема об устойчивости примитивных матриц.
* Динамическая модель В. В. Леонтьева. Теорема о магистрали Моришимы. Экономическая интерпретация вектора Фробениуса — Перрона.
+
# Динамическая модель В. В. Леонтьева. Теорема о магистрали Моришимы. Экономическая интерпретация вектора Фробениуса — Перрона.
* Линейные задачи оптимального распределения ресурсов. Экономическая интерпретация двойственности в задачах линейного программирования.
+
# Линейные задачи оптимального распределения ресурсов. Экономическая интерпретация двойственности в задачах линейного программирования.
* Модель Кокса—Росса—Рубинштейна. Оценка стоимости опциона.
+
# Модель Кокса—Росса—Рубинштейна. Оценка стоимости опциона.
* Модель олигополистической конкуренции Курно. Теорема Нэша.
+
# Модель олигополистической конкуренции Курно. Теорема Нэша.
* Модель Эрроу—Дебре. Конкурентное равновесие. Сведение вопроса о существовании конкурентного равновесия к решению задачи дополнительности. Замкнутость отображений спроса и предложения. Теорема Эрроу—Дебре.
+
# Модель Эрроу—Дебре. Конкурентное равновесие. Сведение вопроса о существовании конкурентного равновесия к решению задачи дополнительности. Замкнутость отображений спроса и предложения. Теорема Эрроу—Дебре.
* Неподвижные точки. Теоремы Брауэра и Какутани. Лемма Гейла — Никайдо — Дебре. Теорема Фань-Цзы.
+
# Неподвижные точки. Теоремы Брауэра и Какутани. Лемма Гейла — Никайдо — Дебре. Теорема Фань-Цзы.
* Оптимальность по Парето конкурентного равновесия (первая теорема теории благосостояния). Теорема Дебре (вторая теорема теории благосостояния). Сравнительная статика в моделях конкурентного равновесия.
+
# Оптимальность по Парето конкурентного равновесия (первая теорема теории благосостояния). Теорема Дебре (вторая теорема теории благосостояния). Сравнительная статика в моделях конкурентного равновесия.
* Проблемы коллективного выбора. Парадокс Эрроу.
+
# Проблемы коллективного выбора. Парадокс Эрроу.
* Индексы неравенства и кривая Лоренца. Теорема мажоризации.
+
# Индексы неравенства и кривая Лоренца. Теорема мажоризации.
  
 
== Основная литература ==
 
== Основная литература ==
  
* Яблонский С. В. Введение в дискретную математику. М.: Высш. школа, 2001.
+
# Яблонский С. В. Введение в дискретную математику. М.: Высш. школа, 2001.
* Кудрявцев В.В, Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М.: Наука, 1985.
+
# Кудрявцев В.В, Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М.: Наука, 1985.
* Мальцев А. И. Алгоритмы и вычислимые функции. М.: Наука, 1986.
+
# Мальцев А. И. Алгоритмы и вычислимые функции. М.: Наука, 1986.
* Оре О. Теория графов. М.: Наука, 1980.
+
# Оре О. Теория графов. М.: Наука, 1980.
* Кибернетический сборник. 1960—1990. Вып. 1—9; вып. 1—28 (новая серия). М.: Мир.
+
# Кибернетический сборник. 1960—1990. Вып. 1—9; вып. 1—28 (новая серия). М.: Мир.
* Дискретная математика и математические вопросы кибернетики. Т. 1. / Под общ. ред. С. В. Яблонского и О. Б. Лупанова. М.: Наука, 1974.
+
# Дискретная математика и математические вопросы кибернетики. Т. 1. / Под общ. ред. С. В. Яблонского и О. Б. Лупанова. М.: Наука, 1974.
* Нигматуллин Р. Г. Сложность булевых функций. М.: Наука, 1991.
+
# Нигматуллин Р. Г. Сложность булевых функций. М.: Наука, 1991.
* Проблемы кибернетики. 1959—1984. Вып. 1—41. М.: Наука.
+
# Проблемы кибернетики. 1959—1984. Вып. 1—41. М.: Наука.
* Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. М.: Наука, 1990.
+
# Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. М.: Наука, 1990.
* Труды Математического института им. В. А. Стеклова. Т. 51. М.: Изд-во АН СССР, 1958.
+
# Труды Математического института им. В. А. Стеклова. Т. 51. М.: Изд-во АН СССР, 1958.
* Математические вопросы кибернетики. 1988—2001. Вып. 1—10. М.: Наука.
+
# Математические вопросы кибернетики. 1988—2001. Вып. 1—10. М.: Наука.
* Гермейер Ю. Б. Введение в теорию исследования операций. М.: Наука, 1969.
+
# Гермейер Ю. Б. Введение в теорию исследования операций. М.: Наука, 1969.
* Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. М.: Наука, 1986.
+
# Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. М.: Наука, 1986.
* Васильев Ф. П. Методы оптимизации. М.: Факториал, 2002.
+
# Васильев Ф. П. Методы оптимизации. М.: Факториал, 2002.
* Карманов В. Г. Математическое программирование. М.: Наука, 2000.
+
# Карманов В. Г. Математическое программирование. М.: Наука, 2000.
* Понтрягин Л. Избранные научные труды. Т. 2. М.: Наука, 1988.
+
# Понтрягин Л. Избранные научные труды. Т. 2. М.: Наука, 1988.
* Тихомиров В. М., Фомин С. В., Алексеев В. М. Оптимальное управление. М.: Наука, 1979.
+
# Тихомиров В. М., Фомин С. В., Алексеев В. М. Оптимальное управление. М.: Наука, 1979.
* Краснощеков П. С., Петров А. А. Принципы построения моделей. М.: Фазис, 2002.
+
# Краснощеков П. С., Петров А. А. Принципы построения моделей. М.: Фазис, 2002.
* Подиновский В. В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1981.
+
# Подиновский В. В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1981.
* Морозов В. В. Основы теории игр. М.: Изд-во МГУ, 2002.
+
# Морозов В. В. Основы теории игр. М.: Изд-во МГУ, 2002.
* Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. М.: Наука, 198 .
+
# Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. М.: Наука, 198 .
* Никайдо Х. Выпуклые структуры и математическая экономика. М.: Мир, 1972.
+
# Никайдо Х. Выпуклые структуры и математическая экономика. М.: Мир, 1972.
* Ашманов С. А. Введение в математическую экономику. М.: Наука, 1984.
+
# Ашманов С. А. Введение в математическую экономику. М.: Наука, 1984.
* Экланд И. Элементы математической экономики. М.: Мир, 1983.
+
# Экланд И. Элементы математической экономики. М.: Мир, 1983.
* Обен Ж.-П. Нелинейный анализ и его экономические приложения. М.: Мир, 1988.
+
# Обен Ж.-П. Нелинейный анализ и его экономические приложения. М.: Мир, 1988.
* Маршалл А., Олкин И. Неравенства, теория мажоризации и ее приложения. М.: Мир, 1983.
+
# Маршалл А., Олкин И. Неравенства, теория мажоризации и ее приложения. М.: Мир, 1983.
* Мельников А. В. Стохастический анализ и расчет производных ценных бумаг. М.: ТВП, 1997.
+
# Мельников А. В. Стохастический анализ и расчет производных ценных бумаг. М.: ТВП, 1997.
  
 
== Дополнительная литература ==
 
== Дополнительная литература ==
  
* МакВильмс Ф. Дж., Слоэн Н. Дж. Теория кодов, исправляющих ошибки. М.: Связь, 1979.
+
# МакВильмс Ф. Дж., Слоэн Н. Дж. Теория кодов, исправляющих ошибки. М.: Связь, 1979.
* Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984.
+
# Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984.
* Сэведж Дж. Э. Сложность вычислений. М.: Факториал, 1998.
+
# Сэведж Дж. Э. Сложность вычислений. М.: Факториал, 1998.
* Марков А. А. Введение в теорию кодирования. М.: Наука, 1982.
+
# Марков А. А. Введение в теорию кодирования. М.: Наука, 1982.
* Орлов В. А. Простое доказательство алгоритмической неразрешимости некоторых задач о полноте автоматных базисов.  //Кибернетика. 1973. № 4. С. 109—113.
+
# Орлов В. А. Простое доказательство алгоритмической неразрешимости некоторых задач о полноте автоматных базисов.  //Кибернетика. 1973. № 4. С. 109—113.
* Редькин Н. П. Надежность и диагностика схем. М.: Изд-во МГУ, 1992.
+
# Редькин Н. П. Надежность и диагностика схем. М.: Изд-во МГУ, 1992.
* Соловьев Н. А. Тесты (теория, построение, применения). Новосибирск: Наука, 1978.
+
# Соловьев Н. А. Тесты (теория, построение, применения). Новосибирск: Наука, 1978.
* Поляк Б. Т. Введение в оптимизацию. М.: Наука, 1984.
+
# Поляк Б. Т. Введение в оптимизацию. М.: Наука, 1984.
  
 
[[Категория:Учёба]]
 
[[Категория:Учёба]]

Версия 16:12, 21 ноября 2009

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

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

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

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

  1. Теоремы о достижении нижней грани функции (функционала) на множестве (в ЕN, в метрических пространствах, в гильбертовых пространствах).
  2. Выпуклые множества, выпуклые функции, сильно выпуклые функции, их свойства.
  3. Критерии оптимальности в гладких выпуклых задачах минимизации (в форме вариационного неравенства <f'(x*), x — x* > ? 0 " x из X).
  4. Правило множителей Лагранжа.
  5. Теорема Куна-Таккера, двойственная задача, ее свойства.
  6. Метод проекции градиента (в ЕN, в гильбертовом пространстве).
  7. Метод Ньютона.
  8. Метод покоординатного спуска.
  9. Метод штрафных функций.
  10. Метод барьерных функций.
  11. Метод динамического программирования.
  12. Устойчивость задач оптимизации. Метод стабилизации (регуляризация по Тихонову).
  13. Линейное программирование. Симплекс-метод. Двойственные задачи линейного программирования.

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

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

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

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

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

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

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

  1. Проблема полноты. Теорема о полноте систем функций двузначной логики P2.
  2. Алгоритм распознавания полноты систем функций k-значной логики Pk.
  3. Теорема Слупецкого.
  4. Особенности k-значных логик.
  5. Автоматы. Регулярные события и их представление в автоматах.
  6. Эксперименты с автоматами.
  7. Алгоритмическая неразрешимость проблемы полноты для автоматов.
  8. Вычислимые функции. Эквивалентность класса рекурсивных функций и класса функций, вычислимых на машинах Тьюринга.
  9. Алгоритмическая неразрешимость проблемы эквивалентности слов в ассоциативных исчислениях.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. Яблонский С. В. Введение в дискретную математику. М.: Высш. школа, 2001.
  2. Кудрявцев В.В, Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М.: Наука, 1985.
  3. Мальцев А. И. Алгоритмы и вычислимые функции. М.: Наука, 1986.
  4. Оре О. Теория графов. М.: Наука, 1980.
  5. Кибернетический сборник. 1960—1990. Вып. 1—9; вып. 1—28 (новая серия). М.: Мир.
  6. Дискретная математика и математические вопросы кибернетики. Т. 1. / Под общ. ред. С. В. Яблонского и О. Б. Лупанова. М.: Наука, 1974.
  7. Нигматуллин Р. Г. Сложность булевых функций. М.: Наука, 1991.
  8. Проблемы кибернетики. 1959—1984. Вып. 1—41. М.: Наука.
  9. Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. М.: Наука, 1990.
  10. Труды Математического института им. В. А. Стеклова. Т. 51. М.: Изд-во АН СССР, 1958.
  11. Математические вопросы кибернетики. 1988—2001. Вып. 1—10. М.: Наука.
  12. Гермейер Ю. Б. Введение в теорию исследования операций. М.: Наука, 1969.
  13. Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. М.: Наука, 1986.
  14. Васильев Ф. П. Методы оптимизации. М.: Факториал, 2002.
  15. Карманов В. Г. Математическое программирование. М.: Наука, 2000.
  16. Понтрягин Л. Избранные научные труды. Т. 2. М.: Наука, 1988.
  17. Тихомиров В. М., Фомин С. В., Алексеев В. М. Оптимальное управление. М.: Наука, 1979.
  18. Краснощеков П. С., Петров А. А. Принципы построения моделей. М.: Фазис, 2002.
  19. Подиновский В. В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1981.
  20. Морозов В. В. Основы теории игр. М.: Изд-во МГУ, 2002.
  21. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. М.: Наука, 198 .
  22. Никайдо Х. Выпуклые структуры и математическая экономика. М.: Мир, 1972.
  23. Ашманов С. А. Введение в математическую экономику. М.: Наука, 1984.
  24. Экланд И. Элементы математической экономики. М.: Мир, 1983.
  25. Обен Ж.-П. Нелинейный анализ и его экономические приложения. М.: Мир, 1988.
  26. Маршалл А., Олкин И. Неравенства, теория мажоризации и ее приложения. М.: Мир, 1983.
  27. Мельников А. В. Стохастический анализ и расчет производных ценных бумаг. М.: ТВП, 1997.

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

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