Программа вступительного испытания по информатике
(по направлениям подготовки 01.03.02 Прикладная математика и информатика и 09.03.01 Информатика и вычислительная техника)
для восстановления после отчисления и перевода из других организаций в МФТИ
Процедура проведения вступительного испытания
Форма проведения
Вступительное испытание по информатике по направлениям подготовки 01.03.02 Прикладная математика и информатика и 09.03.01 Информатика и вычислительная техника проводится с совмещением практической и устной форм.
Порядок проведения
1. Вступительное испытание проводится в соответствии с действующими Положением о восстановлении после отчисления и переводе обучающихся из других организаций и Положением о порядке проведения вступительных испытаний МФТИ.
2. Для выполнения практической части задания используется компьютер с установленным программным обеспечением: текстовым редактором или средой разработки, компилятором C++ и браузером с доступом через Интернет к ресурсу contest.yandex.ru (далее – система Яндекс.Контест).
3. В практической части вступительного испытания предлагаются для решения 5 заданий (при восстановлении или переводе на 2 семестр) или 6 заданий (при восстановлении или переводе на 3 и старше семестры). Решения необходимо отправлять в систему Яндекс.Контест. Допускается доступ только к системе Яндекс.Контест, а также справочным материалам по стандартным библиотекам для допустимых языков программирования. Остальными веб-ресурсами пользоваться запрещено.
4. Длительность практической части составляет 2 астрономических часа (при восстановлении или переводе на 2 семестр) и 2,5 астрономических часа (при восстановлении или переводе на 3 и старше семестры) без перерыва.
5. На устной части вступительного испытания происходит:
− обсуждение решений заданий практической части, которые были отправлены в систему Яндекс.Контест и были успешно решены;
− опрос по билету теоретической части.
6. Устная часть испытания проводится в формате собеседования. Время на подготовку не отводится. Билеты по теоретической части состоят из:
− двух вопросов из блока по программированию и алгоритмам – при переводе и восстановлении на 2 или 3 семестр;
− двух вопросов: одного из блока по программированию и алгоритмам и одного из блока по формальным языкам и трансляциям - при переводе и восстановлении на 4-6 семестры;
− трех вопросов из разных блоков - при переводе и восстановлении на 7 или 8 семестры.
7. Суммарная длительность устной части: 30 минут.
Технические особенности проведения вступительного испытания с применением дистанционных технологий
1.Практическая часть
Во время проведения практической части будет проводиться дистанционный контроль за соблюдением правил проведения вступительного испытания через систему прокторинга МФТИ, расположенную по адресу: http://exams.mipt.ru.
Абитуриент обязан до начала вступительного испытания зарегистрироваться в системе прокторинга, если это не было сделано, и проверить техническую возможность подключения к системе прокторинга. Не подключение к системе прокторинга приравнивается к неявке на письменную часть.
2.Устная часть
Устная часть проводится с использованием одного из общеиспользуемых средств групповой коммуникации (Hangouts, Google Meet, Zoom и пр.).
Блок теоретических вопросов по программированию и алгоритмам
на 2 семестр
1. Алгоритм. Модель вычислений (пример: одноленточные машины Тьюринга). Алгоритм. Сложность алгоритма (время, используемая память). Рекурсия.
2. Сортировка, постановка задачи. Алгоритмы сортировки: пузырьком, вставками, Шелла. Сложность алгоритмов в худшем случае и в среднем.
3. Пирамидальная сортировка. Сложность алгоритмов в худшем случае и в среднем.
4. Сортировка слиянием. Сложность алгоритмов в худшем случае и в среднем.
5. Поразрядная сортировка. Сложность алгоритмов в худшем случае и в среднем.
6. Структуры данных. Операции, реализуемые в структурах данных, их сложности. Абстрактный тип данных
7. Массив, список, односвязный список, кольцевой список, стек.
8. Очередь. Очередь с приоритетами.
9. Куча.
10. Объектно-ориентированное программирование. Язык С++.
11. Метод динамического программирования. Пример задачи, которая решается методом динамического программирования. Оценки сложности.
на 3 семестр
на 4-8 семестры
Блок теоретических вопросов по формальным языкам и трансляциям
на 4-8 семестры
1. Недетерминированные конечные автоматы. Различные варианты определения. Детерминированные конечные автоматы. Их эквивалентность.
2. Регулярные выражения. Теорема Клини об эквивалентности регулярных выражений и конечных автоматов.
3. Минимизация конечных автоматов. Алгоритм минимизации. Алгоритм проверки эквивалентности регулярных выражений.
4. Порождающие грамматики. Иерархия Хомского. Праволинейные, контекстно-свободные, контекстно-зависимые грамматики (определения). Эквивалентность праволинейных грамматик и конечных автоматов.
5. Контекстно-свободные грамматики. Нормальная форма Хомского для контекстно- свободных грамматик.
6. Автоматы с магазинной памятью. Варианты определения. Эквивалентность автоматов с магазинной памятью и контекстно-свободных грамматик.
7. Леммы о разрастании для автоматных и контекстно-свободных языков. Примеры языков, не лежащих в данных классах.
8. Алгоритмы синтаксического разбора для контекстно-свободных грамматик. Алгоритмы Кока-Янгера-Касами и Эрли.
Блок теоретических вопросов по машинному обучению
на 7-8 семестры
1. Основные понятия машинного обучения. Стандартные задачи (классификация, регрессия, кластеризация). Примеры метрик качества. Примеры простых алгоритмов, решающих стандартные задачи: kNN, KMeans, наивный байесовский классификатор.
2. Метрики качества в задачах классификации и регрессии (accuracy, precision, recall, F-мера, ROC-AUC, log loss, MSE, MAE, квантильные потери, MAPE, SMAPE). Работа с признаками: извлечение признаков, кодирование категориальных признаков.
3. Линейные методы классификации и регрессии. Функции потерь и регуляризаторы. Метод стохастического градиентного спуска. Оптимизационная задача в логистической регрессии и оценка вероятности принадлежности к классу.
4. Линейные методы классификации и регрессии. Оптимизационная задача в методе опорных векторов.
5. Решающие деревья в задаче классификации и задаче регрессии. Ансамбли решающих деревьев: случайный лес и градиентный бустинг над деревьями.
6. Решающие деревья в задаче классификации и задаче регрессии. Bias-variance trade-off (без вывода). Анализ бустинга и бэггинга с помощью bias-variance trade-off.
7. Нейронные сети, обучение (backprop), слои для сверточных сетей (dense, conv, pooling, batchnorm, dropout), нелинейности (relu vs sigmoid, softmax), функции потерь (logloss, l2, hinge).
8. Рекуррентные нейросети, обучение (backprop tt), отличие от сверточных, разновидности рекуррентных слоев (RNN, LSTM, GRU), примеры использования.
9. Задача кластеризации. Агломеративные и статистические методы кластеризации. Формула Ланса-Уильямса, алгоритм k-Means.
10. Задача снижения размерности пространства признаков. Метод главных компонент (PCA) и t-SNE (оба метода - основная идея, без доказательств).