ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
 Скачать 4.33 Mb.
|
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Белгородский государственный технологический университет им. В.Г. Шухова Ю. Д. Рязанов ДИСКРЕТНАЯ МАТЕМАТИКА Федеральное государственное автономное образовательное учреждение высшего профессионального образования Московский физико-технический институт государственный университет рекомендует данное учебное издание к публикации Регистрационный номер рецензии 3060 от «29» июня 2015 г. МГУП имени Ивана Федорова Белгород 2016 УДК 519.1 ББК 22.12 Р Рецензенты Доктор физико-математических наук, профессор Белгородского государственного технологического университета им. В. Г. Шухова А. Г. Брусенцев Доктор физико-математических наук, профессор Белгородского государственного аграрного университета имени В.Я. Горина В.А. Ломазов Р Рязанов, Ю. Д. Дискретная математика учеб. пособие. / Ю. Д. Рязанов. — е изд, доп. — Белгород Изд-во БГТУ, 2016. — 298 с. ISBN 978-5-361-00364-8 В учебном пособии рассмотрены вопросы пяти разделов, изучаемых в курсе дискретной математики теории множеств, комбинаторных объектов, отношений, графов и булевых функций. Уделяется внимание применению метода поиска с возвращением для решения различных задач дискретной математики. Пособие содержит теоретические сведения, задания для самостоятельной работы и перечень контрольных вопросов. Содержание учебного пособия соответствует основным разделам дисциплины Дискретная математика и предназначено для студентов, обучающихся по направлениям бакалавриата 09.03.01 Информатика и вычислительная техника и 09.03.04 Программная инженерия УДК 519.1 ББК 22.12 Белгородский государственный технологический университет (БГТУ) им. В.Г. Шухова, 2010 Оформление. ISBN 978-5-361-00364-8 БГТУ им. В.Г. Шухова, 2016 3 Оглавление Предисловие ко второму изданию Введение к первому изданию ..…………………………………………. 1. Множества ...…………………………………………………………… 1.1. Основные понятия ..………………………………………………... 1.2. Способы задания множеств ...............……………………………... 1.3. Операции надмножествами. Свойства операций надмножествами. Нормальные формы Кантора ……………………………………… 1.6. Преобразование теоретико-множественного выражения в нормальную форму Кантора …..…….……………………………... 1.7. Методы доказательства теоретико-множественных тождеств ...... 1.7.1. Метод двух включений .….….……………………………… 1.7.2. Метод эквивалентных преобразований ..….………...………. 1.7.3. Метод характеристических функций ….….…….…..………. 1.7.4. Теоретико-множественный метод …..….……………...……. 1.7.5. Метод симметрической разности ..…….……………………. 1.8. Теоретико-множественные уравнения ..….……………………….. 1.9. Способы представления множества в памяти ЭВМ ..….………… 1.10. Алгоритмы реализации операций надмножествами. Практическое занятие 1.1. Операции надмножествами. Практическое занятие 1.2. Нормальные формы Кантора ..….……. Практическое занятие 1.3. Теоретико-множественные тождества ..….…….…………………………………………………. Практическое занятие 1.4. Теоретико-множественные уравнения ..….…….…………………………………………………. Контрольные вопросы и задания ..…………………………...………… 2. Комбинаторные объекты. 2.1. Введение 2.2. Метод поиска с возвращением. 2.3. Подмножества 2.4. Перестановки. 2.5. Размещения. 2.6. Размещения с повторениями. 2.7. Сочетания. 2.8. Перестановки с повторениями. 2.9. Сочетания с повторениями. 7 8 12 12 13 13 16 18 20 22 22 23 24 27 29 30 32 32 47 50 51 53 57 58 58 58 61 64 67 70 73 76 79 4 2.10. Упорядоченные разбиения множества. 2.10.1. Упорядоченные разбиения множества M на k подмножеств с мощностями (n 1 ,n 2 ,…,n k )…………...…. 2.10.2. Упорядоченные разбиения множества M на k подмножеств с мощностями {n 1 ,n 2 ,…,n k }……………… 2.10.3. Все упорядоченные разбиения множества M на k подмножеств. 2.10.4. Все упорядоченные разбиения множества M.......................... 2.11. Разбиения множества. 2.11.1. Разбиения множества M на k подмножеств с мощностями {n 1 ,n 2 ,…,n k }…….…………..………………... 2.11.2. Все разбиения множества M на k подмножеств. 2.11.3. Все разбиения множества M………………………………… 2.12. Использование алгоритмов порождения комбинаторных объектов при проектировании полнопереборных алгоритмов решения задач выбора 2.13. О неэффективности полнопереборных алгоритмов. Пример. Практическое занятие 2.1. Алгоритмы порождения комбинаторных объектов Практическое занятие 2.2. Разбиения множеств. Практическое занятие 2.3. Задачи выбора Контрольные вопросы и задания 3. Отношения. Основные понятия 3.2. Способы задания отношений 3.3. Операции над отношениями 3.4. Алгоритмы реализации операций над отношениями. 3.5. Свойства отношений. 3.6. Замыкание отношений 3.7. Классы эквивалентности и фактормножества...………………....... 3.8. Упорядоченные множества Практическое занятие 3.1. Отношения и их свойства. Практическое занятие 3.2. Транзитивное замыкание отношения. Практическое занятие 3.3. Фактормножества………….…….……. Практическое занятие 3.4. Упорядоченные множества Контрольные вопросы и задания 4. Графы. 4.1. Основные понятия. 4.2. Матричные способы представления графов 4.3. Изоморфизм графов 82 82 84 86 88 89 89 93 100 102 105 110 111 113 116 119 119 121 122 125 131 134 138 139 143 146 147 148 149 151 151 154 156 5 4.4. Маршруты. 4.5. Метрические характеристики графа. 4.6. Циклы. 4.7. Связность 4.8. Деревья 4.9. Покрывающие деревья графа. 4.10. Покрывающие деревья минимальной стоимости 4.11. Поиск в орграфе 4.12. Связность в орграфе. Компоненты сильной связности. 4.13. Кратчайший путь в орграфе 4.14. Кратчайшие пути между каждой парой вершин в орграфе. 4.15. Центры и медианы во взвешенном орграфе. 4.16. Клики и независимые множества. 4.17. Раскраска графа Практическое занятие 4.1. Маршруты …………...…..…………….. Практическое занятие 4.2. Циклы. Практическое занятие 4.3. Связность Практическое занятие 4.4. Анализ алгоритмов построения покрывающего дерева минимальной стоимости Практическое занятие 4.5. Анализ алгоритмов поиска кратчайшего пути во взвешенном орграфе между заданной парой вершин. Практическое занятие 4.6. Кратчайшие пути во взвешенном орграфе. Практическое занятие 4.7. Анализ алгоритмов поиска кратчайших путей во взвешенном орграфе между каждой парой вершин. Практическое занятие 4.8. Кратчайшие пути между каждой парой вершин во взвешенном орграфе. Контрольные вопросы и задания. 5. Булевы функции. 5.1. Табличные способы задания булевых функций. 5.2. Элементарные булевы функции. 5.3. Функциональная полнота систем булевых функций. 5.4. Аналитические способы задания булевых функций. 5.5. Основные законы булевой алгебры и их следствия 5.6. Минимизация полностью определенных булевых функций 5.6.1. Основные понятия. 5.6.2. Получение сокращенной ДНФ булевой функции. 5.6.3. Получение минимальной ДНФ булевой функции. 5.6.4. Скобочная минимизация булевых функций. 157 163 164 168 170 173 178 182 188 193 201 203 206 215 219 235 236 237 238 239 241 242 244 246 246 247 249 251 255 257 257 259 261 263 6 5.7. Минимизация частично определенных булевых функций. 5.8. Минимизация систем полностью определенных булевых функций. 5.9. Минимизация систем частично определенных булевых функций. 5.10. Графовые способы задания булевых функций 5.10.1. Бинарные деревья и бинарные графы. 5.10.2. Синтаксические деревья. 5.11. Программная реализация булевых функций ……………..……... 5.11.1. Вычисление значения булевой функции по таблице истинности. 5.11.2. Вычисление значения булевой функции по ДНФ…………. 5.11.3. Вычисление значения булевой функции по бинарному графу. 5.11.4. Вычисление значения булевой функции по синтаксическому дереву Практическое занятие 5.1. Полностью определенные булевы функции Практическое занятие 5.2. Частично определенные булевы функции Практическое занятие 5.3. Минимизация систем полностью определенных булевых функций Практическое занятие 5.4. Вычисление систем булевых функций Контрольные вопросы и задания. Заключение……...……………………………………………………..…. Библиографический список 263 268 271 276 276 281 284 284 284 285 287 289 289 291 292 293 295 296 7 Предисловие ко второму изданию Учебное пособие Дискретная математика (издание первое) было издано в 2010 году и активно использовалось в учебном процессе. Совершенствование учебного процесса послужило поводом к переработке некоторого материала пособия и добавлению нового материала. В первую главу добавлен материал по представлению множеств в нормальных формах Кантора и соответствующее практическое занятие. Переработан материал по теоретико-множественным тождествам. Изложение теоретико-множественного метода доказательства тождеств стало более понятными очевидным. Методы арифметических и логических характеристических функций теперь описаны водном стиле. Дополнен метод эквивалентных преобразований. Показан способ доказательства тождества этим методом с использованием совершенной нормальной формы Кантора, не требующий угадывания хода доказательства. Добавлен материал по решению теоретико-множественных уравнений, который практически не встречается в учебной литературе ив сети Интернет. Третья глава пополнилась примерами выполнения операций над реальными, имеющими смысл отношениями, в результате чего получаются отношения, имеющие другой смысл, что позволило приблизить теорию к реальности и сделать изложение материала более понятным. Добавлена информация об упорядоченных множествах. В пятую главу добавлен графовый способ задания булевых функций синтаксическое дерево. Представлены правила построения синтаксического дерева по аналитической форме булевой функции и алгоритм вычисления значения функции по дереву. Алгоритмы построения синтаксических деревьев обычно рассматриваются при изучении вопросов трансляции языков программирования. Исправлены обнаруженные опечатки, дополнен библиографический список. 8 Введение к первому изданию Учебное пособие предназначено для студентов технических вузов, изучающих дискретную математику и программирование и состоит из пяти глав Множества, Комбинаторные объекты, Отношения, Графы и Булевы функции. В каждой главе содержатся теоретические сведения, задания для самостоятельной работы в виде практических занятий и перечень контрольных вопросов. Впервой главе даны основные понятия теории множеств, рассмотрены различные методы доказательства теоретико-множественных тождеств. Представлены алгоритмы реализации операций надмножествами при различных способах их хранения в памяти ЭВМ. Показана зависимость структуры алгоритмов реализации операций надмножествами от способа хранения множества в памяти ЭВМ. Во второй главе рассматриваются основные комбинаторные объекты подмножества, перестановки (без повторений и с повторениями, размещения (без повторений и с повторениями, сочетания (без повторений и с повторениями) и различные виды разбиений множества. При рассмотрении каждого типа объектов дается его определение, формулируется и доказывается теорема о количестве различных комбинаторных объектов и приводится алгоритм порождения всех объектов. Для порождения комбинаторных объектов различных типов используется один и тот же метод — метод поиска с возвращением, поэтому алгоритмы порождения всех типов объектов имеют одинаковую структуру. Далее рассматриваются вопросы использования комбинаторных объектов и алгоритмов их порождения при проектировании полнопере- борных алгоритмов решения дискретных задач выбора. Описаны этапы проектирования полнопереборных алгоритмов с использованием комбинаторных объектов и показано, как преобразовать алгоритм порождения комбинаторных объектов в алгоритм решения задачи. Приведены примеры проектирования полнопереборных алгоритмов. Показана простота проектирования и неэффективность (сточки зрения времени выполнения) полнопереборных алгоритмов. Приводится эффективный алгоритм решения одной задачи выбора. В третьей главе рассматриваются бинарные отношения на множестве. Определены операции над отношениями и свойства отношений. Представлены алгоритмы реализации операций, нахождения транзитивного замыкания и фактормножества по заданному отношению эквивалентности. В четвертой главе даны основные понятия теории графов, графические и матричные представления графов. Определено понятие маршрута 9 в графе и его разновидности различные цепи и циклы. Представлены алгоритмы получения всех маршрутов, обладающих определенными свойствами маршруты заданной длины, простые цепи и циклы, гамиль- тоновы и эйлеровы циклы. Эти алгоритмы основаны на методе поиска с возвращением и поэтому все они имеют одинаковую структуру, что наглядно представлено блок-схемами алгоритмов. Далее рассматривается понятие связность графа. Определено отношение связанности вершин и способы его вычисления, основанные на методе поиска с возвращением и нахождения транзитивного замыкания. Показано, что отношение связанности вершин обладает свойством эквивалентности, а классы эквивалентности представляют собой связные компоненты графа. Затем рассматривается особый подкласс графов — деревья и определяются их свойства. Рассматриваются покрывающие деревья графов и алгоритм Краскала построения покрывающего леса. Для построения всех покрывающих деревьев представлен алгоритм, основанный на методе поиска с возвращением. Для нахождения покрывающих деревьев минимальной стоимости представлены алгоритмы Краскала и Прима, даны рекомендации по программной реализации этих алгоритмов. Рассмотрены задачи, решение которых сводится к нахождению связных компонент и покрывающих деревьев минимальной стоимости. Потом описываются алгоритмы поискав орграфе и примеры задач, решение которых сводится к поиску в орграфе. Затем рассматривается связность в орграфе. Определяются различные виды связности сильная, односторонняя и слабая, и компоненты сильной связности. Определяются отношения достижимости, контрдос- тижимости и взаимодостижимости на множестве вершин орграфа. Представлены различные способы нахождения отношения достижимости с использованием алгоритмов поискав орграфе и вычисления транзитивного замыкания отношения смежности вершин орграфа. Показано, что отношение взаимодостижимости обладает свойством эквивалентности, а классы эквивалентности представляют собой сильносвязные компоненты. Даются определения понятиям конденсация, база и антибаза и приводятся задачи, для решения которых используются эти понятия. Затем рассматриваются кратчайшие пути во взвешенном орграфе. Для нахождения кратчайшего пути от одной заданной вершины до другой рассматривается возможность применения алгоритма перебора простых цепей, основанного на методе поиска с возвращением, и его усовершенствование с использованием идеи метода ветвей и границ. Описан алгоритм Дейкстры нахождения кратчайших путей и даны рекомендации по его программной реализации. Для нахождения кратчайших 10 путей между каждой парой вершин взвешенного орграфа описан способ применения алгоритма Дейкстры, алгоритм Шимбелла и алгоритм Флойда. Даются определения центров и медиан взвешенных орграфов. Приводятся примеры задач, решение которых сводится к нахождению центров и медиан взвешенного орграфа. Далее рассматриваются клики и независимые множества графов. Представлен алгоритм поиска всех максимальных клик, основанный на методе поиска с возвращением, показаны его недостатки и более эффективный алгоритм Брона — Кербоша. Представлены различные эвристические алгоритмы поиска наибольшей клики. Определена связь клики независимых множеств и показано, как алгоритмы поиска клик использовать для поиска независимых множеств. Приводятся примеры задач, решение которых сводится к поиску клики независимых множеств. Заканчивается глава определением понятия раскраска графа. Приводятся алгоритмы, основанные на методе поиска с возвращением, позволяющие получить все или одну правильную раскраску графа не более чем в заданное число цветов. Показано, как эти алгоритмы применить для нахождения минимальной раскраски графа. Приводятся примеры задач, решение которых сводится к нахождению минимальной раскраски графа. В пятой главе рассматриваются различные способы представления булевых функций, методы минимизации полностью и частично определенных булевых функций и их систем и алгоритмы вычисления булевых функций при различных способах представления. В пособии все рассматриваемые задачи дискретной математики доводятся до алгоритмов их решения. Для решения многих задач используются общие методы, например, метод поиска с возвращением, метод перемножения матриц и т.д. Это позволяет строить алгоритмы одинаковой структуры для решения различных задач. Степень детализации алгоритмов выбрана такой, что даже сложные алгоритмы представлены в простой и доступной для понимания форме. Выбор структур данных для реализации алгоритмов отходит на второй план и оставлен для самостоятельной проработки, но, все же, рассматриваются способы хранения объектов дискретной математики в памяти ЭВМ и даются рекомендации по их использованию в программной реализации алгоритмов. В пособии приведено много примеров реальных задач, решение которых сводится к решению рассмотренных задач дискретной математики Практические занятия носят творческий и исследовательский характер. В одних предлагается грамотно применить рассмотренные алгоритмы для решения конкретных задач, в других — выполнить сравнительный анализ различных алгоритмов решения одной и той же задачи. Контрольные вопросы, приведенные в конце каждой главы, охватывают весь изложенный материал. Предполагается, что изучающие материал пособия владеют основами алгоритмизации и программирования на каком-либо языке высокого уровня. Никаких предварительных знаний по дискретной математики не требуется. Все вводимые понятия детально поясняются на примерах. При самостоятельном изучении рекомендуется читать материал последовательно, так как в каждой главе, за исключением первой, используются понятия и алгоритмы, рассмотренные в предыдущих главах. В конце пособия приведен небольшой библиографический список. В качестве основной литературы рекомендуются классические труды и современные издания. Много дополнительной литературы можно найти в сети Интернет. 12 |