МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ДЕРЖАВНИЙ УНІВЕРСИТЕТ ІНФОРМАЦІЙНО-КОМУНІКАЦІЙНИХ ТЕХНОЛОГІЙ

ІНСТИТУТ ЗАОЧНОГО ТА ДИСТАНЦІЙНОГО НАВЧАННЯ

Кафедра вищої математики

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

3 семестр

Навчально-методичний посібник

для самостійної роботи студентів

заочної форми навчання за напрямками:

0912 – Комп’ютерна інженерія;

1601 – Інформаційна безпека.

Київ 2005

Зміст

1. Тематичний план навчальної програми на 3 семестр 3

2. Інформаційно-методичне забезпечення на 3 семестр. Список літератури 4

3. Зміст семестрового контролю

(Перелік екзаменаційних завдань) 4

4. Рекомендації до організації самостійної роботи 11

5. Критерії оцінювання знань та вмінь студентів 12

Укладач: доцент Жданова Ю.Д.

Навчально-методичний посібник обговорений і затверджений на засіданні кафедри вищої математики ДУІКТ.

1. Тематичний план навчальної програми на 1 семестр Розділ 1 Множини, відношення

Тема 1. Елементи теорії множин і відношень.

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

Декартовий добуток множин. Основні поняття теорії відношеннь на множинах (множині). Бінарні відношення. Властивості бінарних відношень. Спеціальні бінарні відношення: відношення еквівалентності та відношення порядку.

Тема 2. Елементи комбінаторики

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

Розділ 2 Елементи теорії булевих функцій

Тема 3. Елементи теорії булевих функцій

Поняття булевої функції. Способи завдання булевих функцій. Елементарні булеві функції та їх властивості.

Реалізація булевих функцій формулами. Рівносильність та тотожність формул. Принцип двоїстості.

Диз’юнктивна та кон’юнктивна нормальні форми. Розкладання булевої функції за змінними. Досконалі диз’юнктивна та кон’юнктивна нормальні форми.

Повні системи булевих функцій.

Мінімізація булевих функції в класі досконалих диз’юнктивних нормальних форм.

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

Розділ 3 Елементи теорії графів. Елементи теорії алгоритмів.

Тема 4. Елементи теорії графів

Означення графа. Способи завдання графа: матрицею інцидентності, списком ребер, матрицею суміжності. Ізоморфізм графів. Елементи графів. Маршрути в графах: ланцюги, цикли; ейлерові ланцюги (цикли ). Необхідні та достатні умови наявності в графі ейлерова цикла (теорема Ейлера). Досяжність і зв’язність. Компоненти зв’язності.

Тема 5. Елементи теорії алгоритмів

Інтуїтивне означення алгоритму. Приклади алгоритмів. Блок-схеми алгоритмів. Проблема уточнення поняття алгоритму. Машина Тьюрінга. Функції, обчислюванні за Тьюрінгом. Теза Тьюрінга. Універсальна машина Тьюрінга. Приклад числової функції, яка не є обчислюванною за Тьюрінгом. Алгоритмічно нерозв'язувані проблеми. Операції над графами. Види графів. Графи без циклів: дерева і ліс. Дерево з коренем.