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

федеральное государственное автономное образовательное учреждение

высшего профессионального образования

физико-технический институт

«Московский

(государственный университет)»

УТВЕРЖДАЮ

Проректор по учебной работе О. А. Горшков «»_2013 г.

ПРОГРАММА ВСТУПИТЕЛЬНЫХ ИСПЫТАНИЙ В МАГИСТРАТУРУ

ФАКУЛЬТЕТА УПРАВЛЕНИЯ И ПРИКЛАДНОЙ МАТЕМАТИКИ

по направлению 010900 «Прикладные математика и физика»

по магистерским программам 010956 «Математические и информационные технологии», 010959 «Управляющие и информационные системы», 010960 «Системное программирование», анализ данных», 010990 «Интеллектуальный «Интеллектуальный анализ данных»

кафедр теоретической кибернетика и методов оптимального управления, управляющих и информационных систем, интеллектуальных системы, системного программирования, информатики (специализация: компьютерные технологии), теоретической и прикладной информатики, предсказательного моделирования и оптимизации Программа обсуждена и одобрена на заседании Ученого совета ФУПМ «19» апреля 2013 г.

Декан факультета _ Шананин А.А.

МАТЕМАТИКА

1. Теоремы о среднем для дифференцируемых функций Ролля, Лагранжа и Коши.

2. Формула Тейлора с остаточным членом в форме Лагранжа и Пеано.

3. Исследование функции одного переменного с помощью производных:

монотонность, экстремумы, выпуклость, перегибы.

4. Дифференцируемость функции нескольких переменных. Необходимые условия и достаточные условия дифференцируемости.

5. Экстремумы функций нескольких переменных. Необходимые условия, достаточные условия.

6. Условный экстремум функций нескольких переменных. Метод множителей Лагранжа (необходимые условия экстремума).

7. Определнный интеграл. Свойства интеграла с переменным верхним пределом:

непрерывность, дифференцируемость. Формула Ньютона--Лейбница.

8. Числовые ряды. Абсолютная и условная сходимость. Признаки сравнения.

9. Функциональные ряды. Равномерная сходимость. Признак Вейерштрасса.

10. Степенные ряды. Радиус сходимости. Ряд Тейлора.

11. Криволинейные интегралы. Формула Грина.

12. Поверхностные интегралы. Формула Остроградского--Гаусса.

13. Тригонометрический ряд Фурье. Условия сходимости ряда Фурье в точке.

14. Различные способы задания прямой и плоскости. Углы между прямыми и плоскостями. Формулы расстояния от точки до прямой и плоскости.

15. Кривые второго порядка. Эллипс, парабола, гипербола и их свойства.

16. Системы линейных алгебраических уравнений. Правило Крамера. Теорема Кронекера--Капелли. Общее решение системы.

17. Линейное преобразование конечномерного пространства, его матрица.

Собственные векторы и собственные значения, их свойства.

18. Квадратичные формы и их приведение к каноническому виду.

19. Линейные обыкновенные дифференциальные уравнения с постоянными коэффициентами. Методы их решения.

20. Линейные обыкновенные дифференциальные уравнения с переменными коэффициентами. Фундаментальная система решений. Метод вариации постоянных. Определитель Вронского, формула Лиувилля--Остроградского.

21. Простейшая задача вариационного исчисления. Уравнение Эйлера.

22. Вероятностное пространство. Независимые события. Теорема сложения. Условная вероятность. Полная система событий. Формула полной вероятности. Формула Байеса.

23. Случайная величина и е функция распределения. Математическое ожидание и дисперсия случайной величины, их свойства.

24. Испытания Бернулли. Неравенство Чебышева и закон больших чисел.

25. Регулярные функции комплексного переменного. Интегральная формула Коши.

Функции, регулярные в кольце. Ряд Лорана.

26. Вычет в изолированной особой точке. Вычисление интегралов при помощи вычетов.

27. Задача Коши для уравнения колебаний струны и одномерного уравнения теплопроводности. Формулы Даламбера и Пуассона.

28. Задачи Дирихле и Неймана для уравнений Лапласа и Пуассона (двумерный и трхмерный случаи).

Литература.

1. Л.Д. Кудрявцев. Краткий курс математического анализа.

2. С.М. Никольский. Курс математического анализа.

3. А.М. Тер-Крикоров, М.И. Шабунин. Курс математического анализа.

4. Г.Н. Яковлев. Лекции по математическому анализу.

5. Г.Е. Иванов. Лекции по математическому анализу.

6. А.Е. Умнов. Аналитическая геометрия и линейная алгебра.

7. В.И. Чехлов. Лекции по аналитической геометрии и линейной алгебре.

8. Д.В. Беклемишев. Курс аналитической геометрии и линейной алгебры.

9. Л.С. Понтрягин. Обыкновенные дифференциальные уравнения.

10. В.В. Степанов. Курс дифференциальных уравнений.

11. М.В. Федорюк. Обыкновенные дифференциальные уравнения.

12. В.К. Захаров, Б.А. Севастьянов, В.П. Чистяков, Теория вероятностей.

13. В.П. Чистяков. Курс теории вероятностей.

14. Е.С. Половинкин. Курс лекций по теории функций комплексного переменного.

15. М.И. Шабунин, Ю.В. Сидоров. Теория функций комплексного переменного.

16. В.С. Владимиров. Уравнения математической физики.

17. В.П. Михайлов. Лекции по уравнениям математической физики.

18. В.М. Уроев. Уравнения математической физики.

КОМПЬТЕРНЫЕ ТЕХНОЛОГИИ И ИНТЕЛЛЕКТУАЛЬНЫЙ АНАЛИЗ ДАННЫХ

1. Функции алгебры логики. Табличное задание функций. Элементарные функции, их свойства, таблица операций, коммутативность, ассоциативность, дистрибутивность элементарных функций. Формулы и функции алгебры логики. Теоремы о разложении функций по одной и нескольким переменным. Совершенная дизьюнктивная нормальная форма.

2. Функциональная полнота систем функций алгебры логики. Замкнутые классы.

Пять предполных замкнутых классов Т 0, T 1, L, S, М. Теорема о функции, двойственной к суперпозиции. Критерий функциональной полноты систем функций алгебры логики (теорема Поста). Основная лемма. Лемма о несамодвойственной функции. Лемма о немонотонной функции. Лемма о нелинейной функции. Следствия из критерия полноты.

3. Предмет комбинаторики. Комбинаторные задачи о числе функций, слов в алфавите и размещений объектов по ячейкам при различных ограничениях (mn, [m] n, [m] n, [m] n /n!, Pn ). Числа Стирлинга первого рода, рекуррентное соотношение для них.

Биноминальные коэффициенты, производящая функция для них, основные комбинаторные тождества. Полиномиальные коэффициенты, производящая функция для них, основные комбинаторные тождества. Число разбиений n объектов на m классов. Числа Стирлинга второго рода. Рекуррентное соотношение для S(n, k) Разложение степени х n в базисе {[x] k }. Числа Белла разбиений множества на непересекающиеся подмножества, рекуррентное соотношение для чисел Белла.

4. Логические методы комбинаторного анализа. Принцип включений-исключений.

Задача о числе беспорядков, задача о числе сюрьективных отображений конечных множеств. Системы представителей множеств. Системы различных представителей (с.р.п.). Необходимое и достаточное условие существования с.р.п. Алгоритм построения с.р.п. для заданной системы множеств. Системы одновременных представителей.

5. Определение графа. Неориентированные и ориентированные графы. Изоморфные графы. Полные ориентированные и неориентированные графы. Локальные степени вершин. Число вершин нечетной степени в конечном графе. Машинное представление графов. Матрица инциденций. Матрица смежности (вершин).

Список пар, список инцидентности. Пути (маршруты, цепи) в графе, простые пути, циклы. Связность. Теорема о связности двух вершин, имеющих нечетную локальную степень. Максимальное число ребер в графе с n вершинами и kсвязными компонентами. Деревья. Связанность любых двух вершин дерева единственным простым путем. Изображение дерева. Концевые (висячие) вершины и концевые (висячие) ребра дерева. Поиск в глубину и в ширину. Теорема о числе различных деревьев с данными n вершинами.

6. Эйлеровы пути и циклы, теорема о существовании эйлеровых путей и циклов в графе. Алгоритм построения эйлеровых циклов. Гамильтоновы пути и циклы.

Пути, имеющие тип цикла. Достаточное условие для того, чтобы полный простой путь имел тип цикла. Связь между наличием в связном графе гамильтоновых циклов и длиной максимальных простых путей в нем.

7. Нахождение кратчайших путей в ориентированном графе от фиксированной вершины (случай неотрицательных весов ребер).

8. Алгебраические структуры. Бинарные операции. Полугруппы и моноиды. Группы.

Примеры групп. Группа перестановок (симметрическая группа). Теорема Келли.

Подгруппы. Порождающие или образующие элементы группы.

9. Левые и правые смежные классы группы по подгруппе. Индекс подгруппы в группе. Порядок элемента группы. Циклические группы. Теорема Лагранжа.

Сопряженные элементы и сопряженные подгруппы. Нормальные делители.

Факторгруппа. Изоморфизмы, автоморфизмы и гомоморфизмы групп. Ядро гомоморфизма. Внутренние автоморфизмы. Теорема о гомоморфизме групп.

10. Кольца. Примеры колец. Кольцо целых чисел. Кольцо многочленов над кольцом (полем). Кольца классов вычетов в кольце целых чисел и кольце многочленов.

Подкольцо. Обратимые элементы кольца, группа обратимых элементов кольца, делители нуля. Левые, правые и двусторонние идеалы. Главные идеалы.

Максимальные и простые идеалы. Кольца классов вычетов. Идеалы в кольцах многочленов. Факторкольцо. Теорема о гомоморфизме колец.

11. Деление с остатком в кольцах целых чисел и многочленов над кольцом целых чисел. Евклидовы кольца. Идеалы в евклидовых кольцах. Кольца главных идеалов.

Факториальность колец главных идеалов.

12. Поля. Примеры полей. Поле классов вычетов. Характеристика поля. Простое подполе. Конечные и алгебраические расширения полей. Поле разложения.

Конечные поля.

13. Метод формальных теорий. Основные понятия исчисления высказываний.

Выражения, формулы и аксиомы. Схемы аксиом и правило вывода. Вывод в исчислении высказываний. Теорема дедукции. Теорема о полноте.

Непротиворечивость исчисления высказываний и независимость его схем аксиом.

14. Основные понятия теорий первого порядка: кванторы, термы, формулы, свободные и связанные вхождения переменных в формулы. Интерпретации. Выполнимость и истинность. Модели. Логически общезначимые формулы. Схемы аксиом и правила вывода исчисления предикатов. Непротиворечивость исчисления предикатов.

Теорема дедукции. Теорема Геделя о полноте (без доказательства).

15. Необходимость уточнения понятия алгоритма. Примеры алгоритмов. Машины Тьюринга (МТ) и их основные свойства. Примеры МТ. Нумерация МТ. Операции над МТ. Понятие нормального алгоритма Маркова. Примеры. Марковские вычисления. Эквивалентность определений алгоритма по Тьюрингу и Маркову.

16. Понятие вычислимости. Примитивно-рекурсивные функции. Тезис Чрча.

17. Алгоритмически неразрешимые проблемы: распознавание применимости, самоприменимости и переводимости.

18. Проблема тождества слов в полугруппах. Разрешимые случаи. Примеры.

Неразрешимость проблемы тождества слов в полугруппах.

19. Языки и их представление. Грамматики. Типы грамматик по Хомскому и их свойства. Связь машин Тьюринга и грамматик типа 0.

20. Конечные автоматы. Регулярные множества и выражения. Детерминированные и недетерминированные конечные автоматы 21. Эквивалентность классов языков, определяемых конечными автоматами, регулярными выражениями и праволинейными грамматиками.

1. Детерминированные машины Тьюринга и класс P. Рекурсивные и рекурсивно перечислимые языки.

2. Недетерминированные вычисления и класс NP.

3. Полиномиальная сводимость и NP-полные задачи. Теорема Кука. Семь основных NP-полных задач (выполнимость, 3-выполнимость, трехмерное сочетание, вершинное покрытие, клика, гамильтонов цикл, разбиение).

Методы доказательства NP-полноты.

4. Задачи с числовыми параметрами. Псевдополиномиальная сводимость.

Сильная NP-полнота (задачи: упорядочение работ внутри интервалов, многопроцессорное расписание без прерываний, коммивояжер, упаковка в 5. Псевдополиномиальные алгоритмы (задачи: разбиение, рюкзак, многопроцессорное расписание без прерываний при фиксированном числе процессоров, упаковка в контейнеры при фиксированном числе 6. Сводимость по Тьюрингу и NP-трудные задачи (задача K-е по порядку множество). NP-эквивалентные задачи (оптимизационные варианты семи основных NP-полных задач, оптимизационная задача коммивояжера).

23. Алгоритмы сортировки и их сложность.

24. Магазинные автоматы. Контекстно-свободные грамматики и автоматы с магазинной памятью. Детерминированные и недетерминированные магазинные 1. Журавлев Ю.И., Флеров Ю.А. Дискретный анализ. Ч. 1: Учебное пособие. – М.: МФТИ, 1999.

2. Дискретная математика и математические вопросы кибернетики / Под ред. С.В.

Яблонского, О.В. Лупанова. – Т. 1. – М.: Наука, 1974.

3. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1979.

4. Стенли Р. Перечислительная комбинаторика. – М.: Мир, 1990.

5. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. – М.: Мир, 1998.

6. Липский В. Комбинаторика для программистов. – М.: Мир, 1988.

7. Рыбников К.А. Введение в комбинаторный анализ. – М.: МГУ, 1972.

8. Уилсон Р. Дж. Введение в теорию графов. – М.: Мир, 1977.

9. Харрари Ф. Теория графов. – М.: Мир, 1973.

10. Холл М. Комбинаторика. – М.: Мир, 1970.

11. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001.

12. Кострикин А.И. Введение в алгебру. М.: Наука, 1977.

13. Ван-дер-Варден Б.Л. Алгебра. М.: Наука, 1976.

14. Мендельсон Э. Введение в математическую логику. М.: Наука, 1984.

15. Трахтенберг Б.А. Алгоритмы и вычислительные автоматы. М.: Сов. Радио, 1974.

15. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972.

16. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность.

М.: Мир, 1985.

17Л. Ловас, М. Пламмер. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. М.: Мир, 1998.

18. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 1999.