Дискретная математика
Покупка
Новинка
Тематика:
Дискретная математика
Издательство:
Директ-Медиа
Год издания: 2025
Кол-во страниц: 253
Возрастное ограничение: 16+
Дополнительно
Вид издания:
Учебно-методическая литература
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-4499-5111-3
Артикул: 891187.01.99
В учебно-методическом пособии изложены основные сведения по дискретной математике. Учебно-методическое пособие содержит расширенный материал лекций по дисциплине «Дискретная математика», предусмотренных учебным планом и рабочей программой дисциплины.
Учебно-методическое пособие предназначено для студентов всех форм обучения направления 09.03.01 «Информатика и вычислительная техника» направленности (профиля) «Автоматизированные системы обработки информации и управления».
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Дискретная математика Учебно-методическое пособие для студентов направления подготовки 09.03.01 «Информатика и вычислительная техника» Москва 2025
УДК 004.023 ББК 32.973.02 Д48 Д48 Дискретная математика : учебно-методическое пособие / сост. Н. Ю. Шабанова, О. А. Ефремова, А. Д. Михед. — Москва : Директ-Медиа, 2025. — 252 с. ; ил. ISBN 978-5-4499-5111-3 В учебно-методическом пособии изложены основные сведения по дискретной математике. Учебно-методическое пособие содержит расширенный материал лекций по дисциплине «Дискретная математика», предусмотренных учебным планом и рабочей программой дисциплины. Учебно-методическое пособие предназначено для студентов всех форм обучения направления 09.03.01 «Информатика и вычислительная техника» направленности (профиля) «Автоматизированные системы обработки информации и управления». УДК 004.023 ББК 32.973.02 ISBN 978-5-4499-5111-3 © Шабанова Н. Ю., Ефремова О. А., Михед А. Д., сост., 2025 © Издательство «Директ-Медиа», оформление, 2025
Оглавление Введение ................................................................................................... 7 Часть 1. Множества и отношения .......................................................... 13 1.1. Множества ................................................................................... 13 1.1.1. Элементы и множества ........................................................ 14 1.1.2. Задание множества ............................................................... 16 1.1.3. Основные определения и понятия ....................................... 17 1.1.4. Парадокс Рассела.................................................................. 21 Контрольные вопросы и упражнения ........................................... 21 1.2. Операции над множествами ........................................................ 22 1.2.1. Сравнение множеств ............................................................ 22 1.2.2. Операции над множествами................................................. 22 1.2.2.1. Предварительные замечания ........................................ 22 1.2.2.2. Объединение множеств ................................................. 24 1.2.2.3. Пересечение множеств .................................................. 25 1.2.2.4. Разность множеств ........................................................ 28 1.2.2.5. Универсальное множество ............................................ 29 1.2.2.6. Дополнение множества ................................................. 30 1.2.2.7. Разбиение множества .................................................... 33 1.2.2.8. Законы (тождества) алгебры множеств ........................ 34 1.2.2.9. Аксиомы теории множеств ........................................... 35 Контрольные вопросы и упражнения ........................................... 37 1.3. Упорядоченное множество. Прямое произведение множеств. Проекции ..................................... 37 1.3.1. Упорядоченные множества .................................................. 37 1.3.2. Прямое произведение множеств .......................................... 39 1.3.3. Проекция множества ............................................................ 41 1.3.4. Кортеж кортежей .................................................................. 42 1.3.5. Характеристический вектор множества .............................. 42 Контрольные вопросы и упражнения ........................................... 43 1.4. Соответствия ............................................................................... 43 1.4.1. Определение соответствия ................................................... 43 1.4.2. Обратное соответствие ......................................................... 46 1.4.3. Композиция соответствий .................................................... 47 Контрольные вопросы ................................................................... 49 1.5. Отображения ................................................................................ 49 1.5.1. Свойства отображений ......................................................... 50 1.5.2. Отображения, заданные на одном множестве .................... 50
Контрольные вопросы ................................................................... 52 1.6. Функция ....................................................................................... 53 1.6.1. Обратная функция ................................................................ 56 1.6.2. Функция времени ................................................................. 56 1.6.3. Принцип Дирихле................................................................. 57 1.6.4. Представление функции в компьютере ............................... 58 Контрольные вопросы ................................................................... 59 1.7. Понятие функционала ................................................................. 59 Контрольные вопросы ................................................................... 61 1.8. Понятие оператора ...................................................................... 61 Контрольные вопросы ................................................................... 62 1.9. Отношения ................................................................................... 62 1.9.1. Общие сведения ................................................................... 62 1.9.2. Свойства отношений ............................................................ 64 1.9.3. Представление отношений в компьютере. Матрицы бинарных отношений. Специальные бинарные отношения .............................................. 66 1.9.4. Отношения эквивалентности ............................................... 68 1.9.5. Отношение порядка .............................................................. 70 1.9.5.1. Решетки ......................................................................... 72 1.9.5.2. Диаграммы Хассе .......................................................... 73 1.9.6. Отношение доминирования ................................................. 74 1.9.7. Отношения в базах данных (БД).......................................... 74 1.9.7.1. Характеристика моделей данных ................................. 74 1.9.7.2. Реляционная модель базы данных ................................ 76 Контрольные вопросы ................................................................... 85 1.10. Нечеткие множества .................................................................. 86 1.10.1. Общие сведения.................................................................. 86 1.10.2. Операции над нечеткими множествами ............................ 87 1.10.3. Нечеткое включение и равенство множеств. Нечеткое бинарное отношение ...................................................... 94 1.10.4. Нечеткая и лингвистическая переменные ......................... 97 Контрольные вопросы ................................................................. 102 1.11. Приложения теории множеств ................................................ 102 1.11.1. Система управления базами данных ............................... 102 1.11.2. Применение нечётких множеств ..................................... 108 Контрольные вопросы ................................................................. 110 Литература ........................................................................................ 110
Часть 2. Элементы теории графов ....................................................... 111 2.1. Основные сведения из теории графов ...................................... 112 2.1.1. История теории графов ...................................................... 113 2.1.2. Теоретико-множественное определение графа, основные понятия и определения ............................................... 116 2.1.3. Операции над графами ....................................................... 124 2.1.4. Математические структуры для представления графов ... 126 2.1.4.1. Матрицы ...................................................................... 126 2.1.4.2. Решение проблемы поиска путей в сетях с помощью вычисления матрицы достижимости по алгоритму Уоршелла .......................................................... 132 Контрольные вопросы и задачи .................................................. 136 2.1.4.3. Списки смежности ...................................................... 137 2.1.4.4. Массив дуг ................................................................... 140 2.1.5. Деревья ............................................................................... 141 2.1.6. Лес. Разрезы ........................................................................ 142 2.1.7. Эйлеровы и гамильтоновы графы...................................... 147 2.1.8. Изоморфизм графов ........................................................... 148 Контрольные вопросы и задачи .................................................. 150 2.1.9. Отношения порядка и эквивалентности на графе ............. 157 Контрольные вопросы ................................................................. 159 2.2. Транспортные сети .................................................................... 160 2.2.1. Нахождение максимального потока .................................. 161 2.2.2. Транспортная задача .......................................................... 165 2.3. Алгоритмы работы с графами ................................................... 167 2.3.1. Алгоритмы анализа графов ................................................ 167 2.3.1.1. Алгоритмы обхода графа ............................................ 167 2.3.2. Алгоритмы оптимизации ................................................... 169 2.3.2.1. Поиск кратчайших путей ............................................ 170 2.3.2.2. Алгоритмы управления проектами ............................ 170 Контрольные вопросы ................................................................. 172 2.4. Некоторые практические задачи ............................................... 172 2.4.1. Поиск гамильтонова цикла ................................................ 172 2.4.2. Раскраска графа .................................................................. 174 2.4.3. Задача о кратчайшем пути между двумя вершинами графа ......................................................................... 176 2.4.3.1. Алгоритм поиска кратчайшего пути .......................... 176 2.4.3.2. Алгоритм Прима ......................................................... 179 2.4.3.3. Задачи с деревьями...................................................... 181 2.4.4. Использование алгоритма Дейкстры при решении задачи оптимизации передачи сообщений в коммуникационных сетях ......................................................... 191
2.4.5. Система ПЕРТ .................................................................... 196 Литература ........................................................................................ 200 Часть 3. Элементы алгебры логики ..................................................... 201 3.1. Введение в алгебру логики ....................................................... 201 3.2. Основные функции алгебры логики ......................................... 203 3.3. Формулы алгебры логики ......................................................... 207 Контрольные вопросы ................................................................. 209 3.4. Законы алгебры логики и следствия из них ............................ 209 Контрольные вопросы ................................................................. 212 3.5. Логические функции многих переменных ............................... 212 3.6. Построение формул алгебры логики по заданной таблице истинности ......................................................................... 213 Контрольные вопросы и упражнения ......................................... 221 3.7. Некоторые замкнутые классы (классы Поста). Понятие базиса ................................................................................. 222 Контрольные вопросы и упражнения ......................................... 229 3.8. Методы минимизации логических функций ............................ 229 Контрольные вопросы ................................................................. 234 3.9. Неполностью определенные логические функции ................. 235 3.10. Формы представления булевых функций ............................... 235 3.10.1. Семантические деревья .................................................... 235 3.10.2. Бинарные диаграммы решений (БДР) ............................. 236 3.11. Построение логических схем .................................................. 237 Контрольные вопросы ................................................................. 240 3.12. Логические конечные автоматы ............................................. 240 3.12.1. Процессы .......................................................................... 240 3.12.2. Конечные автоматы .......................................................... 241 3.12.2.1. Конечные автоматы без памяти (комбинационные) ................................................................... 244 3.12.2.2. Конечные автоматы с памятью (последовательностные) .......................................................... 247 Контрольные вопросы ................................................................. 250 Литература ........................................................................................ 250
Введение Интерес к дискретной математике вполне понятен. Он объясняется постоянно растущей в последние десятилетия потребностью в ней в связи с развитием широких областей её применения, повсеместно курсы дискретной математики входят в программы обучения будущих специалистов по информационным технологиям. Содержание изучаемого материала ориентировано на студентов, обучающихся по специальности 23010265, содержит большое количество примеров. В программе курса предусмотрено изучение элементов теории множеств, основных понятий теории графов, переключательных (логических) функций, схем алгоритмов. Предполагается, что студент не испытывает затруднений в понимании текстов программ, составленных на языках высокого уровня, в частности Object Pascal. Дискретная математика имеет широкий спектр приложений в областях, связанных с информационными технологиями и компьютерами. Самым первоначальным (ныне редко использующимся) названием компьютера было «электронная цифровая вычислительная машина». Слово «цифровая» указывает на принципиально дискретный характер работы данного устройства [5]. Дискретная математика — бурно развивающаяся в XX веке ветвь математики. Её роль и место определяются в основном тремя факторами: • дискретную математику можно рассматривать как теоретические основы компьютерной математики; • модели и методы дискретной математики являются хорошим средством и языком для построения и анализа моделей в различных науках, включая химию, биологию, генетику, физику, психологию, экологию и другие; • язык дискретной математики чрезвычайно удобен и стал фактически метаязыком всей современной математики. Математика как наука, естественно, от рождения делится на дискретную и континуальную математику. Что мы относим к континуальной математике? Все, что явно или неявно содержит идеи теории пределов и непрерывности. Все остальное — дискретная математика (т. е. арифметика, алгебра, теория множеств
и общая теория отображений, математическая логика, комбинаторный анализ, теория алгоритмов и многое другое). Предмет дискретная математика Дискретная математика (дискретный анализ, конечная математика) — это раздел математики, занимающийся изучением свойств объектов конечного характера. К их числу могут быть отнесены конечные группы, конечные графы, некоторые математические модели преобразователей информации, такие как конечные автоматы. Дискретный анализ — раздел математики, занимающийся изучением свойств структур конечного характера, которые возникают как внутри математики, так и в её приложениях. В качестве синонима понятий дискретный анализ и дискретной математики иногда употребляют термин «конечная математика». В отличие от дискретного анализа классическая математика в основном занимается изучением свойств объектов непрерывного характера. Использование классической или дискретной математики как аппаратов исследования связано с задачами, которые ставит перед собой исследователь, и с тем, какую модель изучаемого явления он рассматривает — дискретную или непрерывную. Дискретность (происходит от латинского слова discretus) — «разделённый, прерывистый». Дискретное изменение какой-либо величины во времени — это изменение, происходящее через некоторые промежутки времени (скачками). Деление математики на классическую и дискретную в значительной мере условно, поскольку, например, с одной стороны, происходит активная циркуляция идей и методов между ними, а с другой стороны, часто возникает необходимость исследования моделей, обладающих как дискретными, так и непрерывными свойствами одновременно. Следует отметить, что в математике существуют направления, использующие средства дискретной математики для изучения непрерывных моделей, и наоборот, часто средства и постановки задач классического анализа используются при исследовании дискретных структур. Это указывает на известное слияние рассматриваемых областей.
(Возьмите множество всех подмножеств эталонного дискретного множества — множества натуральных чисел, и вы получите мощность базового для традиционного математического анализа множества — множества действительных чисел.) Специфика методов и задач дискретного анализа обусловлена, в первую очередь, необходимостью отказа от основополагающих понятий классической математики — предела и непрерывности — и в связи с этим тем, для многих задач дискретного анализа сильные средства классической математики оказываются, как правило, мало приемлемыми. Некоторые сведения из истории предмета Элементы дискретного анализа возникли в глубокой древности и развивались параллельно с другими разделами математики, в значительной мере являлись их составной частью. Типичными для этого периода являлись задачи, связанные со свойствами целых чисел и приведшие затем к созданию теории чисел. К их числу могут быть отнесены задачи отыскания алгоритмов сложения и умножения натуральных чисел у древних египтян (2-е тысячелетие до н. э.), задачи суммирования и задачи о делимости натуральных чисел в пифагорейской школе (V–IV век до н. э.). Позже появились элементы комбинаторного анализа и дискретной теории вероятности, а в связи с общими проблемами теории чисел, алгебры и геометрии (XVIII– XIX век) возникли важнейшие понятия алгебры, определившие её развитие, и имевшие дискретную природу. Стремление к строгости математических рассуждений и анализ рабочего инструмента математики — логики — привели к выделению ещё одного важного раздела в математике — математической логики (XIX век). Однако наибольшего развития дискретная математика достигла в связи с запросами практики, приведшими к появлению новой науки — кибернетики и её теоретической части — теоретической кибернетики. (Норберт Винер — основоположник кибернетики.) Теоретическая кибернетика широко использует результаты дискретного анализа при решении задач. Анализ понятий «вычислимость» и «алгоритм» привели к созданию раздела математической логики — теории алгоритмов.
Экономические задачи, задачи электротехники, равно как и внутренние задачи математики, потребовали разработки теории графов. Задачи конструирования и описания работы сложных управленческих систем привели к теории функциональных систем. Наряду с уже отличительными свойствами дискретная математика имеет ещё ряд особенностей. Вместе с задачами, имеющими общий математический характер, важное место в дискретном анализе занимают задачи построения конкретных решающих алгоритмов. В некоторых параграфах в качестве нотаций для описания алгоритмов будем использовать некоторый не специфицированный язык программирования, похожий по синтаксису на Pascal [5]. В программах широко используются математические обозначения, которые являются самоочевидными в некотором контексте. Например: For M x ∈ do ) (x P End for Читаем, как применение какой-то процедуры P ко всем элементам x, принадлежащим множеству М. Оператор Select M m∈ читаем, как выбор произвольного элемента m из множества М. Этот оператор часто используется, например, в алгоритмах «перебора». Оператор Yield x означает возврат значения x, но при этом выполнение функции не прекращается, а продолжается со следующего оператора. Обозначение : = — «по определению» или «положим». В табл. 1 представлены некоторые общепринятые обозначения. В настоящее время популярным становится термин компьютерная математика, введённый американскими исследователями Куком Д. и Бейзом Г. Многие разделы дискретной математики причислены к компьютерной математике.