Программа вступительного испытания по информатике

(по направлениям подготовки 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.    Объясните понятия compilation error, runtime error и undefined behaviour. Приведите по паре примеров того, другого и третьего.

2.    Что такое выражения, операторы? Для чего предназначены и что по стандарту делают следующие операторы: тернарный оператор, оператор “запятая”, унарная звездочка, унарный амперсанд, операторы “точка” и “стрелочка”, двойное двоеточие, префиксный и постфиксный инкремент, бинарные & и &&, операторы простого и составного присваивания, операторы << и >>?

3.    Что такое стековая память, статическая память и динамическая память? Что такое stack overflow? Зачем нужен оператор new? Что такое утечки памяти? Что такое сборка мусора?

4.    Что такое указатели, какие операции они поддерживают, в чем сходства и различия между указателями и массивами?

5.    Объясните идею ссылок (references). Для чего они нужны, чем они отличаются от указателей? Что такое “передача аргументов по ссылке и по значению”? Как в С++03 реализовать функцию swap?

6.    Что такое класс, структура, в чем разница между ними? Что такое поля, методы, модификаторы доступа, инкапсуляция?

7.    Что такое конструкторы, деструкторы, для чего они нужны, каков синтаксис их определения? Те же вопросы про конструктор копирования и оператор присваивания. Приведите примеры определения конструкторов для класса String.

8.    Что такое перегрузка функций? Что такое перегрузка операторов? Приведите примеры операторов, которые можно и нельзя перегружать. Приведите пример перегрузки хоть какого-нибудь оператора (напишите сигнатуру его перегрузки).

9.    Что такое наследование? В чем разница между приватным, публичным, и защищенным наследованием? Как размещаются в памяти объекты при наследовании?

10. Что такое виртуальные функции, чисто виртуальные функции, абстрактные классы? Что такое виртуальное наследование и какую проблему оно решает?

11. Что такое шаблоны? Что такое инстанцирование шаблонов, специализация шаблонов? Покажите на примерах. Приведите пример каких-нибудь шаблонов из STL, обладающих специализацией.

12. Что такое шаблонное метапрограммирование? Реализуйте проверку числа n на простоту в compile-time с помощью шаблонной рекурсии.

13. В чем разница между C-style cast, static_cast, const_cast, reinterpret_cast и dynamic_cast? Когда нужен, а когда неуместен каждый из этих операторов?

14. Что такое исключения? Как пользоваться механизмом обработки исключений? Как бросить, поймать исключение? Приведите какой-нибудь пример.

15. Понятие сложности алгоритма. О-нотация. Определения О-большого, омега-большого и тета-большого с примерами. Сложность умножения длинных чисел. Сложность умножения матриц.

16. Бинарный поиск, оценка времени работы и реализация.

17. Бинарное возведение в степень для чисел и матриц, оценка времени работы. Нахождение n-го числа Фибоначчи с помощью бинарного возведения матрицы в степень.

18. Амортизированная сложность, метод монеток. Оценка сложности добавления в динамический массив. Сложность в среднем, ее отличие от амортизированной сложности.

19. Стек. Очередь. Двусвязный список. Поддерживаемые операции и их сложность. Реализация.

20. Поддержка минимума в очереди. Очередь на двух стеках.

21. Задача сортировки n объектов. Стабильные и нестабильные сортировки. Нижняя оценка O(n log n) для сложности алгоритма сортировки, основанного на сравнениях.

22. Сортировка слиянием. Оценка времени работы. Реализация. Поиск количества инверсий в перестановке за O(n log n).

23. Быстрая сортировка. Оценка времени работы в среднем и худшем случае. Реализация.

24. Двоичная куча. Хранение двоичной кучи в массиве. Поддерживаемые операции, их время работы и реализация. Построение кучи за линейное время. Сортировка с помощью кучи (heapsort).

25. Задача о k-й порядковой статистике. Решение за линейное время в среднем и худшем случае.

26. Хеш-таблицы. Хеширование методом открытой адресации и методом цепочек.

27. Двоичные деревья поиска. AVL-дерево. Определение, оценка времени работы основных операций, их реализация.

28. Красно-черное дерево: определение, оценка времени работы основных операций.

29. Splay-дерево: определение, оценка времени работы основных операций.

30. Декартово дерево: определение, оценка времени работы основных операций, их реализация.

31. Декартово дерево по неявному ключу. Применение для операций над массивом: вставить, удалить элемент, узнать сумму на отрезке.

32. Дерево отрезков (ДО): определение, основные операции, реализация. Нахождение сумм и минимумов на подотрезке.

33. Отложенные операции в дереве отрезков: присваивание на подотрезке, прибавление константы к подотрезку.

на 3 семестр

1. Объясните понятия compilation error, runtime error и undefined behaviour. Приведите по паре примеров того, другого и третьего.

2. Что такое выражения, операторы? Для чего предназначены и что по стандарту делают следующие операторы: тернарный оператор, оператор “запятая”, унарная звездочка, унарный амперсанд, операторы “точка” и “стрелочка”, двойное двоеточие, префиксный и постфиксный инкремент, бинарные & и &&, операторы простого и составного присваивания, операторы << и >>?

3. Что такое стековая память, статическая память и динамическая память? Что такое stack overflow? Зачем нужен оператор new? Что такое утечки памяти? Что такое сборка мусора?

4. Что такое указатели, какие операции они поддерживают, в чем сходства и различия между указателями и массивами?

5. Объясните идею ссылок (references). Для чего они нужны, чем они отличаются от указателей? Что такое “передача аргументов по ссылке и по значению”? Как в С++03 реализовать функцию swap?

6. Что такое класс, структура, в чем разница между ними? Что такое поля, методы, модификаторы доступа, инкапсуляция?

7. Что такое конструкторы, деструкторы, для чего они нужны, каков синтаксис их определения? Те же вопросы про конструктор копирования и оператор присваивания. Приведите примеры определения конструкторов для класса String.

8. Что такое перегрузка функций? Что такое перегрузка операторов? Приведите примеры операторов, которые можно и нельзя перегружать. Приведите пример перегрузки хоть какого-нибудь оператора (напишите сигнатуру его перегрузки).

9. Что такое наследование? В чем разница между приватным, публичным, и защищенным наследованием? Как размещаются в памяти объекты при наследовании?

10. Что такое виртуальные функции, чисто виртуальные функции, абстрактные классы? Что такое виртуальное наследование и какую проблему оно решает?

11. Что такое шаблоны? Что такое инстанцирование шаблонов, специализация шаблонов? Покажите на примерах. Приведите пример каких-нибудь шаблонов из STL, обладающих специализацией.

12. Что такое шаблонное метапрограммирование? Реализуйте проверку числа n на простоту в compile-time с помощью шаблонной рекурсии.

13. В чем разница между C-style cast, static_cast, const_cast, reinterpret_cast и dynamic_cast? Когда нужен, а когда неуместен каждый из этих операторов?

14. Что такое исключения? Как пользоваться механизмом обработки исключений? Как бросить, поймать исключение? Приведите какой-нибудь пример.

15. Понятие сложности алгоритма. О-нотация. Определения О-большого, омега-большого и тета-большого с примерами. Сложность умножения длинных чисел. Сложность умножения матриц.

16. Бинарный поиск, оценка времени работы и реализация.

17. Бинарное возведение в степень для чисел и матриц, оценка времени работы. Нахождение n-го числа Фибоначчи с помощью бинарного возведения матрицы в степень.

18. Амортизированная сложность, метод монеток. Оценка сложности добавления в динамический массив. Сложность в среднем, ее отличие от амортизированной сложности.

19. Стек. Очередь. Двусвязный список. Поддерживаемые операции и их сложность. Реализация.

20. Поддержка минимума в очереди. Очередь на двух стеках.

21. Задача сортировки n объектов. Стабильные и нестабильные сортировки. Нижняя оценка O(n log n) для сложности алгоритма сортировки, основанного на сравнениях.

22. Сортировка слиянием. Оценка времени работы. Реализация. Поиск количества инверсий в перестановке за O(n log n).

23. Быстрая сортировка. Оценка времени работы в среднем и худшем случае. Реализация.

24. Двоичная куча. Хранение двоичной кучи в массиве. Поддерживаемые операции, их время работы и реализация. Построение кучи за линейное время. Сортировка с помощью кучи (heapsort).

25. Задача о k-й порядковой статистике. Решение за линейное время в среднем и худшем случае.

26. Хеш-таблицы. Хеширование методом открытой адресации и методом цепочек.

27. Двоичные деревья поиска. AVL-дерево. Определение, оценка времени работы основных операций, их реализация.

28. Красно-черное дерево: определение, оценка времени работы основных операций.

29. Splay-дерево: определение, оценка времени работы основных операций.

30. Декартово дерево: определение, оценка времени работы основных операций, их реализация.

31. Декартово дерево по неявному ключу. Применение для операций над массивом: вставить, удалить элемент, узнать сумму на отрезке.

32. Дерево отрезков (ДО): определение, основные операции, реализация. Нахождение сумм и минимумов на подотрезке.

33. Отложенные операции в дереве отрезков: присваивание на подотрезке, прибавление константы к подотрезку.

34. Рассмотрим контейнеры std::vector, std::list, std::deque. Каковы основные операции, предоставляемые ими, и скорость работы этих операций? Как (в общих чертах) изнутри реализованы эти контейнеры?

35. Рассмотрим контейнеры std::map, std::set, std::unordered_map, std::unordered_set. Каковы основные операции, предоставляемые ими, и скорость работы этих операций? Как (в общих чертах) изнутри реализованы эти контейнеры?

36. Что такое итераторы? Какие виды итераторов существуют? Зачем они вообще нужны? Какие итераторы поддерживает каждый из контейнеров, упомянутых в предыдущих двух вопросах?

37. Что такое компараторы? Что такое функциональные объекты? Приведите хоть один пример.

38. Для чего нужна move-семантика? Расскажите в общих чертах, что это такое. Для чего нужна функция std::move и что она делает? Что такое lvalue, rvalue, prvalue, glvalue и xvalue? Что такое rvalue-ссылки и в чем их особенности, в чем отличия от обычных ссылок?

39. Что такое perfect forwarding? Для чего нужна функция std::forward и что она делает?

40. В каких контекстах применимо ключевое слово auto? Для чего нужно ключевое слово decltype? Для чего нужна конструкция decltype(auto)?

41. Что такое умные указатели? Для решения каких проблем они нужны? Расскажите об операциях, которые поддерживает класс std::shared_ptr. Как (в общих чертах) он устроен изнутри?

42. Что такое аллокаторы? Что из себя представляет класс std::allocator, как и для чего он используется?

43. Что такое лямбда-выражения, каков их синтаксис? Приведите хоть один пример использования.

44. Что такое SFINAE? Для чего нужна структура std::enable_if, как она устроена и как ей пользоваться?

45. Динамическое программирование (ДП): задача о кузнечике (набор максимальной суммы на массиве), задача о черепашке (набор минимальной суммы на таблице), задача о наибольшей общей подпоследовательности.

46. Задача о рюкзаке: решение с помощью динамического программирования.

47. Задача коммивояжера: решение за O(2^n * n^2).

48. Динамическое программирование по профилю. Задача о симпатичных узорах (количество раскрасок таблицы в 2 цвета без одноцветных квадратиков 2х2), ее решение за O(4^n * (n+m)).

49. Задача о наибольшей возрастающей подпоследовательности. Решение за O(n log n) с помощью ДП и с помощью ДО.

50. Определение графа, орграфа, пути, простого пути, цикла, простого цикла. Связность графа. Способы представления графа в памяти.

51. Обход в ширину (BFS), оценка времени работы, реализация.

52. Обход в глубину (DFS), оценка времени работы, реализация.

53. Топологическая сортировка. Решение за O(m+n), доказательство корректности и реализация.

54. Поиск компонент сильной связности в ориентированном графе, алгоритм Косарайю.

55. Поиск мостов и точек сочленения в графе за O(m+n), доказательство корректности.

56. Определение дерева. Поиск диаметра в дереве, оценка времени работы.

57. Задача о кратчайших путях. Алгоритм Дейкстры. Реализация за O(m log n) и за O(n^2).

58. Алгоритм Форда-Беллмана, оценка времени работы и реализация. Поиск циклов отрицательного веса в графе.

59. Алгоритм Флойда-Уоршелла, оценка времени работы и реализация.

60. Система непересекающихся множеств (DSU). Эвристика по рангу и эвристика сжатия путей, оценка времени работы б/д.

61. Задача о минимальном остовном дереве. Алгоритм Крускала. Оценка времени работы.

62. Алгоритм Прима, оценка времени работы.

63. Паросочетания. Алгоритм Куна поиска наибольшего паросочетания в двудольном графе.

64. Теорема Форда-Фалкерсона. Алгоритм Эдмондса-Карпа поиска максимального потока в графе за O(n * m^2).

65. Алгоритм Диница, оценка времени работы, реализация за O(n^2 * m).

на 4-8 семестры

1. Объясните понятия compilation error, runtime error и undefined behaviour. Приведите по паре примеров того, другого и третьего.
2. Что такое выражения, операторы? Для чего предназначены и что по стандарту делают следующие операторы: тернарный оператор, оператор “запятая”, унарная звездочка, унарный амперсанд, операторы “точка” и “стрелочка”, двойное двоеточие, префиксный и постфиксный инкремент, бинарные & и &&, операторы простого и составного присваивания, операторы << и >>?
3. Что такое стековая память, статическая память и динамическая память? Что такое stack overflow? Зачем нужен оператор new? Что такое утечки памяти? Что такое сборка мусора?
4. Что такое указатели, какие операции они поддерживают, в чем сходства и различия между указателями и массивами?
5. Объясните идею ссылок (references). Для чего они нужны, чем они отличаются от указателей? Что такое “передача аргументов по ссылке и по значению”? Как в С++03 реализовать функцию swap?
6. Что такое класс, структура, в чем разница между ними? Что такое поля, методы, модификаторы доступа, инкапсуляция?
7. Что такое конструкторы, деструкторы, для чего они нужны, каков синтаксис их определения? Те же вопросы про конструктор копирования и оператор присваивания. Приведите примеры определения конструкторов для класса String.
8. Что такое перегрузка функций? Что такое перегрузка операторов? Приведите примеры операторов, которые можно и нельзя перегружать. Приведите пример перегрузки хоть какого-нибудь оператора (напишите сигнатуру его перегрузки).
9. Что такое наследование? В чем разница между приватным, публичным, и защищенным наследованием? Как размещаются в памяти объекты при наследовании?
10. Что такое виртуальные функции, чисто виртуальные функции, абстрактные классы? Что такое виртуальное наследование и какую проблему оно решает?
11. Что такое шаблоны? Что такое инстанцирование шаблонов, специализация шаблонов? Покажите на примерах. Приведите пример каких-нибудь шаблонов из STL, обладающих специализацией.
12. Что такое шаблонное метапрограммирование? Реализуйте проверку числа n на простоту в compile-time с помощью шаблонной рекурсии.
13. В чем разница между C-style cast, static_cast, const_cast, reinterpret_cast и dynamic_cast? Когда нужен, а когда неуместен каждый из этих операторов?
14. Что такое исключения? Как пользоваться механизмом обработки исключений? Как бросить, поймать исключение? Приведите какой-нибудь пример.
15. Понятие сложности алгоритма. О-нотация. Определения О-большого, омега-большого и тета-большого с примерами. Сложность умножения длинных чисел. Сложность умножения матриц.
16. Бинарный поиск, оценка времени работы и реализация.
17. Бинарное возведение в степень для чисел и матриц, оценка времени работы. Нахождение n-го числа Фибоначчи с помощью бинарного возведения матрицы в степень.
18. Амортизированная сложность, метод монеток. Оценка сложности добавления в динамический массив. Сложность в среднем, ее отличие от амортизированной сложности.
19. Стек. Очередь. Двусвязный список. Поддерживаемые операции и их сложность. Реализация.
20. Поддержка минимума в очереди. Очередь на двух стеках.
21. Задача сортировки n объектов. Стабильные и нестабильные сортировки. Нижняя оценка O(n log n) для сложности алгоритма сортировки, основанного на сравнениях.
22. Сортировка слиянием. Оценка времени работы. Реализация. Поиск количества инверсий в перестановке за O(n log n).
23. Быстрая сортировка. Оценка времени работы в среднем и худшем случае. Реализация.
24. Двоичная куча. Хранение двоичной кучи в массиве. Поддерживаемые операции, их время работы и реализация. Построение кучи за линейное время. Сортировка с помощью кучи (heapsort).
25. Задача о k-й порядковой статистике. Решение за линейное время в среднем и худшем случае.
26. Хеш-таблицы. Хеширование методом открытой адресации и методом цепочек.
27. Двоичные деревья поиска. AVL-дерево. Определение, оценка времени работы основных операций, их реализация.
28. Красно-черное дерево: определение, оценка времени работы основных операций.
29. Splay-дерево: определение, оценка времени работы основных операций.
30. Декартово дерево: определение, оценка времени работы основных операций, их реализация.
31. Декартово дерево по неявному ключу. Применение для операций над массивом: вставить, удалить элемент, узнать сумму на отрезке.
32. Дерево отрезков (ДО): определение, основные операции, реализация. Нахождение сумм и минимумов на подотрезке.
33. Отложенные операции в дереве отрезков: присваивание на подотрезке, прибавление константы к подотрезку.

Блок теоретических вопросов по формальным языкам и трансляциям

на 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 (оба метода - основная идея, без доказательств).