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

Мета вивчення дисципліни: формування особистості студентів, розвиток їх інтелекту та здібностей до логічного мислення; забезпечення базової підготовки щодо вільного володіння поняттями та термінологією дискретної математики, використання методів дискретної математики для розв’язання прикладних задач, формування у студентів практичних навичок, які б дали змогу ефективно застосовувати знання та методи з дискретної математики у майбутній професійній роботі.
Практичне значення та використання отриманих знань: оволодіння сучасними методами дискретного аналізу; формування базових знань та володіння поняттями, термінологією дискретної математики; оволодіння методами розв’язання прикладних задач та проведення досліджень з використанням методів та засобів дискретної математики; створення необхідного теоретичного та практичного фундаменту для успішного оволодіння дисциплінами, які пов’язані з теоретичними дослідженнями в галузі програмування та інформаційних технологій; сприяння розвитку тих якостей особистості, що мають для майбутнього бакалавра особисте професійне значення в контексті інтеграції у європейський освітній простір.
Тематика та види навчальних занять
Для денної форми здобуття освіти
Лекційні заняття
Лекція 1. Поняття висловлення. Логічні операції над висловленнями. Закони логіки.
Лекція 2. Алгебра висловлень. Схеми з перемикачів та застосування алгебри висловлень до їх оптимізації.
Лекція 3. Булеві функції. Таблиці істинності основних булевих функцій.
Лекція 4. Нормальні форми булевих функцій. Досконалі нормальні форми: диз'юнктивна (ДДНФ), кон’юнктивна (ДКНФ) та поліноміальна (ДПНФ).
Лекція 5. Мінімізація булевих функцій. Методи мінімізації ДДНФ булевих функцій (метод Квайна, метод сполучених індексів, карти Карно).
Лекція 6. Істотні та неістотні змінні. Двоїсті функції. Самодвоїсті функції. Принцип двоїстості.
Лекція 7. Визначення замкнутих класів булевих функцій. Теорема Поста.
Лекція 8. Поняття формальної теорії. Повнота, несуперечливість формальної теорії. Логічне слідування. Побудова виводу та виводу з системи гіпотез. Теорема про дедукцію.
Лекція 9. Числення висловлень. Основні теореми формальної теорії числення висловлень. Методи доведень в численні висловлень.
Лекція 10. Поняття предикату. Кванторні операції над предикатами. Основні правила перетворення виразів, які містять предикати.
Лекція 11. Визначення формальної теорії числення предикатів. Повнота та несуперечність чистого числення предикатів першого порядку. Теореми Геделя про неповноту.
Лекція 12. Поняття алгоритму та його властивості. Асимптотична складність алгоритму та порівняння алгоритмів.
Лекція 13. Визначення машини Тьюрінга. Основні види машин Тьюрінга. Теза Тьюрінга. Робота машини Тьюрінга.
Лекція 14. Скінченні автомати, види скінченних автоматів. Таблиця станів та діаграма станів скінченного автомату.
Лекція 15. Нормальні алгоритми Маркова. Рекурсивні функції. Алгоритмічна розв’язність задачі.
Практичні заняття
Практичне заняття №1. Логічні операції над висловленнями. Закони логіки.
Мета заняття: Навчитися виконувати перетворення логічних виразів з використанням законів логіки, будувати таблиці істинності та діаграми Ейлера-Венна для логічних виразів.
Практичне заняття №2. Досконалі нормальні форми (диз’юнктивна, кон’юнктивна та поліноміальна нормальні форми).
Мета заняття: Навчитися будувати по таблиці істинності булевої функції досконалі диз’юнктивні, кон’юнктивні та поліноміальну нормальні форми, будувати досконалу поліноміальну нормальну форму за допомогою ДДНФ.
Практичне заняття №3. Мінімізація булевих функцій.
Мета заняття: Навчитися мінімізувати булеві функції за допомогою метода Квайна, метода сполучення індексів, метода карт Карно.
Практичне заняття №4. Істотні та неістотні змінні, двоїсті функції, використання принципу двоїстості.
Мета заняття: Навчитися знаходити істотні та неістотні змінні булевої функції, двоїсті функції за таблицею істинності, визначенням та за принципом двоїстості.
Практичне заняття №5. Повні класи булевих функцій. Теорема Поста.
Мета заняття: Навчитися перевіряти класи булевих функцій на повноту, будувати повні класи.
Практичне заняття №6. Предикати та операції над ними.
Мета заняття: Навчитися знаходити значення істинності предикату, перетворювати виразі з предикатами, які містять квантори, знаходити предварену нормальну форму.
Практичне заняття №7. Машина Тьюрінга. Скінченні автомати.
Мета заняття: Навчитися будувати діаграму станів та таблицю станів скінченного автомату, знаходити результат роботи машини Тьюрінга.
Консультації здійснюються впродовж семестру згідно встановленого розкладу.
Індивідуальна робота. Не має
Форми контрольних заходів та оцінювання результатів навчання
Для денної форми здобуття освіти
Поточний контроль полягає у виконанні
1) 7-ми індивідуальних поточних завдань. Індивідуальні поточні завдання виконуються письмово і полягають в розв’язуванні типових задач відповідно до мети та завдань практичних занять. Бездоганне виконання індивідуальних поточних завдань №1-2 оцінюється у 8 балів; №3-4 оцінюється у 7 балів, №5-7 оцінюються у 10 балів.
2) двох модульних контрольних робіт. Модульна робота складається з теоретичної частини та практичної частини. Бездоганне виконання кожної модульної контрольної роботи становить 20 балів.
Підсумковий контроль – екзамен. Екзаменаційний білет складається з теоретичної частини та практичної частини. Максимальна оцінка, яку може отримати студент – 100 балів.