годин

модулів

1–2

курс

Шкільна математика

передумови

Програма курсу

Модуль 1

Математична логіка

📚 10 тем · ⏱ 12 год

⊕

Висловлення, кон'юнкція, диз'юнкція, заперечення, імплікація
Таблиці істинності. Тавтологія, суперечність, виконуваність
Логічна еквівалентність. Закони де Моргана
Предикати і кванторів ∀,∃. Область квантифікації
Методи доведення: пряме, від суперечного, за індукцією
Принцип математичної індукції та його застосування

Модуль 2

Теорія множин і відношень

📚 10 тем · ⏱ 10 год

⊕

Операції: ∪, ∩, \, △ (симетрична різниця), доповнення
Декартовий добуток. Бінарні відношення. Матриця суміжності
Відношення еквівалентності: рефлексивність, симетричність, транзитивність
Класи еквівалентності та фактор-множина
Відношення порядку. НЧМО (часткове vs повне впорядкування)
Теорема Кантора. Потужність множини. Зліченні та незліченні множини

Модуль 3

Комбінаторика

📚 10 тем · ⏱ 12 год

⊕

Правила суми і добутку. Дерево рішень
Перестановки: P(n) = n!. З повторенням
Розміщення: A(n,k) = n!/(n−k)!
Комбінації: C(n,k) = n!/(k!(n−k)!)
Двочленна формула Ньютона: (a+b)ⁿ = Σ C(n,k)aᵏbⁿ⁻ᵏ
Принцип включень-виключень. Принцип Дірихле
Числа Стірлінга, Каталана, числа Фібоначчі та їх комбінаторний сенс

Модуль 4

Теорія графів

📚 12 тем · ⏱ 16 год

⊕

Граф: вершини та ребра. Орієнтовані та неорієнтовані графи
Ступінь вершини. Лема про рукостискання: Σdeg = 2|E|
Ейлерів та гамільтонів шляхи і цикли. Критерії
Зв'язність. Компоненти зв'язності. DFS / BFS алгоритми
Дерева та ліси. Мінімальне остовне дерево (Прим, Краскал)
Найкоротший шлях: алгоритми Дейкстри і Беллмана-Форда
Потоки у мережах. Теорема Форда-Фулкерсона (max-flow min-cut)
Планарні графи. Формула Ейлера: V−E+F=2

Модуль 5

Булева алгебра

📚 8 тем · ⏱ 10 год

⊕

Булева алгебра: аксіоми, принцип двоїстості
Нормальні форми: КНФ, ДНФ, СКНФ, СДНФ
Мінімізація булевих функцій: метод Карно
Логічні схеми: вентилі AND, OR, NOT, XOR, NAND, NOR
Схеми суматорів, мультиплексорів, демультиплексорів

Модуль 6

Теорія чисел

📚 8 тем · ⏱ 10 год

⊕

Подільність. Алгоритм Евкліда: НСД(a,b) = НСД(b, a mod b)
Прості числа. Теорема про нескінченність простих (Евклід)
Основна теорема арифметики. Факторизація
Рівняння Безу. Лінійні діофантові рівняння
Конгруенції. Мала теорема Ферма. Китайська теорема про залишки

Модуль 7

Автомати та формальні мови

📚 8 тем · ⏱ 10 год

⊕

Кінцеві автомати (ДКА і НКА). Діаграма переходів
Регулярні вирази та регулярні мови. Теорема Кліні
Контекстно-вільні граматики. Дерева розбору
Магазинні автомати. Ієрархія Хомського

Ключові теореми

Формула Ейлера (графи)

V − E + F = 2

Для зв'язного планарного графа

Теорема Кантора

|P(A)| > |A|

Потужність множини < потужності її степеневої множини

Мала теорема Ферма

aᵖ⁻¹ ≡ 1 (mod p)

p — просте, p∤a. Основа RSA-шифрування

Max-flow Min-cut

max flow = min cut

Максимальний потік дорівнює мінімальному перерізу

Ресурси

📘

Rosen — Discrete Mathematics

Найпопулярніший англомовний підручник

🎥

MIT 6.042 Math for CS

Відеолекції з дискретної математики (OCW)

📗

Кнут — Мистецтво програмування т.1

Комбінаторика та дискретні структури

🏫

Brilliant.org — Discrete Math

Інтерактивні задачі з логіки та графів

← Матем. статистика Комплексний аналіз → ↩ Усі курси

Дискретна Математика

Програма курсу

Ключові теореми

Ресурси

🔗 Також за темою