МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Белгородский государственный технологический университет им. В. Г. Шухова Ю. Д. Рязанов ДИСКРЕТНАЯ МАТЕМАТИКА Методические указания к выполнению лабораторных работ для студентов, обучающихся по направлениям подготовки 230100 «Информатика и вычислительная техника», 231000 «Программная инженерия» Белгород 2012 УДК 519.1 ББК 22.12 Р99 Составитель доц. Ю.Д. Рязанов «Дискретная математика»: Методические указания к выполнению лабораторных работ для студентов, обучающихся по направлениям подготовки 230100 «Информатика и вычислительная техника», 231000 «Программная инженерия» и специальности 230105 — Программное обеспечение вычислительной техники и автоматизированных систем / сост. Ю.Д. Рязанов. — Белгород: Изд-во БГТУ, 2012. — 36 с. В методических указаниях представлены задания к лабораторным работам, охватывающим весь курс дисциплины «Дискретная математика». Издание предназначено для студентов, обучающихся по направлениям подготовки 230100 «Информатика и вычислительная техника», 231000 «Программная инженерия» Методические указания публикуются в авторской редакции. УДК 519.1 ББК 22.12 3 ОГЛАВЛЕНИЕ 1. МНОЖЕСТВА Лабораторная работа № 1.1 Операции над множествами …………...…. 4 Лабораторная работа № 1.2 Нормальные формы Кантора ….………..… 7 Лабораторная работа № 1.3 Теоретико-множественные тождества ……………………….………..… 8 Лабораторная работа № 1.4 Теоретико-множественные уравнения ...........……………………..…… 10 Контрольные вопросы …………………………...……………..…….….. 14 2. КОМБИНАТОРНЫЕ ОБЪЕКТЫ Лабораторная работа № 2.1 Алгоритмы порождения комбинаторных объектов ………..…..….. 15 Лабораторная работа № 2.2 Задачи выбора ……...…………………..…. 16 Контрольные вопросы ………………………………..………..……….... 19 3. ОТНОШЕНИЯ Лабораторная работа № 3.1 Отношения и их свойства ……………….. 20 Лабораторная работа № 3.2 Транзитивное замыкание отношения ……………..…………...…..… 23 Лабораторная работа № 3.3 Фактормножества ……………............…… 24 Лабораторная работа № 3.4 Упорядоченные множества ….………...… 25 Контрольные вопросы .……………………………………..…….…….... 26 4. ГРАФЫ Лабораторная работа № 4.1 Маршруты ……..………...…………….….. 28 Лабораторная работа № 4.2 Циклы …………….……...…………….…. 44 Лабораторная работа № 4.3 Связность …………….……...……………. 45 Лабораторная работа № 4.4 Кратчайшие пути во взвешенном орграфе ………………….…...…...………. 46 Лабораторная работа № 4.5 Кратчайшие пути между каждой парой вершин во взвешенном орграфе …………………….…………….... 48 Контрольные вопросы ………………………………………..………….. 50 5. БУЛЕВЫ ФУНКЦИИ Лабораторная работа № 5.1 Полностью определенные булевы функции ……..…………….…….. 52 Лабораторная работа № 5.2 Частично определенные булевы функции ………………………………..… 52 Лабораторная работа № 5.3 Минимизация систем полностью определенных булевых функций ……….. 54 Лабораторная работа № 5.4 Вычисление систем булевых функций …………………………..………. 55 Контрольные вопросы ……………………………………….………….. 56 Библиографический список ………..………………………………..……… 58 4 1. МНОЖЕСТВА Л а б о р а т о р н а я р а б о т а № 1.1 Операции над множествами Цель занятия: изучить и научиться использовать алгебру подмножеств, изучить различные способы представления множеств в памяти ЭВМ, научиться программно реализовывать операции над множествами и выражения в алгебре подмножеств. Задания 1. Вычислить значение выражения (см. “Варианты заданий”, п. а). Решение изобразить с помощью кругов Эйлера. 2. Записать выражение в алгебре подмножеств, значение которого при заданных множествах А, В и С равно множеству D (см. “Варианты заданий”, п. б). 3. Программно реализовать операции над множествами, используя следующие способы представления множества в памяти ЭВМ: а) элементы множества А хранятся в массиве А. Элементы массива А неупорядочены; б) элементы множества А хранятся в массиве А. Элементы массива А упорядочены по возрастанию; в) элементы множества А хранятся в массиве А, элементы которого типа boolean. Если i  A, то Аi = true, иначе Ai = false. 4. Написать программы для вычисления значений выражений (см. “Задания”, п.1 и п.2). 5. Используя программы (см. “Задания”, п.4), вычислить значения выражений (см. “Задания”, п.1 и п.2). Варианты заданий Вариант 1. а) D = (B – A)  (A – (B  C))  (C – A) A = {1,2,3,4,5,6,7} B = {2,5,6,9,10} C = {4,7,8,11,12} б) A = {1,2,8} B = {6,7} C = {2,3,4,5,7} D = {3,4,5} Вариант 2. 5 а) б) D = B  (A  B)  (C – A) A = {2,5,6,7,9} B = {1,4,5,9} C = {3,7,8,10} A = {1,2,3,8} B = {3,6,7} C = {2,3,4,5,7} D = {1,3,4,5,6,8} Вариант 3. а) D = (A – (B  C))  ((B  C) – A) A = {1,2,4,5,8} B = {2,3,5,6,9} C = {4,5,6,7,9} б) A = {2,3,4,5,6} B = {1,2,4,9} C = {4,5,7,8} D = {3,6} Вариант 4. а) D = (A – (B  C))  ((B  C) – A) A = {1,2,3,4,6,7} B = {1,3,6,7} C = {3,4,5,6,8} б) A = {1,2,3,8} B = {3,6,7} C = {2,3,4,5,7} D = {1,3,6,8} Вариант 5. а) D = (A  C)  (B  C) A = {1,2,3,4,8} B = {2,3,8} C = {3,4,5,6,7} б) A = {1,2,3,4,6,7} B = {1,3,6,7} C = {3,4,5,6,8} D = {1,5,7,8} Вариант 6. а) D = (A  B) – (B  C)  (C – A) A = {2,3,4,5,6} B = {1,2,4,9} C = {4,5,7,8} б) A = {1,2,4,5,8} B = {2,3,5,6,9} C = {4,5,6,7,9} D = {2,4,6,9} Вариант 7. а) D = (A  B)  (A – C)  (B – C) A = {1,2,3,8} B = {3,5,6,7} C = {2,3,4,7} б) A = {1,2,3,4,5,6,7} B = {2,5,6,9,10} C = {4,7,8,11,12} D = {2,5,6,7,4} Вариант 8. а) D = ((A  B) – C)  (A  B) A = {1,2,3,8} B = {3,6,7} C = {2,3,4,5,7} б) A = {1,2,3,4,5,6,7} B = {2,5,6,9,10} C = {4,7,8,11,12} D = {1,3,8,9,10,11,12} Вариант 9. 6 а) б) D = ((A  B) – C)  (C – A) A = {1,2,3,4,5,6,7} B = {2,5,6,9,10} C = {4,7,8,11,12} A = {2,5,6,7,9} B = {1,4,5,9} C = {3,7,8,10} D = {1,3,4,8,10} Вариант 10. а) D = A  C – B  B  (A  C) A = {1,2,4,5,8} B = {2,3,5,6,9} C = {4,5,6,7,9} б) A = {1,2,3,4,6,7} B = {1,3,6,7} C = {3,4,5,6,8} D = {2,5,8} Вариант 11. а) D = (В – С)  (С – A) A = {1,2,3,4,6,7} B = {1,3,6,7} C = {3,4,5,6,8} б) A = {1,2,3,8} B = {3,5,6,7} C = {2,3,4,7} D = {1,3,5,6,8} Вариант 12. а) D = ((A - C)  B)  (C – A) A = {1,2,3,4,8} B = {2,3,8} C = {3,4,5,6,7} б) A = {2,3,4,5,6} B = {1,2,4,9} C = {4,5,7,8} D = {3,4,6,7,8} Вариант 13. а) D = A – (C  B) – (B  C) A = {2,3,4,5,6} B = {1,2,4,9} C = {4,5,7,8} б) A = {1,2,4,5,8} B = {2,3,5,6,9} C = {4,5,6,7,9} D = {1,3,5,7,8} Вариант 14. а) D = C – (A  B)  (A  B – C) A = {1,2,3,8} B = {3,6,7} C = {2,3,4,5,7} б) A = {1,2,3,4,8} B = {2,3,8} C = {3,4,5,6,7} D = {2,5,6,7,8} Вариант 15. а) D = C – (A  C  B  C) A = {1,2,8} B = {6,7} C = {2,3,4,5,7} б) A = {1,2,3,4,8} B = {2,3,8} C = {3,4,5,6,7} D = {3,5,6,7} 7 Л а б о р а т о р н а я р а б о т а № 1.2 Нормальные формы Кантора Цель занятия: изучить способы получения различных нормальных форм Кантора множества, заданного произвольным теоретико-множественным выражением. Задания 1. Представить множество, заданное исходным выражением (см. табл. 1), в нормальной форме Кантора. 2. Получить совершенную нормальную форму Кантора множества, заданного исходным выражением. 3. Получить сокращенную нормальную форму Кантора множества, заданного исходным выражением. 4. Получить тупиковые нормальные формы Кантора множества, заданного исходным выражением. Выбрать минимальную нормальную форму Кантора. Таблица 1 Варианты заданий Вариант 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Исходное выражение A  B  C( D  A)  C D D ∩ (D – C) ∪ A – B – C ∆ (B – A) ( AB  B(C  A)B)  D A ∪ C – B ∩ (D – C) ∆ (D – A) D  ( D  A)  C  B(C  A) C ∆ (D – A) ∪ B – C ∩ (B – A) – D A – (C ∆ A) ∪ B – D ∆ (C – B) (С  A) A  ( B  D)  B  C B ∪ A – C ∩ (D – A) ∆ (D ∪ A) ((C ∪ B) – D ∆ (C – B) ∆ A) ∩ A (C ∆ A) ∩ A ∪ D ∆ (C ∪ B) – B СA  ( AB)  D( B  C )B) (A ∆ (B ∪ C) ∪ D – B ∆ A) ∩ C (D ∪ C – B ∆ (B ∪ A) ∆ C) ∩ A A  ( BC )  D( B  A)C (B ∆ (A – C) ∪ D) – A ∩ (B – C) A  B  D(C  D)  BA (B ∆ (A – C) ∪ D) – A ∩ (B – C) 8 Л а б о р а т о р н а я р а б о т а № 1.3 Теоретико-множественные тождества Цель занятия: изучить методы доказательства теоретико-множественных тождеств. Задания 1. На рис.1 изображены круги Эйлера, соответствующие множествам А, В и С, с пронумерованными элементарными областями (не содержащими внутри себя других областей). Заштриховать элементарные области в соответствии с вариантом задания (см. табл.2). А 1 3 5 7 4 В 2 6 С Рис.1. Круги Эйлера, соответствующие множествам А, В и С с пронумерованными элементарными областями 2. Написать выражение 1 над множествами А, В и С, определяющее заштрихованную область, используя операции пересечения, объединения и дополнения. 3. Используя свойства операций над множествами, преобразовать выражение 1 в выражение 2, не содержащее операции дополнения множества. 4. Используя свойства операций над множествами, преобразовать выражение 2 в выражение 3, не содержащее операции объединения множеств. 9 5. Используя свойства операций над множествами, преобразовать выражение 3 в выражение 4, не содержащее операции пересечения множеств. 6. Доказать тождественность выражений 2 и 3 методом характеристических функций. 7. Доказать тождественность выражений 2 и 4 методом логических функций. Для автоматизации доказательства написать программу, которая получает и сравнивает таблицы истинности логических функций. 8. Доказать тождественность выражений 3 и 4 теоретико-множественным методом. Для автоматизации доказательства написать программу, в которой вычисляются и сравниваются значения выражений 3 и 4 при А = {1,3,5,7}, B = {2,3,6,7} и C = {4,5,6,7}. Таблица 2 Варианты заданий Вариант 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Номера областей 1, 2, 3 1, 2, 4 1, 2, 7 1, 3, 4 1, 3, 7 1, 4, 6 1, 5, 6 1, 5, 7 1, 6, 7 2, 3, 4 2, 3, 7 2, 4, 6 2, 5, 7 2, 6, 7 3, 4, 5 3, 4, 6 3, 5, 6 4, 5, 6 4, 5, 7 4, 6, 7 10 Л а б о р а т о р н а я работа № 1.4 Теоретико-множественные уравнения Цель занятия: научиться решать теоретико-множественные уравнения с применением ЭВМ. Задания 1. Преобразовать исходное уравнение (см. “Варианты заданий”) в уравнение с пустой правой частью. 2. Преобразовать левую часть уравнения к виду X    X  U , используя разложение Шеннона по неизвестному множеству X. 3. Написать программу, вычисляющую значения множеств  и U  при заданных исходных множествах. 4. Вычислить значения множеств  и U и сделать вывод о существовании решения уравнения. Если решения уравнения не существует, то выполнить п.п. 1—4 для следующего (предыдущего) варианта. 5. Определить мощность общего решения, найти некоторые (или все) частные решения, в том числе частные решения наименьшей и наибольшей мощности. 6. Написать программу для проверки найденных решений. Варианты заданий Вариант 1. AB  X  C  A  X B  X U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {3, 4, 5, 6, 8, 10} B = {1, 2, 7, 8, 9, 10} C = {1, 2, 3, 4, 5, 10} X—? Вариант 2. ( A  X )B  X  A  X (C  X ) U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {3, 7, 9, 10} B = {1, 3, 8, 9, 10} C = {2, 4, 5, 6, 7} X—? 11 Вариант 3. Вариант 4. A  ( B  (C  X ))  A  ( B  (C  X )) U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {1, 5, 7} B = {2, 4, 6, 10} C = {1, 3, 5, 6, 8, 10} X—? A  ( B  (C  X ))  B  (C  ( A  X )) U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {1, 5, 7} B = {2, 4, 6, 10} C = {1, 3, 5, 6, 8, 10} X—? Вариант 5. A  X  ( X  B)  X  B  C U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {2, 3, 4, 7, 10} B = {1, 2, 6, 9} C = {3, 5, 7, 9} X—? Вариант 6. A  ( X  B)  (C  X )  ( X  A)  ( X  B)  C U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {4, 8, 9} B = {1, 2, 4, 6, 8, 9} C = {4, 5, 7, 9} X—? Вариант 7. ( X  A)  ( X  B)  C  A  X (C  X ) U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {2, 9, 10} B = {1, 2, 8, 9, 10} C = {1, 3, 6, 7} X—? 12 Вариант 8. X  A X  B  C  X  A B U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {3, 4, 5, 6, 10} B = {1, 2, 3, 7, 9} C = {3, 4, 5, 8, 10} X—? Вариант 9. ( AX )  ( B  X )  C  A  X  (CX ) U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {1, 3, 5, 6, 8} B = {2, 4, 6, 9} C = {2, 6, 7, 10} X—? Вариант 10. A  ( B  X )C  A  ( B  X )C  X U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {4, 5, 7, 8, 9, 10} B = {2, 3, 4, 5, 6, 10} C = {4, 5, 7, 8, 10} X—? Вариант 11. B  ( X  C )A  ( A  X )B  X U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {1, 3, 6, 7, 8, 10} B = {1, 3, 4, 5, 9} C = {1, 3, 6, 7, 10} X—? Вариант 12. A  B  C  X  A  B  (C  X ) U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {1, 4, 10} B = {3, 5, 6, 7} C = {3, 6, 7, 10} X—? 13 Вариант 13. A  B  X X  C  A  B  (C  X ) U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {2, 3, 9, 10} B = {1, 5, 8} C = {4, 5, 7} X—? Вариант 14. ( A  X )B  X  C  C  X ( A  X ) U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {1, 4, 8} B = {1, 5, 7, 10} C = {3, 6, 7, 10} X—? Вариант 15. ( A  X  B)  (C  X )  X  ( A  X )  C U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {1, 2, 5, 8, 9} B = {1, 2, 6, 7, 9, 10} C = {2, 4, 6, 9, 10} X—? Вариант 16. B  X  CA  B  X( A  X ) U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {1, 3, 6, 7, 8, 10} B = {1, 3, 4, 5, 9} C = {1, 3, 6, 7, 10} X—? Вариант 17. (C  X ) A  X  ( A  X )B  X U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {3, 7, 9, 10} B = {1, 3, 8, 9, 10} C = {2, 4, 5, 6, 7} X—? 14 Контрольные вопросы 1. Дать определение понятиям: — множество, элемент множества; — конечное множество, мощность множества; — бесконечное, счетное и несчетное множество; — пустое множество, универсум; — подмножество, собственное подмножество; — булеан, операции над множествами, алгебра подмножеств. 2. Привести примеры задания множества различными способами. 3. Проиллюстрировать операции над множествами и свойства операций диаграммами Эйлера. 4. Вычислить значение выражения в алгебре подмножеств. 5. Определить количество подмножеств заданного множества. 6. Дать определение понятиям: — первичный терм; — элементарное пересечение; — нормальная форма кантора; — конституента; — совершенная НФК; — простая импликанта; — сокращенная, тупиковая и минимальная НФК. 7. Как получить сокращенную НФК? 8. Что такое импликантная матрица Квайна? Для чего она используется? 9. Доказать теоретико-множественное тождество различными методами. 10. Дать определение теоретико-множественному уравнению. 11. Что такое частное и общее решение теоретико-множественного уравнения? 12. Что является условием существования решения теоретикомножественного уравнения? 13. Как определить мощность общего решение теоретико-множественного уравнения? 14. Сравнить способы представления множества в памяти ЭВМ (объем памяти, время выполнения операций). 15. Программно реализовать заданную операцию над множествами при заданном способе представления множества в памяти ЭВМ. 16. Изменить алгоритмы 1.19 и 1.20, используя логические операции вместо операций сравнения. 15 2. КОМБИНАТОРНЫЕ ОБЪЕКТЫ Л а б о р а т о р н а я р а б о т а № 2.1 Алгоритмы порождения комбинаторных объектов Цель занятия: изучить основные комбинаторные объекты, алгоритмы их порождения, программно реализовать и оценить временную сложность алгоритмов. Задания 1. Реализовать алгоритм порождения подмножеств. 2. Построить график зависимости количества всех подмножеств от мощности множества. 3. Построить графики зависимости времени выполнения алгоритмов п.1 на вашей ЭВМ от мощности множества. 4. Определить максимальную мощность множества, для которого можно получить все подмножества не более чем за час, сутки, месяц, год на вашей ЭВМ. 5. Определить максимальную мощность множества, для которого можно получить все подмножества не более чем за час, сутки, месяц, год на ЭВМ, в 10 и в 100 раз быстрее вашей. 6. Реализовать алгоритм порождения сочетаний. 7. Построить графики зависимости количества всех сочетаний из n по k от k при n = (5, 7, 9). 8. Реализовать алгоритм порождения перестановок. 9. Построить график зависимости количества всех перестановок от мощности множества. 10. Построить графики зависимости времени выполнения алгоритма п.8 на вашей ЭВМ от мощности множества. 11. Определить максимальную мощность множества, для которого можно получить все перестановки не более чем за час, сутки, месяц, год на вашей ЭВМ. 12. Определить максимальную мощность множества, для которого можно получить все перестановки не более чем за час, сутки, месяц, год на ЭВМ, в 10 и в 100 раз быстрее вашей. 13. Реализовать алгоритм порождения размещений. 14. Построить графики зависимости количества всех размещений из n по k от k при n = (5, 7, 9). 16 Л а б о р а т о р н а я р а б о т а № 2.2 Задачи выбора Цель занятия: приобрести практические навыки в использовании алгоритмов порождения комбинаторных объектов при проектировании алгоритмов решения задач выбора. Задания 1. Ознакомиться с задачей (см. варианты заданий). 2. Определить класс комбинаторных объектов, содержащих решение задачи (траекторию задачи). 3. Определить, что в задаче является функционалом и способ его вычисления. 4. Определить способ распознавания решения по значению функционала. 5. Реализовать алгоритм решения задачи. 6. Подготовить тестовые данные и решить задачу. Варианты заданий 1. Имеется конечное множество исполнителей {х1,...,хn}, каждый из которых может выполнять некоторые из работ {у1,...,уn}. Для каждого исполнителя задано множество работ, которые он может выполнять. Нужно распределить исполнителей по работам, т.е. назначить по одному исполнителю на каждую работу, так, чтобы выполнить все работы. Найти все возможные распределения исполнителей по работам. 2. Числа из заданного девятиэлементного множества разместить в “числовом колесе” (рис.2) так, чтобы одно число было в центре колеса, остальные — у концов каждого диаметра, и чтобы суммы чисел каждого ряда были бы одинаковыми. Рис.2. Числовое колесо 17 3. Определить, существуют ли решения в заданном k-элементном множестве X целых чисел следующего уравнения: a1x1+ a2x2+ …+ anxn = b, n, b и a1,a2,…,an — заданы, xi  X. 4. На прямой расположены n равноотстоящих друг от друга узлов. Можно ли в узлах разместить n предметов из n-элементного множества так, чтобы центр тяжести находился в одном из узлов. Вес каждого предмета задан. 5. Задана точка с натуральными координатами (x,y) на целочисленной решетке. Найти “монотонную” траекторию минимальной стоимости, ведущую из начала координат в заданную точку. На каждом шаге “монотонной” траектории можно двигаться только вправо или вверх к соседней точке. Стоимость возможных шагов из каждой точки решетки задана. 6. Есть n станков. Каждый из станков делает различные операции (какие заданы). При обработке детали необходимо выполнить k заданных операций. Найти минимальное множество станков, требуемых для обработки детали. 7. Заданы n2 попарно различных целых чисел. Разместить их, если можно, в матрице n  n так, чтобы суммы строк, столбцов и диагоналей были одинаковыми. Определить количество таких размещений. 8. Найти все решения уравнения x1 + x2 + … + xn = b в натуральных числах, n и b — заданы. 9. Имеется n исполнителей, каждый из которых может выполнять некоторые из n работ. Для каждого исполнителя задано множество работ, которые он может выполнять, и стоимость выполнения каждой работы. Нужно распределить исполнителей по работам, т.е. назначить по одному исполнителю на каждую работу, так, чтобы выполнить все работы, минимизируя затраты. 10. Задана точка в узле целочисленной решетке размером n  n. Расположить всеми возможными способами k точек в узлах решетки так, чтобы расстояние от каждой до заданной было одинаковым. 11. Необходимо перевести n тонн груза. Имеется k самолетов грузоподъемностью s1, s2, …, sk тонн, s1 + s2 + … + sk > n. Стоимость рейса c1, c2, …, ck руб. не зависит от массы груза, перевозимого самолетом. Найти оптимальное множество самолетов для перевозки груза. 12. Задано множество предметов. Для каждого предмета известен его вес. Можно ли разделить предметы на две равные по весу части. 13. В матрице n  m целых чисел встречаются нули. Можно ли перестановкой строк добиться того, чтобы нули в каждом столбце занимали только самые нижние позиции? Получить все такие матрицы. 18 14. Имеется n различных предметов. Известны масса каждого предмета и его стоимость. Определить, какие предметы надо положить в рюкзак, чтобы масса не превышала заданной, а общая стоимость была максимальна. 15. Каждая из n деталей последовательно обрабатывается на m станках (сначала на 1-м, затем на 2-м и т.д.). Для каждой детали известно время обработки на каждом станке. Определить, в какой последовательности необходимо обрабатывать детали, чтобы время обработки всех деталей было минимальным. 16. Найти все решения в (0,1)-числах следующего неравенства: a1x1 + a2x2 + …+ anxn  an+1xn+1 + an+2xn+2 + …+ amxm, n, m и a1, a2,…, am — заданы. 17. Задана целочисленная матрица размером n  m. Выбрать минимальное количество строк матрицы, таких, что сумма элементов каждого столбца была бы больше заданного числа. 18. Имеется n станков и n деталей. Каждую деталь можно обработать на любом станке, но время обработки детали на одном станке может отличаться от времени ее обработки на другом. Нужно разместить детали по станкам так, чтобы суммарное время работы было наименьшим. 19. Заданы множества A и B, причем B = {x | x  A}. Подмножество множества B называется покрытием множества A, если объединение всех его элементов равно множеству А. Найти все минимальные по мощности покрытия множества А, составленные из элементов множества B. 20. Необходимо перевести n тонн груза. Имеется k самолетов грузоподъемностью s1, s2,…, sk тонн, k  s  n . Стоимость перевозки самолеi i 1 тами тонны груза составляет c1, c2,…, ck руб. Найти оптимальное множество самолетов для перевозки груза. 19 Контрольные вопросы 1.Что называется комбинаторным объектом? 2. В чем заключается правило произведения? Для чего, когда и как его применять? 3. В чем заключается метод поиска с возвращением? Изобразите общий рекурсивный алгоритм поиска с возвращением в виде блоксхемы. 4. Докажите теорему о количестве подмножеств n-элементного множества. 5. Опишите алгоритм порождения подмножеств. Можете ли вы предложить другие алгоритмы порождения подмножеств? 6. Дайте определение перестановки. Докажите теорему о количестве перестановок n-элементного множества. Опишите алгоритм порождения перестановок. 7. Дайте определение размещению. Докажите теорему о количестве размещений n-элементного множества по k местам. Опишите алгоритм порождения размещений. 8. Дайте определение размещению с повторениями. Докажите теорему о количестве размещений с повторениями n-элементного множества по k местам. Опишите алгоритм порождения размещений с повторениями. 9. Дайте определение сочетанию. Докажите теорему о количестве сочетаний из n по k. Опишите алгоритм порождения сочетаний. 10. Предложите алгоритм порождения подмножеств в порядке увеличения (уменьшения) мощности. 11. Дайте определение мультимножеству, мощности мультимножества, кратности элемента. 12. Дайте определение перестановки с повторениями. Докажите теорему о количестве перестановок с повторениями. Опишите алгоритм порождения перестановок с повторениями. 13. Дайте определение сочетания с повторениями. Докажите теорему о количестве сочетаний с повторениями из n элементов по k. Опишите алгоритм порождения сочетаний с повторениями. 14. Какие задачи относятся к задачам выбора? 15. Что называют траекториями задачи выбора? 16. Что называют функционалом траектории, зачем он нужен? 17. В чем заключается проектирование алгоритма решения задачи выбора с использованием алгоритмов порождения комбинаторных объектов? 18. Как преобразовать алгоритм порождения комбинаторных объектов в алгоритм решения задачи выбора? 20 3. ОТНОШЕНИЯ Л а б о р а т о р н а я р а б о т а № 3.1 Отношения и их свойства Цель занятия: изучить способы задания отношений, операции над от ношениями и свойства отношений, научиться программно реализовывать операции и определять свойства отношений. Задания Часть 1. Операции над отношениями 1.1. Представить отношения (см.”Варианты заданий”, п.а) графиком, графом и матрицей. 1.2. Вычислить значение выражения (см.”Варианты заданий”, п.б) при заданных отношениях (см.”Варианты заданий”, п.а). 1.3. Написать программы, формирующие матрицы заданных отношений (см.”Варианты заданий”, п.а). 1.4. Программно реализовать операции над отношениями. 1.5. Написать программу, вычисляющую значение выражения (см. “Варианты заданий”, п.б) и вычислить его при заданных отношениях (см.”Варианты заданий”, п.а). Часть 2. Свойства отношений 2.1. Определить основные свойства отношений (см. ”Варианты заданий”, п.а). 2.2. Определить, являются ли заданные отношения отношениями толерантности, эквивалентности и порядка. 2.3. Написать программу, определяющую свойства отношения, в том числе толерантности, эквивалентности и порядка, и определить свойства отношений (см. ”Варианты заданий”, п.а). Варианты заданий Вариант 1 а) А = {(x,y) | x  N и y  N и x < 11 и y < 11 и (x и y четные)} B = {(x,y) | x  N и y  N и x < 11 и y < 11 и |x– y| < 5} C = {(x,y) | x  N и y  N и x < 11 и y < 11 и y2 кратно x} б) D = (A  B)-1  C  A2 21 Вариант 2 а) А = {(x,y) | x  N и y  N и x < 11 и y < 11 и x — четно и y > x} B = {(x,y) | x  N и y  N и x < 11 и y < 11 и (x – y = 1 или x + y = 11} C = {(x,y) | x  N и y  N и x < 11 и y < 11 и (x,y)  {2,5,8,9,10}  {1,3,5,10}} -1 б) D = А  B  A – C Вариант 3 а) А = {(x,y) | x  N и y  N и x < 11 и y < 11 и (x > y или y > 7)} B = {(x,y) | x  N и y  N и x < 11 и y < 11 и 10x + y кратно 3} C = {(x,y) | x  N и y  N и x < 11 и y < 11 и x — четно и y — нечетно} б) D = A  B  C2  A Вариант 4 а) А = {(x,y) | x  N и y  N и x < 11 и y < 11 и x — четно и x + y < 10} B = {(x,y) | x  N и y  N и x < 11 и y < 11 и x + 2y < 20} C = {(x,y) | x  N и y  N и x < 11 и y < 11 и (x > 7 или y кратно 3)} б) D = (A – B)-1  C  A Вариант 5 а) А= {(x,y) | x  N и y  N и x < 11 и y < 11 и x + y — четно} B = {(x,y) | x  N и y  N и x < 11 и y < 11 и |x – y| > 5} C = {(x,y) | x  N и y  N и x < 11 и y < 11 и если x — четно, то y < x, иначе y > x} б) D=A  B – A  B  C-1 Вариант 6 а) А = {(x,y) | x  N и y  N и x < 11 и y < 11 и x + y — четно и x+y > 8} B = {(x,y) | x  N и y  N и x < 11 и y < 11 и x + 2y > 20} C = {(x,y) | x  N и y  N и x < 11 и y < 11 и (x,y)  {1,2,4,8}  {3,5,7,10}} б) D = A  B-1  A  C  B Вариант 7 а) А = {(x,y) | x  N и y  N и x < 11 и y < 11 и x + y кратно трем} B = {(x,y) | x  N и y  N и x < 11 и y < 11 и (2 < x < 8 или 2 < y < 8)} C = {(x,y) | x  N и y  N и x < 11 и y < 11 и x2 + y2 < 100} б) D = A2 – B  A-1  C Вариант 8 а) А = {(x,y) | x  N и y  N и x < 11 и y < 11 и (y > x + 5 или x > y + 5} B = {(x,y) | x  N и y  N и x < 11 и y < 11 и (x и y четные)} 22 C = {(x,y) | x  N и y  N и x < 11 и y < 11 и |x – y| > 5} б) D = A  B-1  A – C Вариант 9 а) А = {(x,y) | x  N и y  N и x < 11 и y < 11 и y< x + 1 и x  2y} B = {(x,y) | x  N и y  N и x < 11 и y < 11 и x — четно и x + y < 10} C = {(x,y) | x  N и y  N и x < 11 и y < 11 и (x,y)  {2,3,8}  {1,4,5,8}} б) D = A  A-1  B  C Вариант 10 а) А = {(x,y) | x  N и y  N и x < 11 и y < 11 и (x < y < (9 – x) или (9 - x) < y < x)} B = {(x,y) | x  N и y  N и x < 11 и y < 11 и x — четно и y — нечетно} C = {(x,y) | x  N и y  N и x < 11 и y < 11 и xy кратно трем} б) D = A  B2 – C  C-1 Вариант 11 а) А = {(x,y) | x  N и y  N и x < 11 и y < 11 и (y > x + 3 или y < x – 3)} B = {(x,y) | x  N и y  N и x < 11 и y < 11 и если x < 9, то y кратно 3} С = {(x,y) | x  N и y  N и x < 11 и y < 11 и x + 3y > 25} б) D = A  A-1  B  C Вариант 12 а) А = {(x,y) | x  N и y  N и x < 11 и y < 11 и x + y кратно x} B = {(x,y) | x  N и y  N и x < 11 и y < 11 и (x,y)  {2,4,6,8}{1,7,9}} C = {(x,y) | x  N и y  N и x < 11 и y < 11 и x+y — четно и xy < 20} б) D = A  B  C – A-1  C Вариант 13 а) A = {(x,y) | x  N и y  N и x < 11 и y < 11 и если x — четно, то y < x, иначе y > x} B = {(x,y) | x  N и y  N и x < 11 и y < 11 и (y < 7 или x кратно 3)} C = {(x,y) | x  N и y  N и x < 11 и y < 11 и (x2 + y2 > 100 или x = y)} б) D = A  B  C2 – B-1 Вариант 14 а) А = {(x,y) | x  N и y  N и x < 11 и y < 11 и (y – x > 5 или x – y > 5} B = {(x,y) | x  N и y  N и x < 11 и y < 11 и 10x + 2y + 1 кратно 3} C = {(x,y) | x  N и y  N и x < 11 и y < 11 и ((x + 3) < y < (11 – x) или (9 – x) < y < (x + 1))} б) D = (A  B)  ( A – C)-1 23 Л а б о р а т о р н а я р а б о т а № 3.2 Транзитивное замыкание отношения Цель занятия: изучить и выполнить сравнительный анализ алгоритмов вычисления транзитивного замыкания отношения. Задания 1. Изучить и программно реализовать алгоритмы объединения степеней и Уоршалла для вычисления транзитивного замыкания отношения. 2. Разработать и программно реализовать генератор отношений на множестве мощности N и содержащих заданное число пар. 3. Разработать и написать программу, которая генерирует 1000 отношений на множестве мощности N с заданным числом пар, для каждого отношения вычисляет транзитивное замыкание двумя алгоритмами и определяет время выполнения каждого алгоритма. Время вычисления транзитивного замыкания различных отношений на множестве мощности N с заданным числом пар может быть разным, поэтому программа так же должна определять минимальное и максимальное время вычисления транзитивного замыкания сгенерированных отношений. Выполнить программу при N = 50, 100 и 150. Результат для каждого N представить в виде таблицы (табл. 3). Таблица 3 Время выполнения алгоритмов Число пар в отноше1 N2/4 N2/2 N2 N22/3 нии min max min max min max min max min max Алгоритм объединения степеней Алгоритм Уоршалла Примечание. В случае невозможности определения времени выполнения алгоритмов, рекомендуется изменить количество генерируемых отношений и их мощности. 24 Л а б о р а т о р н а я р а б о т а № 3.3 Фактормножества Цель занятия: научиться программно формировать фактормножество для заданного отношения эквивалентности. Задания 1. Отношение (табл. 4) представить графом и характеристической функцией в матричной форме. Найти разбиение Ф, определяемое заданным отношением эквивалентности. 2. Написать программу, которая формирует разбиение, определяемое заданным отношением эквивалентности. Таблица 4 Варианты заданий Вариант 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Отношение А={(x,y) | xN и yN и x<11 и y<11 и ((x и y четные) или x=y)} А={(x,y) | xN и yN и x<11 и y<11 и ((x и y четные) или (x и y нечетные))} A={(x,y) | xN и yN и x<11 и y<11 и (|x-y| кратно 5 или x=y)} А={(x,y) | xN и yN и x<11 и y<11 и (x+y — нечетно или x=y)} А={(x,y) | xN и yN и x<11 и y<11 и x+y — четно} А={(x,y) | xN и yN и x<11 и y<11 и (x+y кратно 3 или x=y)} А={(x,y) | xN и yN и x<11 и y<11 и (|x–y| кратно 3 или x=y)} А={(x,y) | xN и yN и x<11 и y<11 и (x и y меньше 3 или x и y больше 3 или x=y)} А={(x,y) | xN и yN и x<11 и y<11 и (|x–y| кратно 4 или x=y)} А={(x,y) | xN и yN и x<11 и y<11 и (x и y кратно 3 или x и y кратно 5 или x=y)} А={(x,y) | xN и yN и x<11 и y<11 и (x и y четно и меньше 5 или x и y нечетно и больше 5 или x=y)} А={(x,y) | xN и yN и x<11 и y<11 и (x и y четно и меньше 7 или x=y)} А={(x,y) | xN и yN и x<11 и y<11 и ((x,y){1,2,3}2 или (x,y){6,7,8,9}2 или x=y)} А={(x,y) | xN и yN и x<11 и y<11 и ((x,y){1,2,5}2 или (x,y){3,7,8,9}2 или x=y)} А={(x,y) | (x,y){1,3,10}2 или (x,y){2,7,8,9}2 или (x,y){4,5,6}2} 25 Л а б о р а т о р н а я р а б о т а № 3.4 Упорядоченные множества Цель занятия: изучить упорядоченные множества, алгоритм топологической сортировки, научиться представлять множества диаграммами Хассе, находить минимальные (максимальные) и наименьшие (наибольшие) элементы упорядоченного множества. Задания Даны множества точек на плоскости М1 (рис. 3), М2 (рис. 4) и отношение порядка (табл. 5). Для определения отношения на множестве точек примем следующие обозначения: ax — абсцисса точки a; ay — ордината a. На рис. 3 координаты правой верхней точки считать (1,1). На рис. 4 координаты самой верхней точки считать (0,2), а координаты самой правой точки считать (2,0). 1. Написать программы, формирующие матрицы отношений в соответствии с вариантом задания (табл. 5), на множествах М1 и М2. 2. Написать программы, формирующие матрицы отношения доминирования по матрицам отношения порядка. 3. Написать программу, реализующую алгоритм топологической сортировки по матрице отношения доминирования. 4. Изобразить диаграмму Хассе отношения доминирования на множествах М1 и М2. 5. Найти минимальные и максимальные элементы множеств М1 и М2. 6. Найти, если существуют, наименьший и наибольший элементы множеств М1 и М2. Y Y X Рис. 3. Множество М1 X Рис. 4. Множество М2 26 Таблица 5 Варианты заданий Вариант 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Отношение А={(a,b) | ax ≤ bx и ay ≤ by } А={(a,b) | ax ≤ by и bx = ay } A={(a,b) | ax ≤ bx } А={(a,b) | ax – ay ≤ bx – by } А={(a,b) | ax ≤ bx и ay < by } А={(a,b) | ax – bx ≤ ay – by } А={(a,b) | ay ≤ by } А={(a,b) | ax2 + ay2 < bx2 + by2 } А={(a,b) | ax < bx и ay ≤ by } А={(a,b) | ax – bx ≤ by – ay } А={(a,b) | ax ≤ by } А={(a,b) | ax ≤ ay и bx ≤ by } А={(a,b) | ax < bx и ay < by } А={(a,b) | ax + ay < bx + by } А={(a,b) | ax = by и bx ≤ ay } Контрольные вопросы 1. Что называется упорядоченной парой? Чем различаются упорядоченная пара и двухэлементное множество? Какое отличие в обозначениях упорядоченной пары и двухэлементного множества? 2. Что является прямым (декартовым) произведением множеств? 3. Определите мощность прямого (декартова) произведения двух заданных конечных множеств. 4. Что называется бинарным соответствием? 5. Что является областью отправления и областью определения бинарного соответствия? Что является областью прибытия и областью значений бинарного соответствия? 6. Определите область отправления, область определения, область прибытия и область значений заданного бинарного соответствия. 7. Что называется образом и прообразом элемента при бинарном соответствии? 8. Определите образ каждого элемента из области определения заданного соответствия. Определите прообраз каждого элемента из области прибытия заданного соответствия. 9. Какое бинарное соответствие называется функциональным? 27 10. Какое соответствие называется полностью определенным? Что называется отображением? 11. Какая функция называется сюръективной, а какая — инъективной? 12. Что называется взаимно-однозначным отображением? 13. Что называется бинарным отношением? 14. Какое бинарное отношение называется пустым, тождественным, универсальным? 15. Приведите примеры задания отношений различными способами. 16. Определите, принадлежит ли заданная упорядоченная пара композиции заданных отношений. Назовите упорядоченную пару, принадлежащую композиции заданных отношений и упорядоченную пару, не принадлежащую композиции этих отношений. 17. Дайте определения основным и производным свойствам отношений. Определите свойства заданного отношения. 18. Что называется замыканием отношения относительно заданного свойства? 19. Получите транзитивное замыкание отношения, заданного графом. 20. Что называется классом эквивалентности и фактормножеством? 21. Постройте отношение эквивалентности, определяемое заданным разбиением. 22. Что называется упорядоченным множеством? 23. Какие элементы упорядоченного множества называются сравнимыми, а какие — несравнимыми? 24. Какое множество называется линейно упорядоченным? 25. Постройте отношение строгого порядка, ассоциированного с заданным отношением порядка. Используйте матричное и графовое представление отношений. 26. Постройте отношение доминирования, ассоциированного с заданным отношением порядка. Используйте матричное и графовое представление отношений. 27. Что представляет собой транзитивное замыкание отношения доминирования, ассоциированного с заданным отношением порядка. 28. Определите основные свойства отношения доминирования. 29. Является ли отношение доминирования отношением порядка? 30. Что такое диаграмма Хассе? 31. Что такое топологическая сортировка? Примените алгоритм топологической сортировки к отношению, граф которого имеет циклы. 28 4. ГРАФЫ Л а б о р а т о р н а я р а б о т а № 4.1 Маршруты Цель занятия: изучить основные понятия теории графов, способы задания графов, научиться программно реализовывать алгоритмы получения и анализа маршрутов в графах. Задания 1. Представить графы G1 и G2 (см.”Варианты заданий”, п.а) матрицей смежности, матрицей инцидентности, диаграммой. 2. Определить, являются ли последовательности вершин (см. ”Варианты заданий”, п.б) маршрутом, цепью, простой цепью, циклом, простым циклом в графах G1 и G2 (см.”Варианты заданий”, п.а). 3. Написать программу, определяющую, является ли заданная последовательность вершин (см. ”Варианты заданий”, п.б) маршрутом, цепью, простой цепью, циклом, простым циклом в графах G1 и G2 (см.”Варианты заданий”, п.а). 4. Написать программу, получающую все маршруты заданной длины, выходящие из заданной вершины. Использовать программу для получения всех маршрутов заданной длины в графах G1 и G2 (см.”Варианты заданий”, п.а). 5. Написать программу, определяющую количество маршрутов заданной длины между каждой парой вершин графа. Использовать программу для определения количества маршрутов заданной длины между каждой парой вершин в графах G1 и G2 (см.”Варианты заданий”, п.а). 6. Написать программу, определяющую все маршруты заданной длины между заданной парой вершин графа. Использовать программу для определения всех маршрутов заданной длины между заданной парой вершин в графах G1 и G2 (см.”Варианты заданий”, п.а). 7. Написать программу, получающую все простые максимальные цепи, выходящие из заданной вершины графа. Использовать программу для получения всех простые максимальных цепей, выходящих из заданной вершины в графах G1 и G2 (см.”Варианты заданий”, п.а). 29 Варианты заданий Вариант 1 а) диаграмма графа G1 1 2 7 6 матрица смежности графа G2 0  1 0  1 0  1 1  б) 1 0 1 1 0 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1  0 0  0 0  1 0  последовательности вершин 1. 2. 3. 4. 5. 3 (2, 1, 7, 6, 3, 5) (7, 6, 3, 5, 6, 2, 1) (6, 5, 4, 3, 6) (7, 6, 5, 3, 6, 5) (3, 6, 7, 1 ,6 , 5, 3) 4 5 30 Вариант 2 а) 0  1 0  1 1  1  1 матрица смежности графа G1 1 0 1 0 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 1  0 0  0 0  1  0 диаграмма графа G2 2 1 3 6 7 б) последовательности вершин 1. 2. 3. 4. 5. (6, 2, 1, 7) (1, 2, 6, 5, 3, 6, 2) (1, 2, 6, 7, 1) (6, 7, 1, 2, 5, 1, 6) (1, 2, 6, 7, 2, 6, 3) 4 5 31 Вариант 3 а) диаграмма графа G1 2 3 4 1 5 7 6 матрица инцидентности графа G2 1  0 0  0 0  0  1 б) 2. 3. 4. 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 последовательности вершин 1. (6, 7, 1, 4, 3, 2) (2,1, 7, 6, 1, 4) (1, 2, 3, 4, 1) (1, 2, 3, 4. 2, 1) 5. (2. 1, 6. 7, 1. 4, 2) 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0  0 0  0 0  1  1 32 Вариант 4 а) матрица инцидентности графа G1 1  0 0  0 0  0  1 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0  0 0  0 0  1  1 диаграмма графа G2 6 2 3 5 7 б) 2. 3. 4. 5. последовательности вершин 1. (2, 3, 4, 1, 5) (4, 3, 6, 5, 3, 4, 2) (6, 1, 2, 5, 1, 7) (1, 7, 6. 2, 1) (2, 1. 7, 6, 1. 4, 3, 2) 4 1 33 Вариант 5 а) диаграмма графа G1 1 2 3 4 7 6 матрица смежности графа G2 0  1 0  0 0  0  1 1 0 0 0 0 1 1 б) последовательности вершин 1. 2. 3. 4. 5. 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1  1 0  0 0  1  0 (5, 3, 6, 7, 1, 2) (1, 2, 6, 5, 3, 6, 7) (6, 3, 4, 5, 6) (5, 6, 3, 5, 6, 7) (3, 5, 6, 1, 7, 6, 3) 5 34 Вариант 6 а) 0  1 0  1 0  1 1  матрица смежности графа G1 1 0 1 1 0 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1  0 0  0 0  1 0  1 0 1 0 1 0 1 диаграмма графа G2 2 1 3 6 7 б) последовательности вершин 1. 2. 3. 4. 5. (1, 7, 6, 3, 5) (6, 5, 3, 6, 7, 1) (7, 6, 3, 2, 1, 7) (4, 3, 5, 3, 6, 5) (1, 2, 7, 6, 2, 1) 4 5 35 Вариант 7 а) диаграмма графа G1 2 7 3 1 5 4 6 матрица инцидентности графа G2 1  0 0  0 0  0  1 б) 2. 3. 4. 5. 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 последовательности вершин 1. (7, 6, 5, 3, 4) (1, 7, 6, 2, 5, 6) (7, 1, 2, 3, 6, 7) (5, 6, 3, 5, 3, 4) (1, 2, 6. 7, 2, 1) 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0  0 0  0 0  1  1 36 Вариант 8 а) матрица смежности графа G1 0  1 0  0 0  0  1 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1  1 0  0 0  1  0 диаграмма графа G2 1 2 3 4 7 б) 2. 3. 4. 5. 6 последовательности вершин 1. (3, 5, 6, 7, 1, 2) (3, 6, 7, 1, 2, 6, 5) (4, 3. 6. 5, 4) (5, 5, 7, 6, 3, 5) (5, 3, 6, 7. 1, 6, 5) 5 37 Вариант 9 а) диаграмма графа G1 2 3 4 1 5 7 6 матрица инцидентности графа G2 1  1 0  0 0  0  0 б) 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 последовательности вершин 1. 2. 3. 4. 5. (1, 2, 6, 7) (2, 6, 1, 2, 3, 4) (7, 6, 2, 1, 7) (6, 2, 1, 7, 2, 6) (7, 6, 2, 1, 6, 2, 3) 0  0 0  0 1  1  0 38 Вариант 10 а) 1  1 0  0  0 0  0 матрица инцидентности графа G1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0  0 0  0  0 1  1  диаграмма графа G2 6 4 7 б) 2. 3. 4. 5. 1 2 последовательности вершин 1. (2, 3, 4, 1, 7, 6) (4, 1, 6, 7. 1, 2) (1, 4, 3, 2, 1) (1, 2, 4, 3, 2, 1) (2, 4. 1, 7, 6, 1, 2) 3 5 39 Вариант 11 а) диаграмма графа G1 3 2 4 1 5 7 6 матрица инцидентности графа G2 1  1 0  0  0 0  0 б) 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0  0 0  0  0 1  1  последовательности вершин 1. 2. 3. 4. 5. (5, 1, 4, 3, 2) (2, 4, 3, 5, 6, 3, 4) (7, 1, 5, 2, 1, 6) (1, 2, 6, 7, 1) (2, 3, 4, 1, 6, 7, 1, 2) 40 Вариант 12 а) 0  1 0  1 1  1  1 матрица смежности графа G1 1 0 1 0 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 1  0 0  0 0  1  0 диаграмма графа G2 1 2 7 б) последовательности вершин 1. 2. 3. 4. 5. (7, 6, 2, 1) (2, 6, 5, 3, 6, 2, 1) (6, 7, 1, 2, 6) (7, 1, 5, 2, 1, 6, 7) (3, 6, 2, 7, 6, 2, 1) 3 6 4 5 41 Вариант 13 а) диаграмма графа G1 2 7 3 1 4 6 матрица инцидентности графа G2 1  1 0  0  0 0  0 б) 2. 3. 4. 5. 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0  0 0  0  0 1  1  последовательности вершин 1. (7, 1, 2, 6) (2, 6, 3, 5, 6, 2, 1) (1, 7, 6, 2, 1) (6, 1, 5, 2, 1, 7, 6) (3, 6, 2, 7, 6, 2, 1) 5 42 Вариант 14 а) 1  1 0  0 0  0  0 матрица инцидентности графа G1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0  0 0  0 1  1  0 диаграмма графа G2 2 3 4 1 5 7 6 б) 2. 3. 4. 5. последовательности вершин 1. (2, 6, 7, 1) (4, 3, 2, 1, 6, 2) (7, 1, 2, 6, 7) (6, 2, 7, 1, 2, 6) (3, 2, 6, 1, 2, 6, 7) 43 Вариант 15 а) диаграмма графа G1 3 2 4 1 5 7 6 матрица инцидентности графа G2 1  1 0  0  0 0  0 б) 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0  0 0  0  0 1  1  последовательности вершин 1. 2. 3. 4. 5. (3, 4, 1, 6, 7) (5, 3, 4, 1, 6, 7, 1, 2) (2, 3, 4, 1, 6, 7, 1, 2) (6, 7, 1, 2, 6) (1, 4, 3, 2, 1, 7, 6, 1) 44 Л а б о р а т о р н а я р а б о т а № 4.2 Циклы Цель занятия: изучить разновидности циклов в графах, научиться генерировать случайные графы, определять их принадлежность к множеству эйлеровых и гамильтоновых графов, находить все эйлеровы и гамильтоновы циклы в графах. Задания 1. Разработать и реализовать алгоритм генерации случайного графа, содержащего n вершин и m ребер. 2. Написать программу, которая: а) в течение десяти секунд генерирует случайные графы, содержащие n вершин и m ребер; б) для каждого полученного графа определяет, является ли он эйлеровым или гамильтоновым; в) подсчитывает общее количество сгенерированных графов и количество графов каждого типа. Результат работы программы представить в виде таблицы (табл. 6). Таблица 6 Результат работы программы Количество вершин n n n n Количество ребер n n+1 n+2 эйлеровых Количество графов гамильтоновых всех Cn2 3. Выполнить программу при n = 8,9,10 и сделать выводы. 4. Привести пример диаграммы графа, который является эйлеровым, но не гамильтоновым. Найти в нем все эйлеровы циклы. 5. Привести пример диаграммы графа, который является гамильтоновым, но не эйлеровым. Найти в нем все гамильтоновы циклы. 6. Привести пример диаграммы графа, который является эйлеровым и гамильтоновым. Найти в нем все эйлеровы и гамильтоновы циклы. 7. Привести пример диаграммы графа, который не является ни эйлеровым, ни гамильтоновым. 45 Л а б о р а т о р н а я р а б о т а № 4.3 Связность Цель занятия: изучить алгоритм Краскала построения покрывающего леса, научиться использовать его при решении различных задач. Задания 1. Реализовать алгоритм Краскала построения покрывающего леса. 2. Используя алгоритм Краскала, разработать и реализовать алгоритм решения задачи (см. варианты заданий). 3. Подобрать тестовые данные. Результат представить в виде диаграммы графа. Варианты заданий 1. Найти все мосты в связном графе. 2. Найти минимальное множество ребер, удаление которых из связного графа делает его несвязным. 3. Найти минимальное множество вершин, удаление которых из связного графа разбивает его на три связные компоненты. 4. Получить все покрывающие деревья связного графа G = (V,E), исключая всеми способами |E| – |V| + 1 ребер графа. 5. Найти в эйлеровом графе эйлеров цикл, используя алгоритм Флери, по которому выбираются и нумеруются непронумерованные ребра графа по следующим правилам: 1. Произвольно выбрать некоторую вершину v1 и ребро {v1,v2}, инцидентное вершине v1. Этому ребру присвоить номер 1. Перейти в вершину v2. 2. Находясь в вершине vi, следует не выбирать ребро {vi,v1}, если имеется возможность другого выбора. 3. Находясь в вершине vi, следует не выбирать ребро {vi,vj}, которое является мостом, если имеется возможность другого выбора. 4. После того как в графе будут занумерованы все ребра, образуется эйлеров цикл, порядок нумерации состветствует последовательности обхода ребер. 6. Найти все множества вершин, исключение которых из связного графа разбивает его на две связные компоненты, причем каждая компонента не содержит изолированных вершин. 7. Найти все k-элементные множества ребер, исключение которых из связного графа разбивает его на две связные компоненты. 46 8. Найти все множества ребер, исключение которых из связного графа разбивает его на две связные компоненты, причем каждая компонента не содержит изолированных вершин. 9. Найти максимальное множество ребер, исключение которых из связного графа разбивает его на две связные компоненты. 10. Найти минимальное множество ребер, удаление которых из связного графа разбивает его на три связные компоненты. 11. Найти минимальное множество вершин, удаление которых из связного графа делает его несвязным. 12. Найти все точки сочленения в связном графе. 13. Найти все k-элементные множества вершин, исключение которых из связного графа разбивает его на две связные компоненты. 14. Найти максимальное множество вершин, исключение которых из связного графа разбивает его на две связные компоненты. 15. Найти все максимальные множества ребер, исключение которых из связного графа разбивает его на две связные компоненты. Л а б о р а т о р н а я р а б о т а № 4.4 Кратчайшие пути во взвешенном орграфе Цель занятия: изучить алгоритм Дейкстры нахождения кратчайших путей между вершинами взвешенного орграфа, научиться рационально использовать его при решении различных задач. Задания 1. Изучить алгоритм Дейкстры нахождения кратчайших путей между вершинами взвешенного орграфа. 2. Используя алгоритм Дейкстры, разработать и реализовать алгоритм решения задачи (см. варианты заданий). 3. Подобрать тестовые данные. Результат представить в виде диаграммы графа. Варианты заданий 1. Найти множество вершин взвешенного орграфа, до которых длина кратчайшего пути от заданной вершины не превосходит заданной величины. Вывести кратчайшие пути от заданной вершины до каждой из найденного множества и длины путей. 47 2. Найти вершину взвешенного орграфа, через которую проходит наибольшее число кратчайших путей от заданной вершины до всех остальных. Вывести кратчайшие пути от заданной вершины до каждой вершины орграфа. 3. Найти множество вершин взвешенного орграфа, от которых длина кратчайшего пути до заданной вершины превосходит заданную величину. Вывести кратчайшие пути от каждой из вершины из найденного множества до заданной вершины и длины путей. 4. Найти путь наименьшей длины во взвешенном орграфе от вершины x до вершины y, проходящий через вершину z. Вывести найденный путь и его длину. 5. Найти кратчайший путь во взвешенном орграфе от вершины x до вершины y, проходящий сначала через вершину v, а затем — через вершину w. Вывести найденный путь и его длину. 6. Найти множество вершин взвешенного орграфа, до которых длина кратчайшего пути от первой заданной вершины больше, чем длина кратчайшего пути от второй заданной вершины. Вывести найденное множество вершин, кратчайшие пути от заданных вершин до вершин найденного множества и длины этих путей. 7. Во взвешенном орграфе найти путь между вершинами x и y, в котором длина кратчайшей дуги максимальна (временная метка вершины z — это длина кратчайшей дуги на пути от x до z). Вывести найденный путь и длины дуг этого пути. 8. Во взвешенном орграфе найти простой цикл наименьшей длины с начальной вершиной v. Вывести найденный путь и его длину. 9. Во взвешенном орграфе найти путь наименьшей длины между двумя вершинами, проходящий по заданной дуге. Вывести найденный путь и его длину. 10. Определить, существуют ли во взвешенном орграфе две вершины, до которых длины кратчайших путей от заданной вершины одинаковы. Если существуют, то вывести кратчайшие пути от заданной вершины до найденных. 11. Найти вершину взвешенного орграфа, через которую проходит наибольшее число кратчайших путей до заданной вершины от всех остальных. Вывести кратчайшие пути от каждой вершины орграфа до заданной вершины. 12. Найти множество вершин взвешенного орграфа, до которых длина кратчайшего пути от первой заданной вершины равна длине кратчайшего пути от второй заданной вершины. Вывести найденное множество вершин, кратчайшие пути от заданных вершин до вершин найденного множества и длины этих путей. 48 Л а б о р а т о р н а я р а б о т а № 4.5 Кратчайшие пути между каждой парой вершин во взвешенном орграфе Цель занятия: изучить алгоритмы нахождения кратчайших путей между каждой парой вершин во взвешенном орграфе, научиться использовать их при решении различных задач. Задания 1. Изучить алгоритмы нахождения кратчайших путей между каждой парой вершин во взвешенном орграфе. 2. Разработать и реализовать алгоритм решения задачи (см. варианты заданий). 3. Подобрать тестовые данные. Результат представить в виде диаграммы графа. Варианты заданий 1. Во взвешенном орграфе найти все пары вершин vi и vj, такие, что кратчайшее расстояние от vi до vj равно кратчайшему расстоянию от vj до vi. Вывести кратчайшие пути между найденными парами вершин. 2. Дерево кратчайших путей назовем покрывающим, если все вершины взвешенного орграфа принадлежат дереву. Сумму длин дуг дерева назовем стоимостью. Построить все покрывающие деревья кратчайших путей минимальной стоимости. 3. Во взвешенном орграфе найти все такие вершины vi, что сумма кратчайших расстояний от всех вершин орграфа до vi равна сумме кратчайших расстояний от vi до всех вершин орграфа. 4. Определить, есть ли в заданном взвешенном орграфе вершина, которая является и внешней медианой, и внутренним центром. Привести пример орграфа с такой вершиной. 5. Во взвешенном орграфе найти все такие вершины vi, что кратчайшее расстояние от самой “удаленной” вершины орграфа до vi равно кратчайшему расстоянию от vi до самой “удаленной” от нее вершины. 6. Используя алгоритм нахождения кратчайших расстояний между каждой парой вершин в орграфе определить: а) является ли заданный орграф сильно связным; б) является ли заданный орграф односторонне связным. 49 7. Найти все внешние, внутренние и внешне-внутренние центры взвешенного орграфа. Привести примеры орграфов, которые имеют более одного центра каждого вида. 8. Найти все пары вершин взвешенного орграфа, кратчайший путь между которыми содержит заданное число дуг. 9. Определить, есть ли в заданном взвешенном орграфе вершина, которая является и внешней, и внутренней медианой. Привести пример орграфа с такой вершиной. 10. Во взвешенном орграфе найти все пары вершин vi и vj, такие, что кратчайшее расстояние от vi до vj меньше кратчайшего расстояния от vj до vi. Вывести кратчайшие пути между найденными парами вершин. 11. Дерево кратчайших путей назовем покрывающим, если все вершины взвешенного орграфа принадлежат дереву. Сумму длин дуг дерева назовем стоимостью. Построить все покрывающие деревья кратчайших путей максимальной стоимости. 12. Во взвешенном орграфе найти все такие вершины vi, что сумма кратчайших расстояний от всех вершин орграфа до vi меньше суммы кратчайших расстояний от vi до всех вершин орграфа. 13. Определить, есть ли в заданном взвешенном орграфе вершина, которая является и внешним центром, и внутренней медианой. Привести пример орграфа с такой вершиной. 14. Во взвешенном орграфе найти все такие вершины vi, что кратчайшее расстояние от самой “удаленной” вершины орграфа до vi меньше кратчайшего расстояния от vi до самой “удаленной” от нее вершины. 15. Найти множество вершин во взвешенном орграфе, внешние и внутренние передаточные числа которых совпадают. 16. Найти все внешние, внутренние и внешне-внутренние медианы взвешенного орграфа. Привести примеры орграфов, которые имеют более одной медианы каждого вида. 17. Найти все пары вершин взвешенного орграфа, кратчайший путь между которыми содержит не более заданного числа дуг. 18. Найти множество вершин во взвешенном орграфе, числа внешнего и внутреннего разделения которых совпадают. 19. Определить, есть ли в заданном взвешенном орграфе вершина, которая является и внешним, и внутренним центром. Привести пример орграфа с такой вершиной. 20. Найти все пары вершин взвешенного орграфа, кратчайший путь между которыми содержит более заданного числа дуг. 50 Контрольные вопросы 1. Дайте определение графа, орграфа, псевдографа, мультиграфа, гиперграфа, взвешенного графа. Что такое степень вершины, полустепень исхода и полустепень захода? Дайте определение понятиям смежности и инцидентности. 2. Что такое матрица смежности и матрица инцидентности? Предложите различные способы хранения взвешенных графов и орграфов в памяти ЭВМ. Разработайте алгоритмы преобразования одного способа хранения графа в другой. 3. Какие графы называются изоморфными? Сколько существует графов, изоморфных заданному? Разработайте алгоритмы проверки изоморфизма двух графов. 4. Дайте определение маршрута, цепи, простой цепи. Опишите алгоритмы получения всех маршрутов, цепей и простых цепей заданной длины. Как можно подсчитать количество маршрутов заданной длины между каждой парой вершин графа? 5. Что называется расстоянием между заданными вершинами, эксцентриситетом вершины, диаметром и радиусом графа? Какая вершина графа называется переферийной, центральной? Что называется центром графа? Какая цепь называется диаметральной? 6. Дайте определение цикла и простого цикла. Опишите алгоритм получения всех простых циклов в графе. 7. Какой цикл называется гамильтоновым? Как определить, является ли граф гамильтоновым? Какой цикл называется эйлеровым? Как определить, является ли граф эйлеровым? Опишите алгоритмы получения всех гамильтоновых и эйлеровых циклов. 8. Какой граф называется связным? 9. Что такое матрица связанности вершин? Как ее вычислить? 10. Что называется мостом, точкой сочленения, разрезом, реберной и вершинной связностью? 11. Дайте определение дереву и лесу. Какими свойствами обладают дерево и лес? 12. Что такое лист и корень дерева? Сколько корней может иметь дерево? Докажите. 13. Сколько различных деревьев можно построить на n вершинах? Докажите. 14. Дайте определение покрывающему дереву и покрывающему лесу. Сколько ребер нужно удалить из связного графа, чтобы получить покрывающее дерево? Сколько ребер нужно удалить из несвязного графа, чтобы получить покрывающий лес? 51 15. Опишите алгоритм Краскала. Что такое “букет”? 16. Опишите алгоритм формирования всех покрывающих деревьев связного графа. 17. Как определяется стоимость покрывающего дерева взвешенного графа? Опишите алгоритмы построения покрывающего дерева минимальной стоимости. 18. Что называется поиском в орграфе? Опишите алгоритмы поиска в глубину и в ширину. 19. Какие виды связности существуют в орграфе? 20. Дайте определения отношениям достижимости, контрдостижимости и взаимодостижимости вершин орграфа. 21. Что называется компонентой сильной связности орграфа? Опишите алгоритм нахождения компонент сильной связности орграфа. 22. Что называется конденсацией орграфа? Что называется базой и антибазой орграфа? 23. Что называется кратчайшим путем и кратчайшим расстоянием между двумя вершинами во взвешенном орграфе? Опишите алгоритмы нахождения кратчайших путей между заданной парой вершин во взвешенном орграфе. 24. Что такое дерево кратчайших путей? Как его построить? 25. Опишите различные алгоритмы нахождения кратчайших путей между каждой парой вершин во взвешенном орграфе. 26. Что называется числом внешнего, внутреннего и внешневнутреннего разделения вершины? Что называется внешним, внутренним и внешне-внутренним центром взвешенного орграфа? 27. Что называется внешним, внутренним и внешне-внутренним передаточным числом вершины во взвешенном орграфе? Что называется внешней, внутренней и внешне-внутренней медианой взвешенного орграфа? 28. Дайте определение клики, максимальной клики и наибольшей клики. Опишите алгоритмы поиска всех максимальных клик и наибольшей клики. 29. Дайте определение независимому множеству вершин, максимальному и наибольшему независимому множеству. Установите связь между кликами и независимыми множествами вершин. 30. Что такое раскраска графа, правильная раскраска, хроматическое число, минимальная раскраска? 31. Опишите алгоритм получения всех раскрасок графа в число цветов, не превышающее заданного. 32. Опишите алгоритм получения минимальной раскраски. 52 5. БУЛЕВЫ ФУНКЦИИ Л а б о р а т о р н а я р а б о т а № 5.1 Полностью определенные булевы функции Цель занятия: изучить способы задания булевых функций, методы их минимизации и программной реализации. Задания 1. Представить булеву функцию fi (табл. 7), где i — номер варианта, совершенной дизъюнктивной нормальной формой, совершенной конъюнктивной нормальной формой и полиномом Жегалкина. 2. Получить сокращенную ДНФ функции fi методом Квайна — Мак-Класки. 3. Получить минимальную ДНФ функции fi, используя матрицу Квайна. 4. Выполнить скобочную минимизацию минимальной ДНФ функции fi. 5. Построить бинарный граф функции fi. 6. Написать программу, вычисляющую значение функции fi на заданном наборе аргументов по минимальной ДНФ. 7. Написать программу, вычисляющую значение функции fi на заданном наборе аргументов по бинарному графу. 8. Используя программу п.6, написать программу, строящую таблицу истинности функции fi. Результат работы программы сравнить с заданием (табл. 5.7). 9. Используя программу п.7, написать программу, строящую таблицу истинности функции fi. Результат работы программы сравнить с заданием (табл. 5.7). Л а б о р а т о р н а я р а б о т а № 5.2 Частично определенные булевы функции Цель занятия: изучить методы минимизации чистично определенных булевых функций. Задания 1. Получить минимальную ДНФ чистично определенной булевой функции fi (табл. 8), где i — номер варианта, различными способами. 2. Написать программу, строящую таблицу истинности функции fi. Результат работы программы сравнить с заданием (табл. 8). 53 Таблица 7 Таблица истинности полностью определенных булевых функций x1 x2 x3 x4 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 1 1 1 0 1 1 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 1 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 1 0 1 1 0 0 0 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 1 0 1 0 1 1 1 0 0 0 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1 1 1 1 0 0 1 0 0 0 0 1 1 1 0 0 0 1 1 Таблица 8 Таблица истинности частично определенных булевых функций x1 x2 x3 x4 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 0 1 - 0 1 0 1 1 1 1 0 1 0 1 1 1 0 0 0 - 1 0 0 1 1 1 0 1 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 0 0 1 1 - 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 1 0 1 0 1 1 0 1 0 1 1 1 0 0 0 0 1 0 1 1 1 0 1 - 0 1 1 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 1 1 1 0 0 0 1 0 0 1 0 0 1 1 1 0 54 Л а б о р а т о р н а я р а б о т а № 5.3 Минимизация систем полностью определенных булевых функций Цель занятия: научиться минимизировать системы полностью определенных булевых функций, закрепить навыки минимизации полностью определенных булевых функций. Задания В табл. 7 (см. выше) представлено множество {f1, f2,…, f15} полностью определенных булевых функций. В табл. 9 каждому варианту поставлена в соответствие система булевых функций, представляющая собой подмножество множества {f1, f2,…, f15} (см. табл. 7). 1. Минимизировать систему полностью определенных булевых функций в соответствии с вариантом задания (см. табл. 9). 2. Получить систему минимальных ДНФ булевых функций и сравнить с результатом п.1. Таблица 9 Варианты заданий Вариант 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Система булевых функций f1, f2, f3, f4 f1, f3, f4, f5 f4, f5, f6, f7 f2, f3, f5, f6 f5, f6, f7, f8 f1, f2, f6, f7 f1, f4, f5, f9 f3, f4, f8, f10 f5, f7, f9, f10 f8, f9, f10, f11 f10, f11, f12, f14 f11, f12, f13, f15 f7, f8, f13, f14 f4, f6, f10, f13 f2, f4, f11, f14 f3, f5, f9, f13 f5, f6, f8, f15 f5, f8, f11, f15 f6, f7, f10, f12 f7, f9, f13, f14 55 Л а б о р а т о р н а я р а б о т а № 5.4 Вычисление систем булевых функций Цель занятия: научиться минимизировать системы частично определенных булевых функций, строить бинарные графы систем булевых функций и использовать их для вычисления значений функций системы. Задания В табл. 8 (см. выше) представлено множество { f1, f2,…, f15} частично определенных булевых функций. В табл. 9 (см. выше) каждому варианту поставлена в соответствие система булевых функций, представляющая собой подмножество множества {f1, f2,…, f15} (см. табл. 8). 1. Минимизировать систему частично определенных булевых функций в соответствии с вариантом задания (см. табл. 9). 2. Построить бинарный граф системы булевых функций. 3. Написать программу, вычисляющую значение системы булевых функций на заданном наборе аргументов по бинарному графу. Заключительные вершины бинарного графа системы булевых функций дополнительно пронумеруем натуральными числами от 1 до k, где k — количество заключительных вершин, и построим таблицу, которая каждой заключительной вершине поставит в соответствие набор значений функций системы. Такую таблицу можно представить двумерным массивом F, в котором элемент Fij содержит значение функции fj, записанной в заключительной вершине с дополнительным номером i. В основной же таблице в строке, соответствующей заключительной вершине с дополнительным номером i, во втором столбце запишем i. Алгоритм вычисления значения системы булевых функций на заданном наборе аргументов по бинарному графу отличается от алгоритма вычисления значения одной функции тем, что при достижении заключительной вершины (после выхода из цикла) выводятся значения всех функций системы из массива F с использованием дополнительной метки заключительной вершины. 4. Используя программу п.3, написать программу, строящую таблицу истинности системы булевых функций. Результат работы программы сравнить с заданием (табл. 8). 56 Контрольные вопросы 1. Дайте определение булевой функции. 2. Приведите примеры различных таблиц истинности, задающих одну и ту же булеву функцию. 3. Какая булева функция называется элементарной? Сколько их? 4. Что называется функционально полным набором булевых функций? 5. Что называется операцией суперпозиции и суперпозицией функций? 6. Дайте определение классу булевых функций, функционально замкнутого по операции суперпозиции. 7. Дайте определение свойствам булевых функций. Определите свойства заданной булевой функции. 8. Сформулируйте необходимые и достаточные условия функциональной полноты системы булевых функций. Определите, обладает ли функциональной полнотой заданная система функций? 9. Дайте определение конституенты единицы и конституенты нуля. 10. Что представляет собой СДНФ, СКНФ, СПНФ? 11. Что называется элементарной конъюнкцией, элементарной дизъюнкцией? Что представляет собой ДНФ и КНФ? Чем они отличаются от СДНФ и СКНФ. 12. Что называется полиномом Жегалкина? Представьте полиномом Жегалкина булеву функцию, заданную таблицей истинности. 13. Запишите основные законы булевой алгебры. Запишите и докажите истинность правил склеивания, поглощения и вычеркивания. 14. Что такое дизъюнктивное разложение Шеннона? Выполните разложение Шеннона заданной булевой функции по различным аргументам. 15. Что называется импликантой булевой функции? Какая импликанта называется простой? 16. Дайте определение сокращенной ДНФ. Получите сокращенную ДНФ булевой функции, заданной таблицей истинности, различными методами. 17. Дайте определение тупиковой и минимальной ДНФ булевой функции. 18. Что представляет собой матрица Квайна, ядро Квайна? 19. Что такое конъюнктивное представление матрицы Квайна? Как его использовать для получения всех тупиковых ДНФ? 20. Выполните скобочную минимизацию заданной минимальной ДНФ булевой функции. 21. Какая булева функция называется частично определенной? 57 22. Что называется простой импликантой частично определенной булевой функции? Как найти все простые импликанты частично определенной булевой функции? 23. Какая система ДНФ булевых функций называется минимальной? 24. Что называется простой импликантой системы булевых функций? 25. Модифицируйте метод Квайна — Мак-Класки для получения всех простых импликант системы булевых функций. 26. Как строится импликантная матрица Квайна для системы булевых функций? 27. Какие аргументы системы частично определенных булевых функций называются фиктивными? Как их найти? 28. Что называется простой импликантой системы частично определенных булевых функций? Как найти все простые импликанты системы частично определенных булевых функций? 29. Приведите пример бинарного графа булевой функции. Запишите эту функцию в ДНФ. 30. Постройте различные бинарные графы одной и той же булевой функции. 31. Сколько условных вершин может быть в бинарном графе булевой функции? Какова может быть глубина бинарного графа? 32. Приведите пример бинарного графа системы булевых функций. Запишите эти функции в ДНФ. 33. Постройте различные бинарные графы одной и той же системы булевых функций. 34. Сколько условных и заключительных вершин может быть в бинарном графе системы булевых функций? 35. Какова может быть глубина бинарного графа системы булевых функций? 36. Напишите программы для вычисления значения булевой функции по таблице истинности при различных способах ее хранения. 37. Опишите алгоритм вычисления значения булевой функции по ДНФ. 38. Напишите различные программы для вычисления значения булевой функции по заданному бинарному графу. 39. Разработайте способ хранения и алгоритм вычисления системы булевых функций по таблице истинности. 40. Разработайте способ хранения и алгоритм вычисления системы булевых функций по минимальной системе ДНФ булевых функций. 58 Библиографический список 1. Асанов, М. Дискретная математика: графы, матроиды, алгоритмы / М.О. Асанов, В.А. Баранский, В.В. Расин. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. — 288 с. 2. Белоусов, А.И. Дискретная математика: учеб. для вузов / А.И. Белоусов, С.Б. Ткачёв, под ред. В.С. Зарубина, А.П. Крищенко. — 3-е изд., стер. — М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. — 744 с. (Сер. Математика в техническом университете; Вып. ХIХ). 3. Иванов, Б.Н. Дискретная математика. Алгоритмы и программы: учеб. пособие / Б.Н. Иванов. — М.: Лаборатория Базовых Знаний, 2003. — 288 с. 4. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. — М.: Мир, 1978. — 429 с. 5. Кузнецов, О.П. Дискретная математика для инженера / О.П. Кузнецов, Г.М. Адельсон-Вельский. — 2-е изд., перераб. и доп. — М.: Энергоатомиздат, 1988. – 480с. 6. Кузнецов, О.П.. Дискретная математика для инженера / О.П. Кузнецов. — 3-е изд., перераб. и доп. — СПб.: Лань, 2004. — 400 с.: ил. — (Учебники для вузов. Специальная литература). 7. Липский, В. Комбинаторика для программистов / В. Липский. — М.: Мир, 1988. — 201 с. 8. Муромцев, В.В. Проектирование полнопереборных алгоритмов: учеб. пособие./ В.В. Муромцев. — Белгород: Изд-во БелГТАСМ, 2001. — 67 с. 9. Новиков, Ф.А. Дискретная математика для программистов: учеб. для вузов / Ф.А. Новиков. — 3-е изд. — СПб.: Питер, 2008. — 384 с.: ил. — (Серия «Учебник для вузов»). 10. Прикладная теория цифровых автоматов / К.Г. Самофалов, А.М. Романкевич, В.Н. Валуйский и др. — Киев: Вища школа, 1987. – 357 с. 11. Рейнгольд, Э. Комбинаторные алгоритмы. Теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Дэо. — М.: Мир, 1980. — 476 с. 12. Рязанов, Ю.Д. Булевы функции. Способы задания и реализация: учеб. пособие / Ю.Д. Рязанов. — Белгород: Изд-во БТИСМ, 1993. — 124 с. 13. Рязанов, Ю.Д. Множества и комбинаторные объекты: учеб. пособие / Ю.Д. Рязанов — Белгород: Изд-во БГТУ, 2008. — 99 с. 14. Рязанов, Ю.Д. Дискретная математика: учеб. пособие. / Ю.Д. Рязанов. — Белгород: Изд-во БГТУ, 2010. — 274 с. — ISBN 59 15. Седжвик, Р. Фундаментальные алгоритмы на C++. Ч. 5: Алгоритмы на графах: пер. с англ / Р. Седжвик. — СПб.: ООО «ДиаСофтЮП», 2002. — 496 с. 16. Хаггарти, Р. Дискретная математика для программистов / Р. Хаггарти. — М.: Техносфера, 2005. — 400 с. 17. Шапорев, С.Д. Дискретная математика: курс лекций и практических занятий / С.Д. Шапорев. — СПб.: БХВ-Петербург, 2007. — 400 с. 18. Яблонский, С.В. Введение в дискретную математику: учеб. пособие для вузов / под ред. В.А. Садовничего. — 4-е изд., стер. — М.: Высш. шк., 2003. – 384 с. Учебное издание Рязанов Юрий Дмитриевич Теория вычислительных процессов Лабораторный практикум Подписано в печать 08.08.11 Формат 60х84/16. Усл.печ.л. 5,6. Уч.-изд.л.6,1. Тираж 100 экз. Заказ Цена Отпечатано в Белгородском государственном технологическом университете им. В. Г. Шухова 308012, г. Белгород, ул. Костюкова, 46