ДМ_МУ_САМ РАБ

розв’язуються комбінатор-

нимиметодами.(сам.роб.)

Тема 2. Загальні визна-

5

2

2

2

3

3

чення

комбінаторики.

Моделі типових комбі-

наторних конфігурацій.

Поняття r-вибірки. За-

гальні правила

і

задачі

комбінаторики.

Правила

суми і добутку. Переста-

новки, розміщення, спо-

лучення

(без

повторень

та з повтореннями).

Тема

3.

Властивості

0,5

-

0,5

3

3

сполучень.

Біном

Ньютона.

Біноміальні

коефіцієнти.

Трикутник

Паскаля.

Поліноміальна

теорема. (сам. роб.)

Тема 4. Принцип вклю-

3,5

1

1,5

3

3

чення

і

виключення.

Теорема

та

формула

включень івиключень.

Тема

5.

Задачі

про

7

2

2

3

3

3

розподіл

предметів

за

урнами

(урнові

схеми

вирішення

комбіна-

торних задач). Розподіл

однакових об’єктів за

урнами. Розподіл неодна-

кових об’єктів за урнами.

Числа Стирлинга.

Числа

Моргана. Числа Белла.

Композиції і розбиття.

Тема

6.

Підходи

до

1,5

1

0,5

3

3

вивчення

комбінатор-

них об’єктів і чисел.

Поняття про продуктивні

функції. Поняття про ре-

курентні співвідношення.

Тема 7. Метод рекуре-

0,5

-

0,5

3

3

нтних

співвідношень.

ЧислаФібоначчі.(сам.роб.)

Разом за зміст. модулем 6

19,5

6

4

1

8,5

22

1

21

Змістовий модуль 7. Основи теорії кодування.

Тема

1.

Алфавітне

4

1

3

3

3

11

кодування. Кодування з

мінімальною

надлишко-

вістю. Алгоритм Фано.

Алгоритм

Хаффмена.

Завадостійке

кодування.

Стиснення

даних.

Криптографія. (сам. роб.)

Разом за зміст. модулем 7

4

1

3

3

3

Усього годин за мод. 2

72,5

20

16

5

36,5

70

3

4

63

Модуль 3

Змістовий модуль 8. Основні поняття теорії графів

Тема

1.

Зародження

2,5

-

2

0,5

3

3

теорії

графів

як

математичної

дисцип-

ліни.

Типові

задачі

теорії графів. (сам.роб.)

Тема

2.

Походження

9

2

4

3

9

1

2

6

графів.

Визначення

графів. Різновиди гра-

фів.

Неорієнтовані

та

орієнтовані графи. Осно-

вні терміни для неорієн-

тованих та орієнтованих

графів.

Способи задання

графів. Геометрична реа-

лізація

графів.

Матриця

суміжності.

Матриця

інциденцій.

Число

вершин і ребер графа.

Тема

3.

Операції

над

3,5

1

2,5

3

3

графами. Операції вилу-

чення ребер та вершин.

Операція введення ребра,

операція

введення вер-

шини у ребро. Операція

об’єднання

графів.

Операції

додавання

і

множення графів.

Тема

4.

Ізоморфізм

4,5

1

2

1,5

3

3

графів. Плоскі та пла-

нарні графи. Підграфи.

Алгебраїчний

критерій

ізоморфізму

графів.

Зв'язок з відношеннями.

Ізоморфізм

як

відно-

шення

еквівалентності.

Гомеоморфні

графи.

12

Теорема

Понтрягіна-

Куратовського.

Теорема

Жордана.

Жорданова

крива.

Побудова плоского

зображенняграфа.

Тема

5.

Зв'язність

4

2

2

3

3

графів.

Ейлерові

та

гамільтонові

графи.

Поняття зв'язності гра-

фів, компонента зв'язно-

сті, n-зв'язний граф.

Властивості

зв'язних

графів. Метричні харак-

теристики

зв'язних

графів.

Ейлерові

та

гамільтонові

графи.

Теорема Ейлера. Алго-

ритм

знаходження ейле-

рова

цикла

(теорема

Флері). Ознаки існування

гамільтонових

циклів,

шляхів і контурів.

Тема

6.

Цикломатика

1,5

1

0,5

3

3

графів.

Цикломатичне

число та його властивості.

Цикломатична

матриця.

Базис

циклів.

Алгоритм

побудови базисуциклів.

Тема

7.

Задача

1

-

1

3

3

комівояжера.

Приклади

практичних

задач,

що

зводяться

до

задачі

комівояжера.(сам. роб.)

Тема 8. Дерева. Визна-

7

2

2

3

3

3

чення дерева, властивості

дерев, ліс. Перелічення

графів і дерев. Остови

графа.

Орієнтовані

і

бінарні

дерева.

Правила

обходу

бінарних дерев.

Еквівалентні

бінарні

дерева.

Тема 9.

Розфарбування

1,5

1

0,5

3

3

графів. Фарбування вер-

шин та ребер. Хрома-

тичне число, теорема про

біхроматичний

граф.

Хроматичний клас. Теоре-

ма

Брукса.

Гіпотеза

13

чотирьох

фарб.

Теорема

про п'ять фарб. Прикла-

дні задачі, що зв’язані з

розфарбуванням графів.

Тема

10.

Двудольні та

1,5

1

0,5

3

3

k-дольні графи.

Тема

11.

Транспортні

5,5

1

2

2,5

3

3

мережі та течії. Їх

властивості.

Найкорот-

ші відстані та шляхи у

мережах.

Алгоритм

визначення відстані

між

вершинами

на

графі з

одиничними

довжинами

ребер. Алгоритм Дейкст-

ри (Форда) визначення

відстані між

вершинами

на графі

з

довільними

довжинами ребер.

Тема

12.

Алгоритми

1

1

3

3

Флойда

і

Данцига

пошуку

найкоротших

шляхів між всіма парами

вершин графа (сам. роб.).

Тема

13.

Течії

у

11

2

4

5

3

3

мережах.

Задача

про

максимальну

течію

у

мережі. Розріз мережі.

Теорема

про

максима-

льну течію і мінімальний

розріз. Алгоритм Форда-

Фалкерсона.

Разом за зміст. модулем 8

53,5

14

14

2

23,5

45

1

2

42

Змістовий модуль 9. Елементи теорії формальних граматик.

Тема 1. Задачі форма-

5

2

3

3

3

лізації мов та пере-

кладу. Задання мов за

допомогою

граматик.

Типи граматик. (сам.роб.)

Разом за зміст. модулем 9

5

2

3

3

3

Змістовий модуль 10. Елементи теорії скінченних автоматів.

Тема 1. Загальна харак-

4

1

3

3

3

теристика

автоматів.

Розпізнавачі.

Скінченні

автомати.

Способи

задання

автоматів.

Автомати Мили і Мура.

Автомати

з

магазинною

14

пам’яттю.		Машина
Тьюринга. (сам.роб.)
Разомзазміст.модулем10			4				1	3	3					3
Усього годин за мод. 3			61,5	14	14	4	5	29,5	51	1	2			48
			Індивідуальні завдання
Контрольна		робота	4					4
(позааудиторна,		для
денної форми навчання)
Контрольна		робота	2					2
(аудиторна, для денної
форми навчання)
ІДЗ	(позааудиторна							-	20					20
контрольна робота для
заочної форми навчання)
Усього годин за семестр			180	44	40		12	84	180	6	10			164

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

	№	Назва теми	Кількість годин
			денна	заочна
	1	Множини. Алгебра множин.	4	2
	2	Відношення та операції над ними.	4	2
	3	Функціональні відношення.	2
	4	Булеві функції та перетворення.	2	2
	5	Нормальні форми зображення булевих функцій.	2
	6	Мінімізація булевих функцій.	2
	7	Функціональна повнота наборів булевих функцій.	2
	8	Логіка та обчислення висловлень.	2	2
	9	Логіка та обчислення предикатів.	2
	10	Основні правила комбінаторики. Моделі комбінаторних	2
		конфігурацій.
	11	Урнові схеми вирішення комбінаторних задач	2
	12	Способи задання графів. Операції над графами.	4	2
	13	Зв'язність графів. Ейлерові та гамільтонові графи.	2
	14	Дерева. Алгоритми побудови остовного дерева.	2
	15	Відшукання найкоротших відстаней між вершинами	2
		графа (мережі)
	16	Задачі про максимальну течію і максимальний розріз у	4
		мережі.
		Загальна кількість	40	10

15

2.3 Розділи програми для самостійного вивчення

№					Назва теми							Кількість годин
												денна	заочна
1	Вивчення теоретичного матерiалу з використанням конспектiв i											22	82
	навчальної лiтератури.
2	Пiдготовка до практичних занять.											40	20
3	Підготовка до позааудиторної (домашньої) контрольної роботи											4	-
4	Підготовка до аудиторної контрольної роботи											2	-
5	ІДЗ (позааудиторна контрольна робота для заочної форми											-	20
	навчання)
6	Вивчення додаткових тем за літературними джерелами:
6.1	Історія	зародження,		розвитку		і	становлення			дискретної		0,5	3
	математики. Внесок вчених у її розвиток.
6.2	Алгебраїчні операції та їх властивості. Унарна, бінарна, n-арна
	операція. Способи записів операцій. Основні властивості											0,5	3
	операцій. Операції додавання та множення за модулем.
6.3	Поняття	алгебраїчної		структури Підструктура.							Морфізми
	(гомоморфізм, ізоморфізм). Найпростіші алгебраїчні структури.											1	3
	Кільці і поля. Гратки.
6.4	Логічні	схеми. Синтез			комбінаційних			схем. Перемикальні				0,5	3
	ланцюги; двох- і багатоступінчасті комбінаційні схеми.
6.5	Багатозначна		логіка.	Основні		поняття		і	функції		k-значної	0,5	3
	логіки.
6.6	Історія	розвитку		комбінаторіки.					Класичні		задачі
	комбінаторного аналізу. Сучасні задачі, які вирішуються											0,5	3
	комбінаторними методами.
6.7	Властивості		сполучень.		Біном		Ньютона.			Біноміальні		0,5	3
	коефіцієнти. Трикутник Паскаля. Поліноміальна теорема.
6.8	Метод рекурентних співвідношень. Числа Фібоначчі.											0,5	3
6.9	Основи теорії кодування. Алфавітне кодування. Кодування з
	мінімальною		надлишковістю.			Алгоритм			Фано.		Алгоритм	2	3
	Хаффмена. Завадостійке кодування. Стиснення даних.
	Криптографія.
6.10	Зародження теорії графів як математичної дисципліни. Типові											0,5	3
	задачі теорії графів.
6.11	Задача комівояжера. Приклади практичних задач, що зводяться											1	3
	до задачі комівояжера.
6.12	Алгоритми Флойда і Данцига пошуку найкоротших шляхів між											1	3
	всіма парами вершин графа
6.13	Елементи теорії формальних граматик. Задачі формалізації мов
	та перекладу. Задання мов за допомогою граматик. Типи											3	3
	граматик.
6.14	Елементи теорії скінченних автоматів.
	Загальна	характеристика			автоматів.		Розпізнавачі.				Скінченні	3	3
	автомати. Способи задання автоматів. Автомати Мілі і Мура.
	Автомати з магазинною пам’яттю. Машина Тьюринга.
	Загальна кількість											33	164

16

2.4 Навчально-методичні матеріали з дисципліни

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

1.Бондаренко, М. Ф. Комп’ютерна дискретна математика [Текст] : підручник / М. Ф. Бондаренко, Н. В. Білоус, А. Г. Руткас. – Харків: «Компанія СМІТ», 2004. – 480 с. (існує електронний варіант).

2.Капітонова, Ю. В. Основи дискретної математики [Текст] / Ю. В.

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

3. Тевяшев, А. Д. Основы дискретной математики в примерах и задачах [Текст] : учеб. пособие для вузов / А. Д. Тевяшев, И. Г. Гусарова. – Харьков:

ХНУРЭ, 2003. – 272 с.

4. Бардачов, Ю. М. Дискретна математика [Текст] : підручник / Ю.М.

Бардачов, Н.А. Соколова, В.Є. Ходаков; За ред. В.Є. Ходакова. – К.: Вища шк., 2002. – 287 с.

5.Шапорев, С. Д. Дискретная математика. Курс лекций и практических занятий [Текст] / С. Д. Шапорев – СПб.: БХВ-Петербург, 2006. – 400 с. (існує електронний варіант).

6.Кузнецов, О. П. Дискретная математика для инженера [Текст] / О. П.

Кузнецов, Г. М. Адельсон-Вельский. – М.: Энергоатомиздат, 1988. – 480 с.

7. Сигорский, В. П. Математический аппарат инженера [Текст] / В. П.

Сигорский. – Киев: Техніка, 1977. – 768 с. (існує електронний варіант).

8. Яблонский, С. В. Введение в дискретную математику [Текст] / С. В.

Яблонский. – М.: Наука, 1986. – 384 с.

9. Горбатов, В. А. Основы дискретной математики [Текст] / В. А.

Горбатов – М.: Высшая школа, 1986. – 312с.

10.Харари, Ф. Теория графов [Текст] / Ф. Харари. – М.: Мир, 1973. – 304 с.

11.Глускин, Л. М. Задачи и алгоритмы комбинаторики и теории графов [Текст] / Л. М. Глускин, В. Я. Шварц, Л. А. Шор. – Донецк: Изд-во ДПИ, 1982.

–110с.

12.Білоус, Н.В. Основи комбінаторного аналізу. [Текст] : навч. посібник /

Н.В. Білоус, З.В. Дудар, Н.С. Лєсна, І.Ю. Шубін. – Харків: ХТУРЕ, 1999. – 96 с. 13. Бондаренко, М. Ф. Збірник тестових завдань з дискретної математики

[Текст] / М. Ф. Бондаренко, Н. В. Білоус, І. Ю. Шубін. – Харків: ХТУРЕ, 2000. – 156 с. (існує електронний варіант).

17

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

14. Новиков, Ф. А. Дискретная математика для программистов [Текст] /

Ф. А. Новиков. – СПб: Питер, 2001. – 304 с. (існує електронний варіант).

15. Донской, В.И. Дискретная математика [Текст] / В. И. Донской. –

Симферополь: СОНАТ, 2000. – 360 с.

16. Андерсон, Дж. А. Дискретная математика и комбинаторика [Текст] /

Джеймс А. Андерсон. – М.: Издательский дом «Вильямс», 2003. – 960 с.

17.Виленкин, Н.Я. Комбинаторика [Текст] / Н. Я. Виленкин. – М.: Наука, 1969. – 328 с.

18.Белоус, Н.В. Тесты. Физика. Математическая логика [Текст] : Навч.

посібник / Н. В. Белоус, Е. Е. Гетьманова, З. В. Дударь, В. Ф. Захарченко, М. А. Красноголовец, Н. С. Лесная, В. В. Семенец, В. А. Стороженко, А. А.

Харьковская. – Харків: ХТУРЕ, 1998. – 152 с.

19. Капитонова, Ю. В. Лекции по дискретной математике [Текст] / Ю. В.

Капитонова, С. Л. Кривой, А. А. Летичевский, Г. М. Луцкий. – СПб.: БХВ-

Петербург, 2004. – 624 с.

2.4.3 Методичні вказівки до різних видів занять

20.Конспект лекцій з дисципліни «Дискретна математика» для студентів усіх форм навчання напряму 6.050101 Комп’ютерні науки [Електронне видання] / Упоряд.: Н.В. Васильцова, Л.Е. Чала Харків: ХНУРЕ, 2013. – 293 с.

21.Методичні вказівки до практичних робіт з дисципліни «Дискретна математика» (Частина 1) для студентів усіх форм навчання напряму 6.050101 – Комп’ютерні науки / Упоряд. Н. В. Васильцова, Л.Е. Чала – Харків: ХНУРЕ, 2012. – 68 с.

22.Матеріали з дистанційного навчання з дисципліни «Дискретна

математика» для студентів усіх форм навчання напряму 6.050101

Комп’ютерні науки [Електронне видання] / Упоряд.: Н.В. Васильцова, Л.Е.

Чала. Харків: ХНУРЕ, 2012.

23. Методичні вказівки до практичних занять і самостійної роботи з курсу «Основи дискретної математики» [Текст] / Упоряд. В.Ф. Захарченко, Е.О.

Дедіков. – Харків, ХТУРЕ, 2002. – 44 с.

18

3 ХАРАКТЕРИСТИКА ПІДРУЧНИКІВ І НАВЧАЛЬНИХ ПОСІБНИКІВ

Література (навчально-методичні матеріали), яку студенти можуть використовувати при вивченні дисципліни «Дискретна математика», складається з трьох частин: базової літератури [1-13]; допоміжної літератури

[14-19], методичних вказівок до різних видів занять і курсу дистанційного навчання [20-23].

Ця література включає відповіді на всі питання, як з теоретичної частини, так і з практичної частини курсу, які заплановані для вивчення згідно з робочою програмою дисципліни «Дискретна математика».

Допоміжна література [14-19] може використовуватися для уточнювання матеріалу або, за бажанням, для більш глибокого вивчення деяких теоретичних положень і практичних прикладів.

З базової літератури основною для вивчення матеріалу дисципліни є підручник [1] (Бондаренко, М.Ф. Комп’ютерна дискретна математика [Текст] :

підручник / М.Ф. Бондаренко, Н.В. Білоус, А.Г. Руткас. – Харків: «Компанія СМІТ», 2004. – 480 с.). Цей підручник рекомендовано Міністерством освіти і науки України як підручник для студентів вищих навчальних закладів, які навчаються за напрямом «Комп’ютерні науки».

У підручнику [1] викладено основні розділи дискретної математики – теорія множин, теорія відношень, математична логіка, алгебраїчні структури, автомати,

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

Наведено велику кількість вправ і задач для набуття практичного досвіду.

У літературі [2, 14, 19] викладаються методи і засоби дискретної математики як інструментарію при обробці інформації в комп’ютерах.

Книги [2, 19] складаються з декількох частин: математичні основи

(множини, відношення, комбінаторика, основні поняття загальної алгебри, елементи теорії алгоритмів і математичної логіки, елементи теорії графів);

математичні моделі (абстрактна теорія автоматів, теорія скінченних автоматів, моделі алгоритмів і програм, формальні граматики і формальні мови);

застосування (алгебри в комп’ютерних інформаційних технологіях, теорія автоматів і графів в комп’ютерних інформаційних технологіях, методи пошуку доведення теорем у логіці предикатів тощо). Основні математичні властивості теорій, які представлені в [2, 19], надаються разом з даними, які необхідні для розв’язання вправ.

19

Підручник [14] дозволяє використовувати основні положення дискретної математики у програмуванні. В ньому наведено: систематичне викладання основних розділів дискретної математики (множини і відношення, алгебраїчні структури, булеві функції, логічні обчислення, комбінаторика, кодування, графи); опис важливих алгоритмів над об’єктами дискретної математики;

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

В навчальному посібнику [3] викладено основні поняття теорії множин, математичної логіки, комбінаторики, теорії графів і теорії алгоритмів. Після кожного теоретичного розділу наведено приклади розв’язання аудиторних задач і задач для самостійного розв’язання. Цей навчальний посібник можна використовувати для самостійного вивчення основних розділів дисципліни «Дискретна математика».

Підручник [4] присвячений основам сучасної дискретної математики. Викладаються основні поняття і наукові результати теорії множин,

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

В[5], який є курсом лекцій і практичних занять, розглядаються питання трьох розділів, які вивчаються в курсі дискретної математики: теорії множин; комбінаторики і теорії графів. Викладаються основні теоретичні відомості і наведені багато численні приклади розв’язання задач за всіма розділами. Для теорії множин обговорена основна система аксіом, її модифікації і перспективи подальшого розвитку теорії на основі аксіоматичного метода. Розглядаються основні типи задач комбінаторики, які базуються на 4-х схемах вибору елементів множин. Наведені основні оптимізаційні алгоритми теорії графів, алгоритми мережного планування, які найчастіше використовуються на практиці. В [5] також надаються варіанти завдань для виконання контрольних і розрахунково-графічних робіт. Ці завдання можна використовувати для самостійної перевірки знань з дисципліни.

Влітературі [6, 7] викладаються практично важливі розділи апарата сучасної математики, які використовуються в інженерній практиці: множини, матриці, графи, логіка, ймовірності. Теоретичний матеріал ілюструється прикладами з різних областей техніки.

Влітературі [8, 9, 15] розглядаються питання основ дискретної математики, пов’язаних з теорією множин, логікою, комбінаторним аналізом.

Основам комбінаторного аналізу присвячена література [11, 12, 17].

20