Дискретна математика — це розділ математики, який займається дискретними математичними структурами замість безперервних. Дискретні математичні структури включають об’єкти з різними значеннями, наприклад графіки, цілі числа, логічні оператори тощо. У цьому посібнику ми охопили всі теми дискретної математики для інформатики, наприклад теорія множин , рекурентне співвідношення, теорія груп і теорія графів.

Останні статті з дискретної математики!

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

• Вступ до логіки висловлювань
• Застосування логіки висловлювань
• Логіка висловлювань і предикатів
• Пропозиційні еквівалентності
• Нормальна та принципова форми
• Предикати та квантори
• Теорема про вкладені квантори
• Правила висновку
• Введення в докази

Множини та відношення

• Теорія множин
• Типи наборів
• Набір операцій
• Груба теорія множин
• Функції
• Послідовність і підсумовування
• Представлення матриць і графів у відношеннях
• Типи відносин
• Замикання відношення та відношення еквівалентності

Математична індукція

• Математична індукція
• Основи рахунку
• Ідентичність Паскаля
• Принцип перегородки
• Перестановки та комбінації
• Узагальнені перестановки та комбінації
• Генеруючі функції
• Принцип включення-виключення
• Дискретна теорія ймовірностей

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

• Логічні функції
• Булева алгебраїчна теорема
• Властивості булевої алгебри
• Кількість булевих функцій
• Мінімізація булевих функцій

Оптимізація

• Лінійне програмування
• Графічне рішення для лінійного програмування
• Симплексний алгоритм
• PERT

Замовлені набори та решітки

• Частково впорядковані набори
• Елементи POSET
• Діаграми Хассе
• Решітки

Теорія ймовірностей

• Основні поняття ймовірності
• Аксіоми ймовірностей
• Властивості ймовірності
• Умовна ймовірність
• Теорема Байєса
• Рівномірний розподіл
• Експоненціальний розподіл
• Нормальний розподіл
• Розподіл Пуассона

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

• Введення в Graph
• Основна термінологія графа
• Типи графа
• Прогулянки, стежки, доріжки та кола
• Компоненти графіка відстані
• Вершини зрізів і ребра зрізів
• Міст у графі
• Незалежні набори
• Алгоритми найкоротшого шляху [алгоритм Дейкстри]
• Застосування теорії графів
• Обхід графа [DFS]
• Обхід графа [BFS]
• Мінімальне остовне дерево Прима
• Мінімальне остовне дерево Крускала
• Коди Хаффмана
• Обходи дерев
• Проблема комівояжера

Спеціальний графік

• Дводольні графи
• Незалежні комплекти та покриття
• Графи Ейлера
• Графи Ейлера - алгоритм Флері
• Графи Ейлера - Китайська листоноша - Проблема Гамільтона

Зіставлення

• Узгодження - Basics, Perfect, Bipartite
• Алгоритми апроксимації

Розмальовки вершин

• Хроматичні числа, жадібний алгоритм розфарбовування
• Забарвлення краю
• Теорема Візінга
• Планарний граф - основи, перевірка планарності
• Орієнтовані графи - центральність ступеня
• Орієнтовані графи – слабка зв’язність
• Орієнтовані графи - сильні компоненти
• Орієнтовані графи – орієнтовані графи Ейлера, Гамільтона
• Орієнтовані графи – Алгоритм Тар’яна для знаходження сильно зв’язаного компонента
• Рукостискання в графовій теоремі

Теорія груп

• Групи, підгрупи, напівгрупи
• Ізоморфізм, гомоморфізм
• Автоморфізм
• Кільця, Інтегральні області, Поля

Швидкі посилання

• Нотатки в останню хвилину (LMN)
• Тести з дискретної математики