Дискретні структури
Анотація курсу
Дисципліна присвячена вивченню основ дискретної математики, як фундаментальної дисципліни для розуміння та розробки алгоритмів, кодування, побудови структур даних та вирішення різноманітних обчислювальних задач. Теоретична частина охоплює розгляд поняття множин, відношень та операцій з множинами; вивчення поняття алгебраїчних структур та їх типів, особливостей булевої алгебри, логічних функцій та логічного числення; вивчення основ комбінаторики та її застосуванні в програмуванні, вивчення принципів кодування та двійкового представлення різних типів даних, оптимальне та завадостійке кодування; опанування основ теорії графів та огляд фундаментальних алгоритмів на графах Практична складова спрямована на формування навичок використання базових дискретних структур, робота з множинами, вирішення комбінаторних задач, задач кодування та використання фундаментальних алгоритмів на графах в практичних ситуаціях.
Мета:
Метою дисципліни «Дискретні структури» є формування у здобувача розуміння основ дискретної математики, що є фундаментом для розуміння та розробки алгоритмів, структур даних, баз даних та комп’ютерних мереж, та здобуття практичних навичок використання базових дискретних структур в практичних ситуаціях як-то робота з множинами, комбінаторні задачі, кодування та задачі на графах.
Основні завдання:
Завданнями дисципліни «дискретні структури» є: розгляд фундаментального поняття множини, відношень та операцій з множинами та елементами множин; вивчення поняття алгебраїчних структур та їх типів, особливостей булевої алгебри, логічних функцій та логічного числення; вивчення основ комбінаторики та її застосуванні в програмуванні, вивчення принципів кодування та двійкового представлення різних типів даних, оптимальне та завадостійке кодування; опанування основ теорії графів та практичне застосування фундаментальних алгоритмів на графах.
Що ви будете знати:
- поняття множини, математичний опис відношень та операцій з множинами;
- властивості відношень між елементами множини;
- поняття алгебраїчної структури, типи алгебраїчних структур;
- булеві функції та логічне числення;
- базові комбінаторні задачі, принципи оцінки складності алгоритмів;
- основи теорії кодування, способи кодування різних типів даних, методи оптимального та завадостійкого кодування;
- основи теорії графів, поняття графу, орієнтованого графу, дерева, бінарного дерева;
- фундаментальні алгоритми на графах
Що ви будете вміти:
- використовувати множини в програмах; вирішувати практичні задачі з обробкою множин;
- використовувати логічне числення в практичних ситуаціях;
- розв’язувати комбінаторні задачі, пов’язані з перебором різних комбінацій даних;
- використовувати на практиці різні способи кодування даних та алгоритми стиснення даних;
- працювати з різними представленнями графів та дерев;
- використовувати фундаментальні алгоритми на графах в практичних ситуаціях
Тематичний план курсу
Тема 1. Вступ до дисципліни дискретні структури.
Дискретні структури як математичний фундамент програмування. Зв’язок дискретної математики з іншими дисциплінами підготовки майбутніх інженерів-програмістів. Ознайомлення зі структурою, цілями та задачами курсу.
Тема 2. Множини
Базові поняття. Множини та елементи множин. Потужність множин. Підмножини. Пуста множина та Універсум. Парадокс Рассела. Діаграми Ейлера та діаграми Ейлера-Вена як наочне зображення множин та відношень між ними. Використання множин в сучасних мовах програмування.
Тема 3. Відношення та операції над множинами
Відношення між множинами. Операції над множинами. Декартовий добуток двох множин.
Тема 4. Відношення між елементами множин
Бінарні відношення між елементами множин. Область визначення й область значень. Відповідності. Властивості відношень. Комп’ютерне подання відношень.
Тема 5. Алгебраїчні структури
Поняття алгебраїчної структури. Поняття операції. Властивості операції. Гомоморфізм. Морфізми. Типи алгебраїчних структур. Бульова алгебра
Тема 6. Бульові функції
Функції алгебри логіки. Бульові функції однієї змінної. Суттєві та несуттєві змінні. Бульові функції двох змінних. Реалізація функцій формулами. Рівносильні формули.
Тема 7. Комбінаторика
Комбінаторні задачі. Перестановки. Розміщення. Поєднання. Підстановки.
Тема 8. Кодування
Кодування як основний спосіб представлення даних. Аналогові та дискретні сигнали. Аналого-дискретне перетворення. Біт як одиниця інформації та даних. Різновиди даних. Кодування чисел. Кодування символів. Кодування зображень. Кодування звуку. Теорема Шеннона про оптимальне кодування. Алгоритм Шеннона-Фано. Алгоритм Хаффмана. Арифметичне кодування. Словникові алгоритми.
Тема 9. Графи
Витоки та основні визначення теорії графів. Елементи графа. Орієнтовані графи. Графи з петлями. Ізоморфізм графів. Підграфи. Доповнення графа. Спрямовані орграфи та мережі. Маршрути, ланцюги, цикли. Відстань між вершинами. Комп’ютерне представлення графів. Дерева. Визначення та основні властивості дерев. Орієнтовані дерева. Бінарні дерева. Комп’ютерне представлення дерев. Обходи бінарних дерев. Приклади використання дерев.
Тема 10. Фундаментальні алгоритми на графах Обхід графа.
Пошук в глибину. Пошук в ширину. Пошук найкоротшого шляху в графі. Алгоритм Дейкстри. Алгоритм Флойда-Воршалла. Побудова оптимального остового дерева. Алгоритм Крускала. Алгоритм Пріма.
Загальна інформація
| Форма навчання | Кількість кредитів ECTS | Загальна кількість академічних годин | Лекційні | Лабораторні | Самостійна робота | Форма контролю |
|---|---|---|---|---|---|---|
| Денна | 7 | 210 | 54 | 36 | 120 | екзамен |
| Заочна | 7 | 210 | 10 | 8 | 192 | екзамен |
| Компетентності | Результати навчання |
|---|---|
| ЗК02 Здатність застосовувати знання у практичних ситуаціях СК07 Володіння знаннями про інформаційні моделі даних, здатність створювати програмне забезпечення для зберігання, видобування та опрацювання даних СК08 Здатність застосовувати фундаментальні і міждисциплінарні знання для успішного розв’язання завдань інженерії програмного забезпечення СК14 Здатність до алгоритмічного та логічного мислення | ПР05 Знати і застосовувати відповідні математичні поняття, методи доменного, системного і об’єктно-орієнтованого аналізу та математичного моделювання для розробки програмного забезпечення ПР06 Уміння вибирати та використовувати відповідну задачі методологію створення програмного забезпечення ПР13 Знати і застосовувати методи розробки алгоритмів, конструювання програмного забезпечення та структур даних і знань |