В окне печати выберите «Сохранить как 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.Алгоритмы и сложностьСредняя
Какова амортизированная временная сложность добавления элемента в конец динамического массива, который удваивает свою ёмкость при заполнении?
AO(n)
BO(log n)
CO(1)
DO(n²)
2.Алгоритмы и сложностьСложная
Алгоритм динамического программирования Хелда–Карпа точно решает задачу коммивояжёра. Каково время его работы для n городов?
AO(n!)
BO(n² 2ⁿ)
CO(2n²)
DO(n³)
3.Структуры данныхСредняя
Ключи 50, 30, 70, 20, 40 вставляются в таком порядке в пустое двоичное дерево поиска. Кто левый потомок 30?
A20
B70
C40
D50
4.Структуры данныхСложная
Динамический массив удваивается при заполнении. Почему многие реализации уменьшают его, только когда он заполнен на четверть, а не наполовину?
AЧтобы избежать повторных изменений размера, когда push и pop чередуются вблизи границы
BПотому что распределитель памяти может освобождать память только четвертями блока
CПотому что уменьшение вдвое при половинном заполнении привело бы к потере элементов
DЧтобы массив оставался отсортированным
5.Теория графовСредняя
Есть ли в связном графе эйлеров цикл, эйлеров путь, не являющийся циклом, или ни то ни другое? Нажмите на ваш ответ.
|V| = 6|E| = 8
1Эйлеров цикл
2Эйлеров путь, не цикл
3ни то, ни другое
6.Теория графовСложная
Алгоритм Дейкстры запускается из A. Нажмите на вершину, которая фиксируется (становится постоянной) на шаге 4; сама A фиксируется на шаге 1.
начало: Aшаг 4
1A
2B
3C
4D
5E
6F
7G
3Растворы
1.Алгоритмы и сложность
Ответ: C · O(1)
Почему это ответ
Копирование всех элементов происходит только на степенях двойки; если распределить эти затраты на все добавления, средняя стоимость одного добавления постоянна.
Ответ
C · O(1)
2.Алгоритмы и сложность
Ответ: B · O(n² 2ⁿ)
Почему это ответ
Состояний около n 2ⁿ, и каждое вычисляется за O(n); это экспоненциально, но намного быстрее перебора всех (n − 1)! обходов.
Ответ
B · O(n² 2ⁿ)
3.Структуры данных
Ответ: A · 20
Почему это ответ
20 меньше 50 и меньше 30, поэтому становится левым потомком 30; 40 становится его правым потомком.
Ответ
A · 20
4.Структуры данных
Ответ: A · Чтобы избежать повторных изменений размера, когда push и pop чередуются вблизи границы
Почему это ответ
Уменьшение при половинном заполнении в такой последовательности могло бы вызывать изменение размера на каждой операции; промежуток между 1/4 и полным заполнением сохраняет амортизированную стоимость O(1).
Ответ
A · Чтобы избежать повторных изменений размера, когда push и pop чередуются вблизи границы
5.Теория графов
Ответ: ни то, ни другое
Эйлер, Гамильтон и деревья: связный граф имеет эйлеров цикл (каждое ребро один раз, с возвратом в начало), когда все вершины имеют чётную степень, и эйлеров путь, не являющийся циклом, когда ровно две вершины имеют нечётную степень; тогда путь идёт от одной нечётной вершины к другой. Гамильтонов цикл посещает каждую вершину один раз; в Kn их (n − 1)!/2. У дерева на n вершинах n − 1 ребро, а связный граф с m рёбрами сохраняет остовное дерево после удаления m − n + 1 рёбер.
Кратчайшие пути и остовные деревья: алгоритм Дейкстры фиксирует по одной вершине на шаге: нефиксированную вершину с наименьшим предварительным расстоянием. Её расстояние становится окончательным, а каждый сосед v получает d(v) = min(d(v), d(u) + w(u, v)). Алгоритм Краскала строит минимальное остовное дерево, беря рёбра от лёгких к тяжёлым и пропуская любое ребро, которое замкнуло бы цикл; алгоритм Прима растит одно дерево из начальной вершины, всегда добавляя самое лёгкое ребро, выходящее из него. В остовном дереве на n вершинах n − 1 ребро.