Программа для поступления в Школу анализа данных
Алгебра
- Подстановки. Определение подстановки, четность подстановок. Произведение подстановок, разложение подстановок в произведение транспозиций и независимых циклов.
- Комплексные числа. Геометрическое изображение, алгебраическая и тригонометрическая форма записи, извлечение корней, корни из единицы.
- Системы линейных уравнений. Прямоугольные матрицы. Приведение матриц и систем линейных уравнений к ступенчатому виду. Метод Гаусса.
- Линейная зависимость и ранг. Линейная зависимость строк (столбцов). Основная лемма о линейной зависимости, базис и ранг системы строк (столбцов). Ранг матрицы. Критерий совместности и определенности системы линейных уравнений в терминах рангов матриц. Фундаментальная система решений однородной системы линейных уравнений.
- Определитель. Определитель квадратной матрицы, его основные свойства. Критерий равенства определителя нулю. Формула разложения определителя матрицы по строке (столбцу).
- Операции над матрицами. Операции над матрицами и их свойства. Теорема о ранге произведения двух матриц. Определитель произведения квадратных матриц. Обратная матрица, ее явный вид (формула), способ выражения с помощью элементарных преобразований строк.
- Векторные пространства; базис. Векторное пространство, его базис и размерность. Преобразования координат в векторном пространстве. Подпространства как множества решений систем однородных линейных уравнений. Связь между размерностями суммы и пересечения двух подпространств. Линейная независимость подпространств. Базис и размерность прямой суммы подпространств.
- Линейные отображения и линейные операторы. Линейные отображения, их запись в координатах. Образ и ядро линейного отображения, связь между их размерностями. Сопряженное пространство и сопряженные базисы. Изменение матрицы линейного оператора при переходе к другому базису.
- Билинейные и квадратичные функции. Билинейные функции, их запись в координатах. Изменение матрицы билинейной функции при переходе к другому базису. Ортогональное дополнение к подпространству относительно симметрической билинейной функции. Связь между симметрическими билинейными и квадратичными функциями. Существование ортогонального базиса для симметрической билинейной функции. Нормальный вид вещественной квадратичной функции. Закон инерции.
- Собственные векторы и собственные значения. Собственные векторы и собственные значения линейного оператора. Собственные подпространства линейного оператора, их линейная независимость. Условие диагонализируемости оператора.
Математический анализ
- Пределы и непрерывность. Пределы последовательностей и функций. Непрерывные функции.
- Ряды. Числовые и функциональные ряды. Признаки сходимости (Даламбера, Коши, интегральный, Лейбница). Абсолютно и условно сходящиеся ряды.
- Дифференцирование. Дифференцирование функций. Применение производной для нахождения экстремумов функций. Формула Тейлора.
- Интегрирование. Определенный и неопределенный интегралы. Методы интегрирования функций. Первообразные различных элементарных функций.
Комбинаторика
- Основные правила комбинаторики. Правило подсчета количества комбинаторных объектов. Pigeonhole Principle. Примеры.
- Sets. Круги Эйлера, операции на множествах. Формула включений и исключений. Примеры.
- Combinations. Partial Permutations, перестановки и сочетания. Binomial Theorem. Треугольник Паскаля. Combinations с повторениями.
Теория вероятностей
- Основные понятия теории вероятностей. Определение вероятностного пространства, простейшие дискретные случаи (выборки с порядком и без него, упорядоченные и неупорядоченные), классическая вероятностная модель. Случайная величина, функция распределения.
- Условные вероятности. Определение условной вероятности, Law of Total Probability, формула Байеса.
- Математическое ожидание, дисперсия, корреляция. Определение математического ожидания, дисперсии, ковариации и корреляции, их свойства.
- Independence. Попарная независимость и независимость в совокупности. (Chain and Sum Rules in Probability.)
- Основные теоремы теории вероятностей. Chebyshev’s Inequality. Laws of Large Numbers. Центральная предельная теорема.
- Распределения. Стандартные дискретные и непрерывные распределения, их математические ожидания, дисперсии и свойства:
Программирование, алгоритмы и структуры данных
(предполагается владение одним из основных языков программирования, предпочтительным является C/C++)
- Простейшие конструкции языка программирования. Циклы, ветвления, рекурсия.
- Анализ алгоритмов. Понятие о сложности по времени и по памяти. Асимптотика, О-символика. Инварианты, пред- и пост- условия. Доказательство корректности алгоритмов.
- Простейшие структуры данных. Массивы, стеки, очереди, связные списки. Сравнение временных затрат при различных типах операций.
- Строки и операции над ними. Представление строк. Вычисление длины, конкатенация, быстрый поиск подстрок.
- Сортировки. Нижняя теоретико-информационная оценка сложности задачи сортировки. Алгоритмы сортировки вставками, пузырьком, быстрая сортировка, сортировка слиянием. Оценка сложности.
- Указатели. Указатели и динамическое управление памятью.