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

Аркуші з формулами, ключові кроки методів для кожної теми та 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, 3 і 4 та суму 6, скільки монет використовує жадібний метод «спершу найбільша монета» порівняно з оптимумом?

  1. AЖадібний використовує 3 монети; оптимум — 2
  2. BЖадібний використовує 2 монети; оптимум — 2
  3. CЖадібний використовує 3 монети; оптимум — 3
  4. DЖадібний використовує 4 монети; оптимум — 3
2.Алгоритми та складністьСкладна

Для якого варіанта задачі про рюкзак жадібне правило «брати предмети в порядку цінності на одиницю ваги» завжди дає оптимальну відповідь?

  1. AДля рюкзака 0/1, де предмети завжди потрібно брати цілими
  2. BДля неперервного (дробового) рюкзака, де предмети можна ділити
  3. CДля жодного варіанта
  4. DДля обох варіантів
3.Структури данихСередня

У бінарній мін-купі, що зберігається в масиві (індексація з 0), діти вузла з індексом i розташовані на позиціях:

  1. A2i і 2i + 1
  2. B2i + 1 і 2i + 2
  3. Ci/2 і i/2 + 1
  4. Di + 1 і i + 2
4.Структури данихСкладна

Потрібно зберігати k найменших значень із потоку n чисел, використовуючи O(k) пам'яті. Який підхід працює за час O(n log k)?

  1. AМін-купа, що містить усі n значень, з якої наприкінці вилучають k найменших
  2. BВідсортований масив усіх n значень
  3. CЧерга FIFO з останніх k значень
  4. DМакс-купа розміру k, корінь якої замінюють, коли надходить менше значення
5.Теорія графівСередня

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

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

Скористайтеся алгоритмом Дейкстри, щоб знайти довжину d(F) найкоротшого шляху від A до F у зваженому графі.

початок: Aкінець: F
d(F) =

3Розчини

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

Відповідь: A · Жадібний використовує 3 монети; оптимум — 2

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

Жадібний метод бере 4 + 1 + 1 = 3 монети, але 3 + 3 — лише 2, тож для цієї системи монет жадібний метод не оптимальний; оптимальне динамічне програмування.

Відповідь

A · Жадібний використовує 3 монети; оптимум — 2
2.Алгоритми та складність

Відповідь: B · Для неперервного (дробового) рюкзака, де предмети можна ділити

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

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

Відповідь

B · Для неперервного (дробового) рюкзака, де предмети можна ділити
3.Структури даних

Відповідь: B · 2i + 1 і 2i + 2

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

У масивах з індексацією від 0 лівий нащадок має індекс 2i + 1, правий — 2i + 2, а батько — ⌊(i − 1)/2⌋.

Відповідь

B · 2i + 1 і 2i + 2
4.Структури даних

Відповідь: D · Макс-купа розміру k, корінь якої замінюють, коли надходить менше значення

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

Корінь макс-купи — найбільше збережене значення; будь-яке менше нове значення замінює його за O(log k), тож купа завжди містить k найменших значень на цей момент.

Відповідь

D · Макс-купа розміру k, корінь якої замінюють, коли надходить менше значення
5.Теорія графів

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

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

Порахуйте

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

Відповідь

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

Відповідь: d(F) = 20

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

Алгоритм Дейкстри раунд за раундом

Кожен рядок: зафіксована вершина, її остаточна відстань і сусіди, чия відстань покращується.

A (0): B: 7, C: 1
C (1): E: 7
B (7): D: 11
E (7): F: 20
D (11)
F (20)

Найкоротший шлях

A → C → E → F
d(F) = 20

Відповідь

d(F) = 20

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