Главная
страница 1
Программа и правила проведения вступительного испытания

для абитуриентов, поступающих в магистратуру

по направлению подготовки «Фундаментальная информатика и информационные технологии» (программа «Информатика и компьютерные науки»)
Правила проведения собеседования


  1. Все поступающие в магистратуру проходят собеседование, которое оценивается по стобалльной шкале.

  2. Каждый поступающий в магистратуру получает 2 вопроса по основным базовым разделам математики и 3 задачи на проверку базовых навыков решения задач.

  3. Ответ по каждому вопросу оценивается по десятибалльной шкале. Решение каждой задачи оценивается по десятибалльной шкале.

  4. К баллам, полученным на собеседовании, добавляются баллы за выпускную квалификационную работу по следующей схеме:

Оценка «3» – 30 баллов

Оценка «4» – 40 баллов

Оценка «5» – 50 баллов


  1. Минимальное количество баллов, подтверждающее успешное прохождение вступительного испытания, – 55 баллов.


Программа вступительного испытания
Дискретная математика

1. Булева алгебра множеств. Число подмножеств. Бинарные отношения. Отношения эквивалентности и частичного порядка. Отображения, взаимно-однозначные отображения. Мощность множества. Счетные множества и их свойства. Теорема Кантора о несчетности (0,1). Мощность континуума.

2. Основной принцип комбинаторики. Перестановки, сочетания, размещения. Перестановки и сочетания с повторениями. Формула включений и исключений; число беспорядков. Биномиальная и полиномиальная формулы.

3. Производящая функции для последовательности, примеры. Рекуррентные соотношения. Решение линейных рекуррентных соотношений с помощью производящих функций, пример: формула Бине для чисел Фибоначчи.

4. Неориентированные и ориентированные графы. Способы задания с помощью соответствия, матриц смежности и инцидентности. Компоненты связности. Деревья, число остовных деревьев произвольного графа. Эйлеровы и гамильтоновы графы. Раскраска графа. Теорема о 4-х красках.

Математическая логика

1. Формальные системы. Принцип обобщенной индукции. Корректность и полнота.

2. Формальные теории первого порядка. Интерпретации. Истинность и выполнимость. Общезначимые формулы.

3. Формальная арифметика. Система аксиом. Важнейшие арифметические функции и предикаты.

4. Примитивно рекурсивные и рекурсивные функции.

Теория вероятностей

1. Вероятностные пространства. Формулы сложения и умножения, полной вероятности, Байеса. Формула Бернулли.

2. Случайные величины. Функции распределения и плотности распределения. Важнейшие функции распределения.

3. Закон больших чисел для случайных величин. Центральная предельная теорема.

4. Оценки параметров распределения. Доверительные интервалы. Проверка гипотез.

Системное программирование

1. Виды списочных структур. Методы работы со списками.

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

3. Конечные автоматы и регулярные языки. Синтаксический анализ регулярных языков.

4. Формальные языки и грамматики. Классы порождающих грамматик. Методы определения синтаксиса языков программирования.

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

1. Предел функции. Непрерывность. Теоремы Вейерштрасса и Больцано-Коши о непрерывных на отрезке функциях. Точки разрыва функций.

2. Дифференцируемость функции. Основные теоремы дифференциального исчисления (Ферма, Ролля, Лагранжа). Локальный экстремум. Необходимое и достаточное условие существования экстремума.

3. Определенный интеграл. Верхние и нижние суммы Дарбу. Критерий интегрируемости. Несобственные интегралы. Признаки Дирихле и Абеля сходимости несобственных интегралов.

4. Функции нескольких переменных. Дифференцируемость функций нескольких переменных. Частные производные. Формула Тейлора. Необходимые и достаточные условия существования экстремума. Условный экстремум.

Алгебра и геометрия

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

2. Линейный оператор и его матрица. Собственные числа и собственные векторы линейного оператора. Характеристический многочлен линейного оператора и его свойства.

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

4. Определение евклидова пространства. Общий вид скалярного произведения. Матрица Грама и ее изменение при изменении базиса. Связь скалярного произведения с квадратичными формами и теорема о существовании ортонормированного базиса. Скалярное произведение в ортонормированном базисе. Длина (модуль, норма) вектора и неравенство Коши-Буняковского. Неравенство треугольника и теорема Пифагора.

Дифференциальные уравнения

1. Теорема существования и единственности решения задачи Коши для уравнения 1-го порядка. Уравнения 1-го порядка, интегрируемые в квадратурах (с разделяющимися переменными, однородные, линейные, Бернулли, в полных дифференциалах, неразрешимые относительно производной).

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

3. Линейные неоднородные системы. Матричное решение. Фундаментальная матрица. Общее решение линейной неоднородной системы. Матрица Коши. Автономные системы на плоскости. Фазовые портреты.

Численные методы и методы оптимизации

1. Методы одномерной оптимизации (метод половинного деления, метод золотого сечения).

2. Методы многомерной оптимизации. Градиентные методы. Метод покоординатного спуска.

3. Метод последовательных приближений (для решения интегральных уравнений, для задачи Коши).



4. Сеточные методы на примере решения уравнения теплопроводности.

5. Интерполяция. Интерполяционный многочлен Лагранжа. Аппроксимация. Метод наименьших квадратов.


Смотрите также:
Программа «Информатика и компьютерные науки»
50kb.
1 стр.
Аннотация рабочей программы дисциплины
28.98kb.
1 стр.
Рабочей программы дисциплины объектные базы данных Место дисциплины в структуре ооп
24.94kb.
1 стр.
Содержание : Что изучает информатика
178.06kb.
1 стр.
Тезисы. Секция: информатика, подсекция: информационные технологии. Тема работы: Компьютерные игры. Игровая зависимость школьника. Пути и способы преодоления. Лебедев Артем, 9 в класс, 261 гимназия
14.45kb.
1 стр.
Программа дисциплины Электронная коммерция и бизнес для направления 080500. 68 «Бизнес-информатика»
131.28kb.
1 стр.
Программа дисциплины «Электронные платежные средства»
127.13kb.
1 стр.
Программа курса по информатике и икт (региональный компонент) «компьютерные науки»
520.51kb.
2 стр.
Дайте определение науки «Информатика» Информатика
765.73kb.
3 стр.
Вопросы по информатике
253.4kb.
1 стр.
«Информационные технологии в сложных системах»
232.92kb.
1 стр.
История и предмет правовой информатики
840.48kb.
12 стр.