Программа вступителных экзаменов в магистратуру

Вещественный и комплексный анализ
  1. Математический анализ.
    1. Теория пределов. Теория рядов. Основные теоремы о непрерывных функциях.
    2. Основные теоремы дифференциального исчисления, (теорема о средних значениях, теорема о неявных функциях, формула Тейлора.
    3. Основные теоремы интегрального исчисления (теоремы о замене переменных; теоремы о повторных интегралах; формулы Грина, Остроградского, Стокса).
  2. Основы функционального анализа.
    1. Конечномерные вещественные пространства (характеризация открытых, замкнутых и компактных множеств).
    2. Основные теоремы о сходимости последовательностей измеримых функций (теорема Егорова).
    3. Определения и основные свойства интеграла Лебега. Теоремы Лебега, Деви, Фату о предельном переходе под знаком интеграла. Теорема Фубини.
    4. Функции ограниченной вариации и интеграл Стилтьеса.
    5. Основные нормированные пространства, Полнота, сепарабельность, критерий компактности, сильная и слабая сходимости.
    6. Гильбертовы пространства. Теоремы Рисса - Фишера. Ряды и интегралы Фурье.
    7. Элементы теории линейных операторов. Теорема Бахана об обратном операторе. Теорема Хана - Бахана. Теорема Фредгольма для вполне непрерывных операторов.
    8. Линейные функционалы. Теорема Бахана - Штейнгауза. Теорема Рисса о представлении.
    9. Теоремы о неподвижной точке. Принцип Бахана, принцип Шаудера.
  3. Основы теории функций комплексного переменного.
    1. Условия Коши - Римана. Конформные отображения, осуществляемые элементарными функциями. Точки ветвления и римановы поверхности.
    2. Комплексное интегрирование. Теорема Коши. Интеграл типа Коши. Теорема Морера.
    3. Ряды Тейлора и Лорана. Изолированные особые точки аналитической функции. Теорема единственности аналитической функции. Принцип модуля и аргумента для аналитических функций. Элементы теории вычетов.
    4. Бесконечные произведения. Представление целой функции в виде бесконечного произведения.
    5. Принцип аналитического продолжения. Теорема Римана о конформном отображении односвязных областей. Формула Кристофера - Шварца.
    6. Предельные значения интеграла типа Коши (формула Сохоцкого - Племеля). Восстановление функций аналитической функции по ее вещественной части на окружности (формула Шварца). Решение задачи Дирихле для круга (формула Пуассона).
Литература
  1. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. Т. 1-3.
  2. Колмогоров А.Н. и Фомин С.В. Элементы теории функций и функционального анализа.
  3. Бицадзе А.В. Основы теории аналитических функций комплексного переменного.
Обыкновенные дифференциальные уравнения
  1. Системы обыкновенных дифференциальных уравнений первого порядка

    Теоремы существования и единственности решения задачи Коши для дифференциального уравнения и нормальной системы. Зависимость решения от начальных условий и от параметров.

  2. Общая теория линейных систем

    Необходимое и достаточное условие линейной независимости решений линейной однородной системы. Построение общего решения. Неоднородные линейные системы. Метод вариации произвольных постоянных. Линейное уравнение n-го порядка. Линейные системы дифференциальных уравнений с постоянными коэффициентами.

  3. Теория устойчивости

    Теорема Ляпунова об устойчивости. Теоремы о неустойчивости. Устойчивость по первому приближению. Понятие о краевых задачах для уравнения второго порядка. Собственные числа. Собственные функции. Функция Грина.

Литература
  1. Петровский И.Г. Лекции по теории обыкновенных дифференциальных уравнений.
Алгебра
  1. Основные понятия алгебры

    Алгебраические операции и алгебраические системы. Изоморфизм. Группа. Кольцо. Поле. Поле комплексных чисел. Кольцо многочленов. Кольцо матриц. Группа подстановок.

  2. Теория определителей

    Определитель квадратной матрицы и его простейшие свойства. Поведение определителя при транспонировании матрицы, элементарных преобразованиях системы строк и столбцов матрицы и умножении матриц. Разложение определителя по строке, критерий обратимости и формула для обратной матрицы. Решение крамеровых систем линейных уравнений.

  3. Конечномерные векторные пространства

    Линейная зависимость, теорема о замене, база и ранг системы векторов, размерность пространства. Изоморфизм любого конечномерного пространства некоторому пространству строк. Преобразование координат вектора при смене базы пространства. Фактор-пространство. Размерность суммы и пересечения подпространств, фактор-пространства.

  4. Системы линейных уравнений

    Теорема о ранге для матриц. Критерий совместности системы линейных уравнений. Общее решение системы линейных уравнений (определение и отыскание). Однородные системы (пространство решений, фундаментальные системы решений). Связь между множеством решений совместной неоднородной системы и пространством решений соответствующей однородной системы.

  5. Многочлены

    Делимость многочленов (алгоритм деления с остатком, наибольший общий делитель, алгоритм Евклида). Разложение на неразложимые множители. Корни и значения (теорема Безу, формула Тейлора, интерполяционный многочлен). Формулы Виета и основная теорема о симметрических многочленах. Алгебраическая замкнутость поля комплексных чисел.

  6. Линейные преобразования векторных пространств

    Алгебра линейных преобразований пространств, изоморфизм с алгеброй матриц. Образ, ядро, ранг и дефект линейного преобразования. Невырожденные преборазования. Инвариантные подпространства, сужение преобразования на инвариантном подпространстве и индуцирование на фактор-пространстве.

    Собственные векторы, собственные значения и корни характеристического многочлена (спектр) линейного преобразования, теорема Гамильтона-Кэли. Корневые подпространства и корневое разложение пространства относительно линейного преобразования. Нильпотентные преобразования и их классификация. Жорданова классификация линейных преобразований и жорданова форма матриц (существование, единственность). Задача о подобии матриц. Функции от матриц, представление многочленами и ряды от матриц.

  7. Линейные отображения евклидовых и унитарных пространств

    Аксиоматика евклидовых и унитарных пространств, длина вектора и угол между ненулевыми векторами (неравенство Коши-Буняковского, неравенство треугольника). Процесс ортогонализации и изоморфизмы евклидовых и унитарных пространств стандартным пространствам строк, ортогональное дополнение к подпространству и ортогональные разложения евклидовых и унитарных пространств.

    Сопряженное линейное отображение и сопряженная матрица. Эрмитовы и симметрические линейные преобразования и матрицы (определение, спектр и канонический вид). Косоэрмитовы и кососимметрические линейные преобразования и матрицы (определение, спектр и канонический вид). Унитарные и ортогональные преобразования и матрицы (определение, спектр и канонический вид). Сингулярные числа, сингулярное разложение линейного отображения и матрицы. Полярное разложение линейного преобразования матрицы.

  8. Квадратичные формы

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

Литература
  1. Курош А.Г. "Курс высшей алгебры". М.: Наука, 1971.
  2. Мальцев А.И. "Основы линейной алгебры". М.: Наука, 1970.
  3. Фаддеев Д.К. "Лекции по алгебре". М.: Наука, 1984.
  4. Воеводин В.В. "Линейная алгебра". М.: Наука, 1980.
  5. Кострикин А.И. "Введение в алгебру". М.: Наука, 1977.
  6. Винберг Э.Б. "Курс алгебры". М.: Факториал, 1999.
Геометрия
  1. Афинные и ортонормальные системы координат

    Формулы замены координат. Вычисление скалярных произведений, длин отрезков и углов.

  2. Геометрические основы теории определений

    Одинаково и противоположно ориентированные реперы, ориентация пространства. Вычисление объема параллелепипеда, построенного по реперу, через координаты составляющих векторов. Геометрический смысл детерминанта матрицы Грамма. Векторное и смешанное произведение в 3-мерном ориентированном евклидовом пространстве.

  3. Афинные подпространства

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

  4. Линии и поверхности 2-го порядка

    Алгебраические поверхности. Пересечение алгебраической поверхности с прямой, условие касания. Линия второго порядка (фокусы, асимптоты, оптические свойства). Строение поверхностей 2-го порядка. Алгоритмы отыскания канонического уравнения и главных осей поверхности, заданной общим уравнением 2-й степени. Метод Лагранжа (метод выделения полных квадратов) для определения афинного типа поверхности 2-го порядка.

  5. Теория кривых

    Кривизна кривой. Соприкасающаяся плоскость, главная нормаль и бинормаль. Кручение кривой. Теорема о задании кривой натуральными уравнениями.

  6. Теория поверхности

    Первая и вторая квадратичная форма. Универсальная связь между первой и второй квадратичными формами поверхности. Понятие о внутренней геометрии поверхностей и ее многомерном обобщении (римановой геометрии).

Литература
  1. Погорелов А.В. Аналитическая геометрия
  2. Погорелов А.В. Дифференциальная геометрия.
Математические основы информатики и программирования
  1. Понятие алгоритма и его уточнения: машины Тьюринга, нормальныеалгоритмы Маркова, рекурсивные функции. Эквивалентность данных алгоритмических систем. Понятие об алгоритмической неразрешимости.Примеры алгоритмически неразрешимых проблем.
  2. Понятие сложности алгоритмов. Классы P, NP, PSPACE. Теорема Кука об NP-полноте задачи выполнимости булевой формулы. Примеры NP-полных задач. Классы NC^k .
  3. Алгебра логики. Булевы функции, канонические формы задания булевых функций. Понятие полноты системы. Теория Поста.
  4. Исчисление высказываний. Теорема о полноте исчисления высказываний.
  5. Исчисление предикатов 1-го порядка. Понятие интерпретации.Выполнимость и общезначимость формулы 1-го порядка. Понятие модели. Теорема о полноте исчисления предикатов 1-го порядка.
  6. Основные положения теории графов. Типы графов, способы задания графов. Изоморфизм, отображения. Критерий планарности. Виды и свойства бинарных деревьев. Перечисление бинарных деревьев. Алгоритмы обхода вершин графа. Алгоритмы разбиения графа на подграфы заданного типа.
  7. Формальные языки и способы их описания. Классификация формальных грамматик. Их использование в лексическом и синтаксическом анализе. Атрибутные грамматики. Теорема о неразрешимости проблемы распознавания совпадения контекстно-свободных языков.
  8. Основные понятия логического программирования. Теорема Эрбрана. Метод резолюций. Теорема о полноте метода резолюций. Денотационная и операционная семантика.
  9. Основные понятия модальной логики (пропозициональные модальные формулы, реляционная семантика, выполнимость и общезначимость пропозициональных модальных формул в шкалах Крипке). Характеризация рефлексивных и транзитивных шкал Крипке. Примеры модальных логик: темпоральная логика, динамическая логика Пратта.
  10. Основные понятия бестипового lambda -исчисления. Теорема Черча-Россера. Модели Д.Скотта для бестипового lambda -исчисления.
  11. Основные понятия общей алгебры: алгебра, подалгебра, гомоморфизм, конгруэнтность, факторалгебра. Теорема об эпоморфизмах алгебр. Алгебра термов. Универсальное свойство алгебры термов.
  12. Понятие булевой алгебры. Примеры булевых алгебр (алгебра подмножеств, алгебры Линденбаума для теорий первого порядка). Теорема Стоуна о строении конечных алгебр.
  13. Основные понятия исчисления взаимодействующих систем Р.Милнера. Система аксиом CCS . Понятие процесс в CCS . Наблюдаемая конгруэнция на множестве CCS -процессов. Теорема о неподвижной точке.
  14. Понятие схемы программ. Теоремы о неразрешимости свойств пустоты, эквивалентности, тотальности и свободы стандартных схем. Алгоритм распознавания логико-термальной эквивалентности стандартных схем.
  15. Представление о сетях Петри для анализа свойств параллельных программ. Проблема достижимости.
  16. Методы автоматизации распараллеливания программ и векторизация циклов. Ярусно-параллельные формы. Методы гиперплоскостей, параллелепипедов и т.д.
II Элементы смежных областей
  1. Теорема Банаха о существовании и единственности неподвижной точки у произвольного сжимающего отображения на полном метрическом пространстве. Итерационные методы решения вычислительных задач.
  2. Численные методы линейной алгебры. Основные алгоритмы и их сложность.
  3. Численные методы решения обыкновенных дифференциальных уравнений. Основные алгоритмы и их сложность.
  4. Численные методы интегрирования. Основные алгоритмы и их сложность.
  5. Понятие устойчивости разностных схем.
  6. Быстрое преобразование Фурье (БПФ) и его применение.
  7. Погрешность результата, неустранимая, относительная. Погрешность, вызываемая методами выполнения арифметических операций в ЭВМ. Ошибки округления. Накопление ошибок.
  8. Алфавитное кодирование. Алгоритмы распознавания алфавитного кодирования. Коды с исправлением ошибок. Методы сжатия кодированной информации.
  9. Основные понятия линейного программирования. Алгоритм симплекс-метода решения задачи линейного программирования.
III Общие вопросы информатики и вычислительной техники
  1. Понятие архитектуры вычислительных систем (ВС). Основные подходы к классификациям ВС. Основные принципы организации CISC, RISC и VLIW архитектур. Способы организации обработки информации в них. Примеры.
  2. Принципы организации и функционирования потоковых вычислителей и нейросетей. Понятие потоковой схемы программы.
  3. Основные методы организации многопроцессорны систем с распределенным управлением. Примеры. Методы организации обработки информации в таких системах.
  4. Системы с общей и распределенной памятью.
  5. Основные методы организации многопроцессорных систем с централизованным управлением (массовый параллелизм). Методы обработки информации в таких системах.
  6. Понятие и основные виды производительности вычислительных систем. Методы их исследования и анализа.
  7. Методы организации сетей ЭВМ. Основные принципы их функционирования. Классификация сетей по масштабу и топологии.
  8. Понятие сетевого протокола. Семиуровневая модель OSI/ISO. Понятие стандарта.
  9. Сетевая архитектура TCP/IP: основные принципы организации и функционирования.
  10. Способы маршрутизации сообщений в сетях ЭВМ.
  11. Основные функции сервера в сети ЭВМ. Состав и структура его программного обеспечения.
  12. Основные принцип и средства управления сетью.
  13. Понятие о вычислительном эксперименте и его инструментальной поддержке.
  14. Проблемы защиты информации от несанкционированного доступа.
  15. Машинная графика. Средства поддержки машинной графики. Графические пакеты.
  16. Технология программирования. Жизненный цикл программы. Основные этапы. Инструментальные средства поддержки.
  17. Требования к программному продукту (надежность, переносимость, познаваемость, рациональная ресурсоемкость) и их влияние на системы программирования и технологии разработки программных систем.
  18. Методы спецификации программ. Методы проверки спецификации.
  19. Защита авторских прав разработчиков программ. Программистская этика.
IV Операционные системы
  1. Режимы функционирования вычислительных систем, структура и функции операционных систем. Основные блоки и модули.
  2. Основные средства аппаратной поддержки функций ОС: система прерываний, защита памяти, механизм преобразования адресов в системах виртуальной памяти, управление каналами и переферийными устройствами.
  3. Управление доступом к данным. Файловые системы (основные типы, характеристика).
  4. Распределение и использование ресурсов вычислительной системы. Основные подходы и алгоритмы планирования.
  5. Интерфейсы взаимодействия человека с вычислительной системой.Оболочки. Интерпретаторы команд.
  6. Организация сетевого взаимодействия в современных ОС.
  7. Виды процессов и управление ими в современных ОС. Средства взаимодействия процессов. Модель клиент-сервер и ее реализация в современных ОС.
  8. Структура современных распределенных ОС. Объектно-ориентированный подход в организации ОС. Основные международные стандарты для построение ОС.
  9. Управление памятью. Методы организации виртуальной памяти в современных ОС.
V Системы программирования (СП)
  1. Системы программирования, типовые компоненты СП: языки, трансляторы, редакторы связей, отладчики, текстовые редакторы. Понятие иерархии абстрактных машин.
  2. Языки программирования. Синтаксис, семантика. Подходы к классификации языков (по уровню абстракции, по классам применения, по классам пользователей).
  3. Основные концепции процедурно-ориентированных языков программирования. Методы процедурного программирования. Примеры.
  4. Основные концепции логического программирования. Методы составления программ и их исполнения в парадигме логического программирования.
  5. Основные концепции функционального программирования. Методы функционального программирования и их реализация. Примеры систем функционального программирования.
  6. Основные концепции объектно-ориентированного программирования. Организация выполнения объектно-ориентированных программ. Примеры объектно-ориентированных систем программирования.
  7. Понятие о методах трансляции. Лексический, синтаксический, семантический анализ. Основные алгоритмы генерации объектного кода.
  8. Машинно-ориентированные языки типа ассемблера, области применения, способы записи машинных команд и констант. Команды транслятору, их типы, принципы реализации.
  9. Макросредства, макровызовы, языки макроопределений, условная макрогенерация, принципы реализации.
  10. Модульное программирование. Типы модулей (исходный, загрузочный, объектный). Связывание модулей по управлению и данным.
  11. Понятие о подходах к автоматическому синтезу программ.
  12. Пакеты прикладных программ (ППП). Системная часть и наполнение. Языки общения с ППП.
  13. Средства описания параллелизма в современных языках программирования.
VI Методы хранения, организация и доступ к данным
  1. Концепция типа данных. Абстрактные типы данных. Объекты (основные свойства и отличительные черты).
  2. Основные структуры данных, алгоритмы обработки и поиска.
  3. Модели данных. Иерархическая, сетевая, реляционная, алгебра отношений. Примеры соответствующих СУБД.
  4. Информационно-поисковые системы. Классификация. Методы реализации и методы ускорения поиска.
  5. Базы данных. Основные понятия языков управления и манипулирования данными, Распределенные базы данных, активные базы данных, интегрированные базы данных.
  6. Понятие о базе знаний, их использование в экспертных системах и системах логического вывода. Способы представления знаний.
  7. Организация физического уровня баз данных. Методы индексирования и сжатия данных.
  8. Язык баз данных SQL. Средства управления и изменения схемы базы данных, определения ограничений целостности. Контроль доступа.

Список литературы

  1. Бахвалов Н.С. Численные методы. М. Наука. 1975.
  2. Девис У. Операционные системы: Функциональный подход. М. Мир. 1980.
  3. Королев Л.Н. Структуры ЭВМ и их математическое обеспечение. М. Наука. 1980.
  4. Любимский Э.З., Мартынюк В.В., Трифонов Н.П. Программирование. М. Наука. 1978.
  5. Попов Ю.П., Самарский А.А. Вычислительный эксперимент. М. Знание. 1983.
  6. Пратт Т. Языки программирования. Разработка и реализация. М. Мир. 1979.
  7. Уоркли Дж. Архитектура и программирование микро-ЭВМ. В двух томах. М. Мир. 1984.
  8. Яблонский С.В. Введение в дискретную математику. М. Наука. 1979.
  9. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1,2. М. Мир. 1978.
  10. Воеводин В.В. Математические модели и методы в параллельных процессах. М. Наука. 1986.
  11. Хоггер К, Введение в логическое программирование. М. Мир. 1988.
  12. Алексеев В.Б., Ложкин С.А. (составители). Элементы теории графов и схем. Методическое пособие. М. МГУ. 1991.
  13. Мендельсон Э. Введение в математическую логику. М. Мир. 1985.
  14. Фоли Дж., Вэн Дем А. Системы интерактивной графики. М. Мир. 1985.
  15. Роджерс. Алгоритмические основы машинной графики. М. Мир. 1989.
  16. Мартин Дж. Организация баз данных в вычислительных системах. М. Мир. 1987.
  17. Трахтенгерц. Введение в теорию анализа и распараллеливания программ ЭВМ. М. Наука. 1981.
  18. Гэри, Джонсон. Вычислительные машины и труднорешаемые задачи. М. Мир. 1984.
  19. Голдблатт Р. Логика времени и вычислимость. М. Мир. 1993.
  20. Manna Z., Pnueli A. The Temporal Logic of Reactive and Concurrent Systems. Springer-Verlag. 1992.
  21. Handbook of Theoretical Computer Science. Vol. A, B. 1990.
  22. Справочная книга по математической логике. 1984.
  23. Скорняков Л.А. Элементы общей алгебры. 1984.
  24. Котов В.Е., Сабельфельд В.К. Теория схем программ. 1992.