Алгоритми, графи, динамічне програмування та реляційні бази даних

32 картки університетського рівня для повторення сортування, алгоритмів на графах, динамічного програмування, SQL, індексів і транзакцій. Передбачено основи програмування, структур даних і SQL.

Category
Computer Science
Level
basic
Languages
uk → uk
Cards
32
Markdown
Алгоритми, графи, динамічне програмування та реляційні бази даних (.md)

Flashcards (32)

#Front (Term / Question)Back (Definition / Answer)ExampleMultiple-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Як алгоритми Краскала й Прима будують мінімальне кістякове дерево?У зв'язному неорієнтованому зваженому графі Краскал розглядає ребра за зростанням ваги та відкидає цикли за допомогою системи неперетинних множин. Прим нарощує одне дерево, щоразу обираючи ребро мінімальної ваги між деревом і зовнішньою вершиною.