Изменения

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

* # Теоремы о достижении нижней грани функции (функционала) на множестве (в ''Е^N'', в метрических пространствах, в гильбертовых пространствах).* # Выпуклые множества, выпуклые функции, сильно выпуклые функции, их свойства.* # Критерии оптимальности в гладких выпуклых задачах минимизации (в форме вариационного неравенства <''m>(f'''(''x''_{x_*}), ''x — x''<sub>-x_*</sub) > > ? 0 " '', x'' из ''\in X''</m>).* # Правило множителей Лагранжа.* # Теорема Куна-Таккера, двойственная задача, ее свойства.* # Метод проекции градиента (в ''Е^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.

[[Категория:УчёбаКандаминимум]]