Программа вступительных экзаменов по специальности по образовательной программе 09.06.01 Информатика и вычислительная техника. Математическое моделирование, численные методы и комплексы программ

ПРОГРАММА ВСТУПИТЕЛЬНЫХ ЭКЗАМЕНОВ В АСПИРАНТУРУ ПО СПЕЦИАЛЬНОСТИ ПО ОБРАЗОВАТЕЛЬНОЙ  ПРОГРАММЕ 09.06.01 ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ, ЧИСЛЕННЫЕ МЕТОДЫ И КОМПЛЕКСЫ ПРОГРАММ.

ВЕЩЕСТВЕННЫЙ И КОМПЛЕКСНЫЙ АНАЛИЗ

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

ЛИТЕРАТУРА

  1. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. Т. 1-3. Санкт-Петербург: Лань,  2009 г..
  2. А.Н. Колмогоров, С.В. Фомин. Элементы теории функций и функционального анализа, 6-е изд., испр. — М. : Наука, 1989.
  3. Привалов И.И. Введение в теорию функций комплексного переменного, 14-е изд., Москва : Высш. шк., 1999 .

ОБЫКНОВЕННЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ

  1. Системы обыкновенных дифференциальных уравнений первого порядка
    Теоремы существования и единственности решения задачи Коши для дифференциального уравнения и нормальной системы. Зависимость решения от начальных условий и от параметров.
  2. Общая теория линейных систем
    Необходимое и достаточное условие линейной независимости решений линейной однородной системы. Построение общего решения. Неоднородные линейные системы. Метод вариации произвольных постоянных. Линейное уравнение n-го порядка. Линейные системы дифференциальных уравнений с постоянными коэффициентами.
  3. Теория устойчивости.
    Устойчивость по Ляпунову решений обыкновенных дифференциальных уравнений. Теорема об устойчивости по первому приближению. Второй метод Ляпунова.

ЛИТЕРАТУРА

    1. Петровский И.Г. Лекции по теории обыкновенных дифференциальных уравнений. М.: Физматлит, 2009 г.

АЛГЕБРА

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

ЛИТЕРАТУРА

  1. Курош А.Г. "Курс высшей алгебры". Изд.13-е, СПб. ; М. ; Краснодар : Лань, 2004 .
  2. Мальцев А.И. "Основы линейной алгебры". Изд. 4-е, Москва : Наука, 2005
  3. Фаддеев Д.К. "Лекции по алгебре". Изд. 4-е, СПб. ; М. ; Краснодар : Лань, 2005
  4. Воеводин В.В. "Линейная алгебра". М.: Изд. 3-е, СПб. ; М. ; Краснодар : Лань, 2006.
  5. Кострикин А.И. "Введение в алгебру". Москва: Изд-во МЦНМО, 2009.
  6. Винберг Э.Б. "Курс алгебры". Москва : Факториал Пресс, 2002.

ГЕОМЕТРИЯ

  1. Афинные и ортонормальные системы координат.
    Формулы замены координат. Вычисление скалярных произведений, длин отрезков и углов.
  2. Геометрические основы теории определений.
    Одинаково и противоположно ориентированные реперы, ориентация пространства. Вычисление объема параллелепипеда, построенного по реперу, через координаты составляющих векторов. Геометрический смысл детерминанта матрицы Грамма. Векторное и смешанное произведение в 3-мерном ориентированном евклидовом пространстве.
  3. Афинные подпространства.
    Задание афинного подпространства параметрическим уравнением и системой уравнений. Существование и единственность афинного отображения, имеющего заданные значения в заданных точках. Афинные свойства фигур (прямолинейность, выпуклость, связность и т.п.). Инвариантные подпространства афинных и ортогональных преобразований. Разложение афинного отображения в произведение растяжения и ортогонального отображения. Линии и поверхности 2-го порядка.

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

ЛИТЕРАТУРА

  1. Погорелов А.В. Аналитическая геометрия, 4-е изд., перераб. — М.; Ижевск : Регуляр. и хаотич. динамика, 2005
  2. Погорелов А.В. Дифференциальная геометрия, изд. 6-е, стер. — М. : Наука, 1974

 

МЕТОДЫ ВЫЧИСЛЕНИЙ

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

Интерполяционные многочлены. Выбор узлов интерполяции. Быстрое дискретное преобразование Фурье. Интерполяция нелокальными и локальными сплайнами. Численное интегрирование. Интерполяционные квадратурные формулы. Задача оптимизации квадратуры. Квадратурные формулы типа Гаусса. Понятие о методе Монте-Карло. Интегрирование сильно осциллирующих функций. Методы интегрирования обыкновенных дифференциальных уравнений. Численные методы решения задачи Коши и краевых задач.

Разностные схемы для решения дифференциальных уравнений с разрывными коэффициентами. Понятие о жестких системах обыкновенных дифференциальных уравнений и методах их решения. Разностные и вариационно-разностные методы решения уравнений математической физики. Основные понятия (аппроксимация, устойчивость, сходимость). Методы построения разностных схем (метод сеток, интегроинтерполяционный метод, метод аппроксимации интегральных тождеств, вариационно-разностные и проекционно-разностные методы, метод Галеркина, метод конечных элементов, метод аппроксимации квадратичного функционала); их применение к решению краевых и начально-краевых задач для эллиптических, параболических и гиперболических уравнений. Оценка порядка аппроксимации и сходимости. Двухслойные и трехслойные схемы; их устойчивость.

Экономичные методы решения нестационарных многомерных задач; методы решения нелинейных уравнений (теплопроводности и газовой динамики). Методы решения сеточных уравнений. Прямые методы (прогонки, быстрого дискретного преобразования Фурье, циклической редукции). Метод последовательной верхней релаксации, неявные схемы с эквивалентными по спектру операторами, попеременно-треугольный метод. Методы расщепления и переменных направлений.

ЛИТЕРАТУРА

  1. Бахвалов Н.С. Численные методы. М. Наука. 1975.
  2. Фаддеев О.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. М.: Физматгиз, 3-е изд., стер. — СПб. : Лань, 2002.
  3. Холл Дж., Уатт Дж. Современные численные методы решения обыкновенных дифференциальных уравнений. М.: Мир, 1979.
  4. Бахвалов Н.С., Жидков Н.П., Кобельков Т.М. Численные методы. 3-е изд., доп. и перераб. — М. : БИНОМ. Лаборатория знаний, 2003.
  5. Самарский А.А. Теория разностных схем. 3-е изд., испр .— Москва : Наука, 1989.
  6. Марчук Г.И. Методы вычислительной математики. Изд. 4-е, стер .— Санкт-Петербург ; Москва ; Краснодар : Лань, 2009.
  7. Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М: Наука, 1978.
  8. Флетчер К. Вычислительные методы в динамике жидкостей. М.: Мир, 1991, т. 1, 2.

МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ И ПРОГРАММИРОВАНИЯ

  1. Теория алгоритмов.
    Понятие алгоритма и его уточнения: машины Тьюринга, нормальные алгоритмы Маркова, рекурсивные функции. Эквивалентность данных алгоритмических систем. Понятие об алгоритмической неразрешимости. Примеры алгоритмически неразрешимых проблем.
    Понятие сложности алгоритмов. Классы P, NP, PSPACE. Теорема Кука об NP-полноте задачи выполнимости булевой формулы. Примеры NP-полных задач.
  2. Элементы математической логики.
    Алгебра логики. Булевы функции, канонические формы задания булевых функций. Понятие полноты системы. Теория Поста.
    Исчисление высказываний. Теорема о полноте исчисления высказываний. Исчисление предикатов 1-го порядка. Понятие интерпретации. Выполнимость и общезначимость формулы 1-го порядка. Понятие модели. Теорема о полноте исчисления предикатов 1-го порядка.
    Понятие булевой алгебры. Примеры булевых алгебр (алгебра подмножеств, алгебры Линденбаума для теорий первого порядка). Теорема Стоуна о строении конечных алгебр.
    Основные понятия модальной логики (пропозициональные модальные формулы, реляционная семантика, выполнимость и общезначимость пропозициональных модальных формул в шкалах Крипке).
  3. Элементы теории графов.
    Основные положения теории графов. Типы графов, способы задания графов. Изоморфизм, отображения. Критерий планарности. Виды и свойства бинарных деревьев. Перечисление бинарных деревьев. Алгоритмы обхода вершин графа. Алгоритмы разбиения графа на подграфы заданного типа.
  4. Элементы теории и практики программирования.
    Основные понятия логического программирования. Методы составления программ и их исполнения в парадигме логического программирования. Теорема Эрбрана. Метод резолюций. Теорема о полноте метода резолюций. Денотационная и операционная семантика.
    Основные концепции функционального программирования. Методы функционального программирования и их реализация. Примеры систем функционального программирования.
    Основные концепции объектно-ориентированного программирования. Организация выполнения объектно-ориентированных программ. Примеры объектно-ориентированных систем программирования.
    Понятие схемы программ. Теоремы о неразрешимости свойств пустоты, эквивалентности, тотальности и свободы стандартных схем. Алгоритм распознавания логико-термальной эквивалентности стандартных схем.
    Системы программирования, типовые компоненты СП: языки, трансляторы, редакторы связей, отладчики, текстовые редакторы. Понятие иерархии абстрактных машин.
    Языки программирования. Синтаксис, семантика. Подходы к классификации языков (по уровню абстракции, по классам применения, по классам пользователей).
    Основные концепции процедурно-ориентированных языков программирования. Методы процедурного программирования. Примеры.
  5. Общие вопросы архитектуры вычислительных систем.
    Понятие архитектуры вычислительных систем (ВС). Основные подходы к классификациям ВС. Основные принципы организации CISC, RISC и VLIW архитектур. Способы организации обработки информации в них. Примеры. Принципы организации и функционирования потоковых вычислителей и нейросетей. Понятие потоковой схемы программы.
    Основные методы организации многопроцессорных систем с распределенным управлением. Примеры. Методы организации обработки информации в таких системах.Системы с общей и распределенной памятью.
  6. Обшие вопросы организации вычислительного эксперимента.Понятие о вычислительном эксперименте и его инструментальной поддержке. Технология программирования. Жизненный цикл программы. Основные этапы. Инструментальные средства. Машинная графика. Основные графические пакеты.
    Пакеты прикладных программ (ППП). Системная часть и наполнение. Языки общения с ППП.
    Требования к программному продукту (надежность, переносимость, познаваемость, рациональная ресурсоемкость) и их влияние на системы программирования и технологии разработки программных систем.
  7. Операционные системы.
    Структура и функции операционных систем. Основные блоки и модули.    Основные средства аппаратной поддержки функций ОС: система прерываний, защита памяти, механизм преобразования адресов в системах виртуальной памяти, управление каналами и периферийными устройствами.
    Управление доступом к данным. Файловые системы (основные типы, характеристика).
    Распределение и использование ресурсов вычислительной системы. Основные подходы и алгоритмы планирования.
    Управление памятью. Методы организации виртуальной памяти в современных ОС.
  8. Методы хранения, организация и доступ к данным.
    Концепция типа данных. Абстрактные типы данных. Объекты (основные свойства и отличительные черты).
    Основные структуры данных, алгоритмы обработки и поиска.
    Модели данных. Иерархическая, сетевая, реляционная, алгебра отношений. Примеры соответствующих СУБД.
    Базы данных. Основные понятия языков управления и манипулирования данными, Распределенные базы данных, активные базы данных, интегрированные базы данных.
    Понятие о базе знаний, их использование в экспертных системах и системах логического вывода. Способы представления знаний.
    Организация физического уровня баз данных. Методы индексирования и сжатия данных.
    Язык баз данных SQL. Средства управления и изменения схемы базы данных, определения ограничений целостности. Контроль доступа.

 

ЛИТЕРАТУРА

  1. Таненбаум Э. Современные операционные системы. СПб. Питер. 2014.
  2. Таненбаум Э. Архитектура компьютера. СПб. Питер. 2016.
  3. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.. Алгоритмы: построение и анализ, 3-е издание  М. Вильямс. 2015
  4. Зелковиц М., Пратт Т. Языки программирования. Разработка и реализация. СПб. Питер. 2002.
  5. Яблонский С.В. Введение в дискретную математику. 4-е изд., стер. — М. : Высш. шк., 2003.
  6. Ахо А., Лам С., Сети Р., Ульман Дж. Компиляторы. Принципы, технологии и инструментарий, М. Вильямс. 2015
  7. Воеводин В.В. Математические модели и методы в параллельных процессах. М. Наука. 1986.
  8. Хоггер К, Введение в логическое программирование. М. Мир. 1988. 12 Алексеев В.Б., Ложкин С.А. (составители). Элементы теории графов и схем. Методическое пособие. М. МГУ. 1991.
  9. Мендельсон Э. Введение в математическую логику. М. Мир. 1985.
  10. Сиденко, Л.А. и др. Компьютерная графика и геометрическое моделирование [учебное пособие для студентов вузов]. СПб. Питер. 2009 .
  11. Дейт К. Дж. Введение в системы баз данных. М.: Вильямс, 2005.
  12. Гэри, Джонсон. Вычислительные машины и труднорешаемые задачи. М. Мир. 1984.
  13. Справочная книга по математической логике. 1984.
  14. Скорняков Л.А. Элементы общей алгебры. 1984.
  15. Котов В.Е., Сабельфельд В.К. Теория схем программ. 1992.