|
Комп’ютерна
дискретна
|
||||
|
|
|
Ком’ ютерна дискретна математика: Підручник/ М.Ф. Бондаренко, Н.В. Білоус, А.Г. Руткас.-Харків: «Компанія СМІТ», 2004.-480с. ISBN 966-8530-20-9
|
|
|
|
|
||||
|
|
||||
|
Зміст Вступ...................................................…………………………………………3 Список позначень.........................................................………………………5 1. МНОЖИНИ……………………...................................................................9 1.1 Множини. Способи задання множин...............................................……9 1.2 Основні поняття теорії множин................................................…………14 1.3 Геометрична інтерпретація множин.............................................……18 1.4 Операції на множинах ………………………………………………....20 1.5 Алгебра множин ……………………………………………………… 22 1.6 Нескінченні множини …………………………………………………26 2. ВІДНОШЕННЯ …………………………………………………………... 30 2.1 Поняття відношення. Задання відносин …………………………….. 30 2.2 Операції над відношеннями…………………………………………... 37 2.3 Властивості бінарних відношень …………………………...................42 2.4 Відношення еквівалентності, порядку, толерантності ......................... 47 2.5 Функціональні відношення ………………………………………….. 54 2.6 Реляційна модель даних ……………………………………………… 61 3. АЛГЕБРАЇЧНІ СТРУКТУРИ …………………………………………… 73 3.1 Алгебраїчні операції та їх властивості ……………………………… 73 3.2 Поняття алгебраїчної структури …………………………………… 73 3.3 Найпростіші алгебраїчні структури ……………………………….… 80 3.4 Кільця і поля ……………………………………………………...… 90 3.5 Гратки ……………………………………………………………...… 93 4. БУЛЕВІ ФУНКЦІЇ ТА ПЕРЕТВОРЕННЯ …………………………… 99 4.1 Булеві змінні і функції ……………………………………………… 99 4.2 Способи задання мулевих функцій ……………………………… 102 4.2.1 Таблиці істинності ………………………………………………… 102 4.2.2 Номери мулевих функцій та інтерпретацій …………………….… 104 4.2.3 Булеві алгебри: загальна, двохелементна і логічна …………….… 106 4.2.4 Булеві формули та пріоритет операцій ………………………….… 107 4.2.5 Перехід від формули до таблиці істинності функції …………..… 109 4.3 Двоїстість ………………………………………………………..… 111 4.4 Закони мулевої алгебри …………………………………………… 115 4.5 Диз’юнктивні і кон’юнктивні розкладання мулевих функцій …… 120 4.6 Нормальні форми зображання мулевих функцій ……………….… 130 4.7 Алгебра Жегалкіна. Лінійні функції …………………………….… 138 4.7.1 Тотожності алгебри Жегалкіна ………………………………...… 138 4.7.2 Поліном Жегалкіна ……………………………………………..… 140 4.8 Повнота та замкненість…………………………………………......145 4.9 Функції, що зберігають нуль та одиницю. Монотонні функції ...... 147 4.10 Теореми Поста про повноту …………………………................... 151 4.11 Мінімізація булевих функцій ………………………….................. 155 4.11.1 Основні поняття …………………………………........................ 155 4.11.2. Мінімізація булевих функцій методом карт Карно (діаграм Вейча)..158 4.11.3. Мінімізація функцій методом Квайна - Мак-Класкі................. 165 4.11.4 Мінімізація функцій методом Порецького – Блейка .................. 174 4.12. Логічні схеми................................................. 177 5. МАТЕМАТИЧНА ЛОГІКА ……………………………..........................183 5.1. Історія і задачі математичної логіки ………………………............ 183 5.2. Поняття логіки висловлень ……………………………................... 185 5.3. Дедуктивні висновки у логіці висловлень ……………………........ 197 5.4. Обчислення висловлень ………………………………........................201 5.5. Логіка предикатів …………………………………..............................207 5.6. Квантори ………………………………………....................................212 5.7. Формули у логіці предикатів …………………………......................... 217 5.8. Закони і тотожності у логіці предикатів ……………………................220 5.9. Випереджені нормальні форми і логічний висновок у логіці предикатів..223 5.10. Обчислення предикатів……………………………......................... 227 5.11. Багатозначна логіка…………………………………........................230 6. ТЕОРІЯ ГРАФІВ…………………………………..................................239 6.1. Історичні зауваження. Типові задачі………………………............. 239 6.2. Неорієнтовані графи і термінологія………………………...............242 6.3. Ейлерові цикли…………………………………............................... 246 6.4. Абстрактні графи та геометричні реалізації. Орієнтовані графи …248 6.5. Матриця суміжності, ізоморфізмиі операції над графами ........... 253 6.6. Матриця інциденцій ………………………………......................... 257 6.7. Розфарбування …………………………………............................... 260 6.8. Дерева ………………………………………..................................... 269 6.9. Теорема Пуанкаре. Фундаментальні матриці перерізів і циклів ... 286 6.10. Найкоротші відстані та шляхи у мережах ………………………..292 6.11. Гамільтонові цикли і шляхи. Задача комівояжера ....................... 304 6.12. Течії у мережах ……………………………………...........................322 7. МОВИ ТА ГРАМАТИКИ ……………………………..........................338 7.1. Задача формалізації мов та перекладу ………………………….... 338 7.2. Перетворення рядків символів ………………………….............. 339 7.3. Задання мов за допомогою граматик …………………………... 341 7.4. Форма Бекуса — Наура ……………………………........................ 345 7.5. Типи граматик ………………………………….............................. 347 7.6. Регулярні вирази і мови ……………………………....................... 351 7.7. Дерева виводів. Стратегії виводів ………………………….......... 354 7.8. Побудова граматики мови програмування ……………………… 356 8. АЛГОРИТМИ …………………………………......................................360 8.1. Поняття алгоритму…………………………………............................360 8.2. Нормальні алгоритми Маркова …………………………................. 362 8.3. Алгоритми та рекурсивні функції …………………………...............365 8.5. Приклади побудови алгоритмів …………………………............... 369 8.6. Складність алгоритмів ……………………………......................... 374 8.7. Використання швидких алгоритмів …………………………....... 381 9. АВТОМАТИ ………………………………………...............................385 9.1. Загальна характеристика автоматів ………………………...............385 9.2. Розпізнавані …………………………………................................. 389 9.3. Скінченні автомати ……………………………….......................... 391 9.4. Автомати з магазинною пам'яттю ………………………….......... 399 9.5. Машина Тьюринга. Лінійно-обмежені автомати ……………… . 402 10. КОМБІНАТОРИКА …………………………….................................408 10.1. Передмова …………………………………….................................408 10.2. Первинні поняття комбінаторного аналізу………………….......413 10.3. Перестановки, розміщення, сполучення ……………………........418 10.4. Формула включень та виключень. Застосування …………... . . 426 10.5. Біноміальна та поліноміальна формули ……………………........431 10.6. Комбінаторні задачі і теорія чисел ………………………............432 10.7. Композиції та розбиття ……………………………......................438 10.8. Продуктивні функції ……………………………......................... 443 10.9. Асимптотичні оцінки та формули ………………………..............453 Післямова.....................................………………………………………. 464 Список літератури ………………………………….............................. 465 Предметний покажчик ……………………………….............................467
|
||||
|
Copyright® Grey 2006 |
||||
