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

Аркуші з формулами, ключові кроки методів для кожної теми та 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Дерево рішень з n можливими результатами має глибину щонайменше log₂ n
  2. BБінарний пошук — єдиний можливий алгоритм, і йому потрібно log₂ n порівнянь
  3. CКожне порівняння триває логарифмічний час
  4. DКожен елемент треба порівняти щонайменше один раз
3.Структури данихСередня

Геш-таблиця розміру 7 використовує h(k) = k mod 7 і лінійне зондування. Після вставлення 10 де буде збережено 17?

  1. AВ індексі 0
  2. BВ індексі 6
  3. CВ індексі 4
  4. DВ індексі 3
4.Структури данихСкладна

Об'єкт зберігається як ключ у геш-відображенні (hash map), а потім змінюється поле, яке використовує його геш-функція. Який імовірний результат?

  1. AПошук об'єкта може не вдатися, бо він лежить у кошику для свого старого гешу
  2. BВідображення автоматично переміщує ключ у новий кошик
  3. CНічого не змінюється, бо геш ключа обчислюється лише раз, коли програма запускається
  4. DВідображення видає помилку в момент зміни поля
5.Теорія графівСередня

Зв’язний граф має 9 вершин і 10 ребер. Скільки ребер k треба вилучити, щоб залишилося остовне дерево?

|V| = 9|E| = 10
k =
6.Теорія графівСкладна
31051817151611712ABCDEFG

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

|V| = 7|E| = 10
W =

3Розчини

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

Відповідь: B · На кожному кроці робить локально найкращий вибір

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

Жадібні алгоритми швидкі й для деяких задач оптимальні (наприклад, алгоритм Дейкстри, кодування Гаффмана), але не загалом (наприклад, задача про видачу решти для деяких систем монет).

Відповідь

B · На кожному кроці робить локально найкращий вибір
2.Алгоритми та складність

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

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

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

Відповідь

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

Відповідь: C · В індексі 4

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

10 mod 7 = 3 і 17 mod 7 = 3; індекс 3 зайнятий, тож лінійне зондування пробує наступну комірку — індекс 4.

Відповідь

C · В індексі 4
4.Структури даних

Відповідь: A · Пошук об'єкта може не вдатися, бо він лежить у кошику для свого старого гешу

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

Розташування ключа обрано за його старим гешем; з новим гешем пошук іде не в тому кошику, тому ключі мають бути незмінними.

Відповідь

A · Пошук об'єкта може не вдатися, бо він лежить у кошику для свого старого гешу
5.Теорія графів

Відповідь: k = 2

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

Ребра остовного дерева

9 − 1 = 8

Ребра для вилучення

k = 10 − 8 = 2

Відповідь

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

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

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

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

AB (3): взяти
BD (5): взяти
GC (7): взяти
BC (10): взяти
GB (11): пропустити, замикає цикл
GE (12): взяти
DF (15): взяти

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

W = 3 + 5 + 7 + 10 + 12 + 15 = 52

Відповідь

W = 52

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