Алгоритми та структури даних: шпаргалка-підсумок

Аркуші з формулами, ключові кроки методів для кожної теми та 6 задач для практики, з повними розв’язками наприкінці.

Нові задачіНазад до курсу

У вікні друку виберіть «Зберегти як 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
Ейлер
цикл: усі степені парні; шлях: рівно 2 непарні степені
Гамільтонові цикли в Kn
(n − 1)!/2
Оновлення в алгоритмі Дейкстри
d(v) = min(d(v), d(u) + w(u, v))
Маршрути довжиною L
(Mᴸ)ij

Метод

  1. Випишіть степінь кожної вершини; сума степенів дорівнює подвоєній кількості ребер.
  2. У задачах про Ейлера перевірте, що граф зв’язний, і порахуйте вершини з непарним степенем.
  3. Для дерев використовуйте n − 1 ребро та лему про рукостискання.
  4. Для алгоритму Дейкстри ведіть таблицю попередніх відстаней і щоразу фіксуйте незафіксовану вершину з найменшою відстанню.
  5. Для мінімального остовного дерева відсортуйте ребра за вагою й пропускайте кожне ребро, що замикає цикл (Крускал), або нарощуйте одне дерево від початкової вершини (Прім).

2Задачі для практики

1.Алгоритми та складністьСередня

Що обчислює алгоритм Флойда–Воршелла і як швидко?

  1. AНайкоротші шляхи від однієї початкової вершини до всіх інших за O(V + E)
  2. BТопологічний порядок за O(V²)
  3. CНайкоротші шляхи між усіма парами вершин за O(V³)
  4. DМінімальне кістякове дерево за O(E log V)
2.Алгоритми та складністьСкладна

Найкоротші прості шляхи можна знайти за поліноміальний час. Що відомо про пошук найдовшого простого шляху між двома вершинами в загальному графі?

  1. AЇї можна розв'язати алгоритмом Дейкстри з від'ємними вагами
  2. BВона нерозв'язна
  3. CЦе NP-складна задача
  4. DЇї завжди можна розв'язати за O(V + E)
3.Структури данихСередня

Скільки пам'яті займає матриця суміжності графа з V вершинами?

  1. AO(V + E)
  2. BO(E)
  3. CO(V²)
  4. DO(log V)
4.Структури данихСкладна

Структура union-find (система неперетинних множин) з об'єднанням за рангом і стисненням шляху має амортизовану вартість операції:

  1. AO(n)
  2. BРівно O(log n)
  3. CO(α(n)), обернена функція Аккермана, практично стала
  4. DO(n²)
5.Теорія графівСередня

Скільки різних гамільтонових циклів H має повний граф K7? Цикли, що відрізняються лише початковою вершиною чи напрямком, вважаються однаковими.

K7
H =
6.Теорія графівСкладна
11144351913920ABCDEFG

Знайдіть загальну вагу W мінімального остовного дерева зваженого графа.

|V| = 7|E| = 9
W =

3Розчини

1.Алгоритми та складність

Відповідь: C · Найкоротші шляхи між усіма парами вершин за O(V³)

Чому це відповідь

Флойд–Воршелл — алгоритм динамічного програмування, що по черзі дозволяє кожну вершину як проміжну, витрачаючи O(V³) часу.

Відповідь

C · Найкоротші шляхи між усіма парами вершин за O(V³)
2.Алгоритми та складність

Відповідь: C · Це NP-складна задача

Чому це відповідь

Найдовший простий шлях довжиною V − 1 — це гамільтонів шлях, пошук якого є NP-повною задачею; утім, на орієнтованих ациклічних графах задача розв'язна за лінійний час.

Відповідь

C · Це NP-складна задача
3.Структури даних

Відповідь: C · O(V²)

Чому це відповідь

Матриця суміжності зберігає V × V елементів, що ефективно для щільних графів; списки суміжності займають O(V + E) і краще підходять для розріджених графів.

Відповідь

C · O(V²)
4.Структури даних

Відповідь: C · O(α(n)), обернена функція Аккермана, практично стала

Чому це відповідь

З обома оптимізаціями операції виконуються за амортизований час O(α(n)); α(n) ≤ 4 для будь-якого реалістичного n.

Відповідь

C · O(α(n)), обернена функція Аккермана, практично стала
5.Теорія графів

Відповідь: H = 360

Ейлер, Гамільтон і дерева: зв’язний граф має ейлерів цикл (кожне ребро один раз, з поверненням до початку), коли кожна вершина має парний степінь, і ейлерів шлях, що не є циклом, коли рівно дві вершини мають непарний степінь; тоді шлях іде від однієї непарної вершини до другої. Гамільтонів цикл відвідує кожну вершину один раз; у Kn їх (n − 1)!/2. Дерево на n вершинах має n − 1 ребро, а зв’язний граф з m ребрами зберігає остовне дерево після вилучення m − n + 1 ребер.

Порахуйте

H = (7 − 1)!/2 = 720/2 = 360

Відповідь

H = 360
6.Теорія графів

Відповідь: W = 52

Найкоротші шляхи та остовні дерева: алгоритм Дейкстри фіксує одну вершину за раунд: незафіксовану вершину з найменшою попередньою відстанню. Її відстань тоді остаточна, а кожен сусід v отримує d(v) = min(d(v), d(u) + w(u, v)). Алгоритм Крускала будує мінімальне остовне дерево, беручи ребра від легких до важких і пропускаючи кожне ребро, що замкнуло б цикл; алгоритм Пріма нарощує одне дерево від початкової вершини, завжди додаючи найлегше ребро, що виходить з нього. Остовне дерево з n вершин має n − 1 ребро.

Алгоритм Крускала

DE (3): взяти
BC (4): взяти
DF (5): взяти
GC (9): взяти
AB (11): взяти
GB (13): пропустити, замикає цикл
AC (14): пропустити, замикає цикл
EF (19): пропустити, замикає цикл
GE (20): взяти

Загальна вага

W = 3 + 4 + 5 + 9 + 11 + 20 = 52

Відповідь

W = 52

ExamProblems · examproblems.com/courses/data-structures-and-algorithms