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

Математика

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

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

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

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

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

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

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

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

Книги

  • И. В. Романовский. Дискретный анализ
  • А. Шень. Начала теории множеств. Математическая логика и теория алгоритмов
  • Н. Б. Алфутова, А. В. Устинов. Алгебра и теория чисел для математических школ
  • Б. М. Давидович, П. Е. Пушкарь, Ю. В. Чеканов. Математический анализ в 57-й школе. Четырехгодичный курс
  • А. И. Кострикин. Введение в алгебру (в 3 частях)

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

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

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

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

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

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

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

Книги

  • А. Шень. Программирование. Теоремы и задачи
  • Н. Вирт. Алгоритмы и структуры данных
  • Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ

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

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

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


Книги

  • Брайан Керниган, Деннис Ритчи. Язык программирования C
  • Герберт Шилдт. С++ для начинающих. Шаг за шагом
  • Герберт Шилдт. Java. Руководство для начинающих