Темы и требования для вступительных испытаний
Математика
Математический анализ
Предел, обозначения O() и o(), умение корректно доказывать и применять асимптотические оценки, при необходимости переформулируя в "терминах эпсилон и дельта", непрерывность, производная, первообразная, дифференциал, нахождение экстремума функции от одной и от многих переменных, формула Тейлора.
Алгебра и теория чисел
Группы, поля, кольца, факторизация, идеал, сравнения, алгоритм Евклида, теоремы Эйлера и Ферма, кольцо многочленов, число корней многочлена, линейные пространства и операторы, базис, размерность, ранг, собственные числа и собственные векторы, характеристический многочлен.
Дискретная математика и математическая логика
Отображения и отношения и их свойства, транзитивное замыкание отношения, эквивалентность, отношения порядка, логика высказываний, кванторы, метод математической индукции.
Теория вероятностей
Зависимые и независимые события, условные вероятности, формула полной вероятности, математическое ожидание, второй момент, неравенства Маркова и Чебышёва.
Книги
- И. В. Романовский. Дискретный анализ
- А. Шень. Начала теории множеств. Математическая логика и теория алгоритмов
- Н. Б. Алфутова, А. В. Устинов. Алгебра и теория чисел для математических школ
- Б. М. Давидович, П. Е. Пушкарь, Ю. В. Чеканов. Математический анализ в 57-й школе. Четырехгодичный курс
- А. И. Кострикин. Введение в алгебру (в 3 частях)
Алгоритмы и структуры данных
Оценка алгоритмов
Мы рассчитываем, что вы понимаете, какое количество операций и объём дополнительной памяти необходимы для обсуждаемых алгоритмов и из каких соображений это получается.
Простейшие алгоритмы
Поиск заданного элемента, наибольшего элемента, сортировка вставкой, сортировка пузырьком, быстрая сортировка, иерархические сортировки.
Простейшие структуры данных
Массив, список, стек, очередь.
Книги
- А. Шень. Программирование. Теоремы и задачи
- Н. Вирт. Алгоритмы и структуры данных
- Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ
Программирование
Знание базовых принципов одного из «традиционных» (C, C++, Java, Python и др.) языков программирования: основы синтаксиса, переменные, условные выражения, циклы, массивы, функции, рекурсия, динамическая память, стек.
Умение написать код для перечисленных выше элементарных алгоритмов.
Книги
- Брайан Керниган, Деннис Ритчи. Язык программирования C
- Герберт Шилдт. С++ для начинающих. Шаг за шагом
- Герберт Шилдт. Java. Руководство для начинающих
