Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/study/magistr/program.doc Дата изменения: Thu Jun 16 18:54:24 2011 Дата индексирования: Sun Feb 3 00:46:33 2013 Кодировка: koi8-r

I. ВОПРОСЫ ДЛЯ ПОСТУПАЮЩИХ В МАГИСТРАТУРУ ПО КАФЕДРЕ МАТИС

1. Критерий полноты Кузнецова для функций k-значной логики {с
доказательством, [1]}
2. Теорема Слупецкого {с доказательством, [1]}
3. Теорема Линдена для клонов конечных алгебр {постановка задачи,
формулировка результатов, [10]}
4. Теоремы Мура об экспериментах с автоматами {с доказательством, [2]}
5. Теорема Клини о представлении событий {с доказательством, [2], [21]}
6. Теорема Мак-Ноттона о представлении сверхсобытий {постановка задачи,
формулировка результатов, [2]}
7. Моделирование в однородных структурах. Универсальность {определения,
формулировка результатов, [2], [3]}
8. Неэффективность критериев полноты для структурных автоматов
{определения, результат про континуум предполных классов, [2]}
9. Совпадение классов вычислимых и частично-рекурсивных функций
{определения, доказательство вычислимости частично-рекурсивных функций,
[1], [6], [18]}
10. Алгоритмически неразрешимые проблемы {определения, доказательства, [1],
[6], [16]}
11. Алфавитное и оптимальное кодирование {определения, доказательства, [1],
[14]}
12. Теорема Новикова о персепторне {постановка задачи, доказательство, [5]}
13. Графы
а) Теорема о плоской реализации (Понтрягина-Куратовского)
{формулировка, [7], [9], [19]}
б) Теорема Шеннона о реберной раскраске {формулировка, [20]}
в) Теорема о потоке через сеть {формулировка, доказательство, [7],
[11]}
14. Алгоритм распознавания голосованием по тестам {постановка задачи,
описание алгоритма, [5]}
15. Информационно-графовая модель данных {определения, результаты,
доказательства, [4, Глава 1]}
16. Дискретная оптимизация
а) Метод ветвей и границ {формулировка, [6], [13]}
б) Задача о рюкзаке {формулировка, [6], [15]}
в) Минимизация и сложность д.н.ф. Локальные алгоритмы. Теорема
Журавлева {формулировки и доказательства, [1]}
17. Логика и исчисление высказываний. Полнота и непротиворечивость
{определения, формулировки, доказательства, [8]}
18. Логика и исчисление предикатов {определения, формулировки, [8])
19. Формальные языки. Классификация Хомского {определения, формулировки,
[12], [17], [21]}
20. Схемная сложность булевых функций. Теорема Шеннона {определения,
формулировка, доказательство, [1]}
21. Алгоритмическая сложность. P- и NP-полнота. {определения, формулировки,
доказательства, [6], [15], [16], [22]}


СПИСОК ЛИТЕРАТУРЫ

[1] Яблонский С.В. Введение в дискретную математику. Высшая школа, Москва,
2002.
[2] Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию
автоматов. Наука, Москва, 1985.
[3] Кудрявцев В.Б., Подколзин А.С., Болотов А.А. Основы теории однородных
структур. Наука, Москва, 1990.
[4] Гасанов Э.Э., Кудрявцев В.Б. Теория хранения и поиска информации.
Физматлит, Москва, 2002.
[5] Алешин С.В. Распознавание динамических образов. Часть 1. Издательство
МГУ, Москва, 1996.
[6] Носов В.А. Основы теории алгоритмов и анализа их сложности. Курс
лекций. Москва, 1992.
[7] Носов В.А. Комбинаторика и теория графов. Учебное пособие. Московский
государственный институт электроники и математики. Москва, 1999.
[8] Подколзин А.С. Компьютерное моделирование посредством решения
математических задач. МГУ, 2000.
[9] Галатенко А.В. Об одном простом критерии планарности графов.
"Интеллектуальные системы", том 7, выпуск 1-4, 2003.
[10] Линден Р.К. Тождества в конечных алгебрах. "Кибернетический сборник",
выпуск 1 (старая серия).
[11] Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика. Графы,
матроиды, алгоритмы. РХД, 2001.
[12] Ахо А., Ульман Дж. Том 1. Теория синтаксического анализа, перевода и
компиляции. Синтаксический анализ. Мир, 1978.
[13] Ахо А.В., Хопкрофт Дж.Э., Ульман Дж.Д. Построение и анализ
вычислительных алгоритмов. Мир, 1979.
[14] Берлекамп Э. Алгебраическая теория кодирования. Мир, 1971.
[15] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.
Мир, 1982.
[16] Китаев А., Шень А., Вялый М. Классические и квантовые вычисления.
МЦНМО, 1999.
[17] Кук Д., Бейз Г. Компьютерная математика. Наука, 1990.
[18] Мальцев А.Н. Алгоритмы и рекурсивные функции. Наука, 1986.
[19] Харари Ф. Теория графов. Мир, 1973.
[20] Шеннон К. Работы по теории информации и кибернетике. ИЛ, 1963.
[21] Hopcroft J.E., Motwani R., Ullman J.D. Introduction to Automata
Theory, Languages and Computation. 2ed. AW 2001
[22] Greenlaw R., Hoover H.J., Ruzzo W.L. Limits to Parallel Computation.
Oxford University Press, 1995.

Книги [11]-[21] доступны в электронных версиях и могут быть найдены,
например, через сервис http://www.poiskknig.ru/. Электронные версии пособий
[6]-[8] находятся на сайте кафедры МАТИС http://www.intsys.msu.ru/


II. ОБЩАЯ ЧАСТЬ

1. Непрерывность функций одной и многих переменных, свойства непрерывных
функций. Полный дифференциал и его геометрический смысл. Достаточные
условия дифференцируемости. Градиент.
2. Определенный интеграл. Интегрируемость непрерывной функции.
3. Понятие метрического пространства, полные метрические пространства,
компактность. Теорема Больцано-Вейерштрасса. Принцип сходимости Коши.
4. Функции с ограниченным изменением. Мера в смысле Лебега. Теорема
Д.Ф.Егорова, C-свойство. Абсолютно непрерывные функции.
5. Суммируемые функции. Интеграл Лебега и его основные свойства.
Гильбертовы пространства. Изоморфизм L2 и l2. Сходимость в среднем.
6. Интегральные уравнения Фредгольма. Теоремы Фредгольма.
7. Ортогональные системы функций. Неравенство Бесселя, условие полноты.
Ряды Фурье. Сходимость рядов Фурье.
8. Линейные пространства, их подпространства. Базис, размерность. Теорема
о ранге матрицы. Системы линейных уравнений. Геометрическая
интерпретация системы линейных уравнений. Фундаментальная система
решений системы однородных линейных уравнений. Теорема Кронекера-
Капелли.
9. Билинейные и квадратичные функции и формы в линейных пространствах, их
матрицы. Приведение к нормальному виду. Закон инерции.
10. Линейные отображения и преобразования линейного пространства, их
задания матрицами. Характеристический многочлен. Собственные векторы и
собственные значения, связь последних с характеристическими корнями.
Приведение матрицы, линейного оператора к жордановой форме.
11. Евклидово пространство. Ортонормированные базисы. Ортогональные
матрицы. Ортогональные и самосопряженные преобразования, приведение
квадратичной формы к главным осям.
12. Аффинная и метрическая классификация кривых и поверхностей 2-го
порядка. Проективная классификация линий 2-го порядка.
13. Группы. Подгруппы. Порядок элемента. Циклические группы. Фактор-
группы. Теорема о гомоморфизмах.
14. Дифференциальное уравнение первого порядка. Теорема о существовании и
единственности решения.
15. Линейные уравнения с постоянными коэффициентами: однородные и
неоднородные.
16. Линейные уравнения в частных производных второго порядка. Их
классификация. Задача Дирихле для уравнения Лапласа. Задача Коши для
уравнения струны. Первая краевая задача и задача Коши для уравнения
теплопроводности.
17. Функции комплексного переменного. Условия Коши-Римана. Геометрический
смысл аргумента и модуля производной.
18. Элементарные функции комплексного переменного и даваемые ими
конформные отображения. Простейшие многозначные функции. Дробно-
линейные преобразования.
19. Теорема Коши об интеграле по замкнутому контуру. Интеграл Коши. Ряд
Тейлора. Аналитическое продолжение.
20. Ряд Лорана. Полюс и существенно особая точка. Вычеты.
21. Аналитическая функция в целом. Римановы поверхности.
22. Неявные функции. Существование, непрерывность и дифференцируемость
неявных функций. Криволинейные координаты на многообразии.
23. Первая квадратичная форма поверхности. Вторая квадратичная форма
поверхности. Нормальная кривизна линии на поверхности. Теорема Менье.
Геодезическая кривизна. Геодезические линии. Главные направления и
главные кривизны. Формула Эйлера. Гауссова кривизна поверхности.
24. Понятие топологического пространства. Понятие топологического и
гладкого многообразия. Основы римановой геометрии и тензорного анализа
(аффинная связность, ковариантное дифференцирование, тензор кривизны).

25. Понятие о простейшей проблеме вариационного исчисления. Уравнение
Эйлера-Лагранжа. Геодезические линии.
26. Дифференциальные формы на многообразиях. Общая теорема Стокса.
Следствия для векторных полей в трехмерном пространстве. Дивергенция.
Вихрь.


Литература по общей части
1. Александров П.С. Лекции по аналитической геометрии
2. Арнольд В.И. Обыкновенные дифференциальные уравнения.
3. Гельфанд И.М. Лекции по линейной алгебре
4. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального
анализа.
5. Кудрявцев Л.Д. Математический анализ
6. Курош А.Г. Курс высшей алгебры
7. Мальцев А.И. Основы линейной алгебры
8. Маркушевич А.И. Введение в теорию аналитических функций.
9. Никольский С.М. Курс математического анализа.
10. Новиков С.П. Дифференциальная геометрия. I и II.
11. Петровский И.Г. Лекции по обыкновенным дифференциальным уравнениям.
12. Петровский И.Г. Лекции об уравнениях с частными производными.
13. Понтрягин Л.С. Обыкновенные дифференциальные уравнения.
14. Рашевский П.К. Дифференциальная геометрия.
15. Рашевский П.К. Введение в риманову геометрию и тензорный анализ
16. Рудин У. Основы математического анализа
17. Шабат. Б.В. Введение в комплексный анализ
18. Шилов Г.Е. Введение в теорию линейных пространств.

Примечание. Кроме официального списка литературы, еще очень рекомендуются
следующие книжки:

1. Зорич В.А. Математический анализ. Том I и II. [к билетам 1, 2, 7, 22,
26]
2. Мищенко А.С., Фоменко А.Т. Курс дифференциальной геометрии и
топологии. [к билетам 23-26]
3. Дубровин Б.А., Новиков С.П., Фоменко А.Т. Современная геометрия.
Методы и приложения. [к билетам 23-26]
4. Соболев С.Л. Уравнения математической физики. [к билетам 6, 16]
5. Владимиров В.С. Уравнения математической физики. [к билетам 6, 16]
6. Евграфов М.А. Аналитические функции. [к билетам 17-21]