Процедура проведения вступительного испытания
Форма проведения
Вступительное испытание по информатике по направлению подготовки 27.03.03 Системный анализ и управление проводится в устной форме по билетам.
Порядок проведения
1. Вступительное испытание проводится в соответствии с действующими Положением о восстановлении после отчисления и переводе обучающихся из других организаций и Положением о порядке проведения вступительных испытаний МФТИ.
2. Подготовка ответов на вопросы, содержащиеся в билете, проводится в течение одного астрономического часа, начиная со времени начала вступительного испытания.
3. Билет содержит вопросы по темам, указанным в программе:
- Для переводящихся и восстанавливающихся на 2 семестр: с 1 по 37 тему включительно.
- Для переводящихся и восстанавливающихся на 3 семестр: с 38 по 60 тему включительно.
- Для переводящихся и восстанавливающихся на 4 семестр: с 61 по 72 тему включительно.
- Для переводящихся и восстанавливающихся на 5 семестр: с 73 по 86 тему включительно.
- Для переводящихся и восстанавливающихся на 6-8 семестры: по всем темам программы.
4. Преподаватели имеют право задать дополнительные вопросы по темам, указанным в программе:
- Для переводящихся и восстанавливающихся на 2 семестр: с 1 по 37 тему включительно.
- Для переводящихся и восстанавливающихся на 3 семестр: с 38 по 60 тему включительно.
- Для переводящихся и восстанавливающихся на 4 семестр: с 61 по 72 тему включительно.
- Для переводящихся и восстанавливающихся на 5 семестр: с 73 по 86 тему включительно.
- Для переводящихся и восстанавливающихся на 6-8 семестры: по всем темам программы.
5. Продолжительность ответов на вопросы билета с учетом дополнительных вопросов составляет, как правило, не более сорока минут.
Программа вступительного испытания по информатике
по направлению подготовки 27.03.03 Системный анализ и управление
1. Наивный поиск подстроки в строке.
2. Алгоритм обращения чисел в массиве.
3. Алгоритм циклического сдвига в массиве.
4. Поиск корня уравнения методом бисекции. Требования алгоритма к функции.
5. Поиск значения в упорядоченном массиве методом бисекции.
6. Сортировка обезьяны. Применимость и асимптотика алгоритма.
7. Сортировка вставками. Применимость и асимптотика алгоритма.
8. Сортировка выбором. Применимость и асимптотика алгоритма.
9. Сортировка методом пузырька. Применимость и асимптотика алгоритма.
10. Сортировка дурака. Применимость и асимптотика алгоритма.
11. Сортировка подсчётом. Применимость и асимптотика алгоритма.
12. Поразрядная сортировка. Применимость и асимптотика алгоритма.
13. Быстрая сортировка Хоара. Применимость и асимптотика алгоритма.
14. Сортировка слиянием. Применимость и асимптотика алгоритма.
15. Рекурсия. Прямой и обратный ход рекурсии. Стек вызовов при рекурсии.
16. Алгоритм Евклида. Реализация через цикл и через рекурсию.
17. Быстрое возведение в степень. Асимптотика алгоритма.
18. Вычисление чисел Фибоначчи. Реализация через цикл и через рекурсию.
19. Ханойские башни.
20. Динамическое программирование. Сходство с рекурсией и отличие от неё. Когда рекурсия применима, а динамическое программирование нет.
21. Двумерное динамическое программирование. Задача о количестве траекторий шахматного короля.
22. Наибольшая общая подпоследовательность. Асимптотика алгоритма.
23. Наибольшая возрастающая подпоследовательность. Асимптотика алгоритма.
24. Односвязные списки и массивы.
25. Стек. Использование стека для проверки корректности скобочной последовательности.
26. Двусвязный список. Очередь.
27. Пирамида (куча). Асимптотика добавления и удаления элемента в кучу.
28. Пирамидальная сортировка. Асимптотика алгоритма.
29. Открытая и закрытая хеш-таблица. Описать добавление элемента. Асимптотика поиска.
30. Основные конструкции языка: бинарные и унарные операторы, циклы for и while, оператор ветвления.
31. Ссылочная модель. Проблема копирования массива. Способы решения.
32. Синтаксис описания функций. Именованные параметры. Проблема передачи пустого списка как значения по умолчанию. Способы решения.
33. Строки и операции над ними. Срезы.
34. Стандартные типы данных: list, set, dict. Операции и их асимптотика.
35. Кортежи переменных и множественное присваивание. Отличие кортежей от списков.
36. Использование модулей. Импорт. Пример использования модуля random.
37. Списки в Python. List comprehensions: генерация списков.
38. Определение графа. Степень вершины, петли, кратные рёбра, инцидентность, смежные вершины.
39. Вершины и рёбра. Пути и циклы в графах.
40. Связность графов. Компоненты связности. Сильная и слабая связность.
41. Определение дерева. Свойства дерева. Остовное дерево графа.
42. Взвешенный граф. Минимальное остовное дерево. Алгоритм Прима.
43. Способы представления графа в памяти: список рёбер, матрица смежности, списки смежности.
44. Поиск в глубину и поиск в ширину.
45. Алгоритм Косарайю поиска компонент сильной связности орграфа.
46. Выделение компонент связности несвязного графа.
47. Алгоритм Дейкстры. Асимптотика при различных реализациях.
48. Алгоритм Флойда-Уоршелла. Асимптотика алгоритма и преимущества перед алгоритмом Дейкстры.
49. Эйлеров цикл. Эйлеров путь. Эйлеровы графы.
50. Гамильтонов цикл. Гамильтоновы графы. Задача о коммивояжёре.
51. Топологическая сортировка. Алгоритм Тарьяна.
52. Корневые деревья и их хранение в памяти.
53. Двоичное дерево поиска. Хранение двоичного дерева поиска в памяти.
54. Асимптотика поиска, добавления и удаления элемента в двоичное дерево поиска.
55. Сбалансированное дерево поиска. Балансировка деревьев поиска. Левое и правое малое и большое вращение.
56. Вычисление расстояния Левенштейна.
57. Однозначное декодирование неравномерного кода. Условие Фано. Префиксный бор двоичного кода.
58. Z-функция строки. Наивное вычисление и его оптимизация.
59. Префикс-функция строки. Наивное вычисление и алгоритм Кнута-Морриса-Пратта.
60. Машина Алана Тьюринга. Определение и примеры алгоритмов.
61. История эволюции вычислительных систем, основные функции, выполняемые современными операционными системами, принципы их внутреннего построения.
62. Концепция процессов в операционных системах.
63. Основные алгоритмы планирования процессов.
64. Логические основы взаимодействия процессов.
65. Концепция нитей исполнения и их отличие от обычных процессов.
66. Программные алгоритмы организации взаимодействия процессов и предъявляемые к ним требования.
67. Основные механизмы синхронизации в операционных системах.
68. Основные принципы управления файловыми системами.
69. Организацию управления устройствами ввода-вывода на уровне как технического, так и программного обеспечения, основные функции подсистемы ввода-вывода.
70. Основные проблемы безопасности операционных систем и подходы к их решению.
71. Идеология объектно-ориентированного подхода.
72. Принципы программирования структур данных для современных программ; типовые решения, применяемые для создания программ.
73. Event-driven и message-driven программирование на примере XWindows Widgets, Mac OS X Interface Builder и подсистемы GDI MS Windows. Event-driven и message-driven программирование на примере XWindows Widgets, Mac OS X Interface Builder и подсистемы GDI MS Windows. Принципы агрегирования COM-объектов. Принципы поддержки ООП в операционных системах и языках, общее и различное. Реализация исключений в языке С++ и в ОС Windows.
74. Адресное пространство приложения: куча, стек и статические объекты. Адресное пространство приложения: куча, стек и статические объекты. Динамическая инициализация и клонирование объектов. Хранение объектов в адресном пространстве. Виртуальные функции. Наследование абстрактных классов в С++, чисто виртуальные функции.
75. Базовые основы элементарной техники программирования. Базовые основы элементарной техники программирования. Технические основы программной реализации формальных структур данных, итераторы. Списки, очереди, стеки, наборы, упорядоченные наборы, массивы, деревья, хранение графов, hash-таблицы; примеры использования структур данных, как выбрать структуру, соответствующую задаче. Применение hash-таблиц.
76. Безопасность ПО. Безопасность ПО. Написание программ без «дырок». Техника кодирования защищенных программ и типичные ошибки. Переполнение буфера, определение уровня доступа, работа с минимально возможными привилегиями, криптография и ее корректное применение, предохранение секретных данных, работа с входными данными, проблемы разных путей доступа к одним и тем же данным, запросов к базам данных и веб-страницам, а также проблемы поддержки интернационального ПО. Моделирование угроз. Классификация опасностей STRIDE–Spoofing (подмена данных), Tampering (подделка и изменение содержания данных), Repudiation (незаконный отказ от проведенной операции), Information disclosure (разглашение информации), Denial of service (отказ в обслуживании), Elevation of privilege (незаконное поднятие привилегий). Методика оценки риска DREAD – Damage potential (что может быть сломано), Reproducibility (повторяемость), Exploitability (пригодность угрозы для использования), Affected users (на каких пользователей повлияет), Discoverability (возможно ли детектировать факт использования).
77. Динамическая идентификация и приведение типов (RTTI). Динамическая идентификация и приведение типов (RTTI). Обработка исключительных ситуаций. Разные способы «универсализации» алгоритмов – от абстрактных типов данных «ADT» до стандартной библиотеки шаблонов (Standard Template Library) языка программирования C++ (STL).
78. Краткий обзор ООП реализации в языке C++. Краткий обзор ООП реализации в языках C++. Интерфейсы, полиморфизм и перегрузка операторов в С++. Параметризованные классы. Дружественные функции. Потоки ввода-вывода в С++. Наследование как один из вариантов комбинирования объектов.
79. Краткий сравнительный обзор ООП реализации в языках C++ и ObjectiveC, позднее и раннее связывание. Краткий сравнительный обзор ООП реализации в языках C++ и ObjectiveC, позднее и раннее связывание. Техническая организация ООП поддержки языков программирования для позднего связывания.
80. Параллельное программирование. Параллельное программирование. Параллельные программы – от работы с разделяемой памятью, использования массивно- параллельных компьютеров и до распределенных расчетов на многих физических компьютерах. Декомпозиция задач на параллельные куски. Параллелизм данных, параллелизм кода. Паттерны параллельного программирования: параллелизм на уровне задач – декомпозиция задачи, «разделяй и властвуй» – декомпозиция задач и данных, геометрическая декомпозиция – декомпозиция данных, конвейерное исполнение – декомпозиция потока данных, «фронт волны» – декомпозиция данных c «многомерными» зависимостями. Пример типового шаблона программирования – пул нитей.
81. Принципы и философия ООП в языках, программных системах и операционных системах. Принципы и философия ООП в языках, программных системах и операционных системах. Инкапсуляция, полиморфизм и наследование/агрегирование. Динамический и статический подход в описании классов.
82. Проблемы, специфические для параллельного исполнения многонитевых программ. Проблемы, специфические для параллельного исполнения многонитевых программ – синхронизация (между несколькими нитями), коммуникация (проблемы полосы пропускания и задержек, связанных с обменом данными между нитями), балансировка нагрузки (между нитями), масштабируемость (эффективность использования многих нитей). Написание высокопроизводительных программ, оценка условий и выбор способов реализации.
83. Процесс написания программ. Процесс написания программ. Оформление текстов, требования к текстам и комментариям. Сопровождение программ. Документация на ПО, SDP (software development plan – план разработки ПО).
84. Работа с разделяемой памятью. Синхронизационные примитивы (низкоуровневые атомарные команды, критические секции, взаимоисключающая блокировка – mutex, рекурсивная блокировка – lock, блокировка чтения-записи – read/write lock, многопроцессорная блокировка – spinlock, семафоры, барьеры). Реализация одних примитивов через другие, относительная «мощность» примитивов. Задача о консенсусе как способ оценки примитивов.
85. Техническая специфика параллельных программ. Техническая специфика параллельных программ – производительность, условия «гонки» – race condition, взаимная блокировка – deadlock, повторно-входимые программы, потоко-безопасные (thread-safe) библиотеки. Неблокирующие примитивы синхронизации, транзакционная память. Организация высокопроизводительных параллельных вычислений.
86. Эволюция современного аппаратного обеспечения и ее влияние на программное обеспечение. Эволюция современного аппаратного обеспечения и ее влияние на программное обеспечение. Гипертредовые (многопоточные) и многоядерные процессоры, универсальные графические (GPU) процессоры и новые возможности по их использованию.