Экзамен

  • Устный экзамен по билетам
  • В билете два вопроса
  • Итоговая оценка складывается из устного ответа и работы за семестр на практиках

Процесс экзамена:

  • студент тянет билет и задачу;
  • готовится 45 минут (пишет опорный конспект);
  • приходит к преподавателям, рассказывает ответ на вопросы билета;
  • преподаватели могут задавать дополнительные вопросы;

Правила:

  • Пользоваться конспектами, ЭВМ и интернетом нельзя.
  • Если у студента случилась форс-мажорная ситуация, то надо сообщить об этом преподавателю до экзамена.

Вопросы к экзамену

  1. Оценка сложности алгоритма. Асимптотическая нотация. Примеры алгоритмов: константная, O(n), O(n^2), O(log(n)), O(N*log(N)) сложности.
  2. Анализ учетных стоимостей. Банковский метод на примере структуры данных Vector (вставка, удаление элемента; стратегия выделения и освобождения памяти).
  3. Сортировки вставками. Сортировки слиянием.
  4. Модель “Решающее дерево” для оценки сложности сортировки.
  5. Структура данных Куча. Сортировка кучей.
  6. Сортировка подсчетом. Цифровая сортировка.
  7. Хеш-таблица. Разрешение коллизий методом цепочки.
  8. Хеш-таблица. Разрешение коллизий линейным методом.
  9. Бинарный поиск. Поиск верхней и нижней границы.
  10. Динамическое программирование. Разбор задачи “Наибольшая возрастающая подпоследовательность”.
  11. Динамическое программирование. Разбор задачи “Наибольшая общая подпоследовательность”.
  12. Динамическое программирование. Разбор задачи “Редакторское расстояние”.
  13. Запросы на отрезках. Префиксная сумма, корневая эвристика,
  14. Запросы на отрезках. Дерево отрезков.
  15. Двоичное дерево поиска. Обходы дерева поиска (в глубину, в ширину).
  16. AVL Дерево. Большой-малый поворот.
  17. Красно-чёрное дерево.
  18. Косое дерево (Splay Tree)
  19. Поиск в глубину. Проверка на циклы. Топологическая сортировка.
  20. Алгоритм Дейкстры кратчайшего поиска пути в графе.
  21. Алгоритм А* поиска кратчайшего пути в графе.
  22. Алгоритм Форда-Беллмана.
  23. Алгоритм Флойда.
  24. Инфиксная и обратная польская запись. Алгоритм сортировочной станции.
  25. SOLID принципы. Паттерн Итератор.
  26. SOLID принципы. Паттерн Optional, Lazy, Partial.

Материалы для подготовки

  1. Алгоритмы: построение и анализ. Кормен, Лейзерсон, Ривест, Штайн. pdf
  2. E-maxx algo
  3. Записи лекций в ОмГУ
  4. Записи лекций ШАДа