Комбінаторика: підрахунок, перестановки, принцип включень-виключень
Дискретна математика вивчає скінченні та злічено нескінченні структури. На відміну від неперервного аналізу, тут немає «нескінченно малих» — лише точні цілочислові підрахунки.
Базові об'єкти підрахунку:
Перестановки n елементів: P(n) = n!
Розміщення (впорядковані k з n): A(n,k) = n!/(n−k)!
Комбінації (невпорядковані): C(n,k) = n! / (k!(n−k)!)
Формула Паскаля: C(n,k) = C(n-1,k-1) + C(n-1,k)
Біном Ньютона: (a+b)ⁿ = Σₖ₌₀ⁿ C(n,k) aᵏ bⁿ⁻ᵏ
Наслідки: Σₖ C(n,k) = 2ⁿ (кількість підмножин n-елементної множини)
Σₖ (-1)ᵏ C(n,k) = 0
Принцип включень-виключень (PIE) — потужний інструмент для підрахунку об'єднань:
Для двох множин: |A₁ ∪ A₂| = |A₁| + |A₂| − |A₁ ∩ A₂|
Загальна формула для n множин:
|A₁ ∪ … ∪ Aₙ| = Σ|Aᵢ| − Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| − …
Функція Ейлера (число взаємно простих з n):
φ(n) = n · ∏_{p|n} (1 − 1/p)
Доведення: PIE для множин Aₚ = {m≤n : p|m}, |Aₚ| = n/p
Безладки (derangements): D(n) = n!·Σₖ₌₀ⁿ (−1)ᵏ/k!
Значення: D(1)=0, D(2)=1, D(3)=2, D(4)=9
Ймовірність безладку при великому n: D(n)/n! → 1/e ≈ 0.368
Принцип Рамсея та голубятника
Принцип Дірікле (голубятника): якщо n+1 предмет розмістити у n ящиків, то хоча б один ящик містить щонайменше 2 предмети. Здається тривіальним, але має дивовижні застосування:
Принцип голубятника: ⌈n/k⌉ ящиків потребуємо, де n—предмети, k—місць
Теорема Рамсея R(m,n):
R(m,n) — мінімальне N: будь-яке 2-забарвлення K_N
містить або K_m (червоний kліку) або K_n (синій kліку)
R(3,3) = 6: серед 6 людей є або 3 взаємних знайомих
або 3 взаємних незнайомих.
Доведення R(3,3) = 6:
Для N=6, вузол v: 5 ребер (2 кольори) → ≥3 одного кольору
Нехай {u₁,u₂,u₃} з'єднані з v червоно.
Якщо хоч одне ребро серед uᵢ червоне → маємо K₃ (червоний).
Якщо жодного → {u₁,u₂,u₃} утворюють K₃ (синій). ∎
R(m,n) ≤ R(m-1,n) + R(m,n-1) (рекурентна нерівність)
Теорія графів: Ейлер, Гамільтон, дерева
Граф G = (V, E) — множина вершин V та ребер E ⊆ V×V. Теорія графів народилась у 1736 р. з задачі Ейлера про Кенігсберзькі мости.
Ейлерів шлях / цикл:
Ейлерів ЦиКл (обходить всі ребра один раз, повертається):
⟺ граф зв'язний і всі вершини мають парний степінь
Ейлерів Шлях (не обов'язково повертається):
⟺ рівно 2 вершини непарного степеня
Формула Ейлера для планарних графів:
V − E + F = 2 (вершини − ребра + грані = 2)
К₅ та К_{3,3} — непланарні (теорема Куратовського)
Гамільтонів цикл (відвідати кожну ВЕРШИНУ один раз):
Необхідна умова Оре: deg(u)+deg(v) ≥ n для всіх u,v без ребра
→ Гамільтонів ЦиКл існує.
Задача комівояжера (TSP): знайти найкоротший Г-цикл → NP-тяжка
Ключові теореми про дерева — зв'язні ациклічні графи:
Властивості дерева з n вершин:
· Рівно n-1 ребер
· Між будь-двома вершинами — рівно один простий шлях
· Видалення будь-якого ребра → незв'язний граф
· Додавання будь-якого ребра → рівно один цикл
Формула Кейлі: кількість помічених дерев на n вершинах = nⁿ⁻²
n=3: 3¹=3 дерева (зірка A-B-C, B-A-C, C-A-B)
n=4: 4²=16 дерев
Алгоритми на графах: BFS, DFS, Дейкстра
BFS (обхід у ширину):
Черга Q. Мітимо s як відвіданий, Q = {s}.
Поки Q ≠ ∅: v = dequeue(Q)
для кожного сусіда u: якщо ¬відвіданий → мітимо, enqueue(Q)
Складність: O(V+E)
Знаходить найкоротший шлях у незваженому графі
DFS (обхід у глибину):
dfs(v): мітимо v
для кожного сусіда u: якщо ¬відвіданий → dfs(u)
Складність: O(V+E)
Застосування: пошук циклів, топологічне сортування
Алгоритм Дейкстри (найкоротший шлях у зваженому графі):
Пріоритетна черга (min-heap). dist[s]=0, всі інші=∞.
Поки черга ≠ ∅: v = extract_min()
для кожного сусіда u: якщо dist[v]+w(v,u) < dist[u]:
dist[u] = dist[v]+w(v,u); оновлюємо чергу.
Складність: O((V+E) log V) із бінарною купою
Тільки для невід'ємних ваг!
Беллман-Форд: O(V·E), коректний для від'ємних ваг.
Модульна арифметика та криптографія RSA
Модульна арифметика — серце сучасної криптографії. Кільце ℤ/nℤ — множина лишків {0,1,…,n−1} з операціями додавання і множення за модулем n.
Китайська теорема про лишки (CRT):
Якщо m₁, m₂, …, mₖ попарно взаємно прості і M = m₁m₂…mₖ, то
система x ≡ aᵢ (mod mᵢ) має єдиний розв'язок mod M.
Застосування: прискорення RSA (CRT-оптимізація)
Розширений алгоритм Евкліда: gcd(a,b) і зворотні елементи
gcd(48,18): 48=2·18+12 → 18=1·12+6 → 12=2·6+0 → gcd=6
Безу: ∃s,t: sa+tb = gcd(a,b)
RSA (Райвест-Шамір-Адлемен, 1977):
1. Вибрати великі прості p, q; n = p·q
2. φ(n) = (p-1)(q-1)
3. Вибрати e: gcd(e, φ(n)) = 1 (відкритий ключ)
4. Знайти d: e·d ≡ 1 (mod φ(n)) (закритий ключ)
Шифрування: C = Mᵉ mod n
Дешифрування: M = Cᵈ mod n
Коректність: Mᵉᵈ = M^(kφ(n)+1) ≡ M (mod n) (за малою т. Ферма)
Теорія ймовірностей дискретних просторів
Простір: Ω — вибіркова множина, P: 2^Ω → [0,1]
P(Ω) = 1, P(A∪B) = P(A)+P(B) якщо A∩B=∅
Умовна ймовірність: P(A|B) = P(A∩B)/P(B)
Формула Байєса:
P(Aᵢ|B) = P(B|Aᵢ)P(Aᵢ) / Σⱼ P(B|Aⱼ)P(Aⱼ)
Ланцюги Маркова: {Xₙ} — послідовність випадкових величин
P(Xₙ₊₁=j | X₀,…,Xₙ) = P(Xₙ₊₁=j | Xₙ) (властивість Маркова)
Матриця переходів P: Pᵢⱼ = P(Xₙ₊₁=j | Xₙ=i), рядки суми = 1
Стаціонарний розподіл π: πP = π, Σπᵢ = 1
Що таке продуктивна функція й навіщо вона?
Продуктивна функція (generating function) послідовності (a₀,a₁,a₂,…): G(x) = Σaₙxⁿ. Вона перетворює рекурентні співвідношення на алгебраїчні рівняння. Для Фібоначчі F(x) = x/(1-x-x²) → формула Біне Fₙ = (φⁿ−ψⁿ)/√5.
P vs NP: в чому суть?
P — задачі, що вирішуються за поліноміальний час. NP — задачі, де розв'язок можна перевірити за поліноміальний час (зокрема: SAT, TSP, підбір рюкзака). Питання P=NP? — найважливіша відкрита проблема інформатики (Millennium Prize). Якщо P=NP, RSA-шифрування стане безсильним.
Про цю статтю
Ця стаття є частиною бази знань calculator.party — освітнього ресурсу, що поєднує теорію з практичними інструментами. Матеріал орієнтований на студентів, учнів і фахівців, що прагнуть глибокого розуміння теми. Тут зібрані ключові концепції, формули та реальні приклади застосування.
Інформатика та алгоритміка лежать в основі сучасного світу: від пошукових алгоритмів до нейронних мереж та квантових обчислень.
Навіщо читати цю статтю
Після прочитання ви зможете впевнено пояснити тему, вирішувати практичні задачі та застосовувати знання у навчанні й роботі. Стаття охоплює теоретичне підґрунтя і числові приклади, що полегшують запам'ятовування матеріалу.
Часті запитання (FAQ)
Що таке Дискретна математика і чому це важливо знати?
Дискретна математика — ключова тема в комп'ютерних наук. Розуміння її основ дає змогу вирішувати практичні задачі, успішно складати іспити та застосовувати знання в реальних ситуаціях. Стаття розкриває концепцію доступними словами з конкретними прикладами.
Які ключові формули та методи використовуються в дискретна математика?
Основні формули та методи для дискретна математика охоплюють як аналітичні підходи, так і числові алгоритми. У статті наведені всі ключові вирази з поясненням кожного позначення та вказівкою одиниць вимірювання.
Де в реальному житті застосовується дискретна математика?
Сфери застосування дискретна математика надзвичайно широкі: програмуванні (бекенд, алгоритми), штучному інтелекті, кібербезпеці та обробці великих даних. Знання цієї теми відкриває кар'єрні можливості в інженерії, науці, фінансах та IT-галузі.
Як розрахувати дискретна математика онлайн?
На calculator.party є безкоштовні онлайн-калькулятори з тематики 'Дискретна математика'. Достатньо ввести вхідні дані — і ви миттєво отримаєте точний результат з покроковим поясненням. Це ідеально для перевірки ручних розрахунків.
Яка різниця між дискретна математика та суміжними темами?
Стаття чітко описує межі тематики 'Дискретна математика', порівнюючи її з близькими поняттями. Чітке розуміння відмінностей допомагає уникнути типових помилок та плутанини при розв'язанні задач.