Шпаргалка: Інформаційні технології
66 пунктів із 14 тем — усе, що варто знати напамʼять.
Відкриється вікно друку — там можна одразу зберегти у PDF. Шапка сайту й кнопки на аркуш не потраплять.
Поняття алгоритму; часова та просторова складність
- П'ять властивостей алгоритму: дискретність, визначеність, скінченність, масовість, результативність.
- Порядок класів: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).
- Один цикл по n → O(n); два вкладені → O(n²); поділ навпіл → O(log n).
- В O-оцінці відкидаємо сталі та молодші доданки.
Абстрактні типи даних: стеки, списки, вектори, словники, множини, черги
- Стек = LIFO, операції push / pop / top.
- Черга = FIFO, операції enqueue / dequeue.
- Множина = унікальні, без порядку.
- Словник = пари «ключ → значення», доступ за ключем.
- Вектор = доступ за індексом O(1).
Реалізація АТД (кортежі, множини, словники, звʼязні списки) та складність операцій
- set і dict: пошук/вставка/видалення — у середньому O(1).
- Звʼязний список: доступ/пошук — O(n), вставка на початку — O(1).
- Масив: доступ за індексом O(1), вставка в середину O(n).
- Кортеж — незмінний, список — змінний.
- Множина зберігає лише унікальні елементи.
Базові алгоритми пошуку та сортування і їх складність
- Лінійний пошук — O(n), двійковий — O(log n) (лише для відсортованих).
- Бульбашкове, вибором, вставками — усі O(n²).
- Шкала зростання: O(1) < O(log n) < O(n) < O(n·log n) < O(n²).
- Двійковий пошук щоразу відкидає половину елементів.
Алгоритми на графах та їх складність (пошук вшир/вглиб, компоненти, кістякове дерево, найкоротші шляхи)
- BFS і DFS: складність O(V+E).
- BFS — черга, DFS — стек/рекурсія.
- Кістякове дерево: V−1 ребро, без циклів.
- MST: Прим і Крускал.
- Дейкстра — найкоротші шляхи за невідʼємних ваг.
- Матриця суміжності — O(V²), список — O(V+E).
Стратегія «розділяй та володарюй»
- Три кроки: розділяй → володарюй → обʼєднуй.
- Бінарний пошук — O(log n), потрібен відсортований масив.
- Merge sort — O(n·log n) завжди.
- Quick sort — O(n·log n) у середньому, O(n²) у гіршому.
- Обовʼязкова наявність базового випадку рекурсії.
Стратегія балансування
- Збалансоване дерево: висота ≈ log₂n, операції O(log n).
- Незбалансоване («лінія»): O(n).
- Сортування злиттям / розділяй-і-володарюй при рівному поділі: O(n·log n).
- Принцип: рівномірний поділ зменшує глибину з n до log n.
Динамічне програмування
- Дві умови застосовності: оптимальна підструктура + перекривання підзадач.
- Два підходи: згори вниз (мемоізація) і знизу вгору (табличний).
- Фібоначчі: рекурсія O(2^n), ДП O(n).
- Складність ДП = число підзадач × вартість однієї підзадачі.
- ДП ≠ жадібний: ДП перебирає, жадібний бере локально найкраще.
Оцінювання складності при застосуванні стратегій розроблення алгоритмів
- Порядок класів: O(1) < O(log n) < O(n) < O(n·log n) < O(n²) < O(2ⁿ) < O(n!).
- Двійковий пошук — O(log n); якісні сортування — O(n·log n); вкладені цикли — O(n²).
- О-нотація відкидає сталі та молодші доданки.
- Чотири стратегії: перебір, розділяй і володарюй, жадібний, динамічне програмування.
Імперативний та декларативний підходи до програмування
- Імперативний = ЯК (послідовність команд, зміна стану). Приклади: Pascal, C, асемблер.
- Декларативний = ЩО (опис результату). Приклади: SQL, HTML/CSS, Prolog, формули таблиць.
- Цикли й присвоєння — ознака імперативного стилю.
- Запит/опис без явних кроків — ознака декларативного.
Розвʼязні, напіврозвʼязні та нерозвʼязні проблеми; проблема зупинки
- Розвʼязна = завжди зупиняється з правильною відповіддю.
- Напіврозвʼязна = гарантована лише відповідь «так».
- Нерозвʼязна = алгоритму не існує в принципі.
- Проблема зупинки — нерозвʼязна, але напіврозвʼязна.
- Доведення — від супротивного (самозастосування програми).
Функції бінарної логіки
- Таблиці істинності НЕ, І, АБО, XOR — без роздумів.
- І (AND) = 1 лише при 1∧1; АБО (OR) = 0 лише при 0∨0.
- Імплікація хибна тільки 1→0.
- Пріоритет: НЕ → І → АБО.
- Кількість рядків таблиці = 2ⁿ.
- Закони де Моргана.
Позиційні системи числення; беззнаковий та доповнювальний код цілих; арифметика
- Основи: 2, 8, 10, 16; шістнадцяткові A=10, B=11, C=12, D=13, E=14, F=15.
- Беззнаковий діапазон: 0 … 2ⁿ−1. Доп. код: −2ⁿ⁻¹ … 2ⁿ⁻¹−1.
- 8=2³ → групи по 3; 16=2⁴ → групи по 4.
- Алгоритм доп. коду: модуль → інверсія → +1.
Числа з плаваючою комою: подання, переваги/недоліки, арифметика
- Формула: N = ±M · 2^E.
- float: 32 біти = 1 + 8 + 23, зсув 127.
- double: 64 біти = 1 + 11 + 52, зсув 1023.
- Прихований біт = 1 (у нормалізованій формі).
- E_реальне = E_записане − зсув.