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

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

  

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

 

Математический анализ.

 1.Теория пределов. Теория рядов. Основные теоремы о непрерывных функциях.

2.Основные теоремы дифференциального исчисления, (теорема о средних значениях, теорема о неявных функциях, формула Тейлора.

3.Основные теоремы интегрального исчисления (теоремы о замене переменных; теоремы о повторных интегралах; формулы Грина, Остроградского, Стокса).

 

Основы функционального анализа.

 4.Конечномерные вещественные пространства (открытые, замкнутые и компактные множества).

5.Определения и основные свойства интеграла Лебега. Теоремы Лебега. Теорема Фубини.

6.Основные нормированные пространства, Полнота, сепарабельность.

7.Гильбертовы пространства. Теоремы Рисса - Фишера. Ряды и интегралы Фурье.

8.Элементы теории линейных операторов. Теорема Банаха об обратном операторе. Теорема Хана - Банаха. Теорема Фредгольма для вполне непрерывных операторов.

9.Линейные функционалы. Теорема Банаха - Штейнгауза. Теорема Рисса о представлении.

10.Теоремы о неподвижной точке. Принцип Банаха, принцип Шаудера.

 

Основы теории функций комплексного переменного.

 11.Условия Коши - Римана. Конформные отображения, осуществляемые элементарными функциями.

12.Комплексное интегрирование. Теорема Коши. Интеграл типа Коши. Теорема Морера.

13.Ряды Тейлора и Лорана. Изолированные особые точки аналитической функции. Теорема единственности аналитической функции.  Элементы теории вычетов.

14.Теорема Римана о конформном отображении односвязных областей.

 

ЛИТЕРАТУРА

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

  

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

 1.Системы обыкновенных дифференциальных уравнений первого порядка

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

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

 

ЛИТЕРАТУРА

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.Афинные подпространства

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

  

ЛИТЕРАТУРА

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

  

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

 1.Теорема Банаха о существовании и единственности неподвижной точки у произвольного сжимающего отображения на полном метрическом пространстве. Итерационные методы решения вычислительных задач.

2.Погрешность результата, неустранимая, относительная. Погрешность, вызываемая методами выполнения арифметических операций в ЭВМ. Ошибки округления. Накопление ошибок.

3.Численные методы линейной алгебры. Вычисление наибольшего по модулю собственного значения матрицы Прямые и итерационные методы. Способы ускорения сходимости. Градиентные методы. Методы ортогонализации.

4.Квадратурные формулы. Основные алгоритмы и их сложность.

5.Быстрое преобразование Фурье (БПФ) и его применение.

6.Основные численные методы: метод конечных разностей и конечных объемов, метод конечных элементов. Аппроксимация, устойчивость и сходимость. Теорема о сходимости. Корректность постановок краевых задач при их численной аппроксимации.

7.Основные численные алгоритмы решения обыкновенных дифференциальных уравнений: методы Рунге-Кутта и Адамса.

8.Основные методы решения уравнений в частных производных. Понятие слабой аппроксимации и метод дробных шагов. Схемы расщепления для многомерных задач мат. физики.

 

ЛИТЕРАТУРА

  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.Методы организации сетей ЭВМ.

 Основные принципы функционирования сетей ЭВМ. Классификация сетей по масштабу и топологии.

Понятие сетевого протокола. Семиуровневая модель OSI/ISO. Понятие стандарта.

Сетевая архитектура TCP/IP: основные принципы организации и функционирования.

Способы маршрутизации сообщений в сетях ЭВМ.

Основные функции сервера в сети ЭВМ. Состав и структура его программного обеспечения.

Основные принцип и средства управления сетью.

Проблемы защиты информации от несанкционированного доступа.

 

7.Общие вопросы организации вычислительного эксперимента.

 Понятие о вычислительном эксперименте и его инструментальной поддержке. Технология программирования. Жизненный цикл программы. Основные этапы. Инструментальные средства. Машинная графика. Основные графические пакеты.

Пакеты прикладных программ (ППП). Системная часть и наполнение. Языки общения с ППП.

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

Защита авторских прав разработчиков программ. Программистская этика.

 

8.Операционные системы.

 Структура и функции операционных систем. Основные блоки и модули.

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

Управление доступом к данным. Файловые системы (основные типы, характеристика).

Распределение и использование ресурсов вычислительной системы. Основные подходы и алгоритмы планирования.

Управление памятью. Методы организации виртуальной памяти в современных ОС.

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

Организация сетевого взаимодействия в современных ОС.

Виды процессов и управление ими в современных ОС. Средства взаимодействия процессов. Модель клиент-сервер и ее реализация в современных ОС.

Структура современных распределенных ОС. Объектно-ориентированный подход в организации ОС. Основные международные стандарты для построения ОС.

 

9.Методы хранения, организация и доступ к данным

 Концепция типа данных. Абстрактные типы данных. Объекты (основные свойства и отличительные черты).

Основные структуры данных, алгоритмы обработки и поиска.

Модели данных. Иерархическая, сетевая, реляционная, алгебра отношений. Примеры соответствующих СУБД.

Информационно-поисковые системы. Классификация. Методы реализации и методы ускорения поиска.

Базы данных. Основные понятия языков управления и манипулирования данными, Распределенные базы данных, активные базы данных, интегрированные базы данных.

Понятие о базе знаний, их использование в экспертных системах и системах логического вывода. Способы представления знаний.

Организация физического уровня баз данных. Методы индексирования и сжатия данных.

Язык баз данных 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.