Темы и требования для вступительных испытаний

Математика

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

Предел, обозначения O() и o(), умение корректно доказывать и применять асимптотические оценки, при необходимости переформулируя в «терминах эпсилон и дельта», непрерывность, производная, первообразная, дифференциал, нахождение экстремума функции от одной и от многих переменных, формула Тейлора.

Дискретная математика и математическая логика

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

Алгебра и теория чисел

Группы, поля, кольца, факторизация, идеал, сравнения, алгоритм Евклида, теоремы Эйлера и Ферма, кольцо многочленов, число корней многочлена, линейные пространства и операторы, базис, размерность, ранг, собственные числа и собственные векторы, характеристический многочлен.

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

Зависимые и независимые события, условные вероятности, формула полной вероятности, математическое ожидание, второй момент, неравенства Маркова и Чебышёва.

Алгоритмы и структуры данных

Оценка алгоритмов

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

Простейшие алгоритмы

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

Простейшие структуры данных

Массив, список, стек, очередь.

Программирование

Знание базовых принципов одного из «традиционных» (C, C++, Java, Python и др.) языков программирования: основы синтаксиса, переменные, условные выражения, циклы, массивы, функции, рекурсия, динамическая память, стек.

Умение написать код для перечисленных выше элементарных алгоритмов.