Коллоквиум 1

Устный коллоквиум по лекциям 1–5. Он закрывает блок про анализ алгоритмов, последовательности, сортировки, рекурсию и бинарный поиск.

Смысл коллоквиума в том, чтобы прослушанное стало ответом, который вы можете произнести и проследить на маленьком примере. Готовясь, вы заучиваете формулировки и решения коротких задач. Это закрепляет материал лекций и семинаров и тренирует тот же навык, который понадобится на устном экзамене: говорить своими словами, держать пример и не терять ход рассуждения.

Ниже закрытый список. На коллоквиуме спрашивают только из него: два теоретических вопроса и одну задачу на листочке. Стек, очередь и дек как абстрактные типы данных в этот список не входят: их читают отдельной лекцией после коллоквиума.

Приходите заранее. Экзаменаторы уже будут на месте, подготовку можно начать до общего сбора.

Как проходит

Как готовить теоретический ответ

  1. Назовите задачу, которую решает алгоритм: что на входе и что обещаем на выходе.
  2. Объясните алгоритм и пройдите маленький пример.
  3. Корректность работы алгоритма: инвариант цикла либо база и рекурсивный шаг. Отдельно — почему работа заканчивается.
  4. Назовите размер входа, модель стоимости и случай: худший, лучший или средний.
  5. Оценку времени объясните исходя из числа операций, а не просто по памяти «там было $n \log n$».

Код на Python обязателен только для решения задачи, пишем его ручкой на листочке. Теоретический алгоритм можно объяснять словами, псевдокодом или рисунком.

Раздел 1. Асимптотики, последовательности

1. Определение и свойства алгоритма.

2. Модель RAM: что считается элементарной операцией, сколько и почему стоит доступ a[i]?

3. Чем наилучший, наихудший и средний случаи работы алгоритма отличаются друг от друга? Каким обычно пользуются?

4. Дайте определение $f(n) = O(g(n))$ с константой и порогом $n_0$.

5. Дайте определения $\Omega$ и $\Theta$ и отличия от $O$.

6. Приведите пример алгоритма с разными оценками $\Theta$ для наихудшего и наилучшего случая.

7. Как по дереву рекурсивных вызовов получить оценку количества операций?

8. Чем list в Python отличается от массива модели RAM? В чём идея амортизированной стоимости append?

9. Частотный массив: когда индекс — это значение, а не позиция? От чего зависят время и дополнительная память?

10. Слияние двух отсортированных массивов двумя указателями. Инвариант результата и оценка числа перемещений.

11. Скользящее окно фиксированной длины. Как обновить сумму при сдвиге на одну позицию? Время на весь массив и дополнительная память.

12. Префиксные суммы: как построить массив и как получить сумму на полуинтервале? Время подготовки и одного запроса.

13. Разностный массив: как прибавить число на целом диапазоне и как потом восстановить значения? Почему серия таких прибавлений не стоит квадрат от длины массива?

Раздел 2. Сортировки

14. Постановка задачи сортировки. Что такое «отношение порядка» (order relation) и почему оно важно? Что требуется от сортируемой структуры, в которой лежат элементы?

15. Что такое инвариант цикла? Какие три свойства у него проверяют и как отдельно обосновывают завершение цикла?

16. Monkey Sort. Почему число попыток — комбинаторный взрыв? Точное ожидание выводить не нужно.

17. Fool Sort. Почему программа без вложенных циклов всё ещё может работать квадратичное время?

18. Пузырьковая сортировка: идея, инвариант, время в худшем случае. Что меняет ранний выход с помощью флажка is_sorted?

19. Сортировка вставками: идея, инвариант, время в худшем случае и на почти упорядоченном входе.

20. Сортировка выбором: идея, инвариант, время и дополнительная память.

21. Устойчивость и ключ сортировки. Пример, где у равных ключей разная полезная нагрузка и порядок этой нагрузки важен.

22. Сортировка подсчётом: при каких ключах она уместна, откуда время $\Theta(n+U)$ и какова оценка по памяти?

23. Поразрядная сортировка LSD: в каком порядке идут разряды, зачем каждый проход устойчив, какой инвариант после $k$ проходов и от чего зависит стоимость?

24. Нижняя оценка количества операций сортировки в модели сравнений. Какие вопросы задаёт алгоритм, при чём здесь $n!$ и высота дерева решений? Какая оценка получается? (Формулу Стирлинга выводить не нужно.)

25. Почему сортировка подсчётом и поразрядная сортировка не противоречат нижней оценке необходимого количества операций из вопроса 24?

Раздел 3. Рекурсия, генерация, бинарный поиск

26. Синхронный вызов: что происходит с вызывающей функцией в момент вызова и после возврата? Что такое стек вызовов? Почему это позволяет делать вызов функции из неё же?

27. Чем рекуррентная формула отличается от рекурсивной программы, которая её вычисляет? Чем действия до рекурсивного вызова отличаются от действий после возврата?

28. Рекурсия. Базовый случай, рекурсивный шаг и уменьшение задачи. Почему без уменьшения масштаба задачи рекурсия не работает и как завершается программа в этом случае.

29. Чем дерево всех вызовов отличается от текущей цепочки активных вызовов? На примере fib объясните, почему глубина, число вызовов и объём работы — три разные величины.

30. gen_bin: как ветвится рекурсия, в какой момент печатается строка и почему для длины $n$ получаются все двоичные строки этой длины и нет лишних?

31. gen_permutations: как не использовать число дважды, где происходит печать и почему на маленьком $n$ перебор полный?

32. Поиск корня непрерывной функции делением пополам. На основании какой теоремы матанализа на отрезке имеется корень уравнения $f(x) = 0$? Какие есть требования к функции $f(x)$? Когда алгоритм должен останавливаться?

33. Дискретный бинарный поиск. Что такое монотонный предикат одной дискретной переменной и какую границу в нём ищут?

34. Бинарный поиск значения в отсортированном массиве. Чем lower_bound отличается от upper_bound? Как проверить, что ключ есть, и как найти участок равных ключей?

35. Бинарный поиск по ответу. Как из задачи получить монотонный предикат и границы шкалы? Разберите задачу поиска целого квадратного корня числа.

Раздел 4. Рекурсивные сортировки

36. Слияние двух упорядоченных массивов: инвариант, время и почему при равных ключах берётся элемент из левого массива.

37. Сортировка слиянием: база, в каком порядке идут рекурсивные вызовы и как корректность следует из решения меньших задач.

38. Откуда у сортировки слиянием наихудшее время $\Theta(n \log n)$? Каковы дополнительная память и глубина рекурсии?

39. Идея быстрой сортировки. Что делается до рекурсивных вызовов и почему части после разбиения можно сортировать независимо?

40. Разбиение Ломуто: инвариант прохода и где оказывается опорный элемент. Проведите разбиение массива $[4, 1, 6, 3, 2, 5]$.

41. Разбиение Хоара: встречные указатели, что происходит с элементами, равными опорному, и чем граница двух частей отличается от окончательной позиции опорного у Ломуто.

42. Когда дерево быстрой сортировки даёт $\Theta(n \log n)$, а когда в худшем случае $\Theta(n^2)$? Приведите вход, на котором сортировка Хоара с использованием разбиения Ломуто с опорным в конце вырождается.

43. Что меняет случайный выбор опорного элемента? В каком смысле оценка $\Theta(n \log n)$ ожидаемая и почему худший случай остаётся квадратичным? Доказательство ожидания не требуется.

44. Почему случайный опорный не спасает разбиение Ломуто на массиве из одинаковых элементов?

45. Разбиение идёт внутри исходного массива. Какова дополнительная память всей рекурсивной быстрой сортировки? Устойчивы ли сортировка слиянием и быстрая сортировка?

Задачи

В билете одна задача из этого списка. Напишите функцию на базовом Python: ветвления, циклы, список по индексу. Ориентир по длине — от 6 до 15 строк. Ввод и вывод контеста не нужны, достаточно return или изменения переданного списка, как сказано в задаче.

Не вызывайте готовую функцию, которая делает ровно эту работу: sum для суммы, max и min для экстремума, sorted и reversed для порядка, math.sqrt для корня в задаче про делители.

Т1. digit_sum(n) — сумма десятичных цифр неотрицательного целого n.

Т2. is_leap(year) — високосный ли год по григорианскому правилу.

Т3. triangle_type(a, b, c) — по трём положительным сторонам вернуть, что треугольника нет, либо что он прямоугольный, тупоугольный или остроугольный. Сначала проверьте неравенство треугольника.

Т4. sum_squares(n) — сумма квадратов $1^2 + 2^2 + \ldots + n^2$. Список квадратов не строить.

Т5. years(x, p, y) — сколько целых лет вклад x при целых процентах p в год дорастёт до y. Каждый год сумма заменяется на $\lfloor x(100+p)/100 \rfloor$.

Т6. doubling_steps(n) — минимальное целое $k \ge 0$, при котором $2^k \ge n$ для $n \ge 1$. Возведение в степень одной операцией не использовать: только цикл удвоения.

Т7. count_max(a) — сколько раз в непустом списке чисел встречается его максимум.

Т8. count_even(a) — сколько чётных чисел в списке.

Т9. find(a, x) — индекс первого вхождения x в список a или $-1$, если его нет.

Т10. is_sorted(a) — истина, если список упорядочен по неубыванию. Пустой список и список из одного элемента считать упорядоченными.

Т11. swap_min_max(a) — в списке поменять местами минимальный и максимальный элементы. Если экстремумов несколько, брать первое вхождение каждого. Список менять на месте.

Т12. reverse(a) — развернуть список на месте.

Т13. factorial(n) — $n!$ для целого $n \ge 0$, циклом. Считать $0! = 1$.

Т14. divisor_count(n) — число положительных делителей натурального n. Перебор вести не дальше квадратного корня, проверяя d * d <= n.

Т15. rotate_left(a) — сдвинуть список на одну позицию влево на месте: первый элемент становится последним. Пустой список не менять.

Банк дополнительных вопросов (вне билетов)

Д1. Цикл делает $1+2+\ldots+n$ действий. Откуда берётся $\Theta(n^2)$?

Д2. Целый параметр на каждом шаге заменяют частным от деления на 2, пока он положителен. Сколько шагов?

Д3. Как за один проход найти сумму, максимум или число элементов по условию, не сохраняя весь поток? Сколько при этом дополнительной памяти?

Д4. Почему фраза «$O$ — это худший случай, $\Omega$ — лучший, $\Theta$ — средний» неверна?

Д5. Верно ли, что $3n+7 = O(n^2)$? Какая оценка точна по порядку?

Д6. Проверок $\Theta(\log M)$, каждая стоит $\Theta(n)$. Какое общее время? Что здесь $n$ и что такое $M$?

Д7. Несколько замеров времени показали правдоподобный рост. Почему этого недостаточно, чтобы утверждать $\Theta$?

Д8. Как проверить, что массив упорядочен по неубыванию, за один проход?

Д9. Проследите короткую линейную рекурсию типа «матрёшка» на маленьком $n$: в каком порядке выполняются действия до вызова и после возврата.

Д10. Полуинтервал непроверенных индексов $[l, r)$. Почему ответ может совпасть с правым концом?

Д11. Как выбирают середину? Когда пишут $r = m$, а когда $l = m + 1$? Почему диапазон строго уменьшается и цикл завершается?