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

Аркуші з формулами, ключові кроки методів для кожної теми та 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.Алгоритми та складністьСередня

Яка часова складність обчислення n-го числа Фібоначчі за допомогою таблиці знизу вгору?

  1. AO(n)
  2. BO(log n)
  3. CO(2ⁿ)
  4. DO(n²)
2.Алгоритми та складністьСкладна

Яке твердження про позначення «мале o» правильне?

  1. An² = o(n)
  2. B2n = o(n), бо 2n зростає повільно
  3. Cn = o(n²), але n не є o(n)
  4. Dn = o(n), бо кожна функція є «мале o» від самої себе
3.Структури данихСередня

Як знайти мінімальний ключ у бінарному дереві пошуку?

  1. AІти від кореня лівими дітьми, доки лівої дитини не буде
  2. BВідвідати кожен листок і порівняти їх
  3. CІти від кореня правими дітьми, доки правої дитини не буде
  4. DПодивитися лише на корінь
4.Структури данихСкладна

Чому сервер може обирати свою геш-функцію випадково з універсального сімейства?

  1. AЩоб зробити дуже малоймовірним, що зловмисник підбере багато ключів, які всі матимуть колізію
  2. BЩоб гарантувати, що жодні два ключі ніколи не матимуть колізії, які б ключі не надсилав зловмисник
  3. CЩоб усунути потребу змінювати розмір таблиці
  4. DЩоб зробити геш-таблицю відсортованою
5.Теорія графівСередня
ABCDEFGЕйлерів циклЕйлерів шлях, не циклжодна з цих

Чи має зв’язний граф ейлерів цикл, ейлерів шлях, що не є циклом, чи нічого з цього? Клікніть свою відповідь.

|V| = 7|E| = 11
  1. 1Ейлерів цикл
  2. 2Ейлерів шлях, не цикл
  3. 3жодна з цих
6.Теорія графівСкладна
51114141518310ABCDEFG

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

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

3Розчини

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

Відповідь: A · O(n)

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

Заповнення таблиці від 0 до n потребує одного додавання на запис, тож робота лінійна, а не експоненційна.

Відповідь

A · O(n)
2.Алгоритми та складність

Відповідь: C · n = o(n²), але n не є o(n)

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

f = o(g) означає, що f(n) / g(n) прямує до 0; n / n² прямує до 0, а n / n = 1 — ні.

Відповідь

C · n = o(n²), але n не є o(n)
3.Структури даних

Відповідь: A · Іти від кореня лівими дітьми, доки лівої дитини не буде

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

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

Відповідь

A · Іти від кореня лівими дітьми, доки лівої дитини не буде
4.Структури даних

Відповідь: A · Щоб зробити дуже малоймовірним, що зловмисник підбере багато ключів, які всі матимуть колізію

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

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

Відповідь

A · Щоб зробити дуже малоймовірним, що зловмисник підбере багато ключів, які всі матимуть колізію
5.Теорія графів

Відповідь: Ейлерів шлях, не цикл

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

Степені

deg(A) = 2, deg(B) = 4, deg(C) = 3, deg(D) = 4, deg(E) = 3, deg(F) = 2, deg(G) = 4

Непарні вершини

C, E → 2
Ейлерів шлях, не цикл

Відповідь

Ейлерів шлях, не цикл

Ейлерів шлях починається в одній непарній вершині й закінчується в другій.

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

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

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

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

DF (1): взяти
GD (3): взяти
EF (4): взяти
AC (5): взяти
GE (10): пропустити, замикає цикл
BC (11): взяти
DE (14): пропустити, замикає цикл
GB (15): взяти

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

W = 1 + 3 + 4 + 5 + 11 + 15 = 39

Відповідь

W = 39

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