Программа-минимум кандидатского экзамена по специальности 01. 01. 09 «Дискретная математика и математическая кибернетика» по физико-математическим наукам




НазваниеПрограмма-минимум кандидатского экзамена по специальности 01. 01. 09 «Дискретная математика и математическая кибернетика» по физико-математическим наукам
Дата04.02.2016
Размер14,4 Kb.
ТипПрограмма-минимум


Министерство образования и науки Российской Федерации


ПРОГРАММА-МИНИМУМ

кандидатского экзамена по специальности

01.01.09 «Дискретная математика и математическая кибернетика»

по физико-математическим наукам


Программа-минимум


содержит 10 стр.


2004
Введение


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

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

Литература: ([14] – [16], [36])


  1. Теоремы о достижении нижней грани функции (функционала) на множестве (в ЕN, в метрических пространствах, в гильбертовых пространствах).

  2. Выпуклые множества, выпуклые функции, сильно выпуклые функции, их свойства.

  3. Критерии оптимальности в гладких выпуклых задачах минимизации (в форме вариационного неравенства *), x- x* >  0  x из X).

  4. Правило множителей Лагранжа.

  5. Теорема Куна-Таккера, двойственная задача, ее свойства.

  6. Метод проекции градиента (в ЕN, в гильбертовом пространстве).

  7. Метод Ньютона.

  8. Метод покоординатного спуска.

  9. Метод штрафных функций.

  10. Метод барьерных функций.

  11. Метод динамического программирования.

  12. Устойчивость задач оптимизации. Метод стабилизации (регуляризация по Тихонову).

  13. Линейное программирование. Симплекс-метод. Двойственные задачи линейного программирования.



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

([13], [19] – [21])


  1. Антагонистические игры. Матричные игры, теорема о минимаксе.

  2. Выпукло-вогнутые антагонистические игры. Теорема существования седловой точки.

  3. Бескоалиционные игры n лиц. Равновесие по Нэшу.

  4. Принцип гарантированного результата. Минимаксные задачи.

  5. Многокритериальная оптимизация. Оптимальность по Парето. Лексикографический подход.

  6. Кооперативные игры (с-ядро, вектор Шепли).

  7. Задача распределения ресурсов (модель Гросса, принцип уравнивания Гермейера).

  8. Иерархические игры.

  9. Потоки в сетях (теорема Форда-Фалкерсона, задача и алгоритмы поиска кратчайшего пути в графе, задача составления расписаний, транспортная задача).



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

([18],[17])


  1. Постановка задач оптимального уравнения, их классификация.

  2. Принцип максимума Понтрягина. Краевая задача принципа максимума.

  3. Линейная задача быстродействия, ее свойства (существование решения, число переключений).

  4. Принцип максимума и вариационное исчисление.

  5. Управляемость и наблюдаемость в линейных системах, их взаимосвязь (взаимодвойственность). Теоремы Калмана, Красовского.

  6. Метод динамической регуляризации в задаче наблюдения.

  7. Дифференциальные игры.



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

([22],[14])


  1. Целочисленное линейное программирование (метод Гомори, свойства унимодулярности матрицы ограничений).

  2. Метод ветвей и границ (на примере задач целочисленного или булева линейного программирования).

  3. Временная сложность решения задач дискретной оптимизации. Основные классы сложности (P, NP, NPC).

  4. NP–трудные задачи (задача о рюкзаке, задача коммивояжера).


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


1. Проблема полноты. Теорема о полноте систем функций двузначной логики . ([1], часть I, гл. 1, §5, 6.)

2. Алгоритм распознавания полноты систем функций k-значной логики . ([1], часть I, гл. 2, § 3.)

3. Теорема Слупецкого. ([1], часть I, гл. 2, § 4.)

4. Особенности k-значных логик. ([1], часть I, гл. 2, § 5.)

5. Автоматы. Регулярные события и их представление в автоматах. ([2], гл. 1, гл. 2, § 1, 2, 7, 8; [5], вып. 3, с. 147-166.)

6. Эксперименты с автоматами. ([2], гл.2, § 4-6: с.57-67, 80-84.)

7. Алгоритмическая неразрешимость проблемы полноты для автоматов.([2], гл. 3, §1-6, 10.)

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

9. Алгоритмическая неразрешимость проблемы эквивалентности слов в ассоци­ативных исчислениях. ([3], §13.1.)


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


1. Основные комбинаторные числа; ([1], часть II, § 1, 2.)

2. Оценки и асимптотики для комбинаторных чисел. ([1], часть II, § 4.)

3. Графы и сети. Оценки числа графов и сетей различных типов. ([1], часть III; [4], гл. 1,2.);

4. Плоские и планарные графы. Формула Эйлера для плоских графов. Необходи­мые условия планарности в теореме Понтрягина-Куратовского (без доказательства достаточности). ([9], § 36-39: с. 150-160.)

5. Экстремальная теория графов. Теорема Турана. ([4], гл. 13, § 13.4.)

  1. Теорема Рамсея. ([4], гл. 13, § 13.5.)


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


1. Алфавитное кодирование. Критерии однозначности декодирования. Неравен­ство Крафта-Макмиллана. ([1], часть IV, § 1-3.)

  1. Оптимальное кодирование. Построение кодов с минимальной избыточностью. ([1], часть IV, §4.)

  2. Самокорректирующиеся коды. Граница упаковки. Коды Хемминга, исправля­ющие единичную ошибку. ([1], часть IV, § 5.)

  3. Конечные поля и их основные свойства ([29]).

  4. Коды Боуза—Чоудхури—Хоквингема. ([5], с. 83-94.)




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


Понятие управляющей системы. Основные модельные классы управляющих си­стем: дизъюнктивные нормальные формы, формулы, контактные схемы, схемы из функциональных элементов, автоматы, машины Тьюринга, операторные алгоритмы. Основные проблемы теории управляющих систем. ([8], вып. 2, с. 7-12; вып. 1, с. 78-81; вып. 9, с. 5-22.)


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


1. Проблема минимизации булевых функций. Дизъюнктивные нормальные фор­мы (ДНФ). Постановка задачи в геометрической форме. ([1], часть V, гл. 1, § 1-4.)

2. Локальные алгоритмы построения ДНФ. Построение ДНФ Т («сумма тупи­ковых») с помощью локального алгоритма. ([1], часть V, гл. 1, § 5-7.)

  1. Невозможность построения ДНФ М («сумма минимальных») в классе ло­кальных алгоритмов. ([6], раздел 2, гл. II, § 14.)




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


1. Асимптотически оптимальный метод синтеза схем из функциональных эле­ментов. ([8], вып. 10. с. 63-72, 89-93.)

2. Асимптотически оптимальный метод синтеза контактных схем. ([8], вып. 10, с. 73-83, 94-96.)

3. Инвариантные классы и их свойства. ([8], вып. 2, с. 82-89.)

4. Синтез схем для функций из некоторых инвариантных классов. ([8], вып. 14,
с. 37-39, 59-61; [1], часть V, § 7, 8.)

5. Нижние оценки сложности реализации булевых функций параллельно-последовательными контактными схемами. ([7], гл. 8, § 5.)

  1. Нижние оценки сложности реализации булевых функций формулами в произвольном базисе. ([7], гл.8, § 6.)


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


1. Эквивалентные преобразования формул двузначной логики Р. ([1], часть I, гл. 1, § 1-4.)

2. Эквивалентные преобразования контактных схем. ([8], вып. 5, с. 61-70.)

3. Эквивалентные преобразования операторных алгоритмов. ([8], вып. 1, с. 75-112.)

  1. Пример Линдона. ([5], вып. 1, с. 246-248.)


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


1. Построение надежных контактных схем из ненадежных контактов. ([5], вып. 1, с. 109-148.)

2. Логический подход к контролю исправности и диагностике неисправностей управляющих систем. Тесты. ([10], с. 270-293; [11], вып. 1, с. 16-20.)


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

[23 - 28]


1. Модель межотраслевого баланса В.В. Леонтьева. Продуктивные матрицы. Критерии продуктивности. Теорема Фробениуса-Перрона. Свойства числа Фробениуса-Перрона. Теорема об устойчивости примитивных матриц.

2. Динамическая модель В.В. Леонтьева. Теорема о магистрали Моришимы. Экономическая интерпретация вектора Фробениуса - Перрона.

3. Линейные задачи оптимального распределения ресурсов. Экономическая интерпретация двойственности в задачах линейного программирования.

4. Модель Кокса-Росса-Рубинштейна. Оценка стоимости опциона.

5. Модель олигополистической конкуренции Курно. Теорема Нэша..

6. Модель Эрроу-Дебре. Конкурентное равновесие. Сведение вопроса о существовании конкурентного равновесия к решению задачи дополнительности. Замкнутость отображений спроса и предложения. Теорема Эрроу-Дебре.

7. Неподвижные точки. Теоремы Брауэра и Какутани. Лемма Гейла - Никайдо - Дебре. Теорема Фань-Цзы.

8. Оптимальность по Парето конкурентного равновесия (первая теорема теории благосостояния). Теорема Дебре (вторая теорема теории благосостояния). Сравнительная статика в моделях конкурентного равновесия.

9. Проблемы коллективного выбора. Парадокс Эрроу.

10. Индексы неравенства и кривая Лоренца. Теорема мажоризации.


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


  1. Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.

  2. Кудрявцев В.В, Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М.: Наука, 1985.

  3. Мальцев А. И. Алгоритмы и вычислимые функции. М.: Наука, 1986.

  4. Оре О. Теория графов. М.: Наука, 1980.

  5. Кибернетический сборник. Вып. 1-9; вып. 1-28 (новая серия). М.: Мир, 1960-1990.

  6. Дискретная математика и математические вопросы кибернетики. Том I. / Под общ. ред. С. В. Яблонского и О. Б. Лупанова. М.: Наука, 1974.

  7. Нигматуллин Р. Г. Сложность булевых функций. М.: Наука, 1991.

  8. Проблемы кибернетики. Вып. 1-41. М.: Наука, 1959-1984.

  9. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990.

  10. Труды Математического института им. В. А. Стеклова. Том 51. М.: Изд-во АН СССР, 1958.

  11. Математические вопросы кибернетики. Вып. 1-10. М.: Наука, 1988-2001.

  1. Кострикин А.Н. Введение в алгебру.

  2. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1969.

  3. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986.

  4. Васильев Ф.П. Методы оптимизации. М.: Факториал, 2002.

  5. Карманов В.Г. Математическое программирование. М.: Наука, 2000.

  6. Понтрягин Л. Избранные научные труды, т.II. М.: Наука, 1988.

  7. Тихомиров В.М., Фомин С.В., Алексеев В.М. Оптимальное управление. М.: Наука, 1979.

  8. Краснощеков П.С., Петров А.А. Принципы построения моделей, М.: Фазис, 2002.

  9. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1981.

  10. Морозов В.В. Основы теории игр. М.: Изд-во МГУ, 2002.

  11. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. М.: Наука, 198 .

  12. Никайдо Х. Выпуклые структуры и математическая экономика. М.: Мир, 1972, 518с.

  13. Ашманов С.А. Введение в математическую экономику. М.: Наука, 1984, 294с.

  14. Экланд И. Элементы математической экономики. М.: Мир, 1983, 248с.

  15. Обен Ж.-П. Нелинейный анализ и его экономические приложения. М.: Мир, 1988, 264с.

  16. Маршалл А., Олкин И. Неравенства, теория мажоризации и ее приложения. М.: Мир, 1983, 574с.

  17. Мельников А.В. Стохастический анализ и расчет производных ценных бумаг. М.: ТВП, 1997, 125с.


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

  1. МакВильмс Ф. Дж., Слоэн Н. Дж. Теория кодов, исправляющих ошибки. М.: Связь, 1979.

  2. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984.

  3. Сэведж Дж. Э. Сложность вычислений. М.: Факториал, 1998.

  4. Марков А. А. Введение в теорию кодирования. М.: Наука, 1982.

  5. Орлов В. А. Простое доказательство алгоритмической неразрешимости неко­торых задач о полноте автоматных базисов. //Кибернетика. 1973. № 4. С. 109-113.

  6. Редькин Н. П. Надежность и диагностика схем. М.: Изд-во МГУ, 1992.

  7. Соловьев Н. А. Тесты (теория, построение, применения). Новосибирск: Наука, 1978.

  8. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1984.


Похожие:

Программа-минимум кандидатского экзамена по специальности 01. 01. 09 «Дискретная математика и математическая кибернетика» по физико-математическим наукам iconПрограмма-минимум кандидатского экзамена по специальности 01. 02. 04 «Механика деформируемого твердого тела» по физико-математическим наукам
...
Программа-минимум кандидатского экзамена по специальности 01. 01. 09 «Дискретная математика и математическая кибернетика» по физико-математическим наукам iconПрограмма-минимум кандидатского экзамена по специальности
Данная программа является единой по смежным отраслям наук –химическим, физико-математическим и техническим
Программа-минимум кандидатского экзамена по специальности 01. 01. 09 «Дискретная математика и математическая кибернетика» по физико-математическим наукам iconПрограмма-минимум кандидатского экзамена по специальности 14. 00. 21 «Стоматология» по медицинским наукам
Настоящая программа-минимум кандидатского экзамена по специальности «Стоматология» отражает современный уровень знаний в данной научной...
Программа-минимум кандидатского экзамена по специальности 01. 01. 09 «Дискретная математика и математическая кибернетика» по физико-математическим наукам iconПрограмма кандидатского экзамена по специальности 05. 27. 03 «Квантовая электроника» по физико-математическим и техническим наукам
В основу настоящей программы положены следующие дисциплины: электродинамика; квантовая механика; физическая оптика; физика твердого...
Программа-минимум кандидатского экзамена по специальности 01. 01. 09 «Дискретная математика и математическая кибернетика» по физико-математическим наукам iconПрограмма-минимум кандидатского экзамена по специальности 25. 00. 01 «Общая и региональная геология» по геолого-минералогическим наукам
Программа разработана экспертным советом Высшей аттестационной комиссии по наукам о Земле при участии Московского государственного...
Программа-минимум кандидатского экзамена по специальности 01. 01. 09 «Дискретная математика и математическая кибернетика» по физико-математическим наукам iconПрограмма вступительного экзамена в аспирантуру по специальности 01. 01. 09 «Дискретная математика и математическая кибернетика»
Спектр эрмитовой и унитарной матриц. Квадратичные формы: определение. Матрица квадратичной формы. Приведение квадратичной формы к...
Программа-минимум кандидатского экзамена по специальности 01. 01. 09 «Дискретная математика и математическая кибернетика» по физико-математическим наукам iconПрограмма вступительного экзамена по специальности научных работников 01. 01. 09 «Дискретная математика и математическая кибернетика»
Спектр эрмитовой и унитарной матриц. Квадратичные формы: определение. Матрица квадратичной формы. Приведение квадратичной формы к...
Программа-минимум кандидатского экзамена по специальности 01. 01. 09 «Дискретная математика и математическая кибернетика» по физико-математическим наукам iconПрограмма кандидатского экзамена по специальности 01. 01. 01 Вещественный, комплексный и функциональный анализ кэ. А. 03; цикл кэ. А. 00 «Кандидатские экзамены»
«Вещественный, комплексный и функциональный анализ» по физико-математическим и техническим наукам, утвержденной приказом Министерства...
Программа-минимум кандидатского экзамена по специальности 01. 01. 09 «Дискретная математика и математическая кибернетика» по физико-математическим наукам iconПрограмма-минимум кандидатского экзамена по специальности 25. 00. 02 «Палеонтология и стратиграфия» по геолого-минералогическим и биологическим наукам
Программа разработана экспертным советом Высшей аттестационной комисии по наукам о Земле при участии экспертного совета по биологическим...
Программа-минимум кандидатского экзамена по специальности 01. 01. 09 «Дискретная математика и математическая кибернетика» по физико-математическим наукам iconПрограмма кандидатского экзамена по специальности 05. 13. 18 «Математическое моделирование, численные методы и комплексы программ» по техническим наукам
В основе настоящей программы лежит материал курсов: функциональный анализ, математическая физика, теория вероятностей, математическая...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib2.znate.ru 2012
обратиться к администрации
Библиотека
Главная страница