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

Аркуші з формулами, ключові кроки методів для кожної теми та 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Лише випадкові вхідні дані
  2. BОдин цикл
  3. CЖодних підзадач, тож її можна розв'язати за один крок
  4. DПерекривні підзадачі та оптимальну підструктуру
2.Алгоритми та складністьСкладна

Чому будь-який пошук порівняннями у відсортованому масиві потребує Ω(log n) порівнянь у найгіршому випадку?

  1. AКожне порівняння триває логарифмічний час
  2. BБінарний пошук — єдиний можливий алгоритм, і йому потрібно log₂ n порівнянь
  3. CКожен елемент треба порівняти щонайменше один раз
  4. DДерево рішень з n можливими результатами має глибину щонайменше log₂ n
3.Структури данихСередня

Префіксне дерево (trie) особливо ефективне для:

  1. AПошуку за префіксом, наприклад автодоповнення
  2. BПошуку найкоротших шляхів
  3. CСортування чисел
  4. DЗберігання матриць
4.Структури данихСкладна

Який час роботи пошуку в ширину (BFS) у графі з V вершинами, що зберігається як матриця суміжності?

  1. AO(V + E)
  2. BO(E log V)
  3. CO(V)
  4. DO(V²)
5.Теорія графівСередня

Дерево має 4 вершин степеня 3, 2 вершин степеня 5, а всі його інші вершини — листки (степінь 1). Скільки листків L воно має?

4 × deg 32 × deg 5
L =
6.Теорія графівСкладна
6132161418199ABCDEF

Алгоритм Крускала будує мінімальне остовне дерево. Клікніть ребро, яке він додає як ребро номер 5; пропущені ребра не враховуються.

k = 5
  1. 1ребро AB
  2. 2ребро AC
  3. 3ребро BC
  4. 4ребро BD
  5. 5ребро CE
  6. 6ребро DE
  7. 7ребро DF
  8. 8ребро BE

3Розчини

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

Відповідь: D · Перекривні підзадачі та оптимальну підструктуру

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

Збереження результатів перекривних підзадач (мемоізація або табуляція) дає змогу уникнути повторної роботи й перетворює експоненційні алгоритми на поліноміальні.

Відповідь

D · Перекривні підзадачі та оптимальну підструктуру
2.Алгоритми та складність

Відповідь: D · Дерево рішень з n можливими результатами має глибину щонайменше log₂ n

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

Кожне порівняння щонайбільше вдвічі зменшує множину можливостей, що залишилися, тож для розрізнення n позицій потрібно щонайменше log₂ n порівнянь.

Відповідь

D · Дерево рішень з n можливими результатами має глибину щонайменше log₂ n
3.Структури даних

Відповідь: A · Пошуку за префіксом, наприклад автодоповнення

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

Trie зберігає рядки посимвольно вздовж шляхів, тому пошук і запити за префіксом займають час, пропорційний довжині ключа.

Відповідь

A · Пошуку за префіксом, наприклад автодоповнення
4.Структури даних

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

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

Кожна з V вершин переглядає рядок із V елементів, що дає O(V²); зі списками суміжності BFS має складність O(V + E).

Відповідь

D · O(V²)
5.Теорія графів

Відповідь: L = 12

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

Лема про рукостискання для дерева

L + 22 = 2(L + 6) − 2
L = 12

Відповідь

L = 12

Скорочення: L = 2 + Σ (d − 2) за вершинами зі степенем d ≥ 3.

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

Відповідь: ребро DF

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

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

1. BC (2)
2. AB (6)
3. BE (9)
4. BD (16)
5. DF (19)

номер ребра 5

DF

Відповідь

ребро DF

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