1. Дискретная математика
Булевы функции. Проблема полноты. Теорема о полноте в P2. Функции k-значной логики. Теорема Кузнецова ([20], гл. 1, 2). ДНФ. Упрощение ДНФ. Геометрическая интерпретация. ДНФ типа åT. Теорема Журавлёва ([20], ч. V, гл. 1). Синтез схем из функциональных элементов. Нижняя оценка для функции L(n). Метод Шеннона. Метод Лупанова ([20], ч. V, гл. 2). Кодирование. Алфавитное кодирование, критерий однозначности декодирования. Коды с минимальной избыточностью. Самокорректирующиеся коды. Коды Хэмминга ([20], гл. 4). Принцип включения и исключения. Производящие функции и рекуррентные соотношения. Разбиения чисел и множеств. Матроиды и трансверсали. Теорема Холла и теорема Радо ([19], гл. 1-4; [9], гл. 3; [11], гл. 4). Графы. Матричная теорема Кирхгофа. Оценки числа вершинной независимости. Паросочетания. Хроматическое число и хроматический индекс графа. Критерии планарности. Эйлеровы графы. Достаточные условия гамильтоновости графа ([9], гл. 2, 4, 6, 7, 9). Автоматы. Регулярные языки и допускающие их автоматы ([2], гл. 9). Вычислимые функции. Эквивалентность класса рекурсивных функций и функций, вычислимых на машинах Тьюринга ([12], §§ 1, 2, 3.1-3.4, 12.1-12.3). Комбинаторные алгоритмы. Модели вычислений и сложность алгоритма. Алгоритмы сортировки. Поиск в графе. Кратчайшие пути. Минимальные остовные деревья. Наибольшие паросочетания. Алгоритм расстановки пометок для построения максимального потока. Классы P и NP. Полиномиальная сводимость и NP-полные задачи. Сильная NP-полнота ([2], гл.1, [8], гл. 1-4; [9], гл. 12; [11], гл. 2, 3, 4).
2. Математическое программирование
Основные понятия теории экстремальных задач. Глобальный и локальный минимум Задачи минимизации функций без ограничений. Необходимые условия локального минимума первого и второго порядка. Достаточные условия строгого локального минимума. ([1], § 3.1.1; [6], гл. 3, §2; [7], Введение, § 2.1). Задача нелинейного программирования. Необходимые условия Зойтендейка и условие Каруша–Джона. Достаточные условия оптимальности первого порядка в задаче нелинейного программирования. Условия оптимальности второго порядка. [18], гл. 4, § 1; [7], § 3; [6], гл. 3, §§ 1 – 4). Минимизация негладких функций. Векторная оптимизация. ([6], гл. 3, §§ 5, 6). Задача выпуклого программирования. Условия оптимальности (необходимые и/или достаточные) для решений задачи выпуклого программирования. Условия регулярности Слейтера. Теорема Куна–Таккера. Двойственная задача выпуклого программирования. ([16], гл. 3, § 1; [18], гл. 4, §§ 2, 3; [7], § 2.3; [6], гл. 2). Задача линейного программирования. Критерий оптимальности решений в задаче линейного программирования. Двойственная задача линейного программирования. Теоремы двойственности. Симплекс–метод. Метод эллипсоидов. ([15], гл. 2, 3, 8; [5], гл. 3; [18], гл. 4, § 1; [7], § 3; [6], гл. 1). Целочисленное линейное программирование. Вполне унимодулярность. Алгоритм Гомори. Метод "ветвей и границ" ([15], гл. 13, 14, 18). Численные методы минимизации. Методы одномерной минимизации (метод деления отрезка пополам, метод ломаных, метод касательных, метод золотого сечения). Методы безусловной минимизации функций многих переменных (градиентные методы, ньютоновские методы, методы случайного поиска). Методы условной минимизации. (метод проекций градиента, метод условного градиента, метод возможных направлений, метод множителей Лагранжа, метод штрафных функций). ([5], гл. 1, 5; [6], гл. 4). Динамическое программирование ([6], гл. 5). Теория игр. Игры двух лиц. Матричные игры. Чистые и смешанные стратегии. Теорема о минимаксе для матричных игр. Некооперативные и кооперативные игры n–лиц. ([1], [13], гл. 7,12, 13; [14]).
3. Вариационные задачи и задачи оптимального управления
Простейшая задача вариационного исчисления. Понятия слабого и сильного локального минимума. Уравнение Эйлера. Условия Лежандра и Якоби. Необходимое условие Вейерштрасса для сильного локального минимума. Достаточные условия слабого локального минимума. ([7], §§ 4,5; [1] §§ 1.4, 4.1, 4.4; [6], гл. 6). Простейшая задача терминального управления. Принцип максимума. Задачи оптимального управления с ограничениями на правый конец траекторий. ([7], § 6; [1], § § 1.5, 4.2; [6], гл. 7; [17]). Динамическое программирование в теории оптимального управления ([4], [6], гл.7). Связь методов вариационного исчисления, принципа максимума и динамического программирования ([6], гл. 6; 7, § 2). Проблема синтеза оптимальных систем ([17], гл. 1, § 5). Основные понятия теории дифференциальных игр ([17], гл. 4, § 28; [6], гл.7, § 8, [10]).
4. Элементы математической экономики
Модель Леонтьева. Модель Неймана–Гейла. Теория экономического равновесия. Отношения предпочтения и функции полезности. Неоклассическая теория спроса. Модель Вальраса. Модели динамического равновесия. ([3], ч. I, II; [13], гл. 10,11).
Литература
1. , , Фомин управление. – М.: Наука, 1979.
2. Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.
3. Ашманов в математическую экономику. – М.: Наука, 1984.
4. инамическое программирование. — М.: Изд-во иностранной литера туры. 1960.
5. Васильев методы решения экстремальных задач. – М.: Наука, 1980.
6. Кириллова оптимизации. – Минск: Изд–во БГУ, 1981.
7. , Тихомиров курс теории экстремальных задач. – М.: Изд--во МГУ, 1989.
8. ычислительные машины и труднорешаемые задачи. – М.: Мир, 1982.
9. , , Тышкевич по теории графов. – М.: Наука, 1990.
10. Красовский управления движением. — М.: Наука, 1968.
11. омбинаторика для программистов. – М.: Мир, 1988.
12. Мальцев и вычислимые функции. – М.: Наука, 1965.
13. --П. Нелинейный анализ и его экономические приложения. – М.: Мир, 1988.
14. еория игр. – М.: Мир, 1971.
15. омбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир, 1985.
16. Поляк в теорию оптимизации. – М.: Наука, 1983.
17. , , Мищенко тическая теория оптимальных процессов. — М.: Наука, 1976.
18. Пшеничный анализ и экстремальные задачи. – М.: Наука, 1980.
19. омбинаторика. – М.: Мир, 1970.
20. Яблонский в дискретную математику. – М.: Наука, 1986.
|
