Алгоритми, графи, динамічне програмування та реляційні бази даних
32 картки університетського рівня для повторення сортування, алгоритмів на графах, динамічного програмування, SQL, індексів і транзакцій. Передбачено основи програмування, структур даних і SQL.
- Category
- Computer Science
- Level
- basic
- Languages
- uk → uk
- Cards
- 32
- Markdown
- Алгоритми, графи, динамічне програмування та реляційні бази даних (.md)
Flashcards (32)
| # | Front (Term / Question) | Back (Definition / Answer) | Example | Multiple-Choice Options |
|---|---|---|---|---|
| 1 | Які дві фази двофазного блокування (2PL)? | Зростання: отримувати блокування без звільнення. Скорочення: звільняти без отримання нових. За належних конфліктних блокувань читання й запису 2PL гарантує розклади, серіалізовні за конфліктами, але взаємні блокування все ще можливі. | ||
| 2 | Чим відрізняються мемоізація та динамічне програмування знизу вгору? | Мемоізація обчислює підзадачі за потреби, зазвичай рекурсивно, та кешує результати. ДП знизу вгору обчислює стани в порядку, за якого їхні залежності вже доступні, зазвичай заповнюючи таблицю. | ||
| 3 | Чим відрізняються WHERE і HAVING у запиті з групуванням? | WHERE фільтрує вхідні рядки до групування. HAVING фільтрує отримані групи й може використовувати агрегатні умови, наприклад COUNT(*)>1. | ||
| 4 | Що таке неповторюване читання і який стандартний рівень ізоляції його забороняє? | Повторне читання рядка дає змінені дані або рядок зникає після фіксації оновлення чи видалення іншою транзакцією. REPEATABLE READ і SERIALIZABLE забороняють цю аномалію. | ||
| 5 | Що таке фантомне читання і як йому запобігають? | Повторний запит із предикатом знаходить інший набір відповідних рядків після фіксації змін іншою транзакцією. SERIALIZABLE запобігає фантомам у стандартній моделі; деякі реалізації, зокрема PostgreSQL REPEATABLE READ, запобігають їм і на нижчому рівні. | ||
| 6 | Який спрощений логічний порядок опрацювання SQL-запиту SELECT? | Для запиту без CTE, віконних функцій та операцій над множинами: FROM/JOIN → WHERE → GROUP BY й агрегати → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. Це логічна модель, не обов'язково фізичний порядок виконання оптимізатора. | ||
| 7 | Чим жадібний алгоритм відрізняється від динамічного програмування? | Жадібний алгоритм остаточно робить локальний вибір і потребує доказу, що такі вибори зберігають оптимум. ДП порівнює альтернативи за рекурентним співвідношенням і повторно використовує результати підзадач. Глобальний оптимум потребує правильної моделі та рекурентного співвідношення, а не лише назви «ДП». | ||
| 8 | Що означають властивості транзакцій ACID? | Атомарність: ефекти повністю або жодних. Узгодженість: коректні транзакції зберігають обмеження й інваріанти застосунку. Ізоляція: одночасна робота відповідає обраному рівню ізоляції. Довговічність: зафіксовані ефекти переживають збої, охоплені налаштованими гарантіями бази. | ||
| 9 | Чому динамічне програмування корисне для багатьох задач оптимізації? | Оптимальна підструктура дозволяє виразити оптимум через оптимуми підзадач. Якщо підзадачі перекриваються, збереження відповідей усуває повторну роботу. Визначення станів і рекурентне співвідношення мають правильно описувати вихідну задачу. | ||
| 10 | Чому B+ дерева корисні для індексів баз даних і діапазонних запитів? | Велика кількість нащадків зменшує висоту дерева та кількість звернень до сторінок. Впорядковані ключі й зв'язані листки підтримують перегляд діапазонів. Хеш-індекси призначені для пошуку за рівністю і самі собою не забезпечують такого впорядкованого доступу до діапазонів. | ||
| 11 | Яке рекурентне співвідношення ДП для довжини найдовшої спільної підпослідовності (LCS)? | Нехай L[i,j] — довжина LCS префіксів довжини i,j. Задамо L[0,j]=L[i,0]=0. Якщо останні символи збігаються, L[i,j]=1+L[i−1,j−1]; інакше L[i,j]=max(L[i−1,j],L[i,j−1]). Повна таблиця потребує O(mn) часу й пам'яті. | ||
| 12 | Як пошук у глибину виявляє цикл в орієнтованому графі? | DFS рухається вглиб за допомогою рекурсії або явного стека. Ребро до вершини, ще активної на поточному шляху DFS, є зворотним і доводить наявність орієнтованого циклу; ребра до будь-якої раніше відвіданої вершини недостатньо. | ||
| 13 | Що робить алгоритм сортування стабільним? | Елементи з однаковими ключами зберігають початковий взаємний порядок. Сортування злиттям може бути стабільним, якщо за рівності спочатку брати лівий елемент; стандартне швидке сортування на місці зазвичай нестабільне. Стабільність залежить від реалізації. | ||
| 14 | Чого вимагають перша, друга й третя нормальні форми? | 1НФ: атомарні значення атрибутів. 2НФ: 1НФ і відсутність залежності неключового атрибута від власної підмножини атрибутів будь-якого кандидатного ключа. 3НФ: 1НФ і для кожної нетривіальної залежності X→A або X — суперключ, або A входить принаймні до одного кандидатного ключа. Неключовий атрибут не входить до жодного кандидатного ключа. | ||
| 15 | Чим відрізняються INNER JOIN і LEFT JOIN? | INNER JOIN повертає поєднання рядків, які задовольняють умову з'єднання. LEFT JOIN також зберігає кожен лівий рядок без відповідності, підставляючи NULL у праві стовпці. Кілька відповідних правих рядків можуть дати кілька результатів для одного лівого рядка. | ||
| 16 | Як працює сортування вставками і від чого залежить час для майже відсортованих даних? | Кожен елемент вставляється у відсортований префікс. Звичайний варіант зі зсувами або обмінами сусідніх елементів потребує Θ(n+I), де I — кількість інверсій. За I=O(n) час лінійний; сам малий розмір входу не змінює найгіршу оцінку Θ(n²). | ||
| 17 | Як алгоритм Беллмана–Форда працює з від'ємними ребрами та виявляє досяжний від'ємний цикл? | Усі ребра релаксують до V−1 разів. Подальше покращення через досяжну вершину виявляє від'ємний цикл, досяжний із джерела. Найгірший час — O(VE); для вершин, досяжних із такого циклу, немає скінченної вартості найкоротшого шляху. | ||
| 18 | Чим відрізняються кластеризовані й некластеризовані індекси рядкового зберігання в SQL Server? | Кластеризований індекс зберігає рядки таблиці в порядку ключа, тому він може бути лише один. Некластеризований має власні ключі й покажчики на рядки та може містити інші стовпці. Терміни й деталі зберігання різняться між СУБД. | ||
| 19 | Як порівняти матрицю суміжності та звичайні списки суміжності? | Для V вершин і E ребер матриця потребує O(V²) пам'яті та перевіряє ребро за O(1). Списки займають O(V+E); пошук ребра (u,v) у невідсортованому списку потребує O(deg(u)), де deg(u) — довжина цього списку. | ||
| 20 | Як пошук у ширину знаходить найкоротші шляхи в незваженому графі? | BFS використовує чергу FIFO й обходить вершини за відстанню в ребрах. Позначення вершини під час додавання до черги запобігає повторним відвідуванням. Перший знайдений шлях до досяжної вершини має найменшу кількість ребер. | ||
| 21 | Що таке брудне читання і який стандартний рівень ізоляції першим його забороняє? | Читання незафіксованих даних іншої транзакції незалежно від того, чи буде вона потім скасована. READ COMMITTED і сильніші стандартні рівні ізоляції забороняють брудне читання. | ||
| 22 | Що потрібно для двійкового пошуку і коли він працює за O(log n)? | Він послідовно ділить навпіл інтервал пошуку в даних, відсортованих за порядком порівняння. У масиві з доступом за індексом за O(1) і порівняннями за сталий час пошук серед n елементів займає O(log n). | ||
| 23 | Чим відрізняються первинний і зовнішній ключі в PostgreSQL? | Первинний ключ ідентифікує рядки унікальними значеннями без NULL. Зовнішній ключ вимагає відповідності значенням зазначеного ключа з урахуванням правил NULL. Він може посилатися на придатний ключ UNIQUE або первинний ключ у тій самій чи іншій таблиці. | ||
| 24 | Як WAL у PostgreSQL підтримує довговічність за звичайної синхронної фіксації? | Потрібні записи журналу потрапляють у стійке сховище до підтвердження фіксації та до запису змінених сторінок даних. Після збою WAL може відтворити зміни, відсутні на сторінках. Асинхронна фіксація може втратити нещодавно підтверджені транзакції. | ||
| 25 | Яке стандартне рекурентне співвідношення задачі про рюкзак 0/1 із цілою місткістю W? | Нехай D[i,w] — найбільша цінність перших i предметів за місткості w і додатних цілих ваг wᵢ. Задамо D[0,w]=0. Якщо wᵢ>w, беремо D[i−1,w]; інакше max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). Час O(NW) є псевдополіноміальним. | ||
| 26 | Коли алгоритм Дейкстри коректний і яка звичайна оцінка реалізації з купою? | За невід'ємних ваг ребер він послідовно фіксує вершину з найменшою попередньою відстанню. Реалізація зі списками суміжності й двійковою мінімальною купою потребує O((V+E) log V). Від'ємні ребра можуть порушити обґрунтування остаточності відстані. | ||
| 27 | Чому швидке сортування може потребувати Θ(n²) часу і як допомагає рандомізація? | Повторні дуже нерівномірні розбиття, наприклад постійний вибір найменшого з різних ключів, дають квадратичну роботу. За різних ключів або належного опрацювання повторів випадкові опорні елементи дають очікуваний час O(n log n). Медіана трьох — корисна евристика, а не гарантія для найгіршого випадку. | ||
| 28 | Що таке топологічний порядок і як алгоритм Кана його знаходить? | В орієнтованому ациклічному графі кожне ребро u→v вимагає поставити u перед v. По черзі виводять вершину з нульовим вхідним степенем і видаляють її вихідні ребра, додаючи нові вершини нульового вхідного степеня до черги. Якщо виведено менше V вершин, граф має цикл. | ||
| 29 | Які найгірші оцінки часу й додаткової пам'яті пірамідального сортування на місці? | Побудова купи потребує O(n), а всі вилучення — O(n log n). За ітеративного просіювання вниз у вхідному масиві сортування займає O(n log n) часу в найгіршому випадку та O(1) додаткової пам'яті. | ||
| 30 | Як працює стандартне сортування масиву злиттям і які його часові та просторові оцінки? | Воно рекурсивно сортує дві половини та зливає їх за лінійний час. Стандартний варіант потребує Θ(n log n) часу й O(n) додаткової пам'яті за порівнянь зі сталою вартістю. | ||
| 31 | Коли сортування підрахунком або порозрядне сортування можуть бути лінійними? | Сортування підрахунком коштує O(n+k) для n ключів із діапазону k значень. Порозрядне сортування з d стабільними проходами за розрядами й основою b коштує O(d(n+b)). Лінійність можлива лише за відповідних параметрів; ці алгоритми використовують структуру ключів, а не тільки порівняння. | ||
| 32 | Як алгоритми Краскала й Прима будують мінімальне кістякове дерево? | У зв'язному неорієнтованому зваженому графі Краскал розглядає ребра за зростанням ваги та відкидає цикли за допомогою системи неперетинних множин. Прим нарощує одне дерево, щоразу обираючи ребро мінімальної ваги між деревом і зовнішньою вершиною. |