Коллоквиум 1. Материалы для подготовки и ответы
Ответы к вопросам и задачам коллоквиума. Номера совпадают со списком в коллоквиуме. Приведены ссылки на конкретные места в конспектах лекций. По-возможности также ссылки на видеозаписи старых лекций 2017 года. К сожалению, в видеозаписях не всегда точное соответствие изложению курса ФИИ МГУ, поэтому первичными остаются живые лекции и конспекты к ним.
Раздел 1. Асимптотики, последовательности
1. Определение и свойства алгоритма.
2. Модель RAM: что считается элементарной операцией, сколько и почему стоит доступ a[i]?
3. Чем наилучший, наихудший и средний случаи работы алгоритма отличаются друг от друга? Каким обычно пользуются?
Лекция 2. Нотации $O$, $\Omega$, $\Theta$
4. Дайте определение $f(n) = O(g(n))$ с константой и порогом $n_0$.
Лекция 5. Что именно оцениваем
5. Дайте определения $\Omega$ и $\Theta$ и отличия от $O$.
Лекция 5. Что именно оцениваем
6. Приведите пример алгоритма с разными оценками $\Theta$ для наихудшего и наилучшего случая.
Лекция 5. Быстрая сортировка: время, опорный, память
7. Как по дереву рекурсивных вызовов получить оценку количества операций?
Лекция 5. Рекурсия, случаи и нижняя оценка
8. Чем list в Python отличается от массива модели RAM? В чём идея амортизированной стоимости append?
Лекция 2. Нотации $O$, $\Omega$, $\Theta$
Старая лекция №6, 1:10. list — не массив
Старая лекция №6, 5:05. Динамический массив
9. Частотный массив: когда индекс — это значение, а не позиция? От чего зависят время и дополнительная память?
Старая лекция №6, 1:18:16. Частотный анализ
10. Слияние двух отсортированных массивов двумя указателями. Инвариант результата и оценка числа перемещений.
Лекция 5. Слияние двух упорядоченных массивов
11. Скользящее окно фиксированной длины. Как обновить сумму при сдвиге на одну позицию? Время на весь массив и дополнительная память.
12. Префиксные суммы: как построить массив и как получить сумму на полуинтервале? Время подготовки и одного запроса.
Лекция 2. Префиксные суммы и разностный массив
13. Разностный массив: как прибавить число на целом диапазоне и как потом восстановить значения? Почему серия таких прибавлений не стоит квадрат от длины массива?
Лекция 2. Префиксные суммы и разностный массив
Раздел 2. Сортировки
14. Постановка задачи сортировки. Что такое «отношение порядка» (order relation) и почему оно важно? Что требуется от сортируемой структуры, в которой лежат элементы?
Лекция 3. Сортировка — не корзины
Лекция 3. Камень, ножницы, бумага
Лекция 3. Что можно упорядочить
15. Что такое инвариант цикла? Какие три свойства у него проверяют и как отдельно обосновывают завершение цикла?
Старая лекция №6, 29:40. Инвариант цикла
16. Monkey Sort. Почему число попыток — комбинаторный взрыв? Точное ожидание выводить не нужно.
Лекция 3. Обезьяна и комбинаторный взрыв
17. Fool Sort. Почему программа без вложенных циклов всё ещё может работать квадратичное время?
Лекция 3. Fool: повторять прогон
18. Пузырьковая сортировка: идея, инвариант, время в худшем случае. Что меняет ранний выход с помощью флажка is_sorted?
Старая лекция №6, 19:00. Квадратичные сортировки
Старая лекция №6, 34:19. Пузырёк
Старая лекция №6, 1:08:03. Алгоритм пузырька
19. Сортировка вставками: идея, инвариант, время в худшем случае и на почти упорядоченном входе.
Старая лекция №6, 19:00. Квадратичные сортировки
Старая лекция №6, 20:28. Сортировка вставками
Старая лекция №6, 59:35. Алгоритм вставок
20. Сортировка выбором: идея, инвариант, время и дополнительная память.
Старая лекция №6, 19:00. Квадратичные сортировки
Старая лекция №6, 26:16. Сортировка выбором
Старая лекция №6, 1:05:59. Алгоритм выбора
21. Устойчивость и ключ сортировки. Пример, где у равных ключей разная полезная нагрузка и порядок этой нагрузки важен.
22. Сортировка подсчётом: при каких ключах она уместна, откуда время $\Theta(n+U)$ и какова оценка по памяти?
Лекция 3. Сортировка подсчётом
Старая лекция №6, 1:11:53. Подсчёт: время и память
Старая лекция №6, 1:13:50. Малый диапазон значений
23. Поразрядная сортировка LSD: в каком порядке идут разряды, зачем каждый проход устойчив, какой инвариант после $k$ проходов и от чего зависит стоимость?
24. Нижняя оценка количества операций сортировки в модели сравнений. Какие вопросы задаёт алгоритм, при чём здесь $n!$ и высота дерева решений? Какая оценка получается? (Формулу Стирлинга выводить не нужно.)
Лекция 3. Нижняя оценка в модели сравнений
25. Почему сортировка подсчётом и поразрядная сортировка не противоречат нижней оценке необходимого количества операций из вопроса 24?
Лекция 3. Нижняя оценка в модели сравнений
Лекция 5. Рекурсия, случаи и нижняя оценка
Раздел 3. Рекурсия, генерация, бинарный поиск
26. Синхронный вызов: что происходит с вызывающей функцией в момент вызова и после возврата? Что такое стек вызовов? Почему это позволяет делать вызов функции из неё же?
Лекция 4. Синхронный вызов: репка
Старая лекция №4, 28:50. Синхронный вызов
Старая лекция №4, 30:35. Стек вызовов
Старая лекция №7, 10:35. Функция вызывает сама себя
Старая лекция №7, 18:42. У каждого вызова своё пространство имён
27. Чем рекуррентная формула отличается от рекурсивной программы, которая её вычисляет? Чем действия до рекурсивного вызова отличаются от действий после возврата?
Лекция 4. Рекуррентное задание функции и рекурсия
Старая лекция №7, 13:22. Рекурсию можно заменить циклом
Старая лекция №7, 17:42. Прямой ход, крайний случай, обратный ход
28. Рекурсия. Базовый случай, рекурсивный шаг и уменьшение задачи. Почему без уменьшения масштаба задачи рекурсия не работает и как завершается программа в этом случае.
Лекция 4. Рекуррентное задание функции и рекурсия
Старая лекция №7, 6:09. Подзадача проще задачи
Старая лекция №7, 6:46. Крайний случай
Старая лекция №7, 7:11. Рекурсивный случай
29. Чем дерево всех вызовов отличается от текущей цепочки активных вызовов? На примере fib объясните, почему глубина, число вызовов и объём работы — три разные величины.
Дерево — все вызовы за всё выполнение. Цепочка — те, кто ещё не вернулся; её длина и есть глубина. У fib(n) глубина $\Theta(n)$, а число вызовов экспоненциально, потому что каждая ветвь считается заново. Объём работы следует из числа вызовов, а не из одной только глубины.
30. gen_bin: как ветвится рекурсия, в какой момент печатается строка и почему для длины $n$ получаются все двоичные строки этой длины и нет лишних?
Лекция 4. Генерация двоичных последовательностей: gen_bin
Старая лекция №8, 32:17. Все двоичные строки
31. gen_permutations: как не использовать число дважды, где происходит печать и почему на маленьком $n$ перебор полный?
Лекция 4. Генерация перестановок: gen_permutations
Старая лекция №8, 39:19. Генерация перестановок
32. Поиск корня непрерывной функции делением пополам. На основании какой теоремы матанализа на отрезке имеется корень уравнения $f(x) = 0$? Какие есть требования к функции $f(x)$? Когда алгоритм должен останавливаться?
Лекция 4. Непрерывная функция и корень
Лекция 4. Классический бинпоиск по вещественной оси
33. Дискретный бинарный поиск. Что такое монотонный предикат одной дискретной переменной и какую границу в нём ищут?
34. Бинарный поиск значения в отсортированном массиве. Чем lower_bound отличается от upper_bound? Как проверить, что ключ есть, и как найти участок равных ключей?
Лекция 4. lower_bound и upper_bound
Старая лекция №10, 0:38. Бинарный поиск в отсортированном массиве
Старая лекция №10, 6:11. Левая граница
Старая лекция №10, 16:22. Правая граница
35. Бинарный поиск по ответу. Как из задачи получить монотонный предикат и границы шкалы? Разберите задачу поиска целого квадратного корня числа.
Раздел 4. Рекурсивные сортировки
36. Слияние двух упорядоченных массивов: инвариант, время и почему при равных ключах берётся элемент из левого массива.
Лекция 5. Слияние двух упорядоченных массивов
Старая лекция №9, 2:00. Слияние отсортированных массивов
Старая лекция №9, 11:42. Устойчивое слияние
37. Сортировка слиянием: база, в каком порядке идут рекурсивные вызовы и как корректность следует из решения меньших задач.
Старая лекция №9, 20:25. Рекурсивная сортировка слиянием
38. Откуда у сортировки слиянием наихудшее время $\Theta(n \log n)$? Каковы дополнительная память и глубина рекурсии?
39. Идея быстрой сортировки. Что делается до рекурсивных вызовов и почему части после разбиения можно сортировать независимо?
Лекция 5. Быстрая сортировка: работа до рекурсивных вызовов
Старая лекция №9, 33:25. Идея быстрой сортировки
40. Разбиение Ломуто: инвариант прохода и где оказывается опорный элемент. Проведите разбиение массива $[4, 1, 6, 3, 2, 5]$.
41. Разбиение Хоара: встречные указатели, что происходит с элементами, равными опорному, и чем граница двух частей отличается от окончательной позиции опорного у Ломуто.
42. Когда дерево быстрой сортировки даёт $\Theta(n \log n)$, а когда в худшем случае $\Theta(n^2)$? Приведите вход, на котором сортировка Хоара с использованием разбиения Ломуто с опорным в конце вырождается.
Лекция 5. Быстрая сортировка: время, опорный, память
43. Что меняет случайный выбор опорного элемента? В каком смысле оценка $\Theta(n \log n)$ ожидаемая и почему худший случай остаётся квадратичным? Доказательство ожидания не требуется.
Лекция 5. Быстрая сортировка: время, опорный, память
44. Почему случайный опорный не спасает разбиение Ломуто на массиве из одинаковых элементов?
Лекция 5. Быстрая сортировка: время, опорный, память
45. Разбиение идёт внутри исходного массива. Какова дополнительная память всей рекурсивной быстрой сортировки? Устойчивы ли сортировка слиянием и быстрая сортировка?
Лекция 5. Слияние двух упорядоченных массивов
Старая лекция №9, 9:25. Устойчивость сортировки
Лекция 5. Быстрая сортировка: время, опорный, память
Задачи
Т1. digit_sum(n) — сумма десятичных цифр неотрицательного целого n.
digit_sum(0) = 0, digit_sum(905) = 14.
def digit_sum(n):
s = 0
while n > 0:
s += n % 10
n //= 10
return s
Т2. is_leap(year) — високосный ли год по григорианскому правилу.
2000 — да, 1900 — нет, 2024 — да, 2023 — нет.
def is_leap(year):
if year % 400 == 0:
return True
if year % 100 == 0:
return False
return year % 4 == 0
Т3. triangle_type(a, b, c) — по трём положительным сторонам вернуть, что треугольника нет, либо что он прямоугольный, тупоугольный или остроугольный. Сначала проверьте неравенство треугольника.
3, 4, 5 — прямоугольный; 2, 2, 3 — тупоугольный; 2, 3, 3 — остроугольный; 1, 2, 3 — не треугольник. Двумя обменами ставим в c наибольшую сторону.
def triangle_type(a, b, c):
if c < a:
a, c = c, a
if c < b:
b, c = c, b
if a + b <= c:
return "нет"
if a * a + b * b == c * c:
return "прямоугольный"
if a * a + b * b < c * c:
return "тупоугольный"
return "остроугольный"
Т4. sum_squares(n) — сумма квадратов $1^2 + 2^2 + \ldots + n^2$. Список квадратов не строить.
sum_squares(3) = 14.
def sum_squares(n):
s = 0
i = 1
while i <= n:
s += i * i
i += 1
return s
Т5. years(x, p, y) — сколько целых лет вклад x при целых процентах p в год дорастёт до y. Каждый год сумма заменяется на $\lfloor x(100+p)/100 \rfloor$.
years(100, 10, 130) = 3: 110, 121, 133.
def years(x, p, y):
k = 0
while x < y:
x = x * (100 + p) // 100
k += 1
return k
Т6. doubling_steps(n) — минимальное целое $k \ge 0$, при котором $2^k \ge n$ для $n \ge 1$. Возведение в степень одной операцией не использовать: только цикл удвоения.
doubling_steps(1) = 0, doubling_steps(5) = 3.
def doubling_steps(n):
k = 0
v = 1
while v < n:
v *= 2
k += 1
return k
Т7. count_max(a) — сколько раз в непустом списке чисел встречается его максимум.
count_max([3, 1, 3, 2]) = 2. Максимум берут с первого элемента, не с нуля.
def count_max(a):
best = a[0]
cnt = 0
for x in a:
if x > best:
best = x
cnt = 1
elif x == best:
cnt += 1
return cnt
Т8. count_even(a) — сколько чётных чисел в списке.
count_even([1, 2, 3, 4]) = 2.
def count_even(a):
cnt = 0
for x in a:
if x % 2 == 0:
cnt += 1
return cnt
Т9. find(a, x) — индекс первого вхождения x в список a или $-1$, если его нет.
find([4, 7, 7], 7) = 1, find([4, 7], 5) = -1.
def find(a, x):
i = 0
while i < len(a):
if a[i] == x:
return i
i += 1
return -1
Старая лекция №5, 36:20. Линейный поиск
Т10. is_sorted(a) — истина, если список упорядочен по неубыванию. Пустой список и список из одного элемента считать упорядоченными.
[] и [1] — истина. [1, 2, 2] — истина, [1, 3, 2] — ложь. Соседей сравнивают строгим >: равенство порядок не ломает.
def is_sorted(a):
i = 0
while i + 1 < len(a):
if a[i] > a[i + 1]:
return False
i += 1
return True
Старая лекция №9, 50:02. Проверка упорядоченности за один проход
Т11. swap_min_max(a) — в списке поменять местами минимальный и максимальный элементы. Если экстремумов несколько, брать первое вхождение каждого. Список менять на месте.
[3, 1, 4, 1, 5] → [3, 5, 4, 1, 1]. Если минимум и максимум — один и тот же элемент, список не меняется.
def swap_min_max(a):
if len(a) == 0:
return
imin = 0
imax = 0
for i in range(len(a)):
if a[i] < a[imin]:
imin = i
if a[i] > a[imax]:
imax = i
a[imin], a[imax] = a[imax], a[imin]
Т12. reverse(a) — развернуть список на месте.
[1, 2, 3, 4] → [4, 3, 2, 1].
def reverse(a):
i = 0
j = len(a) - 1
while i < j:
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
Старая лекция №5, 49:19. Обращение массива
Т13. factorial(n) — $n!$ для целого $n \ge 0$, циклом. Считать $0! = 1$.
factorial(0) = 1, factorial(5) = 120.
def factorial(n):
p = 1
i = 2
while i <= n:
p *= i
i += 1
return p
Т14. divisor_count(n) — число положительных делителей натурального n. Перебор вести не дальше квадратного корня, проверяя d * d <= n.
divisor_count(1) = 1, divisor_count(6) = 4, divisor_count(9) = 3. Пока d * d < n, делители идут парами. Целый квадратный корень считают один раз после цикла.
def divisor_count(n):
cnt = 0
d = 1
while d * d < n:
if n % d == 0:
cnt += 2
d += 1
if d * d == n:
cnt += 1
return cnt
Т15. rotate_left(a) — сдвинуть список на одну позицию влево на месте: первый элемент становится последним. Пустой список не менять.
[1, 2, 3, 4] → [2, 3, 4, 1].
def rotate_left(a):
if len(a) == 0:
return
first = a[0]
i = 0
while i + 1 < len(a):
a[i] = a[i + 1]
i += 1
a[len(a) - 1] = first
Старая лекция №5, 1:04:06. Циклический сдвиг влево
Банк дополнительных вопросов (вне билетов)
Д1. Цикл делает $1+2+\ldots+n$ действий. Откуда берётся $\Theta(n^2)$?
Лекция 5. Как складывать стоимость действий
Д2. Целый параметр на каждом шаге заменяют частным от деления на 2, пока он положителен. Сколько шагов?
Лекция 5. Как складывать стоимость действий
Д3. Как за один проход найти сумму, максимум или число элементов по условию, не сохраняя весь поток? Сколько при этом дополнительной памяти?
Лекция 1. Потоки чисел и память $O(1)$
Д4. Почему фраза «$O$ — это худший случай, $\Omega$ — лучший, $\Theta$ — средний» неверна?
Лекция 5. Что именно оцениваем
Д5. Верно ли, что $3n+7 = O(n^2)$? Какая оценка точна по порядку?
Лекция 5. Что именно оцениваем
Д6. Проверок $\Theta(\log M)$, каждая стоит $\Theta(n)$. Какое общее время? Что здесь $n$ и что такое $M$?
Лекция 5. Как складывать стоимость действий
Д7. Несколько замеров времени показали правдоподобный рост. Почему этого недостаточно, чтобы утверждать $\Theta$?
Лекция 5. Время и память — отдельные оценки
Д8. Как проверить, что массив упорядочен по неубыванию, за один проход?
Лекция 3. Проверка за один проход
Старая лекция №9, 50:02. Проверка упорядоченности за один проход
Д9. Проследите короткую линейную рекурсию типа «матрёшка» на маленьком $n$: в каком порядке выполняются действия до вызова и после возврата.
Песня «Чтобы сделать матрёшку»
Старая лекция №7, 15:18. Алгоритм «Матрёшка»
Старая лекция №7, 17:42. Прямой ход, крайний случай, обратный ход
Д10. Полуинтервал непроверенных индексов $[l, r)$. Почему ответ может совпасть с правым концом?
Д11. Как выбирают середину? Когда пишут $r = m$, а когда $l = m + 1$? Почему диапазон строго уменьшается и цикл завершается?