«Утверждаю» | |
Председатель Ученого совета математико-механического факультета СПбГУ, декан математико-механического факультета СПбГУпрофессор ________________ «12» мая 2011 г. |
Программа вступительного экзамена
по специальности 01.01.09
«Дискретная математика и математическая кибернетика»
Утверждена на заседании Ученого совета математико-механического факультета СПбГУ, протокол от 01.01.2001 г.
Программа утверждена на заседаниикафедры исследования операций протокол от «6» мая 2011 г. Заведующий кафедрой, |
Санкт-Петербург
2011
Кафедра исследования операций
Выписка из протокола заседания кафедры
N 4 от 6 мая 2011 года
ПРОГРАММА ВСТУПИТЕЛЬНОГО ЭКЗАМЕНА В АСПИРАНТУРУ
ПО СПЕЦИАЛЬНОСТИ
01.01.09 - «Дискретная математика и математическая кибернетика»
на 2011 год
Часть 1. Общеобразовательная
1. Матричная алгебра
Конечномерное линейное пространство. Линейные комбинации. Линейная независимость. Полнота. Базис. Линейный оператор в конечномерном линейном пространстве. Матрица. Замена базиса. Свойства определителей. Разрешимость квадратных систем линейных алгебраических уравнений. Обратная матрица. Прямоугольные системы: теорема Кронекера - Капелли. Характеристический многочлен. Теорема Гамильтона - Кэли. Минимальный многочлен вектора и матрицы. Собственные числа и собственные векторы. Инвариантное подпространство. Жорданова форма. Унитарное пространство. Эрмитовы и унитарные матрицы. Нормальные матрицы. Существование ортонормированного собственного базиса у нормальной матрицы. Спектр эрмитовой и унитарной матриц. Квадратичные формы: определение. Матрица квадратичной формы. Приведение квадратичной формы к сумме квадратов методом Лагранжа. Положительно определённые формы. Критерий Сильвестра. Одновременное приведение пары квадратичных форм к сумме квадратов.
Литература: 1. Гантмахер матриц. М., Наука, 1967.
2.Глазман линейный анализ.
2. Теория функций действительной переменной
Интеграл Римана. Алгебра множеств, 
- алгебра множеств. Определение счётно-аддитивной меры. Мера Каратеодори. Прямое произведение мер. Мера Лебега в R. Интеграл Лебега. Теоремы о предельном переходе под знаком интеграла. Пространства 
, 
. Ряды и интегралы Фурье. Преобразования Фурье и Лапласа. Неравенства Коши-Буняковского, Гёльдера, Минковского.
Литература 1. Натансон функций вещественной переменной. М.-Л., 1950.
2. Шварц Дж. Линейные операторы. Общая теория. М., 1962.
3. Теория функций комплексной переменной
Определение аналитической функции. Условия Коши-Римана. Теоремы Коши и Морера. Формула Коши. Принцип максимума модуля. Разложение аналитической функции в ряд Тейлора. Круг сходимости. Ряд Лорана. Классификация особенностей. Вычисление интеграла по контуру, включающему изолированные особенности. Вычеты. Экспонента и тригонометрические функции. Формула Эйлера. Многозначные аналитические функции. Корень и логарифмы. Приращение аргумента. Принцип аргумента и теорема Руше. Функции от матриц и проектор Рисса. Пространства Харди в круге и в полуплоскости. Две теоремы Винера - Пели.
Литература: 1. Привалов в теорию функций комплексного переменного. М., 1954.
2. Банаховы пространства аналитических функций. М.,1963.
4. Функциональный анализ
1. Линейные нормированные пространства. Полунормы и нормы. Их свойства. Теорема о топологиях, задаваемых семейством полунорм.
2. Банаховы и Гильбертовы пространства. Ограниченные и неограниченные операторы. Линейные функционалы.
3. Теорема Стоуна - Вейерштрасса.
4. Неравенства Гёльдера и Минковского.
5. Гильбертовы пространства (скалярное произведение, его свойства, теоремы об ортогональной проекции).
6. Полнота.
7. Теорема об ортогональном разложении. Неравенство Бесселя,
неравенство Парсеваля.
8.Теорема Рисса об общем виде функционала в гильбертовом пространстве.
9. Теорема Банаха - Штейнгауза.
10. Теорема Банаха о замкнутом графике.
11. Теорема Хана - Банаха.
12. Слабые и сильные топологии. Их свойства.
13. Теорема Хаусдорфа и критерии компактности.
14. Вполне непрерывные операторы и теорема об их свойствах.
15. Нормальные и самосопряжённые операторы. Теорема Гильберта - Шмидта.
16. Дифференциалы Фреше и Гато.
17. Теорема о неявной функции и её применения.
18. Исчисление дифференциалов Фреше и Гато.
Литература: 1., Акилов анализ. М., 1984.
2. Функциональный анализ. М., 1975.
3. Балакришнан функциональный анализ. М., 1980.
4. Дифференциальное исчисление. М., 1971.
Часть II специальная (для кафедры теоретической кибернетики)
5. Линейная теория регулирования
1. Способы задания динамических блоков. Понятие динамического оператора.
2. Управляемые системы. Теорема об эквивалентности 4-х условий управляемости. Свойства управляемых систем.
3. Полная система инвариантов при линейных преобразованиях состояния системы для множества управляемых пар.
4. Приведение управляемых систем к стандартному виду.
5. Наблюдаемые системы. Свойства наблюдаемости. Теорема двойственности Калмана.
6. Полная система инвариантов для наблюдаемых систем, а также для управляемых и наблюдаемых систем.
7. Синтез системы по передаточной функции.
8. Преобразование обратной связи. Полная система инвариантов при преобразованиях обратной связи.
9. Теорема о произвольном изменении спектра матрицы коэффициентов при преобразованиях обратной связи.
10. Критерий Михайлова - Найквиста.
Литература: 1. Воронов , управляемость, наблюдаемость. М., 1979, гл. 1,2,5.
2. Первозванский теории автоматического управления. М., 1986, гл. 1, 2, 3, 6, 7.
3. Справочник по теории автоматического управления. Под ред. , М., 1987, гл. 1, 2.
4. , , Якубович нелинейных систем с неедииственным состоянием равновесия. М., 1978, гл. 1.
6. Частотные методы исследования нелинейных систем (нелинейная теория регулирования)
1. Частотная теорема.
2. S - процедура. Теоремы Дайнса и Хаусдорфа.
3. Нелинейные системы квадратичного топологического типа.
4. Квадратичный критерий для локальных и интегральных связей.
5. Свойства решений систем квадратичного топологического типа.
6. Круговой критерий (скалярный и матричный случай).
7. Критерий Попова.
8. Критерий абсолютной устойчивости (неустойчивости) для дифференцируемых нелинейностей.
9. Критерии автоколебаний.
10. Диссипативность. Квадратичный критерий диссипативности. Частотные критерии диссипативности для одной нелинейности.
11. Частотные условия существования и устойчивости в целом вынужденных режимов: а) периодических; б) почти периодических; в) стационарных.
Литература: 1. Воронов , управляемость, наблюдаемость. М., 1979, гл. 1, 2, 5.
2. Первозванский теории автоматического управления. М., 1986, гл. 1, 2, 3, 6, 7.
3. Справочник по теории автоматического управления. Под ред. , М., 1987, гл. 1, 2.
4. , , Якубович нелинейных систем с неединственным состоянием равновесия. М., 1978, гл.1.
5. Методы исследования нелинейных систем автоматического управления. М., 1975, гл. 2, 3.
7. Теория оптимального управления
1. Постановка задачи об оптимальном управлении. Связь с вариационным исчислением. Абстрактная задача об оптимальном управлении.
2. Абстрактная задача оптимизации без дополнительных ограничений. Лемма о приращении сложной функции. Дифференцирование сложной функции по пучку кривых. Теоремы о необходимых условиях экстремума.
3. Дифференцирование интегрального функционала по пучку простых игольчатых вариаций.
4. Абстрактный принцип максимума в задаче без дополнительных ограничений.
5. Условия, при которых абстрактный принцип максимума — достаточный критерий оптимальности.
6. Принцип максимума Понтрягина для обыкновенных дифференциальных уравнений (в задаче без дополнительных ограничений): а) как необходимое условие; б) как достаточное условие.
7. Вариационное исчисление. Уравнение Эйлера. Два условия Эрдмана - Вейерштрасса. Условие Лежандра. Условие Вейерштрасса.
8. Аналитическая теория конструирования оптимальных регуляторов (нестационарные системы, конечный временной интервал). Уравнение Лурье — Риккати.
9. Аналитическая теория конструирования оптимальных регуляторов ( стационарные системы, бесконечный временной интервал). Уравнение Лурье.
10. Частотная теорема.
11. Фильтрация. Фильтр Калмана (нестационарные системы, конечный временной интервал).
12. Фильтрация. Фильтр Винера-Калмана (стационарные системы, бесконечный временной интервал).
Литература: 1. , , Мищенко теория оптимальных процессов. М., 1973.
2. , , Фомин управление. М.,1979.
3. , Якубович теория оптимального управления. Сиб. Матем. журнал:
1) т.8, № 3, 1977, с.685-707;
2) т.19,№2, 1978, с.436-460; Ш, т.20, № 4, 1979, с.385-410.
8. Рекуррентное оценивание и адаптивная фильтрация
1. Байесовские критерии (1, 81.2).
2. Элементы регрессионного анализа (1, 8 1.3).
3. Элементы теории оценивания (1, 81.4).
4. Конечно-сходящиеся алгоритмы и их стохастические аналоги (1, 8 2.1).
5. Метод стохастической аппроксимации в задаче самообучения (1, 8 2.2).
6. Рекуррентное байесовское оценивание (1, 82.3).
7. Робастное оценивание (3, гл.4).
8. Абсолютно оптимальные алгоритмы идентификации (3, гл. З).
9. Модифицированные алгоритмы идентификации (3, гл.8).
10. Фильтр Винера - Колмогорова (1, 83.1).
11. Фильтр Калмана - Бьюси (1, 83.2).
12. Применение принципа максимума в теории фильтрации (2, 8 27).
13. Оптимальная фильтрация коррелированных сигналов (2, 8 30).
14. Экстраполяция и интерполяция случайных последовательностей (2, 8 3.2).
15. Глобальная теория фильтрации (2, 8 29).
16. Минимаксная фильтрация (1, 8 3.3).
17. Адаптивные фильтры (1, 8 4.3).
Литература: 1. Фомин оценивание и адаптивная фильтрация. М., Наука, 1984.
2. Ройтенберг управление М., 1978.
3. З. Основы информационной теории идентификации. М.,1984.
9. Оптимальная фильтрация
1. Линейное оценивание случайных процессов в классе устойчивых фильтров.
2. Причинное пространство и финитные в нем операторы.
3. Расширенное причинное пространство и линейные в нем преобразования.
4. Связь устойчивости и каузальности операторов в расширенном причинном пространстве.
5. Абстрактный вариант теории Винера - Колмогорова оптимального оценивания случайных элементов.
6. Оптимальное оценивание случайных элементов в пространстве с дискретной временной структурой.
7. Спектральная факторизация положительных операторов.
8. «Усиленная» спектральная факторизация.
9. Структура оптимального фильтра в случае дискретного времени. Формула Боде - Шеннона.
10. Спектральная факторизация положительных операторов в дискретном причинном пространстве.
11. Связь задачи спектральной факторизации с задачей минимизации квадратичных функционалов.
Литература: 1. , Фомин фильтрация случайных процессов. Уч. пособие. Л., 1991.
2. Фомин методы теории линейной фильтрации случайных процессов. СПб., 1995.
3. Яглом теория стационарных случайных процессов. Л., 1981.
Часть П специальная (для кафедры исследования операций)
5. Теория оптимального управления
1. Постановка задачи об оптимальном управлении. Связь с вариационным исчислением. Абстрактная задача об оптимальном управлении.
2. Абстрактная задача оптимизации без дополнительных ограничений. Лемма о приращении сложной функции. Дифференцирование сложной функции по пучку кривых. Теоремы о необходимых условиях экстремума.
3. Дифференцирование интегрального функционала по пучку простых игольчатых вариаций.
4. Абстрактный принцип максимума в задаче без дополнительных ограничений.
5. Условия, при которых абстрактный принцип максимума — достаточный критерий оптимальности.
6. Принцип максимума Понтрягина для обыкновенных дифференциальных уравнений (в задаче без дополнительных ограничений): а) как необходимое условие; б) как достаточное условие.
7. Вариационное исчисление. Уравнение Эйлера. Два условия Эрдмана - Вейерштрасса. Условие Лежандра. Условие Вейерштрасса.
8. Аналитическая теория конструирования оптимальных регуляторов (нестационарные системы, конечный временной интервал). Уравнение Лурье — Риккати.
9. Аналитическая теория конструирования оптимальных регуляторов ( стационарные системы, бесконечный временной интервал). Уравнение Лурье.
10. Частотная теорема.
11. Фильтрация. Фильтр Калмана (нестационарные системы, конечный временной интервал).
12. Фильтрация. Фильтр Винера - Калмана (стационарные системы, бесконечный временной интервал).
Литература: 1. , , Мищенко теория оптимальных процессов. М., 1973.
2. , Тихомиров В-М., Фомин управление. М.,1979.
3. , Якубович теория оптимального управления. Сиб. Матем. журнал 1, т.8, № 3, 1977, с.685-707;
П, т.19,№2, 1978, с.436-460; Ш, т.20, № 4, 1979, с.385-410.
6. Математическое программирование
1. Постановка задачи линейного программирования. Прямая и двойственная задача. Теория двойственности. Критерий оптимальности.
2. Базисные решения задач ЛП.
3. Методы решения задач линейного программирования. Симплекс-метод и его модификации. Мультипликативное представление обратной базисной матрицы. Небазисные методы решения задач ЛП. Метод генерирования столбцов.
4. Частные случаи задач линейного программирования и специальные методы их решения. Транспортная задача ЛП в матричной и сетевой постановке. Специальные методы их решения, в частности метод потенциалов и венгерский метод.
5. Вырожденные случаи транспортной задачи. Задача о назначениях, задачи о потоках в сетях.
6. Задачи дискретного программирования и методы их решения. Классификация задач дискретного программирования по сложности. Задача о ранце. Методы улучшенного перебора.
7. Динамическое программирование. Различные методы
Литература: 1. Данциг Дж. Линейное программирование.
2. Динамическое программирование. М.,1979.
3. Романовский решения экстремальных задач. М,, 1977.
7. Теория игр
1. Игра в нормальной форме. Ситуация равновесия по Нэшу. Свойства
ситуаций равновесия в антагонистической игре. Теорема о минимаксе.
2.Смешанные стратегии. Теорема Нэша. Сведение решения матричных игр к задачам линейного программирования. Достаточные условия существования значения антагонистической игры ( теорема Вальда).
3. Позиционные игры. Нахождение ситуации равновесия в конечной позиционной игре с полной информацией.
4. Кооперативные игры. Примеры. С-ядро, необходимое и достаточное условие его непустоты.
Вектор Шепли. Его вероятностные интерпретации и аксиоматические обоснования Янгом и Шепли. Вектор Шепли для игр голосования. Вектор Банзафа. N-ядро, его существование и одноточечность.
5. Проблема решения по Нейману-Моргенштерну в кооперативных играх.
Литература. 1.Г. Оуэн “ Теория игр “, М, 1973
2. “ Теория игр для экономистов – кибернетиков “ Л.,1973
3. Э. Мулен “Кооперативное принятие решений : аксиомы и модели “ . М., “Мир” , 1991.
8 Векторная оптимизация
1. Постановка задачи. Построение решений по бинарным отношениям. Достаточные условия непустоты множества максимальных элементов бинарных отношений.
2. Парето-оптимальные и слабо Парето-оптимальные множества. Их параметрическое представление. Арбитражные схемы Нэша и Калаи- Смородинского.
3. Теорема Биркгофа о представимости полного транзитивного отношения, инвариантного относительно сдвига. Отношения, инвариантные при независимых сжатиях координат. Теорема Биркгофа для функции выбора.
4. Теория средних. Аксиоматические обоснования обобщенных средних по Колмогорову. Обобщенные средние, инвариантные относительно общего сдвига. Положительно однородные обобщенные средние. Аксиоматическое обоснование порядковой статистики.
5. Теорема Фишберна - Рубинштейна об усреднении векторов.
6. Коммутирование усредняющих операторов. Парадокс Острогорского и его обобщения.
7. Основные парадоксы теории голосования
Литература. 1. , Алескеров вариантов: основы теории. М., 1990.
2. , Ногин - оптимальные решения многокритериальных задач. М.,1982.
3. Наумова предпочтения в задачах векторной оптимизации. СПб, 2002.
Зав. кафедрой,
Петров
