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

ID: 5984
Навчальна дисципліна загальної підготовки
Год внедрения: 
2020.
Количество кредитов ЭКТС: 
4.50.
Форма контроля: 
Экзамен.
Преподаватель: 
к.ф.-м.н., доц. Гришина В.О.
Количество аудиторных занятий: 
30 годин лекційних занять, 16 годин практичних занять..

Анотація навчальної дисципліни

Мета дисципліни:

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

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

 

Програмні компетентності

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

 

Програмні результати навчання

Знати лінійну та векторну алгебру, диференціальне та інтегральне числення, теорію функцій багатьох змінних, теорію рядів, диференціальні рівняння для функції однієї та багатьох змінних, операційне числення, теорію ймовірностей та математичну статистику в обсязі, необхідному для розробки та використання ІСТ та інфокомунікацій, сервісів та інфраструктури організації.
Застосовувати знання фундаментальних і природничих наук, системного аналізу та технологій моделювання, стандартних алгоритмів та дискретного аналізу при розв’язанні задач проектування і використання ІСТ.

Форми організації освітнього процесу та види навчальних занять

  • Л – лекційні заняття;
  • ПЗ – практичні заняття;
  • СРС – самостійна робота здобувача вищої освіти;
  • РГР- розрахунково-графічна робота;
  • МКР – модульна контрольна робота;
  • К – консультації.

 

Тематика та види навчальних занять

  • 1 тиждень 
    • Л1. Визначення, способи завдання множин. Операції над множинами та їх властивості. Діаграми Ейлера-Венна. [1, cтор. 23-31].
    • ПЗ1. Основні поняття теорії множин.      Тотожні перетворення виразів з множинами.
    •  [1, cтор. 32-39].
    • СРС. К.
  • 2 тиждень 
    • Л2. Декартовий добуток множин. Відношення. Відображення [1, cтор. 48-52].
    • СРС. К.
  • 3 тиждень 
    • Л3. Перетворення множини. Композиція відношень. [1, cтор. 52-64].
    • ПЗ2. Бінарні відношення. Композіції відношень.
    • СРС. К.
  • 4 тиждень 
    • Л4. Відношення еквівалентності та відношення порядку. [1, cтор. 65-74].
    • СРС. К.
  • 5тиждень 
    • Л5.    Розміщення, сполучення, перестановки без повторень та с повтореннями. [1, cтор. 180-184].
    • ПЗ3. Відношення еквівалентності та порядку.
    • СРС. К.
  • 6 тиждень 
    • Л6. Властивості перестановок. [1, cтор. 184-188].
    • СРС. К.
  • 7 тиждень
    • Л7. Біном Ньютона та поліноміальна формула [1, cтор. 188-195].
    • ПЗ4. Комбінаторний аналіз.
    • СРС. К.
  • 8 тиждень 
    • Л8. Твірні функції  [1, cтор. 203-204].
    • МКР1. 
    • СРС. К.
  • 9 тиждень 
    • Л9. Основні комбінаторні числа. [1, cтор. 195-203, 204-207]
    • ПЗ5. Твірні функції та їх застосування. Комбінаторні числа.
    • СРС. К.
  • 10 тиждень 
    • Л10. Основні поняття теорії графів. [1, cтор. 240-247]
    • СРС. К.
  • 11 тиждень 
    • Л11. Представлення графів в комп’ютерних програмах. . [1, cтор.  252-260]
    • ПЗ6. Основні поняття теорії графів. Представлення графів  в комп’ютерних програмах.
    • СРС. К.
  • 12 тиждень 
    • Л12. Зв’язность графа та орграфа. Вершинна та реберна зв'язність графа. [1, cтор. 247-250, 265-273, 281-284]
    • СРС. К.
  • 13 тиждень 
    • Л13. Ейлерові та гамільтонові цикли в графі. [1, cтор. 340-345]
    • ПЗ7. Зв’язність графів та характеристики зв’язних графів.
    • СРС. К.
  • 14 тиждень 
    • Л14. Дерева. Дводольні та планарні графи. [1, cтор. 292-313, 355-364]
    • СРС. К.
  • 15 тиждень 
    • Л15. Мережі. Потоку в мережі. Максимальний потік в мережі, теорема Форда-Фалкерсона. [1, cтор. 275-280]
    • ПЗ8. Основні класи графів.
    • МКР2.
    • СРС. К.

 

Індивідуальна робота

Виконується РГР. 

Мета РГР: набуття загальних та спеціальних компетентностей майбутніх бакалаврів, поглиблення теоретичних і практичних знань з “Дискретної математики ” .

  • 1–6 тижні Вибір варіанту. Виконання завдань 1- 6 частини 1- Теорія множин.
  • 7 тиждень Захист  частини 1 
  • 8–13 тижні Виконання завдань 7-12  частини 2  -  Комбінаторика. Теорія графів.
  • 14 тиждень Захист  частини 2. 
  • 15 тиждень Аналіз та оцінка розрахунково-графічної роботи викладачем

 

Самостійна робота

Самостійна робота складає 89 годин. Розподіл самостійної роботи за видами навчальних робіт:

  • підготовка до лекційних занять – 15 годин;
  • підготовка до практичних занять та до виконання розрахунково-графічної роботи –   разом 44 години;
  • підготовка до екзамену – 30 годин.

 

Процедура оцінювання

Система оцінювання рівня навчальних досягнень ґрунтується на принципах ЄКТС та є накопичувальною. Дисципліна поділяється на два семестрові модулі. Здобувачі протягом семестру готуються до лекційних та практичних занять, виконують РГР, 2 модульні контрольні роботи та 6 практичних завдань для  самостійної роботи.

Модульні контрольні роботи № 1 та № 2 виконуються у письмовій формі. Модульна робота складається з теоретичної частини (2 запитання) та практичної частини (3 задачі). Відповідь на кожне теоретичне питання оцінюється максимум 5 балами. Правильне розв’язання кожної задачі оцінюється в 5 балів.

Кожний модуль оцінюється у максимально можливі 50 балів:

Семестровий модуль № 1

  • ПЗ1. Оцінка за виконання – 4 бали. Термін надання – 1 тиждень.
  • ПЗ2. Оцінка за виконання – 3 бали. Термін надання – 2 тиждень.
  • ПЗ3. Оцінка за виконання – 3 бали. Термін надання – 3 тиждень.
  • ПЗ4. Оцінка за виконання – 5 бали. Термін надання – 4 тиждень.
  • РГР(ч.1). Оцінка за виконання – 10 балів. Термін надання  та захист – 7 тиждень.
  • МК1. Модульна контрольна робота – 20 балів (8 тиждень). Перескладання можливе протягом 9–11 тижнів за розкладом консультацій.

Семестровий модуль № 2

  • ПЗ5. Оцінка за виконання – 3 бали. Термін надання – 9 тиждень.
  • ПЗ6. Оцінка за виконання – 3 бали. Термін надання – 10 тиждень.
  • ПЗ7. Оцінка за виконання – 4 бали. Термін надання – 11 тиждень.
  • ПЗ8. Оцінка за виконання – 5 бали. Термін надання – 12 тиждень.
  • РГР(ч.2). Оцінка за виконання – 10 балів. Термін надання та захист – 14 тиждень. 
  • МК2. Модульна контрольна робота – 20 балів (15 тиждень).

Максимальна оцінка за повний обсяг виконаних навчальних елементів дисципліни – 100 балів.

Підсумковим контролем з дисципліни є усний екзамен, білет до якого складається з теоретичної частини (2 запитання) та практичної частини (3завдання). Максимальна оцінка за правильні відповіді на всі питання екзаменаційного білету становить 100 балів. 

 

Умови допуску до підсумкового контролю

До екзамену допускаються здобувачі вищої освіти, які виконали всі види навчальних елементів навчальної дисципліни на не менш, ніж на 60 %.

Екзамен відбувається за всіма тематичними (змістовними) модулями дисципліни.

Складання/перескладання екзаменів організується за встановленим деканатом розкладом.

 

Політика освітнього процесу

Здобувач зобов’язаний своєчасно та якісно виконувати всі отримані завдання; за необхідністю з метою з’ясування всіх не зрозумілих під час самостійної та індивідуальної роботи питань, відвідувати консультації викладача. Дотримуватись принципів академічної доброчесності. 

Виконаний не свій варіант завдання здобувачем не оцінюється.

Робота, яка виконана після встановлених викладачем термінів, не приймається.

Відсутність здобувача на екзамені або на контрольній роботі відповідає оцінці «0».

Складання/перескладання екзаменів – за встановленим деканатом розкладом.

Під час лекції здійснювати телефонні дзвінки забороняється.

 

РЕКОМЕНДОВАНА ЛІТЕРАТУРА

Основна література

  1. Дискретна математика для програмістов/Ф.А. Новіков.  – СПб.: Питер, 2008. 
  2. Теорія графів/Ф. Харарі. – М.: Мир, 1993.
  3. Дискретна математика и комбінаторика /Дж. Андерсон. –  Изд. дом Вільямса, 2004. 
  4. Введення в теорію графів /Р. Уилсон  –  М.: Мир, 1977
  5. Комбінаторика для програмістов / В. Липский.– М.: Мир, 1988.
  6. Лекції по теоріи графів /В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. – М.: Наука, 1990.
  7. Задачі по теорії множин, математичної логіии і теорії алгоритмів / И.А. Лавров, Л.Л.  Максимова / М. – Физматлит, 2004. 
  8. Задачник з дискретної математики / А.Ю. Эвнин –ЮУрГУ, 2002.

 

Додаткова література

  1. Основи дискретної математики. / Ю.В. Капітонова, С.Л. Кривий, О.А. Летичевський– К.: Наукова думка, 2002. 
  2. Теорія графів/ О. Орэ – М.: Наука, 1980.
  3. Комбинаторика. / М. Холл– М.: Мир, 1970.
  4. Введення в комбінаторні методи дискретної математики /В. Н. Сачков. М.: Наука, 1982.
  5. Дискретна математика і математичні питання кібернетики / С.В.Яблонский, А.А. Лупанов.  – М.: Наука, 1974.
  6. Основи теорії графів / А.А. Зыков.. – М.: Наука, 1987.
  7. Дискретна математика. Логіка, групы, графы / О.Е Акимов.– М.: Лаборатория базовых знаний, 2001.
  8. Конспект лекцій по дисципліні  «Дискретна математика» / В.О. Гришина. Одеса:ОНПУ,2014 .