СПЕЦІАЛЬНІ РОЗДІЛИ МАТЕМАТИКИ. ЧАСТИНА 1. ДИСКРЕТНА МАТЕМАТИКА

Робоча програма навчальної дисципліни (Силабус)

Реквізити навчальної дисципліни

Рівень вищої освіти Перший (бакалаврський)
Галузь знань 12 Інформаційні технології
Спеціальність 126 Інформаційні системи та технології
Освітня програма Інтегровані інформаційні системи
Статус дисципліни Нормативна
Форма навчання очна(денна)
Рік підготовки, семестр 1 курс, осінній семестр
Обсяг дисципліни 150 годин (36 годин – лекції, 36 годин – практичні, 78 годин – СРС)
Семестровий контроль/ контрольні заходи Екзамен
Розклад занять http://rozklad.kpi.ua/Schedules/ScheduleGroupSelection.aspx
Мова викладання Українська
Інформація про
керівника курсу / викладачів

Лектор: професор Теленик Сергій Федорович,

yulia.s.timofeeva@gmail.com,

моб. +38(097)492-57-27

Практичні: асистент Шинкевич Микола Костянтинович,

shinekolya@gmail.com,

моб. +38(063)742-64-46
Розміщення курсу https://campus.kpi.ua

Програма навчальної дисципліни

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

Опис дисципліни. Під час навчання студенти ознайомляться з основними поняттями дискретної математики. На практичних заняттях навчаться вирішувати задачі, а також використовувати мову Python для програмування множин, відношень, графів, булевих функцій. Передбачено контроль якості отриманих знань у вигляді тестової та модульної контрольних робіт.

Предмет навчальної дисципліни: дискретні процеси та системи.

Міждисциплінарні зв’язки. Дисципліна Спеціальні розділи математики-1. Дискретна математика базується на наступних дисциплінах: вища математика (операції над матрицями) та є основою для наступних дисциплін: теорія алгоритмів (задачі на графах, дерева, автомати, зокрема машина Т’юрінга), програмування (булева алгебра, теорія граматик та автоматів), теорія ймовірностей і математична статистика (теорія множин, теорія автоматів), електроніка та мікропроцесорна техніка (булева алгебра, мінімізація булевих функцій), бази даних (відношення), теорія інформації та кодування (булева алгебра), теорія прийняття рішень (бінарні відношення).

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

Основні завдання навчальної дисципліни

Знання:

  • методи теорії множин та відношень;

  • алгоритми мінімізації булевих функцій;

  • алгоритми пошуку найкоротшого шляху на графах та побудови кістякового дерева;

  • синтез автоматів для розпізнавання формальних мов;

  • застосування правил виведення в логіках висловлювань та предикатів.

Уміння:

  • застосовувати множини, відношення, графи для представлення типових задач;

  • зведення складних задач до типових задач на графах, множинах, відношеннях;

  • описувати формальні мови за допомогою граматик та системи за допомогою автоматів.

Пререквізити та постреквізити дисципліни (місце в структурно-логічній схемі навчання за відповідною освітньою програмою)

Пререквізити: мати базові знання з математики.

Постреквізити: вирішення практичних задач на множинах, відношеннях, графах, застосування булевих функцій, формальних мов, автоматів та правил логіки.

Зміст навчальної дисципліни

Лекційні заняття

Розділ 1. Алгебра множин

1.1 Визначення множин та способи їх представлення

1.2 Операції над множинами та їх властивості

1.3 Потужність, покриття та розбиття множин

Розділ 2. Відношення та функції

2.1 Основні поняття теорії відношень. Властивості відношень

2.2 Види відношень. Замикання відношень

2.3 Функціональні відображення та їх властивості. Поняття функції

Розділ 3. Алгебри. Булева алгебра

3.1 Алгебраїчні системи, алгебри та моделі

3.2 Булеві функції та їх властивості

3.3 Класи булевих функцій

3.4 Задача мінімізації булевих функцій

Розділ 4. Основи теорії графів

4.1. Поняття та види графів

4.2. Задача про найкоротший шлях

4.3. Поняття дерева, способи обходу дерев

4.4. Задача побудови кістякового дерева

Розділ 5. Основи теорії граматик та формальних мов

5.1. Основні поняття теорії граматик

5.2. Типи граматик та дерева виведення

Розділ 6. Теорія автоматів

6.1. Основні поняття теорії автоматів

6.2. Синтез детермінованих та недетермінованих автоматів

Розділ 7. Основи математичної логіки

7.1. Логіка висловлювань

7.2. Логіка предикатів

7.3. Правила логічного виведення

Практичні заняття

Метою практичних занять є вирішення з задач дискретної математики за допомогою програмних засобів та мови програмування Python

  1. Представлення множин за допомогою програмних засобів

  2. Програмна реалізація операцій над множинами

  3. Представлення та операції над множинами за допомогою бітових рядків

  4. Задання відношення булевою матрицею та операції над відношенням

  5. Перевірка властивостей відношення

  6. Побудова замикання відношення

  7. Побудова таблиці істинності булевої функції

  8. Побудова досконалої диз’юнктивної та кон’юнктивної форм булевої функції

  9. Визначення класу, до якого належить булева функція

  10. Програмне представлення графу та перевірка його на ейлерівість

  11. Пошук найкоротшого шляху в графі

  12. Представлення арифметичного виразу у прямому та зворотному польському записі

  13. Побудова дерева арифметичного виразу

  14. Програмна реалізація детермінованого скінченного автомату

Навчальні матеріали та ресурси

Базова література

  1. Нікольський Ю.В., Пасічник В.В., Щербина Ю.М. Дискретна математика. К.: Видавнича група BHV, 2007, 368с.

  2. Плотников А.Д. Дискретная математика: учеб. пособие. М.: Новое знание, 2005, 288 с.

  3. Новиков Ф.А. Дискретная математика для программистов: СПб.: Питер, 2009, 384 с.

  4. Капітонова Ю.В., Кривий С.Л. Летичевський О.А., Луцький Г.М., Печурін М.К. Основи дискретної математики. К.: Наукова думка, 2002, 560 с.

  5. Таран Т.А. Основы дискретной математики. К.: «Просвіта», 2003, 288с.

  6. Гетманова А.Д. Логика. М.: Высш.шк.. 1986, 288 с

Допоміжна література

  1. Андерсон Д. Дискретная математика и комбинаторика. СПб.:Вильямс,

    2003, 968с.

  2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для

    инженера. М.: Энергоатомиздат, 1988, 480с

  3. Спеціальні розділи математики – 1. Дискретна математика. Методичні

    вказівки до виконання комплексних контрольних робіт (ККР). [Електронне видання] / Уклад.: Я.Ю. Дорогий – К.: НТУУ «КПІ», 2012. – 36 с.

  4. Ковальски Р. Логика в решении проблем. М.: Наука, 1990, 280с.

  5. Susanna S. Epp. Discrete Mathematics with Applications. Cengage

    Learning, 2019, 1057p.

Навчальний контент

Методика опанування навчальної дисципліни (освітнього компонента)

Лекційні заняття

№ з/п Назва теми лекції та перелік основних питань
(перелік дидактичних засобів, посилання на літературу та завдання на СРС)
1

Лекція 1. Визначення множин та способи їх представлення, операції над множинами

Поняття множини. Способи представлення множин. Поняття підмножини. Порожня та універсальні множини. Булеан. Операції над множинами: об’єднання, перетин, доповнення, різниця, симетрична різниця. Представлення множин та операцій над ними за допомогою діаграм Ейлера-Венна.

Л. ( 1-ст.37-39)

Завдання на СРС. Комп’ютерне подання множин.
2

Лекція 2. Властивості операцій над множинами. Потужність, покриття та розбиття множин

Властивості операцій над множинами. Скінченні та нескінченні множини. Потужність множин. Обчислення потужностей множин. Рівнопотужні множини. Покриття і розбиття множин. Кортежі, елементи кортежів. Декартів добуток множин і його потужність. Лічильні множини та їхні властивості. Теорема Кантора. Методи доведення тотожностей в алгебрі множин..

Л. (4 – ст. 6-15)

Завдання для СРС Генерування розбиттів множини.
3

Лекція 3. Основні поняття теорії відношень. Властивості відношень

Поняття відношення. Місність відношення. Бінарні відношення. Поле відношення. Обернене відношення. Способи представлення бінарних відношень. Операції над бінарними відношеннями: об’єднання, перетин, доповнення, різниця, композиція. Універсальна множина відношення. Властивості бінарних відношень: рефлексивність, симетричність, транзитивність.

Л. ( 1- ст. 185-188, 195-197) (4 – ст.15-25)

Завдання для СРС. Використання відношень у базах даних.
4

Лекція 4. Види відношень. Замикання відношень.

Степінь відношення. Відношення еквівалентності. Класи еквівалентності. Зв’язок між відношенням еквівалентності та розбиттям. Відношення порядку. Частковий порядок. Строгий порядок. Порівнянні та непорівнянні елементи. Максимальний та мінімальний елементи. Топологічне сортування та його алгоритм. Замикання відношень. Симетричне, рефлексивне та транзитивне замикання, способи їх одержання. Діаграми Гассе. Побудова транзитивного замикання відношення. Алгоритм Уоршалла.

Л.(1-ст.188-195, 197-202)

Завдання для СРС. Розбиття частково впорядкованої множини на ланцюги
5

Лекція 5. Функціональні відображення та їх властивості. Поняття функції

Функціональні відображення. Області значень та визначення. Образ та прообраз. Сур’єктивне, ін’єктивне та бієктивне відображення. Функція. Аргументи та значення функцій. Функції-константи. Місність функції. Обернені функції. Композиція функцій. Способи подання функцій. Функціонали.

Л. (4- ст. 25-30, 5- ст. 25-37)

Завдання для СРС. Матроїди та їх застосування
6

Лекція 6. Алгебраїчні системи, алгебри та моделі

Поняття та складові алгебраїчної системи. Алгебри та моделі. Групоїди, їхні властивості. Напівгрупа. Абелева напівгрупа. Підстановка. Моноїд. Група. Абелева

група. Кільце. Властивості елементів кільця. Абелеве кільце. Поняття тіла та

поля. Алгебри Кантора та Буля.

Л.( 2- стр.86-93)

Завдання для СРС. Гомоморфізм та ізоморфізм в алгебраїчних системах.
7

Лекція 7. Булеві функції та їх властивості

Булеві змінні та функції. Набори. Місність функцій. Таблиця істинності булевих функцій. Функції нуля та однієї змінних. Булеві функції двох змінних. Властивості булевих функцій.

Л.( 1- ст.235-250)

Завдання для СРС. Реалізація булевих функцій схмами з функціональних елементів.
8

Лекція 8. Класи булевих функцій

Класи булевих функцій: функції, що зберігають константу, двоїсті функції, лінійні функції, монотонні функції. Властивості двоїстості, самодвоїстість. Суперпозиція булевих функцій. Замкнені класи булевих функцій. Функціонально повні системи.

Л. ( 1- ст 250-257, 2- ст 102-108 )

Завдання для СРС. Поліноміальне представлення булевих функцій. Поліном Жегалкіна
9

Лекція 9 Задача мінімізації булевих функцій

Диз’юнктивна нормальна форма. Досконала диз’юнктивна нормальна форма. Кон’юнктивна нормальна форма. Досконала кон’юнктивна нормальна форма. Способи їх отримання. Задача та мета мінімізації булевих функцій. Операції склеювання та поглинання. Скорочена, тупикова та мінімальна диз’юнктивні нормальні форми. Загальний алгоритм мінімізації булевих функцій. Метод Квайна-Мак-Класкі. Пошук мінімальної диз’юнктивної нормальної форми.

Л.(1-ст. 257-267, 2- ст. 128-139)

Завдання для СРС. Мінімізація булевих функцій методом Блейка.
10

Лекція 10. Поняття та види графів

Поняття графа. Неорієнтовані та орієнтовані графи. Мультиграфи. Інцидентність та суміжність. Види графів. Способи представлення графів. Підграфи. Операції на графах: об’єднання, перетин, видалення вершини, стягування ребра. Зв’язність графів. Компоненти зв’язності. Діаметр, центр, радіус графа. Степінь вершин. Цикломатичне число.

Л. (1-ст.88-100)

Завдання для СРС. Автоматична генерація графів.
11

Лекція 11. Задача про найкоротший шлях. Поняття дерева

Поняття шляхів та циклів в орієнтованому та неорієнтованому графах. Визначення наявності шляхів заданої довжини. Ейлерові та Гамільтонові графи. Ізоморфні графи. Планарні графи. Теорема Ейлера. Зважені графи. Задача про найкоротший шлях. Алгоритм Дейкстри. Поняття дерева. Властивості дерев. Корінь, внутрішні вершини дерев. Глибина вершини та висота дерева. Збалансованість дерева.

Л. (1-ст.100-126)

Завдання для СРС. Задача розфарбування графів
12

Лекція 12. Способи обходу дерев. Задача побудови кістякового дерева

Кістякове дерево. Алгоритм Пріма. Алгоритм Краскала. Способи обходу дерева: прямий, внутрішній та зворотній. Відповідні форми запису виразів: префіксний, інфіксний та постфіксний. Обчислення значення виразів, поданих у різних формах.

Л. (1-ст.150-160, 175-177)

Завдання для СРС. Дерево прийняття рішень
13

Лекція 13. Основні поняття теорії граматик. Типи граматик

Поняття символу, алфавіту, слова. Конкатенація та степінь. Поняття граматики. Виведення слів. Породжувана мова. Типи граматик та відповідні їм типи мов: без обмежень, контекстно-залежні, контекстно-вільні, регулярні. Співвідношення між граматиками різного типу.

Л. (1- ст.276-281)

Завдання для СРС. Визначення типу граматики та побудова її ланцюжків.
14

Лекція 14. Дерева виведення. Основні поняття теорії автоматів

Дерева виведення. Нотація Бекуса-Наура. Поняття скінченного автомату. Способи представлення автомата. Автоматне відображення та його властивості. Скінченні автомати без виходу. Розпізнавання мов за допомогою автомата

Л. (1 – ст. 283-289)

Завдання для СРС. Побудова граматики мови, яку розпізнає заданий автомат.
15

Лекція 15. Синтез детермінованих та недетермінованих автоматів

Недетерміновані автомати та еквівалентні їм детерміновані. Алгебра Кліні. Подання мов за допомогою автоматів. Приклад.

Л. ( 1 – ст. 289-310)

Завдання для СРС. Машина Т`юрінга.
16

Лекція 16. Логіка висловлювань. Логіка предикатів

Поняття висловлювання. Атомарні та складні висловлювання. Логічні операції. Формули логіки висловлювань. Таблиці істинності складних висловлювань. Алгебра висловлювань. Інтерпретації, тавтології та суперечності. Виконувані формули. Закони логіки висловлювань. Речення зі змінними. Основні поняття логіки предикатів. Квантори загальності й існування. Формули логіки предикатів. Зв’язані та вільні змінні. Закони логіки предикатів.

Л. ( 1- ст.9-25, 5- ст. 168-181)

Завдання для СРС. Випереджена нормальна форма.
17

Лекція 17. Правила логічного виведення.

Префіксна нормальна форма. Алгоритм зведення до префіксної нормальної форми. Логічне виведення. Критерій логічного виведення. Принцип прямої дедукції. Правила виведення в логіці висловлювань. Метод резолюцій. Алгоритм методу резолюцій. Логічні виведення в логіці предикатів.

Л. ( 1- ст.26-32)

Завдання для СРС. Методи доведення теорем
18 Лекція 18. Модульна контрольна робота

Практичні заняття

№ з/п Назва практичного заняття (комп’ютерного практикуму) Кількість ауд. годин
1 Представлення множин за допомогою програмних засобів 2
2 Програмна реалізація операцій над множинами 4
3 Представлення та операції над множинами за допомогою бітових рядків 2
4 Задання відношення булевою матрицею та операції над відношенням 2
5 Перевірка властивостей відношення 2
6 Побудова замикання відношення 4
7 Побудова таблиці істинності булевої функції 2
8 Побудова досконалої диз’юнктивної та кон’юнктивної форм булевої функції 2
9 Визначення класу, до якого належить булева функція 4
10 Програмне представлення графу та перевірка його на ейлерівість 2
11 Пошук найкоротшого шляху в графі 2
12 Представлення арифметичного виразу у прямому та зворотному польському записі 2
13 Побудова дерева арифметичного виразу 4
14 Програмна реалізація детермінованого скінченного автомату 2

Самостійна робота студента

№ з/п Назва теми, що виноситься на самостійне опрацювання Кількість годин СРС
1 Комп’ютерне подання множин 4
2 Генерування розбиттів множини 4
3 Використання відношень у базах даних 4
4 Розбиття частково впорядкованої множини на ланцюги 4
5 Матроїди та їх застосування 4
6 Гомоморфізм та ізоморфізм в алгебраїчних системах 4
7 Реалізація булевих функцій схемами з функціональних елементів 4
8 Поліноміальне представлення булевих функцій. Поліном Жегалкіна 4
9 Мінімізація булевих функцій методом Блейка 4
10 Автоматична генерація графів 4
11 Задача розфарбування графів 4
12 Дерево прийняття рішень 4
13 Визначення типу граматики та побудова її ланцюжків 4
14 Побудова граматики мови, яку розпізнає заданий автомат 4
15 Машина Т’юрінга 4
16 Випереджена нормальна форма 4
17 Методи доведення теорем 4
18 Підготовка до модульної контрольної роботи 4
19 Підготовка до екзамену 6

Політика та контроль

Політика навчальної дисципліни (освітнього компонента)

Система вимог, які ставляться перед студентом:

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

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

  • питання на лекції задаються у відведений для цього час;

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

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

  • штрафні бали виставляються за: переписування модульної контрольної роботи. Кількість штрафних балів не більше 10.

Види контролю та рейтингова система оцінювання результатів навчання (РСО)

Рейтинг студента з дисципліни складається з балів, що він отримує за:

  1. виконання модульної контрольної роботи;

  2. виконання практичних завдань;

  3. заохочувальні та штрафні бали.

Система рейтингових балів та критерії оцінювання

Практичні завдання:

«відмінно», повна відповідь на питання під час захисту (не менш ніж 90% потрібної інформації), практичне завдання виконано правильно – 3 бали;

«добре», достатньо повна відповідь на питання під час захисту (не менш ніж 75% потрібної інформації), практичне завдання виконане правильно – 2 бали;

«задовільно», неповна відповідь на питання під час захисту (не менш ніж 60% потрібної інформації), незначні помилки в виконанні практичного завдання – 1 бал;

«незадовільно», незадовільна відповідь та/або значні помилки в розв’язанні практичного завдання – 0 балів.

Модульна контрольна робота:

«відмінно», повна відповідь (не менш ніж 90% потрібної інформації), завдання розв’язане без помилок, дії обґрунтовано – 9-10 балів;

«добре», достатньо повна відповідь (не менш ніж 75% потрібної інформації), завдання розв’язано без значних помилок – 7-8 балів;

«задовільно», неповна відповідь, в деяких задачах можуть бути присутні значні помилки, але не менше 60% розв’язано правильно – 6 балів;

«незадовільно», незадовільна відповідь (неправильний розв’язок задач), потребує обов’язкового повторного написання в кінці семестру – 0-5 балів.

Заохочувальні бали

за виконання творчих робіт з кредитного модуля (наприклад, участь у факультетських та інститутських олімпіадах з навчальних дисциплін, участь у конкурсах робіт, підготовка оглядів наукових праць тощо); за активну роботу на очному практичному занятті 1-2 бали, але в сумі не більше 10.

Міжсесійна атестація

За результатами навчальної роботи за перші 7 тижнів максимально можлива кількість балів – 18 балів (4 практичних завдання). На першій атестації (8-й тиждень) студент отримує «зараховано», якщо його поточний рейтинг не менший ніж 9 балів.

За результатами 13 тижнів навчання максимально можлива кількість балів – 30 балів (10 практичних завдань). На другій атестації (14-й тиждень) студент отримує «зараховано», якщо його поточний рейтинг не менший ніж 15 балів.

Максимальна сума вагових балів контрольних заходів протягом семестру складає:

RD = 14*rпракт +rмкр + (rз - rш)=14*3+10+ (rз - rш)=52 + (rз - rш),

де rпракт – бал за практичне завдання (0…3);

rмкр – бал за написання МКР (0…10);

rз – заохочувальні бали (0…10);

rзш – штрафні бали (0…10).

Екзамен:

Максимальна сума балів стартової складової дорівнює 52 бали. Необхідною умовою допуску до екзамену є виконання всіх практичних завдань, написання модульної контрольної і стартовий рейтинг не менше 25 балів.

На екзамені студенти готуються до письмового екзамену. Кожний білет містить два теоретичних і два практичних питання.

Система оцінювання питань:

«відмінно», повна відповідь (не менше 90% потрібної інформації) – 11-12 балів;

«добре», достатньо повна відповідь (не менше 75% потрібної інформації, або незначні неточності) – 9-10 балів;

«задовільно», неповна відповідь (не менше 60% потрібної інформації та деякі помилки) – 7-8 балів;

«незадовільно», незадовільна відповідь – 0-6 балів.

Сума набраних балів, набраних за семестрову роботу та за екзамен переводиться до підсумкової оцінки згідно з таблицею:

Таблиця 1 — Переведення рейтингових балів до оцінок за університетською шкалою

Кількість балів Оцінка
100-95 Відмінно
94-85 Дуже добре
84-75 Добре
74-65 Задовільно
64-60 Достатньо
Менше 60 Незадовільно
Не виконані умови допуску Не допущено

Додаткова інформація з дисципліни (освітнього компонента)

перелік теоретичних питань, які виносяться на екзамен, наведено в Додатку 1.

Робочу програму навчальної дисципліни (Силабус):

Складено професор, Теленик Сергій Федорович

Ухвалено кафедрою АУТС (протокол № 1 від 27.08.2020 р.)

Погоджено Методичною комісією факультету (протокол № 1 від 02.09.2020 р.)

Додаток 1

Перелік теоретичних питань на екзамен

  1. Поняття множини. Способи представлення множин. Навести приклади. Поняття підмножини. Порожня та універсальні множини. Булеан. Навести приклади.

  2. Операції над множинами: об’єднання, перетин, доповнення, різниця, симетрична різниця. Представлення за допомогою діаграм Ейлера-Венна. Навести приклади.

  3. Властивості операцій над множинами. Навести приклади.

  4. Скінченні та нескінченні множини. Потужність множин. Обчислення потужностей множин. Рівнопотужні множини. Навести приклади.

  5. Покриття і розбиття множин. Навести приклади. Кортежі, елементи кортежів. Декартів добуток множин і його потужність. Навести приклади.

  6. Лічильні множини та їхні властивості. Навести приклади. Теорема Кантора.

  7. Методи доведення тотожностей в алгебрі множин.

  8. Поняття відношення. Місність відношення. Бінарні відношення. Навести приклади. Поле відношення. Обернене відношення.

  9. Способи представлення бінарних відношень. Навести приклади.

  10. Операції над бінарними відношеннями: об’єднання, перетин, доповнення, різниця, композиція. Навести приклади. Універсальна множина відношення.

  11. Властивості бінарних відношень. Навести приклади.

  12. Степінь відношення. Відношення еквівалентності. Класи еквівалентності. Навести приклади. Зв’язок між відношенням еквівалентності та розбиттям.

  13. Відношення порядку. Частковий порядок. Строгий порядок. Навести приклади. Порівнянні та непорівнянні елементи. Максимальний та мінімальний елементи. Топологічне сортування.

  14. Замикання відношень. Симетричне, рефлексивне та транзитивне замикання, способи їх одержання. Навести приклади.

  15. Діаграми Гассе. Побудова транзитивного замикання відношення. Алгоритм Уоршалла.

  16. Функціональні відображення. Області значень та визначення. Образ та прообраз. Сур’єктивне, ін’єктивне та бієктивне відображення. Навести приклади.

  17. Функція. Аргументи та значення функцій. Функції-константи. Місність функції. Обернені функції. Композиція функцій. Способи подання функцій. Функціонали. Навести приклади.

  18. Поняття та складові алгебраїчної системи. Алгебри та моделі. Навести приклади. Групоїди, їхні властивості. Навести приклади.

  19. Напівгрупа. Абелева напівгрупа. Підстановка. Моноїд. Група. Абелева група. Навести приклади.

  20. Кільце. Властивості елементів кільця. Абелеве кільце. Поняття тіла та поля. Навести приклади. Алгебри Кантора та Буля.

  21. Булеві змінні та функції. Набори. Місність функцій. Таблиця істинності. Функції нуля та однієї змінних. Навести приклади.

  22. Булеві функції двох змінних. Навести приклади.

  23. Властивості булевих функцій.

  24. Класи булевих функцій: функції, що зберігають константу, двоїсті функції, лінійні функції, монотонні функції. Властивості двоїстості, самодвоїстість.

  25. Суперпозиція булевих функцій. Замкнені класи булевих функцій. Функціонально повні системи. Навести приклади.

  26. Диз’юнктивна нормальна форма. Досконала диз’юнктивна нормальна форма. Способи їх отримання. Навести приклади.

  27. Кон’юнктивна нормальна форма. Досконала кон’юнктивна нормальна форма. Способи їх отримання. Навести приклади.

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

  29. Загальний алгоритм мінімізації булевих функцій. Метод Квайна-Мак-Класкі. Пошук мінімальної диз’юнктивної нормальної форми.

  30. Поняття графа. Неорієнтовані та орієнтовані графи. Мультиграфи. Інцидентність та суміжність. Види графів. Навести приклади.

  31. Способи представлення графів. Навести приклади.

  32. Підграфи. Операції на графах: об’єднання, перетин, видалення вершини, стягування ребра. Навести приклади.

  33. Поняття шляхів та циклів в орієнтованому та неорієнтованому графах. Визначення наявності шляхів заданої довжини. Ейлерові та Гамільтонові графи.

  34. Зв’язність графів. Компоненти зв’язності. Діаметр, центр, радіус графа. Степінь вершин. Цикломатичне число.

  35. Ізоморфні графи. Планарні графи. Теорема Ейлера. Зважені графи.

  36. Задача про найкоротший шлях. Алгоритм Дейкстри.

  37. Поняття дерева. Властивості дерев. Корінь, внутрішні вершини дерев. Глибина вершини та висота дерева. Збалансованість дерева. Навести приклади.

  38. Каркасне дерево. Алгоритм Пріма. Алгоритм Краскала. Навести приклади.

  39. Способи обходу дерева. Відповідні форми запису виразів. Навести приклади.

  40. Поняття символу, алфавіту, слова. Конкатенація та степінь. Поняття граматики. Виведення. Породжувана мова. Навести приклади.

  41. Типи граматик та відповідні типи мов. Дерева виведення. Нотація Бекуса-Наура. Навести приклади.

  42. Поняття скінченного автомату. Навести приклади. Способи представлення автомата.

  43. Автоматне відображення. Його властивості. Скінченні автомати без виходу. Навести приклади. Розпізнавання мов.

  44. Недетерміновані автомати та еквівалентні їм детерміновані. Алгебра Кліні. Подання мов за допомогою автоматів.

  45. Поняття висловлювання. Навести приклади. Атомарні та складні висловлювання. Логічні операції.

  46. Формули логіки висловлювань. Таблиці істинності. Навести приклади. Алгебра висловлювань.

  47. Інтерпретації, тавтології та суперечності. Виконувані формули. Навести приклади. Правило логічного виводу.

  48. Закони логіки висловлювань.

  49. Речення зі змінними. Логіка предикатів. Поняття логіки предикатів. Навести приклади.

  50. Квантори загальності й існування. Формули логіки предикатів. Зв’язані та вільні змінні. Навести приклади.

  51. Закони логіки предикатів.

  52. Префіксна нормальна форма. Алгоритм зведення до префіксної нормальної форми.

  53. Логічне виведення. Критерій логічного виведення. Принцип прямої дедукції.

  54. Правила виведення в логіці висловлювань.

  55. Метод резолюцій. Алгоритм методу резолюцій.

  56. Логічні виведення в логіці предикатів.