© 2001-2017 Московский физико-технический институт
(государственный университет)
Программа по информатике (зима)
на 2 семестр обучения
1. Алгоритм. Модель вычислений (пример: одноленточные машины Тьюринга). Алгоритм. Сложность алгоритма (время, используемая память). Рекурсия.
2. Сортировка, постановка задачи. Алгоритмы сортировки: пузырьком, вставками, Шелла. Сложность алгоритмов в худшем случае и в среднем.
3. Пирамидальная сортировка. Сложность алгоритмов в худшем случае и в среднем.
4. Сортировка слиянием. Сложность алгоритмов в худшем случае и в среднем.
5. Поразрядная сортировка. Сложность алгоритмов в худшем случае и в среднем.
6. Структуры данных. Операции, реализуемые в структурах данных, их сложности. Абстрактный тип данных
7. Массив, список, односвязный список, кольцевой список, стек.
8. Очередь. Очередь с приоритетами.
9. Куча.
10. Объектно-ориентированное программирование. Язык С++.
11. Метод динамического программирования. Пример задачи, которая решается методом динамического программирования. Оценки сложности.
на 4 семестр обучения
1. Алгоритм. Модель вычислений (пример: одноленточные машины Тьюринга). Алгоритм. Сложность алгоритма (время, используемая память). Рекурсия.
2. Сортировка, постановка задачи. Алгоритмы сортировки: пузырьком, вставками. Пирамидальная сортировка. Поразрядная сортировка. Сортировка слиянием. Сложность алгоритмов в худшем случае и в среднем.
3. Структуры данных. Операции, реализуемые в структурах данных, их сложности. Абстрактный тип данных.
4. Массив, список, односвязный список, кольцевой список, стек. Очередь. Очередь с приоритетами.
5. Объектно-ориентированное программирование. Язык С++.
6. Граф. Ориентированный граф. Представления графа. Обход графа в глубину и в ширину. Топологическая сортировка. Подсчет числа путей в орграфе.
7. Сильно связные компоненты. Алгоритм Тарьяна.
8. Поиск кратчайших путей в графе. Алгоритм Флойда. Алгоритм Дейкстры. Алгоритм Форда-Беллмана. Алгоритм A*. Эвристики.
9. Минимальное остовное дерево. Алгоритм Прима. Биномиальная куча. Амортизационная стоимость. Фибоначчиева куча.
10. .Система непересекающихся множеств. Алгоритм Крускала.
11. .Потоки, алгоритм Форда-Фалкерсона.
12. Деревья поиска. Декартовы деревья. Дерево Фенвика. Дерево отрезков и динамическое программирование (Sparse table) для RMQ. Сведение RMQ к LCA и наоборот. Поиск нескольких минимумов на отрезке.
13. Задача поиска подстрок. Алгоритм Рабина-Карпа. Конечный автомат. Алгоритм Бойера-Мура. Алгоритм Кнута-Морриса-Пратта.
14. Алгоритм Ахо-Корасика. Суффиксное дерево. Бор. Алгоритм Укконена. Суффиксный массив.
15. Основные понятия ООП. Конструкторы/деструкторы. Перегрузка методов. Сокрытие методов. Какие методы и операторы необходимы для использования типа в качестве параметра стандартного шаблонного контейнера? Ключевые слова virtual и const. Что такое срезка? Множественное наследование.
16. Исключения. Генерирование и перехват исключений. throw-списки. Их изменение в переопределенных методах. Обработка ошибок в конструкторах и деструкторах.
17. Шаблоны. Последовательные контейнеры STL и адаптеры. Что такое адаптер над контейнером STL?
18. .STL: итераторы. Что такое итератор? Какие бывают итераторы? Что такое итератор с произвольным доступом?
19. .Устройство, основные операции и их стоимость, особенности использования для: vector, . list, deque, stack, map, set, bitset и vector<bool>, unordered_map, priority_queue,
20. .. Сортировка и поиск в STL. В каких контейнерах элементы хранятся упорядоченно? Куча в STL. Ассоциативный массив. Интерфейс, варианты реализации - хэш-таблицы, rb-tree. Реализации в языке.
на 6 семестр обучения
1. Алгоритм. Модель вычислений (пример: одноленточные машины Тьюринга). Алгоритм. Сложность алгоритма (время, используемая память). Рекурсия.
2. Сортировка, постановка задачи. Алгоритмы сортировки: пузырьком, вставками. Пирамидальная сортировка. Поразрядная сортировка. Сортировка слиянием. Сложность алгоритмов в худшем случае и в среднем.
3. Структуры данных. Операции, реализуемые в структурах данных, их сложности. Абстрактный тип данных.
4. Массив, список, односвязный список, кольцевой список, стек. Очередь. Очередь с приоритетами.
5. Объектно-ориентированное программирование. Язык С++.
6. Граф. Ориентированный граф. Представления графа. Обход графа в глубину и в ширину. Топологическая сортировка. Подсчет числа путей в орграфе.
7. Сильно связные компоненты. Алгоритм Тарьяна.
8. Поиск кратчайших путей в графе. Алгоритм Флойда. Алгоритм Дейкстры. Алгоритм Форда-Беллмана. Алгоритм A*. Эвристики.
9. Минимальное остовное дерево. Алгоритм Прима. Биномиальная куча. Амортизационная стоимость. Фибоначчиева куча.
10. .Система непересекающихся множеств. Алгоритм Крускала.
11. .Потоки, алгоритм Форда-Фалкерсона.
12. Деревья поиска. Декартовы деревья. Дерево Фенвика. Дерево отрезков и динамическое программирование (Sparse table) для RMQ. Сведение RMQ к LCA и наоборот. Поиск нескольких минимумов на отрезке.
13. Задача поиска подстрок. Алгоритм Рабина-Карпа. Конечный автомат. Алгоритм Бойера-Мура. Алгоритм Кнута-Морриса-Пратта.
14. Алгоритм Ахо-Корасика. Суффиксное дерево. Бор. Алгоритм Укконена. Суффиксный массив.
15. Основные понятия ООП. Конструкторы/деструкторы. Перегрузка методов. Сокрытие методов. Какие методы и операторы необходимы для использования типа в качестве параметра стандартного шаблонного контейнера? Ключевые слова virtual и const. Что такое срезка? Множественное наследование.
16. Исключения. Генерирование и перехват исключений. throw-списки. Их изменение в переопределенных методах. Обработка ошибок в конструкторах и деструкторах.
17. Шаблоны. Последовательные контейнеры STL и адаптеры. Что такое адаптер над контейнером STL?
18. .STL: итераторы. Что такое итератор? Какие бывают итераторы? Что такое итератор с произвольным доступом?
19. .Устройство, основные операции и их стоимость, особенности использования для: vector, list, deque, stack, map, set, bitset и vector<bool>, unordered_map, priority_queue,
20. .Сортировка и поиск в STL. В каких контейнерах элементы хранятся упорядоченно? Куча в STL. Ассоциативный массив. Интерфейс, варианты реализации - хэш-таблицы, rb-tree. Реализации в языке.
на 8 семестр обучения
1. Алгоритмы и структуры данных
1. Быстрая сортировка (QuickSort).
2. Сортировка слиянием (МегgеSогt).
3. Двоичная куча и сортировка кучей (НеарSort).
4. Хеш-таблица, полиномиальная хэш-функция.
5. Динамическое программирование: общая идея, линейная динамика, матричная, динамика
6. на отрезках.
7. Амортизационный анализ.
8. RMQ.
9. LCA: сведение к RMQ и метод двоичного подъема.
10. Декартово дерево. Декартово дерево по неявному ключу.
11. Минимальное остовное дерево: алгоритмы Прима и Крускала.
12. Максимальные потоки в сети. Методы: Форда-Фалкерсона; Эдмондса-Карпа (б/д).
13. Обход графа в глубину, ширину.
14. Поиск кратчайших путей в графе: алгоритмы Дейкстры, Форда-Беллмана, Флойда-Уоршелла.
15. Поиск сильносвязных компонент в графе.
16. Мосты и точки сочленения в графе.
17. Нахождение подстроки в строке: префикс-функция, алгоритм Кнута-Морриса-Пратта.
18. Стандартные контейнеры: vector, deque, queue, priority_queue, set, map, интераторы, компараторы.
2. Машинное обучение
1. Байесовские методы классификации. Наивный байесовский классификатор.
2. Логистическая регрессия. L1 и L2 регуляризации. Теорема об оптимальности.
3. Метод опорных векторов, решение двойственной задачи. Спрямляющее пространство. Ядра.
4. Многомерная линейная регрессия. Лассо тибширани. Гребневая регрессия.
5. Бустинг. Алгоритм АdaBoost
3 Формальные языки и трансляции
1. Недетерминированные конечные автоматы. Различные варианты определения. Детерминированные конечные автоматы. Их эквивалентность.
2. Регулярные выражения. Теорема Клини об эквивалентности регулярных выражений и конечных автоматов.
3. Минимизация конечных автоматов. Алгоритм минимизации. Алгоритм проверки эквивалентности регулярных выражений.
4. Порождающие грамматики. Иерархия Хомского. Праволинейные, контекстно-свободные, контекстно-зависимые грамматики (определения). Эквивалентность праволинейных грамматик и конечных автоматов.
5. Контекстно-свободные грамматики. Нормальная форма Хомского для контекстно-свободных грамматик.
6. Автоматы с магазинной памятью. Варианты определения. Эквивалентность автоматов с магазинной памятью и контекстно-свободных грамматик.
7. Леммы о разрастании для автоматных и контекстно-свободных языков. Примеры языков, не лежащих в данных классах.
8. Алгоритмы синтаксического разбора для контекстно-свободных грамматик. Алгоритмы Кока-Янгера-Касами и Эрли.
