- •Міністерство освіти і науки україни
- •Розділ 1 Основи теорії множин
- •§ 1.1. Основні поняття
- •§ 1.2. Операції із множинами
- •§ 1.3. Приклади розв'язування задач
- •Питання для самоконтролю
- •Задачі для самостійного розв'язування
- •Розділ 2 елементи теорії графів
- •§ 2.1. Основні поняття теорії графів
- •§ 2.2. Задача про найкоротший шлях у графі
- •Алгоритм пошуку найкоротшого шляху (алгоритм Дейкстри)
- •§ 2.3. Задача побудови мінімального кістякового дерева
- •§ 2.4. Задача про максимальний потік у графі
- •2.4.1. Алгоритм пошуку збільшувального ланцюга
- •2.4.2. Алгоритм пошуку максимального потоку (Форда й Фалкерсона)
- •Питання для самоконтролю
- •Задачі для самостійного розв'язування
- •Розділ 3 елементи математичної логіки й теорії автоматів
- •§ 3.1. Основні поняття
- •§ 3.2. Мінімізація логічних функцій
- •3.2.1. Метод Квайна
- •3.2.2. Метод Квайна – Мак-Класкі
- •3.2.3. Метод Вейча – Карно
- •§ 3.3. Мінімізація частково визначених двійкових функцій
- •§ 3.4. Пошук мінімальних кнф
- •§ 3.5. Синтез логічних (комбінаційних) схем
- •§ 3.6. Синтез скінченних автоматів
- •Питання для самоконтролю
- •Задачі для самостійного розв'язування
- •Основні позначення
- •Предметний покажчик
- •Список літератури
- •Дискретна математика у прикладах і задачах
- •49027, М. Дніпропетровськ, просп. К. Маркса,19.
Предметний покажчик
R
r-куб 61
а
алгоритм
Форда 22
А
Алгоритм
Дейкстри 21
пошуку найкоротшого шляху 21
Форда 22
а
асоціативність 53
в
вершини
суміжні 17
вершини графа 16
г
граф 16
неорієнтований 17
орієнтований 17
д
двійковий набір 50
дерево
орієнтоване найкоротших шляхів 21
джерело 34
Д
Диз'юнктивна нормальна форма 54
Диз'юнкція 52
Дистрибутивність 53
д
діаграма
Вейча-Карно 64
діаграми Ейлера. 5
добуток множин 8
довжина дуги 20
довжина шляху 21
Д
Доповнення множини 9
д
дуга 17
зворотня 36
пряма 36
е
елемент.
логічний 74
З
Задача
про максимальний потік 34
Закони
де Моргана 53
ідемпотентності 54
поглинання 54
Заперечення. 51
з
змінні
булеві 50
і
ізоморфізм 18
імпліканти
первинні 56
імпліцент 56
к
кардинальне число 6
код Грея 65
комутативність 53
К
Кон'юнктивна нормальна форма 54
к
контур 18
л
ланцюг
збільшуючий 36
Л
Ланцюг 17
м
максимальне збільшення потоку 36
макстерм 55
М
Матриця
інцинденцій для вершин графа 19
інцинденцій для ребер графа 19
суміжності 19
м
мінімізація логічних функцій 55
мінтерм 55
множина 5
контінуальна 7
лічильна 7
нескінченна 6
порожня 5, 86
скінченна 6
універсальна 5, 86
О
Об'єднання множин 7
о
одиниці потоку 34
орієнтоване дерево найкоротших шляхів. 21
П
Перетин множин 8
Петля 17
п
підмножина 5
покривне дерево
покривне 22
потужність множини 6
пропускна здатність 34
р
ребра графа 17
ребро
орієнтоване 17
Р
Різниця множин 10
с
стік 34
сума множин 7
т
таблиця істинності 50
у
умова сполученого сусідства 65
ф
факторизація 56
форма
досконала 55
мінімальна 56
тупикова 56
формула
логічна 52
функції
рівносильні 52
функціїї
булеві 50
ц
цикл 18
ш
шлях 18
найкоротший 21
Список літератури
Гилл А. Введение в теорию конечных автоматов [Текст] /А. Гилл. – М. : Наука, 1966. – 272 с.
Глушков В.М. Синтез цифровых автоматов [Текст] / В.М. Глушков. – М. : Физматгиз, 1962. – 476 с.
Закревский А.Д. Алгоритмы синтеза дискретных устройств [Текст] / А.Д. Закревский. – М. : Наука, 1971. – 511с.
Кузин Л.Т. Основы кибернетики. Т. 2. Основы кибернетических моделей [Текст] / Л.Т. Кузин. – М.: Энергия, 1979. – 584 с.
Лазарев В.Г. Проектирование дискретных устройств автоматики [Текст] / В.Г. Лазарев, Н.П. Маркин, Ю.В. Лазарев. – М. : Радио и связь, 1985. – 168 с.
Майника Э. Алгоритмы оптимизации на сетях и графах [Текст] / Э. Майника. – М. : Мир, 1981. – 323 с.
Мелихов А.Н. Ориентированные графы и конечные автоматы [Текст] / А.Н. Мелихов. – М. : Наука, 1971. – 415 с.
Подлипенский В.С. Бесконтактные логические схемы автоматики: основы построения [Текст] / В.С. Подлипенский. – К. : 1965. – 216 с.
Поспелов Д.А. Логические методы анализа и синтеза схем [Текст] / Д.А. Поспелов. – М. : Энергия, 1974. – 368 с.
Сигорский В.П. Математический аппарат инженера [Текст] / В.П. Сигорский. – К. : Техніка, 1977. – 768 с.
Трачик, В. Дискретные устройства автоматики [Текст] / В. Трачик. – М. : Энергия, 1978. – 445 с.
Филлипс Д., Методы анализа сетей [Текст] / Д. Филлипс, А. Гарсиа-Диас. – М. : Мир, 1984. – 496 с.
Форд Л.Р. Потоки в сетях [Текст] / Л.Р. Форд, Д. Фалкерсон. – М. : Мир, 1966. – 276 с.
Уилсон Р. Введение в теорию графов [Текст] / Р. Уилсон. – М. : Мир, 1977. – 208 с.
Шоломов Л.А. Основы теории дискретных логических и вычислительных машин [Текст] / Л.А. Шоломов. – М. : Физматгиз, 1980. – 362 с.
Навчальне видання
Ігор Валерійович Новицький
Світлана Альбертівна Ус