В окне печати выберите «Сохранить как PDF», чтобы сохранить копию на своём устройстве.
1Формулы и методы
Теория графов
Лемма о рукопожатиях
Σ deg(v) = 2|E|
Полные графы
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Регулярный граф
|E| = n·k/2
Дерево и лес
|E| = n − 1, |E| = n − c
Листья дерева
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Эйлер
цикл: все степени чётные; путь: ровно две нечётные степени
Гамильтоновы циклы в Kn
(n − 1)!/2
Обновление в алгоритме Дейкстры
d(v) = min(d(v), d(u) + w(u, v))
Маршруты длины L
(Mᴸ)ij
Метод
Запишите степень каждой вершины; сумма степеней равна удвоенному числу рёбер.
В задачах об эйлеровых путях проверьте, что граф связный, и посчитайте вершины нечётной степени.
Для деревьев используйте n − 1 ребро и лемму о рукопожатиях.
В алгоритме Дейкстры ведите таблицу предварительных расстояний и на каждом шаге фиксируйте нефиксированную вершину с наименьшим расстоянием.
Для минимального остовного дерева отсортируйте рёбра по весу и пропускайте каждое ребро, замыкающее цикл (Краскал), либо растите одно дерево из начальной вершины (Прим).
2Тренировочные задачи
1.Алгоритмы и сложностьСредняя
Почему основание логарифма в O большом обычно не указывают, как в O(log n)?
AЛогарифмы всегда округляются до целых
BОснование имеет значение только при малых n
CВсе логарифмы в информатике имеют основание 10, так что оно подразумевается
DЛогарифмы по разным основаниям отличаются лишь постоянным множителем
2.Алгоритмы и сложностьСложная
Почему любой поиск в отсортированном массиве, основанный на сравнениях, требует в худшем случае Ω(log n) сравнений?
AДерево решений с n возможными исходами должно иметь глубину не менее log₂ n
BКаждый элемент нужно сравнить хотя бы один раз
CБинарный поиск — единственный возможный алгоритм, и ему нужно log₂ n сравнений
DКаждое сравнение занимает логарифмическое время
3.Структуры данныхСредняя
Как в кольцевой очереди, хранящейся в массиве ёмкостью n, вычисляется следующая позиция после индекса i?
A(i + 1) mod n
Bi + 1
C2i + 1
D(i − 1) mod n
4.Структуры данныхСложная
Временная сложность операции decrease-key в двоичной куче (при известной позиции элемента) составляет:
AO(n)
BO(n log n)
CO(log n)
DO(1)
5.Теория графовСредняя
Есть ли в связном графе эйлеров цикл, эйлеров путь, не являющийся циклом, или ни то ни другое? Нажмите на ваш ответ.
|V| = 6|E| = 8
1Эйлеров цикл
2Эйлеров путь, не цикл
3ни то, ни другое
6.Теория графовСложная
Сколько существует замкнутых маршрутов длины 2, начинающихся и заканчивающихся в C? Маршрут может повторять вершины и рёбра. Обозначим это число N.
M = матрица смежностиL = 2
N =
3Растворы
1.Алгоритмы и сложность
Ответ: D · Логарифмы по разным основаниям отличаются лишь постоянным множителем
Почему это ответ
Смена основания умножает логарифм на константу, а O большое игнорирует постоянные множители.
Ответ
D · Логарифмы по разным основаниям отличаются лишь постоянным множителем
2.Алгоритмы и сложность
Ответ: A · Дерево решений с n возможными исходами должно иметь глубину не менее log₂ n
Почему это ответ
Каждое сравнение уменьшает множество оставшихся вариантов не более чем вдвое, поэтому для различения n позиций нужно не менее log₂ n сравнений.
Ответ
A · Дерево решений с n возможными исходами должно иметь глубину не менее log₂ n
3.Структуры данных
Ответ: A · (i + 1) mod n
Почему это ответ
Операция взятия по модулю переводит индекс n − 1 обратно в 0, поэтому массив используется повторно без сдвига элементов.
Ответ
A · (i + 1) mod n
4.Структуры данных
Ответ: C · O(log n)
Почему это ответ
После уменьшения ключа элемент поднимается не более чем на высоту кучи. Фибоначчиевы кучи достигают амортизированного decrease-key за O(1).
Ответ
C · O(log n)
5.Теория графов
Ответ: ни то, ни другое
Эйлер, Гамильтон и деревья: связный граф имеет эйлеров цикл (каждое ребро один раз, с возвратом в начало), когда все вершины имеют чётную степень, и эйлеров путь, не являющийся циклом, когда ровно две вершины имеют нечётную степень; тогда путь идёт от одной нечётной вершины к другой. Гамильтонов цикл посещает каждую вершину один раз; в Kn их (n − 1)!/2. У дерева на n вершинах n − 1 ребро, а связный граф с m рёбрами сохраняет остовное дерево после удаления m − n + 1 рёбер.
Степени: степень вершины — это число рёбер, которые в ней сходятся. У каждого ребра два конца, поэтому степени в сумме дают удвоенное число рёбер: Σ deg(v) = 2|E| (лемма о рукопожатиях). Следовательно, число вершин нечётной степени чётно. У Kn имеется n(n − 1)/2 рёбер, у k-регулярного графа на n вершинах nk/2, а у дерева на n вершинах n − 1 ребро.