Дискретная математика: основы теории и практикум
Покупка
Основная коллекция
Тематика:
Дискретная математика
Издательство:
Инфра-Инженерия
Автор:
Бунаков Павел Юрьевич
Год издания: 2025
Кол-во страниц: 292
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-9729-2406-6
Артикул: 867083.01.99
Содержит материалы по отдельным разделам дискретной математики: теории множеств, комбинаторике, дискретной теории вероятностей, теории графов, теории алгоритмов и теории конечных автоматов. Имеет практическую направленность и помимо теоретических сведений включает задачи для решения и лабораторные работы по программированию на языке Python. Особое внимание уделяется разбору примеров решения задач и написания программ, а также самостоятельной работе обучающихся, для чего каждая тема сопровождается дополнительными заданиями. Для студентов высших учебных заведений, изучающих основы дискретной математики. Будет полезно студентам средних специальных учебных заведений, школьникам старших классов и всем интересующимся вопросами дискретной математики и программирования.
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Ƕ ȅ ǨȚȔȇȑȕȉ ǫǯǸDZǷǬǹǴǧȆ dzǧǹǬdzǧǹǯDZǧ ǵǸǴǵǩȂ ǹǬǵǷǯǯ ǯ ǶǷǧDZǹǯDZǺdz ǺȞȌȈȔȕȌ ȖȕȘȕȈȏȌ dzȕȘȑȉȇ ǩȕȒȕȊȋȇ ªǯȔțȗȇ-ǯȔȍȌȔȌȗȏȦ« 2025
УДК 519.854 ББК 22.17 Б91 Р е ц е н з е н т ы : доктор технических наук, профессор, профессор кафедры вычислительной и прикладной математики Рязанского государственного радиотехнического университета им. В. Ф. Уткина Белов Владимир Викторович; доктор технических наук, профессор, профессор кафедры автоматизации производства и информационных технологий Коломенского института (филиала) Московского политехнического университета Романов Петр Сергеевич Бунаков, П. Ю. Б91 Дискретная математика: основы теории и практикум : учебное пособие / П. Ю. Бунаков. – Москва ; Вологда : Инфра-Инженерия, 2025. – 292 с. : ил., табл. ISBN 978-5-9729-2406-6 Содержит материалы по отдельным разделам дискретной математики: теории множеств, комбинаторике, дискретной теории вероятностей, теории графов, теории алгоритмов и теории конечных автоматов. Имеет практическую направленность и помимо теоретических сведений включает задачи для решения и лабораторные работы по программированию на языке Python. Особое внимание уделяется разбору примеров решения задач и написания программ, а также самостоятельной работе обучающихся, для чего каждая тема сопровождается дополнительными заданиями. Для студентов высших учебных заведений, изучающих основы дискретной математики. Будет полезно студентам средних специальных учебных заведений, школьникам старших классов и всем интересующимся вопросами дискретной математики и программирования. УДК 519.854 ББК 22.17 ISBN 978-5-9729-2406-6 Бунаков П. Ю., 2025 Издательство «Инфра-Инженерия», 2025 Оформление. Издательство «Инфра-Инженерия», 2025
ǵǪDzǧǩDzǬǴǯǬ Введение .............................................................................................................................. 5 1. Множества ...................................................................................................................... 8 1.1. Кванторы и специальные математические символы .......................................... 8 1.2. Основные понятия теории множеств .................................................................... 9 1.3. Способы задания множеств ................................................................................. 11 1.4. Операции над множествами ................................................................................ 13 1.5. Покрытие множества ............................................................................................ 18 1.6. Отображения, соответствия и отношения множеств ........................................ 19 1.7. Способы задания отношений............................................................................... 26 1.8. Практическая часть ............................................................................................... 27 1.9. Лабораторный практикум .................................................................................... 35 Вопросы для повторения ............................................................................................ 42 2. Комбинаторика ............................................................................................................. 44 2.1. Основные понятия комбинаторики ...................................................................... 45 2.2. Перестановки, сочетания и размещения ............................................................ 47 2.3. Биноминальные коэффициенты .......................................................................... 51 2.4. Практическая часть ............................................................................................... 54 2.5. Лабораторный практикум .................................................................................... 58 Вопросы для повторения ............................................................................................ 62 3. Математическая логика ............................................................................................... 64 3.1. Логика высказываний ........................................................................................... 65 3.2. Логические операции над высказываниями ............................................................ 65 3.3. Булевы функции .......................................................................................................... 67 3.4. Нормальные формы .................................................................................................... 70 3.5. Карты Карно .......................................................................................................... 74 3.6. Логический базис .................................................................................................. 78 3.7. Практическая часть ............................................................................................... 84 3.8. Лабораторный практикум .................................................................................... 90 Вопросы для повторения ............................................................................................ 95 4. Дискретная теория вероятностей ............................................................................... 96 4.1. События ................................................................................................................. 97 4.2. Алгебра событий ................................................................................................. 101 4.3. Вероятность события .......................................................................................... 102 4.4. Условная вероятность события и умножение вероятностей .......................... 111 4.5. Сложение вероятностей ..................................................................................... 113 4.6. Формула полной вероятности ........................................................................... 117 4.7. Формула Байеса .................................................................................................. 119 4.8. Повторные независимые испытания................................................................. 123
4.9. Дискретные случайные величины .................................................................... 128 4.10. Числовые характеристики дискретных случайных величин ....................... 131 4.11. Практическая часть ........................................................................................... 136 4.12. Лабораторный практикум ................................................................................ 154 Вопросы для повторения .......................................................................................... 167 5. Основы теории графов ............................................................................................... 169 5.1. Основные понятия теории графов .................................................................... 170 5.2. Типы графов ........................................................................................................ 173 5.3. Операции над графами ....................................................................................... 175 5.4. Способы задания графов .................................................................................... 177 5.5. Связность графов ................................................................................................ 180 5.6. Деревья ................................................................................................................. 185 5.7. Поиск путей в графе ........................................................................................... 189 5.8. Циклы в графе ..................................................................................................... 191 5.9. Поиск кратчайших путей в графе ..................................................................... 196 5.10. Практическая часть ........................................................................................... 202 5.11. Лабораторный практикум ................................................................................ 220 Вопросы для повторения .......................................................................................... 243 6. Теория алгоритмов ..................................................................................................... 244 6.1. Формальное определение и свойства алгоритма ............................................. 244 6.2. Способы представления алгоритмов ................................................................ 248 6.3. Типы моделей алгоритмов ................................................................................. 250 6.3.1. Алгоритмические машины ......................................................................... 250 6.3.2. Нормальный алгоритм Маркова ................................................................ 252 6.3.3. Рекурсивные функции ................................................................................ 255 6.4. Рекурсивные функции ........................................................................................ 258 6.5. Лямбда-исчисление ............................................................................................ 260 6.6. Введение в теорию сложности алгоритмов ..................................................... 266 6.7. Практическая часть ............................................................................................. 269 Вопросы для повторения .......................................................................................... 278 7. Введение в теорию конечных автоматов ................................................................. 279 7.1. Основные понятия .............................................................................................. 279 7.2. Автоматное программирование ........................................................................ 283 7.3. Лабораторный практикум .................................................................................. 286 Вопросы для повторения .......................................................................................... 289 Библиографический список .......................................................................................... 290
ǩǩǬǫǬǴǯǬ Дискретной математикой называют область математики, которая изучает дискретные (от лат. discretus – разделённый) объекты и структуры, которые состоят из отдельных, неделимых и чётко обособленных друг от друга элементов. Сам термин стал употребляться в науке, начиная с 50-х годов XX века, хотя научная дисциплина, имеющая дело с дискретными объектами, появилась намного раньше. По сути, с момента зарождения математики и до XVII века, когда появились математические методы изучения движения (непрерывного процесса, который нельзя разбить на отдельные дискретные элементы1), математика была дискретной. С древних времен до нас дошли описания задач, которые сегодня назвали бы комбинаторно-логическими задачами. Для их решения необходимо перебирать различные комбинации дискретных объектов, логически анализируя каждую из них. Многие из таких задач сохранились до настоящего времени и успешно используются в качестве логических головоломок. В качестве примера приведем задачу о перевозчике, автором которой считается англо-саксонский учёный и богослов Алкуин, живший более 1200 лет назад. Суть ее в том, что перевозчик должен перевезти через реку волка, козу и капусту, но в лодке кроме него может поместиться только кто-то один, а оставшись на берегу вдвоем волк съедает козу, а коза – капусту. Для нахождения решения надо перебрать и проанализировать все варианты действий перевозчика. В данной задаче их количество невелико, поэтому решение находится достаточно быстро. Однако во многих реальных задачах количество вариантов может быть очень большим, соответственно, нахождение решения, если не удается сократить перебор, может потребовать длительного времени, даже при работе на высокопроизводительных компьютерах. К дискретным устройствам относятся и известные с древности такие вычислительные приспособления, как абак2 и счеты, современным аналогом которых являются калькуляторы (от англ. calculus – камешек). 1 Иллюстрацией невозможности дискретного подхода к изучению движения может служить известный парадокс, или апория (логически верная ситуация, которая не может существовать в реальности), об Ахиллесе и черепахе. Согласно ей Ахиллес никогда не догонит черепаху, если в начальный момент времени она будет находиться впереди него. Насколько быстро бы не шел Ахиллес, за то время, пока он преодолеет начальное расстояние между ним и черепахой, она успеет отползти на некоторое расстояние. За то время, пока Ахиллес будет преодолевать это расстояние, черепаха опять отползет, и так далее. 2 Абак – простейшее счетное устройство, представляющее собой доску с прорезями, в которых можно перемещать камешки, или другие предметы. Его история насчитывает более пяти тысяч лет. Как показывают археологические раскопки, абак применялся практически на всей обитаемой суше.
Вторым рождением дискретной математики можно считать середину XIX века, когда появились исследования в области теории множеств (работы немецких математиков Рихарда Дедекинда и Георга Кантора), математической логики (английский математик и логик Джордж Буль), теории графов (математик и механик Леонард Эйлер3) и других дисциплин, имеющих дело с дискретными объектами. Особенно бурно дискретная математика стала развиваться в XX веке, когда возникли такие научные направления, как кибернетика, информатика, теория алгоритмов, программирование и другие, а также появились средства вычислительной техники. Компьютеры и другие цифровые устройства с одной стороны создаются на основе отдельных разделов дискретной математики, а с другой стороны сами являются эффективным инструментом для проведения новых научных исследований. Одной из характерных особенностей современной дискретной математики является отсутствие единого математического ядра и широкий спектр научных направлений. Для исследования непрерывных процессов есть дифференциальное и интегральное исчисления, которые позволяют единообразно описывать процессы, имеющие самую различную физическую природу. В дискретной математике подобной универсальной теоретической базы нет, поэтому в каждом из ее разделов используются свои методы и подходы. В широком смысле дискретная математика включает в себя такие разделы математики, как абстрактная алгебра, теория чисел, математическая логика, дискретная теория вероятностей, комбинаторика, теория графов, теория алгоритмов, теория автоматов, теория формальных грамматик и языков и целый ряд других. Она составляет математическую основу современной информатики и других компьютерных наук. Таким образом, содержание конкретного курса по дискретной математике во многом определяется будущей специальностью студентов. Данное пособие базируется на курсе «Дискретная математика», который автор ведет в Государственном социально-гуманитарном университете для будущих учителей информатики. Учебная программа специальности предусматривает значительный объем дисциплин, связанных с программированием. Это объясняется просто: для развития современного общества требуется большое количество специалистов в области информационных технологий и, прежде всего, программистов. Одна из важнейших задач учителя информатики заключается, по мнению автора, в том, чтобы заинтересовать школьников этим направлением будущей профессиональной деятельности. Обладая широкими знаниями и навыками, он сможет эффективно вести раннюю профориентационную работу. По этой причине в пособие включены те разделы дискретной математики, которые имеют непосредственную связь с программированием. Под этим подразумевается, что объектам их изучения соответствуют прямые 3 Леонард Эйлер – швейцарский, российский и прусский математик, внёсший огромный вклад в развитие математики, механики, физики и астрономии. Он по праву считается одним из величайших математиков в истории человечества. Почти половину жизни Эйлер жил и работал в России.
аналоги в языках программирования, либо используемые в них методы допускают эффективные алгоритмические решения. Это теория множеств, комбинаторика, дискретная теория вероятностей, теория графов, теория алгоритмов и теория конечных автоматов. Пособие имеет практическую направленность, поэтому каждый раздел состоит из трех частей: основные теоретические сведения, задачи для практического решения и лабораторные работы по программированию на языке Python в соответствующей области. Сам язык программирования подробно не рассматривается. Предполагается, что читатель знаком с основами алгоритмизации и программирования на языке Python, поэтому каждая работа предваряется лишь краткими сведениями о тех инструментах языка, которые необходимы для ее выполнения.
dzǴǵǭǬǸǹǩǧ DZȉȇȔșȕȗȢ ȏ ȘȖȌȝȏȇȒȣȔȢȌ ȓȇșȌȓȇșȏȞȌȘȑȏȌ ȘȏȓȉȕȒȢ В различных математических теоремах, утверждениях, аксиомах очень часто можно встретить одинаковые фразы, например, «тогда и только тогда», «любой», «существует», «единственный» и так далее. Вспомним теорему о существовании действительных корней квадратного уравнения: квадратное уравнение имеет действительные корни тогда и только тогда, когда его дискриминант неотрицателен. Еще два примера: 1. В любой треугольник можно вписать окружность. 2. Через две любые пересекающиеся прямые можно провести единственную плоскость. Для краткой и понятной записи высказываний о математических объектах и соотношениях между ними существуют специальные обозначения – кванторы, заменяющие часто встречающиеся фразы. Первоначально они использовались в логике, но постепенно стали общематематическими обозначениями. Поясним смысл кванторов на примерах: 1. Квантор всеобщности – . Запись n = 1, 2, ... обозначает, что некоторое утверждение справедливо для любого натурального числа. 2. Квантор существования – . Рассмотрим теорему о существовании суммы двух натуральных чисел: для любых двух натуральных чисел существует третье число, равное их сумме. Объединив два рассмотренные квантора, ее можно записать так: x = 1, 2, 3, …, y = 1, 2, 3, …, z = x + y. Обозначения кванторов представляют собой перевернутые первые буквы английских слов Any (любой) и Exists (существует). Помимо кванторов в математике широко используются специальные символы: 1. Единственность – !. Чаще всего он употребляется совместно с квантором существования. Предыдущую теорему надо дополнить уточнением о том, что сумма двух натуральных чисел не только существует, но и является единственной: x = 1, 2, 3, …, y = 1, 2, 3, …, ! z = x + y. 2. Принадлежность – . Если совокупность всех положительных вещественных чисел обозначить через R+, то теорему о логарифме произведения двух положительных чисел можно записать кратко: x, yR+: logaxy = logax logay.
3. Непринадлежность – . Обозначив совокупность неположительных вещественных чисел через R–, предыдущую теорему можно переписать иначе: x, yR–: logaxy = logax logay. 4. Конкретный выбор – или запятая. Символы используются вместо союза и при связке двух утверждений. 5. Альтернативный выбор – . Символ используется вместо союза или при связке двух утверждений. 6. Конкретизация – | или двоеточие. Символы заменяют фразы типа такой что ..., при условии... и аналогичные. 7. Следственность – . Символ предназначен для замены конструкций вида если … то …или из ... следует .... Рассмотрим известную теорему: если взять два любых положительных рациональных числа r1 и r2, таких что r1 < r2, то всегда можно найти третье положительное рациональное число r3, такое что r1<r3<r2. Переведем ее на язык кванторов и математических символов, обозначив совокупность рациональных чисел через Q: r1Q r2Q: r1 > 0 r2 > 0 r3Q r3 > 0: r1 < r3 < r2 8. Равносильность – . Символ заменяет конструкции вида... тогда и только тогда, когда…, ... в том и только в том случае... и им подробные. Запишем символически признак равенства треугольников по трем сторонам: ǻA1B1C1 = ǻ A2B2C2 A1B1 = A2B2 A1C1 = A2C2 C1B1 = C2B2. В любой математической литературе, включая и настоящее учебное пособие, в большинстве определений, утверждений и теорем используются символические обозначения. С одной стороны, это придает им компактность и наглядность, а, с другой стороны, приучает читателя мыслить логически, что необходимо, в том числе, и при разработке программ на алгоритмических языках. Очень важно уметь видеть за последовательностью обозначений смысл «зашифрованного» утверждения, а также «переводить» словесные утверждения на язык кванторов и символов. ǵȘȔȕȉȔȢȌ ȖȕȔȦșȏȦ șȌȕȗȏȏ ȓȔȕȍȌȘșȉ Множество – это одно из основных понятий математики, которое широко используется в физике, истории, химии, социологии и многих других науках. В математике оно является неопределимым, первичным понятием, которое нельзя определить через более простые понятия. Смысл первичных понятий должен быть очевиден. Аналогичными понятиями являются, например, точка или прямая. Удачное описание множества впервые дал известный немецкий математик Георг Кантор, который по праву считается создателем теории множеств.
В одной из своих работ он написал: «Множество есть многое, мыслимое нами
как единое». Это практически в точности совпадает с современным определением множества.
Определение. Множеством ܺ = {ݔ1, ݔ2, ..., ݔ݊} называется совокупность отличных друг
от друга объектов, объединенных по некоторому признаку.
Конкретизируем это определение. Во-первых, природа элементов множества не имеет значения. Это может быть множество чисел, студентов, букв
русского алфавита и т. д. С математической точки зрения все они элементы
множества. Во-вторых, имеется некоторый признак, в соответствии с которым
все мыслимые объекты разделяются на две части: принадлежащие множеству
и не принадлежащие ему. Возьмем множество студентов некоторого университета. Для любого человека планеты Земля, можно точно сказать, принадлежит он этому множеству или нет: достаточно взять список студентов этого
университета. В-третьих, внутри множества каждый элемент уникален, т. е.
в примере со студентами университета одного студента от другого всегда
можно отличить по номеру студенческого билета.
В рассмотренных примерах факт принадлежности или не принадлежности
элемента множеству является бесспорным, поскольку границы множества четко
описаны. Соответственно, множества такого рода называются четкими множествами, и в классической теории рассматриваются именно они. Однако в
1965 году американский математик азербайджанского происхождения Лотфи
Заде ввел понятие нечетких множеств, у которых границы «размыты», и вопрос
о принадлежности элемента множеству решается с некоторой вероятностью.
В настоящее время теория нечетких множеств используется в задачах экономического анализа, при оценках инвестиционных рисков, в бизнес-аналитике и т. д.
Как правило, множества обозначаются большими буквами латинского алфавита, причем некоторые буквы зарезервированы за конкретными множествами, например, N – множество натуральных чисел, Z – множество целых чисел, Q – множество рациональных чисел, R – множество действительных чисел.
Определение. Элемент множества – это любой объект, входящий в состав множества.
Факт принадлежности объекта x к множеству X обозначается следующим образом x X.
Определение. Мощностью множества Х (обозначается ŇXŇ) называется количество
элементов в нем.
В зависимости от количества элементов множества бывает конечными и
бесконечными. С практической точки зрения интерес представляют конечные
множества, которые и будут рассматриваться в данном пособии. Если ŇXŇ = n,
где n – натуральное число, то множество X часто называют n-множеством.