«Утверждаю» |
Председатель Ученого совета математико-механического факультета СПбГУ, декан математико-механического факультета СПбГУпрофессор ________________ «10» мая_2012 г. |
ПРОГРАММА ВСТУПИТЕЛЬНОГО ЭКЗАМЕНА
ПО СПЕЦИАЛЬНОЙ ДИСЦИПЛИНЕ
на основную образовательную программу
послевузовского профессионального образования (аспирантура)
«Теоретическая кибернетика»
по специальности научных работников
01.01.09 «Дискретная математика и математическая кибернетика»
Утверждена на заседании Ученого совета математико-механического факультета СПбГУ, протокол № 5 от 01.01.2001г.
Санкт-Петербург
2012
Специализация «Информатика», «Исследование операций» и «Прикладная кибернетика»
Часть 1. Общеобразовательная
1. Матричная алгебра
Конечномерное линейное пространство. Линейные комбинации. Линейная независимость. Полнота. Базис. Линейный оператор в конечномерном линейном пространстве. Матрица. Замена базиса. Свойства определителей. Разрешимость квадратных систем линейных алгебраических уравнений. Обратная матрица. Прямоугольные системы: теорема Кронекера - Капелли. Характеристический многочлен. Теорема Гамильтона - Кэли. Минимальный многочлен вектора и матрицы. Собственные числа и собственные векторы. Инвариантное подпространство. Жорданова форма. Унитарное пространство. Эрмитовыи унитарные матрицы. Нормальные матрицы. Существование ортонормированного собственного базиса у нормальной матрицы. Спектр эрмитовой и унитарной матриц. Квадратичные формы: определение. Матрица квадратичной формы. Приведение квадратичной формы к сумме квадратов методом Лагранжа. Положительно определённые формы. Критерий Сильвестра. Одновременное приведение пары квадратичных форм к сумме квадратов.
Литература
Теория матриц. М., Наука, 1967. Конечномерный линейный анализ.2. Теория функций действительной переменной
Интеграл Римана. Алгебра множеств, 
- алгебра множеств. Определение счётно-аддитивной меры. Мера Каратеодори. Прямое произведение мер. Мера Лебега в R. Интеграл Лебега. Теоремы о предельном переходе под знаком интеграла. Пространства 
, 
. Ряды и интегралы Фурье. Преобразования Фурье и Лапласа. Неравенства Коши-Буняковского, Гёльдера, Минковского.
Литература
Теория функций вещественной переменной. М.-Л., 1950. Шварц Дж. Линейные операторы. Общая теория. М., 1962.3. Теория функций комплексной переменной
Определение аналитической функции. Условия Коши-Римана. Теоремы Коши и Морера. Формула Коши. Принцип максимума модуля. Разложение аналитической функции в ряд Тейлора. Круг сходимости. Ряд Лорана. Классификация особенностей. Вычисление интеграла по контуру, включающему изолированные особенности. Вычеты. Экспонентаи тригонометрическиефункции. Формула Эйлера. Многозначные аналитические функции. Корень и логарифмы. Приращение аргумента. Принцип аргумента и теорема Руше. Функции от матриц и проектор Рисса. Пространства Харди в круге и в полуплоскости. Две теоремы Винера - Пели.
Литература
Введение в теорию функций комплексного переменного. М., 1954. анаховы пространства аналитических функций. М.,1963.4. Функциональный анализ
1. Линейные нормированные пространства. Полунормы и нормы. Их свойства. Теорема о топологиях, задаваемых семейством полунорм.
2. Банаховы и Гильбертовы пространства. Ограниченные и неограниченные операторы. Линейные функционалы.
3. Теорема Стоуна - Вейерштрасса.
4. Неравенства Гёльдера и Минковского.
5. Гильбертовы пространства (скалярное произведение, его свойства, теоремы об ортогональной проекции).
6. Полнота.
7. Теорема об ортогональном разложении. Неравенство Бесселя,
неравенство Парсеваля.
8.Теорема Рисса об общем виде функционала в гильбертовом пространстве.
9. Теорема Банаха - Штейнгауза.
10. Теорема Банаха о замкнутом графике.
11. Теорема Хана - Банаха.
12. Слабые и сильные топологии. Их свойства.
13. Теорема Хаусдорфа и критерии компактности.
14. Вполне непрерывные операторы и теорема об их свойствах.
15. Нормальные и самосопряжённые операторы. Теорема Гильберта - Шмидта.
16. Дифференциалы Фреше и Гато.
17. Теорема о неявной функции и её применения.
18. Исчисление дифференциалов Фреше и Гато.
Литература
, Функциональный анализ. М., 1984. ункциональный анализ. М., 1975. Прикладной функциональный анализ. М., 1980. ифференциальное исчисление. М., 1971.Часть II специальная
5. Логика и теория алгоритмов
1. Исчисление высказываний и его свойства.
2. Исчисление предикатов первого порядка и его свойства.
3. Исчисление предикатов с равенством.
4. Формальная арифметика.
5. Теорема Геделя о неполноте арифметики.
6. Машины Тьюринга.
7. Нормальные алгорифмы.
8. Элементарные по Кальмару алгорифмы.
9. Перечисление графов.
10. Теорема Пойа.
11. Анализ сложности алгоритма сортировки Шелла.
12. Алгоритмы глобального анализа графов.
13. Эквивалентность некоторых комбинаторных задач. Классы Р и NP. NP-трудные и NP-полные задачи.
Литература
лгоритмы: построение и анализ. —МЦНМО, 1999. Основы теории элементарных алгоритмов. — Л.: Изд-во Ленингр. ун-та, 1987. , Теория алгоритмов: основные открытия и приложения. — М.: Наука, 1987. 4. онкретная математика. Основание информатики. — М.: Мир, 1998. еречисление графов. — М.: Мир, 1982. Кнут Дональд. Искусство программирования, том 1. Основные алгоритмы (3-е изд.). — М.: Издательский дом "Вильямс", 2000.6. Теория формальных языков и трансляций
1. Формальные грамматики, их основные классы. КС-грамматики и деревьявыводов в них. Приведенные и неукорачивающие КС-грамматики. Нормальные формы неукорачивающих КС-грамматик.
2. Однозначность и существенная неоднозначность КС-языков. Примеры не КС-языков.
3. Автоматные грамматики и конечные автоматы. Регулярные выражения. Детерминированные конечные автоматы.
4. МП-автоматы различных типов, их эквивалентность КС-грамматикам. Детерминированные автоматы и языки, их основные свойства.
5. LR(k)-грамматики и языки, их основные свойства.
6. Определение трансляции как формального объекта.
7. Простые синтаксически-управляемые трансляции. Эквивалентность простых схем синтаксически-управляемых трансляций и недерминированных магазинных преобразователей.
8. Эквивалентность магазинных преобразователей, реализующих трансляции при конечном состоянии и при пустом магазине.
9. Простые семантически однозначные схемы синтаксически-управляемых трансляций и детерминированные магазинные преобразователи.
10. Определение класса LL(k)-грамматик. Необходимые и достаточные признаки LL(k)-грамматик.
11. Алгоритм тестирования КС-грамматики на ее принадлежность классу LL(k)-грамматик для заданного значения k.
12. Специальные необходимые и достаточные условия LL(1)-грамматик. Сильные LL(k)-грамматики.
13. k-предсказывающие алгоритмы анализа и трансляции, задаваемые при помощи k-предсказывающих алгоритмов анализа (использование этих алгоритмов в качестве анализаторов LL(k)-языков).
14. LL(k)-таблицы. Построение множества необходимых и достаточных таблиц для анализа LL(k)-языков.
15. Оценка числа шагов k-предсказывающего алгоритма анализа.
16. Реализация простых семантически однозначных трансляций с входными языками класса LL(k) при помощи k-предсказывающих алгоритмов трансляции.
Литература
1. Ульман Дж. Теория синтаксического анализа, перевода и компиляции. В 2-х т. — М.: Мир, 1978. 2. Синтаксически управляемая обработка данных — СПб.: Изд-во СПбГУ, 1997. 3. Формальные грамматики. — Л.: Изд-во ЛГУ. — 1984.7. Компьютерное моделирование динамических систем
1.Динамические системы. Определения. Фазовое пространство динамических систем. Неподвижные и периодические точки дискретных динамических систем, типы устойчивости.
2. Понятие чувствительной зависимости от начальных данных. Хаотические режимы.
3.Логистическое уравнение. Бифуркация удвоения периода, константа Фейгенбаума. Логистическое уравнение для 
. Канторово множество и его построение с помощью логистического уравнения.
4.Фрактальные множества и фрактальные размерности. Хаусдорфова размерность. Алгоритмы вычисления размерностей.
5.Характеристики хаотического движения: показатель Ляпунова. Показатель Ляпунова для треугольного и логистического уравнений. Алгоритмы вычисления ляпуновских показателей.
6.Аттракторы динамических систем. Определение и примеры.
7.Методы построения инвариантных многообразий седловых гиперболических точекплоскости. Гомоклинические точки.
8.Приближенное интегрирование траекторий. Устойчивость численных методов.
9.Исследование динамических систем методами символической динамики. Пространства сдвига, клеточные отображения, символический образ.
10. Клеточные автоматы. Связь клеточных автоматов с теорией формальных языков и грамматик.
11.Методы нелинейной динамики для анализа временных рядов. Реконструкция аттракторов. Теорема Такенса.
Литература
,, , Динамика одномерных отображений. Киев: Наукова думка, 1989. Parker T. S, Chua L. O. Practical numerical algorithms for chaotic systems. N. Y., 1989. , . Современные проблемы нелинейной динамики. М. 2000. П. Биллингслей. Эргодическая теория и информация. М.1969. О символическом образе динамической системы, сб. Граничные задачи, Пермь, 1983, 101-105.8. Линейная теория регулирования
1. Способы задания динамических блоков. Понятие динамического оператора.
2. Управляемые системы. Теорема об эквивалентности 4-х условий управляемости. Свойства управляемых систем.
3. Полная система инвариантов при линейных преобразованиях состояния системы для множества управляемых пар.
4. Приведение управляемых систем к стандартному виду.
5. Наблюдаемые системы. Свойства наблюдаемости. Теорема двойственности Калмана.
6. Полная система инвариантов для наблюдаемых систем, а также для управляемых и наблюдаемых систем.
7. Синтез системы по передаточной функции.
8. Преобразование обратной связи. Полная система инвариантов при преобразованиях обратной связи.
9. Теорема о произвольном изменении спектра матрицы коэффициентов при преобразованиях обратной связи.
10. Критерий Михайлова - Найквиста.
Литература
Устойчивость, управляемость, наблюдаемость. М., 1979, гл. 1,2,5. Курс теории автоматического управления. М., 1986, гл. 1, 2, 3, 6, 7. Справочник по теории автоматического управления. Под ред. , М., 1987, гл. 1, 2. , , Устойчивость нелинейных систем с неединственным состоянием равновесия. М., 1978, гл. 1.Специализация «Статистическое моделирование»
I. Элементы дискретной математики
1. Множества и операции над ними. Мощности множества. Отношения
и их свойства.
2. Алгебры. Логические функции.
3. Графы. Способы задания и геометрическая интерпретация графов.
Основные свойства. Связность. Планарность. Деревья. Представ-
ления графов в ЭВМ.
4. Конечные геометрии. Латинские квадраты. Блок-схемы.
II. Теория вероятностей и математическая статистика
1. Аксиоматика. Свойства вероятности. Условные вероятности.
Независимость событий.
2. Законы распределения случайных величин. Типы распределений.
Свойства функции распределения и плотности. Независимость
случайных величин. Конкретные законы (нормальное и связанные
с ним распределения, распределения схемы Бернулли, распреде-
ление Пуассона).
3. Числовые характеристики случайных величин. Свойства матема-
тического ожидания и дисперсии. Моменты. Ковариационная
матрица. Свойства коэффициента корреляции.
4. Сходимость последовательностей случайных величин. Закон
больших чисел. Центральная предельная теорема.
5. Оценка параметров. Теория оценивания с минимальной дисперсией.
Метод максимального правдоподобия.
6. Проверка статистических гипотез. Основные критерии (хи-
квадрат, Стьюдента и Фишера).
7. Метод наименьших квадратов. Регрессионный и дисперсионный
анализы.
III. Дискретные цепи Маркова
1. Классификация марковских цепей. Возвратность. Матрица перехода
и ее свойства. Теорема о предельном поведении переходных
вероятностей в марковский цепи.
2. Условные вероятности и условные математические ожидания.
Условные распределения и их свойства. Условные гауссовские
распределения.
3. Марковские цепи с произвольным пространством состояний.
Конечномерные распределения. Поглощающие состояния.
IV. Метод Монте-Карло
1. Моделирование случайных величин. Основные методы получения
псевдослучайных чисел. Методы моделирования случайных величин
с заданным распределением. Трудоемкость моделирования.
Моделирование марковских процессов. Моделирование гауссовских
процессов. Моделирование стационарных в широком смысле
процессов.
2. Методы оценивания интегралов. Метод уменьшения трудоемкости.
Оценки по поглощению и столкновению для решения интегральых
уравнений. Решение задач переноса излучений. Решение простейших
задач математической физики.
3. Принципы и методы имитационного моделирования.
V. Теория автоматов
1. Понятие о вероятностном конечном автомате. Автоматы частного
вида. Детерминированные автоматы.
2. Способ задания вероятностных автоматов. Методы задания детер-
минированных автоматов (графы, автоматная матрица, таблицы
переходов и выходов, системы канонических уравнений).
VI. Экстремальные задачи
1. Оптимизационные задачи на графах. Алгоритмы построения крат-
чайших деревьев, кратчайших путей, критических путей. Потоки
в сетях.
2. Необходимые условия экстремума. Метод множителей Лагранжа.
Теорема Куна-Таккера. Понятие о двойственности. Линейное
программирование.
3. Приближенные методы решения экстремальных задач. Градиентный
метод. Метод Ньютона. Методы решения одномерных задач. Метод
золотого сечения.
4. Многокритериальная оптимизация. Оптимум Парето.
VII. ЭВМ и программирование
1. История развития вычислительной техники. Принцип действия
ЭВМ. Архитектура современных ЭВМ.
2. Операционные системы. Управление памятью. Управление процес-
сами. Управление процессором. Управление устройствами.
Управление файлами.
3. Основные этапы решения задач на ЭВМ. Алгоритмические языки
высокого уровня. Объектно-ориентированный подход.
ЛИТЕРАТУРА
Вероятность. М., МЦНМО, 2007 Теория вероятностей. М., Либроком, 2009. Численные методы Монте-Карло. М., Наука, 1974. , Курс статистического моделирования. М., Наука, 1982. , Математическая теория оптимального эксперимента. М., Наука, 1987. Вариационные методы в математической физике. М., Наука, 1970. рафы, сети и алгоритмы. М., Мир, 1984. Исследование операций. М., Высшая школа, 1972. митационное моделирование систем - искусство и наука. М., Мир, 1978. , Стационарные детерминированные и вероятностные автоматы (Теория автоматных моделей). СПб: Издательство СПбГУ, 2008. Математическое программирование. М., Наука, 1985. Методы решения экстремальных задач. 1981, М.,Физмат., 455 с. Исследование операций. М., Высшая школа, 1986, 320 с. Прикладной регрессионный анализ. Множественная регрессия. М. Диалектика, 2011 атематические методы в статистике. М., РХД, 2003. Метод Монте-Карло в вычислительной математике. Вводный курс. - СПб.: Невский Диалект, М.: Бином. Лаборатория знаний, 2009, 192 с.Специализация «Теоретическая кибернетика»
1. Линейная теория регулирования
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.
2. Частотные методы исследования нелинейных систем (нелинейная теория регулирования)
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.
3. Теория оптимального управления
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.
4. Рекуррентное оценивание и адаптивная фильтрация
1. Байесовские критерии (1, §1.2).
2. Элементы регрессионного анализа (1, § 1.3).
3. Элементы теории оценивания (1, §1.4).
4. Конечно-сходящиеся алгоритмы и их стохастические аналоги (1, § 2.1).
5. Метод стохастической аппроксимации в задаче самообучения (1, § 2.2).
6. Рекуррентное байесовское оценивание (1, § 2.3).
7. Робастное оценивание (3, гл.4).
8. Абсолютно оптимальные алгоритмы идентификации (3, гл. З).
9. Модифицированные алгоритмы идентификации (3, гл.8).
10. Фильтр Винера - Колмогорова (1, § 3.1).
11. Фильтр Калмана - Бьюси (1, § 3.2).
12. Применение принципа максимума в теории фильтрации (2, § 27).
13. Оптимальная фильтрация коррелированных сигналов (2, § 30).
14. Экстраполяция и интерполяция случайных последовательностей (2, § 32).
15. Глобальная теория фильтрации (2, § 29).
16. Минимаксная фильтрация (1, § 3.3).
17. Адаптивные фильтры (1, § 4.3).
Литература: 1. Рекуррентное оценивание и адаптивная фильтрация. М., Наука, 1984.
2. Автоматическое управление М., 1978.
3. Основы информационной теории идентификации. М.,1984.
5. Оптимальная фильтрация
1. Линейное оценивание случайных процессов в классе устойчивых фильтров.
2. Причинное пространство и финитные в нем операторы.
3. Расширенное причинное пространство и линейные в нем преобразования.
4. Связь устойчивости и каузальности операторов в расширенном причинном пространстве.
5. Абстрактный вариант теории Винера - Колмогорова оптимального оценивания случайных элементов.
6. Оптимальное оценивание случайных элементов в пространстве с дискретной временной структурой.
7. Спектральная факторизация положительных операторов.
8. «Усиленная» спектральная факторизация.
9. Структура оптимального фильтра в случае дискретного времени. Формула Боде - Шеннона.
10. Спектральная факторизация положительных операторов в дискретном причинном пространстве.
11. Связь задачи спектральной факторизации с задачей минимизации квадратичных функционалов.
Литература: 1. , Линейная фильтрация случайных процессов. Уч. пособие. Л., 1991.
2. Операторные методы теории линейной фильтрации случайных процессов. СПб., 1995.
3. Корреляционная теория стационарных случайных процессов. Л., 1981.
