9968
.pdfМинистерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования
«Нижегородский государственный архитектурно-строительный университет»
Прокопенко Н.Ю.
ДИСКРЕТНАЯ МАТЕМАТИКА
Учебно-методическое пособие по подготовке к лекциям, практическим занятиям
(включая рекомендации по организации самостоятельной работы)
для обучающихся по дисциплине «Дискретная математика» по направлению подготовки 09.03.03 Прикладная информатика профиль Прикладная информатика в экономике
Нижний Новгород
2016
УДК 004.9
Прокопенко Н.Ю. / Дискретная математика [Электронный ресурс]: учеб.- метод. пос. / Н.Ю. Прокопенко; Нижегор. гос. архитектур. - строит. ун-т – Н. Новгород: ННГАСУ, 2016. – 181 с.– 1 электрон. опт. диск (CD-RW).
В настоящем учебно-методическом пособии по дисциплине «Дискретная математика» даются конкретные рекомендации учащимся для освоения как основного, так и дополнительного материала дисциплины и тем самым способствующие достижению целей, обозначенных в учебной программе дисциплины. Цель учебно-методического пособия – это помощь в усвоении лекций и в подготовке к практическим занятиям.
Учебно-методическое пособие предназначено для обучающихся в ННГАСУ по дисциплине «Дискретная математика» по направлению подготовки 09.03.03 Прикладная информатика, профиль Прикладная информатика в экономике.
Учебно-методическое пособие ориентировано на обучение в соответствии с календарным учебным графиком и учебным планом по основной профессиональной образовательной программе направления 09.03.03 Прикладная информатика, профиль Прикладная информатика в экономике, утверждённым решением учёного совета ННГАСУ от 02.09.2016 г. (протокол № 1).
© Н.Ю. Прокопенко, 2016 © ННГАСУ, 2016
2
Оглавление
1.Общие положения………………………………………………………………...4
1.1Цели изучения дисциплины и результаты обучения………………………4
1.2Содержание дисциплины…………………………………………………….4
1.3Порядок освоения материала………………………………………………...5
2.Методические указания по подготовке к лекциям……………………………..6
2.1Общие рекомендации по работе на лекциях………………………………..6
2.2Общие рекомендации при работе с конспектом лекций…………………...7
2.3Краткое содержание лекций………………………………………………….8
2.4Контрольные вопросы……………………………………………………….91
3.Методические указания по подготовке к практическим занятиям…………...93
3.1Общие рекомендации по подготовке к практическим занятиям…………93
3.2Примеры задач для практических занятий…………………………...……93
4.Методические указания по организации самостоятельной работы………...114
4.1Общие рекомендации для самостоятельной работы…………………….114
4.2Темы для самостоятельного изучения……………………………………117
4.3. Учебно-методическое обеспечение самостоятельной работы………….118
4.4 Задания для самостоятельной работы…………………………………….118
3
1. Общие положения
1.1 Цели изучения дисциплины и результаты обучения
Основными целями освоения учебной дисциплины «Дискретная математи-
ка» являются: знакомство с основными разделами теории множеств, математи-
ческой логики, теории графов, комбинаторного анализа, развитие логического и алгоритмического мышления, овладение основными методами постановки ма-
тематических задач, которые необходимы для создания и эксплуатации слож-
ных автоматизированных систем обработки информации и их компонент в об-
ласти экономики, математического и программного обеспечения вычислитель-
ной техники, сетей передачи данных и многих других сферах деятельности че-
ловека.
В процессе освоения дисциплины студент должен Знать:
основные понятия, методы, алгоритмы, способы решения задач учебной дисциплины «Дискретная математика»;
описание основных комбинаторных конфигураций; основные свойства комбинаторных объектов и чисел, методы их изучения (теоретико-
множественный, алгебраический, метод рекуррентных соотношений);
основные понятия и определения теории графов, способы представления графов, типы графов и алгоритмы обхода графов;
методы математической логики, основу которых составляют булева ал-
гебра и теория предикатов.
Уметь:
перевести содержательную задачу на теоретико-множественный язык,
найти подходящий метод решения комбинаторной задачи;
применять основные эффективные алгоритмы решения задач теории гра-
фов (алгоритмы нахождения кратчайшего пути, эйлерова и гамильтонова цикла);
упрощать логические формулы, реализующие булевы функции, строить
4
нормальные формы и соответствующие им релейно-контактные схемы,
знать примеры полных и замкнутых систем булевых функций.
Владеть:
техникой решения задач комбинаторного характера и навыками исследо-
вания теоретических проблем комбинаторного анализа;
навыками абстрактных рассуждений, навыками решения логических за-
дач;
навыками решения задач теории графов, связанных с построением графов и подграфов, поиском кратчайших маршрутов, циклов и цепей в графах специального вида и др.
1.2Содержание дисциплины
Материал дисциплины сгруппирован по следующим разделам:
1. Теория множеств и отношений.
Понятие множества и подмножества. Операции над множествами и их свойства. Бинарные отношения и их свойства. Понятие функции. Свойства функций. Отношение порядка, эквивалентности, предпочтения, ранжирования.
2. Комбинаторный анализ.
Правила комбинаторики и основные комбинаторные конфигурации (пере-
становки, размещения, сочетания с повторением и без повторения). Алгебраи-
ческий метод изучения комбинаторных объектов и чисел. Комбинаторные тож-
дества. Бином Ньютона и полиномиальная формула Свойства биномиальных коэффициентов. Теоретико-множественный метод изучения комбинаторных объектов и чисел. Метод включений и исключений.
3. Теория графов.
Основные понятия теории графов. Способы задания графов. Операции над графами. Типы графов. Связность. Компоненты графа. Маршруты, цепи, цик-
лы. Метрические характеристики графа. Эйлеровы и гамильтоновы графы.
Кратчайшие пути и цепи. Деревья и их свойства. Алгоритмы на графах. Двух-
полюсные сети и потоки в сетях.
5
4. Алгебра логики.
Высказывания и операции над ними. Формулы алгебры высказываний,
таблицы истинности, типы формул (выполнимые, опровержимые, тавтологии,
противоречия). Основные эквивалентности. Применение алгебры высказыва-
ний к решению логических задач: упрощение систем рассуждений, проверка правильности рассуждений. Логическое следствие и его свойства. Приложение алгебры высказываний к релейно-контактным схемам (РКС).
5. Булевы функции.
Булевы функции. Совершенные дизъюнктивные и конъюнктивные нор-
мальные формы. Полином Жегалкина. Полнота и замкнутость систем булевых функций. Теорема Поста.
1.3 Порядок освоения материала
Материал дисциплины изучается в соответствии с порядком, определён-
ным в следующей таблице:
Таблица 1
Порядок освоения дисциплины
№ |
Раздел дисциплины |
№№ предшествую- |
|
|
щих разделов |
|
|
|
1 |
Теория множеств и отношений |
- |
|
|
|
2 |
Комбинаторный анализ |
1 |
|
|
|
3 |
Теория графов |
1,2 |
|
|
|
4 |
Алгебра логики |
1,2 |
|
|
|
5 |
Булевы функции |
1,2,4 |
|
|
|
2. Методические указания по подготовке к лекциям
2.1 Общие рекомендации по работе на лекциях
Лекция является главным звеном дидактического цикла обучения. Ее цель
– формирование основы для последующего усвоения учебного материала. В
ходе лекции преподаватель в устной форме, а также с помощью презентаций
6
передает обучаемым знания по основным, фундаментальным вопросам изучае-
мой дисциплины.
Назначение лекции состоит в том, чтобы доходчиво изложить основные положения изучаемой дисциплины, ориентировать на наиболее важные вопро-
сы учебной дисциплины и оказать помощь в овладении необходимых знаний и применения их на практике.
Личное общение на лекции преподавателя со студентами предоставляет большие возможности для реализации образовательных и воспитательных це-
лей.
При подготовке к лекционным занятиям студенты должны ознакомиться с презентаций, предлагаемой преподавателем, отметить непонятные термины и положения, подготовить вопросы с целью уточнения правильности понимания.
Рекомендуется приходить на лекцию подготовленным, так как в этом случае лекция может быть проведена в интерактивном режиме, что способствует по-
вышению эффективности лекционных занятий.
2.2Общие рекомендации при работе с конспектом лекций
Входе лекционных занятий необходимо вести конспектирование учебного материала. Конспект помогает внимательно слушать, лучше запоминать в про-
цессе осмысленного записывания, обеспечивает наличие опорных материалов при подготовке к семинару, зачету, экзамену.
Полезно оставить в рабочих конспектах поля, на которых делать пометки из рекомендованной литературы, дополняющие материал прослушанной лек-
ции, а также подчеркивающие особую важность тех или иных теоретических положений.
В случае неясности по тем или иным вопросам необходимо задавать пре-
подавателю уточняющие вопросы. Следует ясно понимать, что отсутствие во-
просов без обсуждения означает в большинстве случаев неусвоенность матери-
ала дисциплины.
7
2.3 Краткое содержание лекций.
Раздел 1. Теория множеств и отношений – 4 лекции.
Множеством называется совокупность объектов любой природы, кото-
рые объединены в одну группу (систему, совокупность) по тем или иным при-
знакам (множество городов, множество положительных чисел, множество сту-
дентов, множество действительных чисел и т.д.).
Элементы множества – это объекты, которые образуют данное множе-
ство, могут обладать некоторыми свойствами и находиться в некоторых отно-
шениях между собой или с элементами других множеств.
Множество можно задавать перечислением его элементов:
Х х1 , х2 , , xn или характеристическим свойством Х = {х | Р(x)}, где Р(х)
означает, что элемент х обладает свойством P(x).
Способы записи множеств: А= {1, 2, 3, … ,10}, А= {а R |a|1}.
Принадлежность элемента х множеству А записывается, как х А (чи-
тают: элемент х принадлежит множеству А). В противном случае, обозначают
х A (читают: элемент х не принадлежит множеству А).
Множества могут быть конечными и бесконечными.
Множество A={1,2,3,4,5,6,7,8,9,0} цифр в десятичной системе счисления конечно. Множество точек окружности бесконечно.
Число элементов в конечном множестве М называется мощностью М и
обозначается |M|. Пусть задано множество A={x| 5 x 10, x N}, тогда |A|=6,
В={1,5,8,0,1,1,5}, тогда |В|=4.
Элементами множеств могут быть другие множества. Запись А={{x,y},z}
означает, что множество A содержит два элемента: множество {x,y} и элемент z, |A|=2.
Пример 1.1.
A = {D, C}, D={a, b}, C={c, d, e}. При этом D A, C A, но a A и с A.
8
Множество А, все элементы которого принадлежат множеству В, называ-
ется подмножеством множества В.
Обозначение: A B; A B, при этом говорят, что А включено в В.
Нестрогое включение обозначается А В, означает, что А – подмноже-
ство множества В, возможно совпадающее с В. Строгое включение обознача-
ется А В, и означает, что А – подмножество множества В, не совпадающее с B.
Равенство множеств А В означает, по определению, что верны оба включения в ту и другую сторону: А В и В А.
Множество, не содержащее ни одного элемента, называется пустым
множеством и обозначается Ø. Пустое множество является подмножеством любого множества, т.е. А, где А – любое множество.
Пустое множество – это множество, поэтому, если некоторое множество
A не содержит ни одного элемента, то A=; |A|=0. Запись A={ } означает, что
A содержит один элемент – , |A|=1.
Обычно в конкретных рассуждениях элементы всех рассматриваемых множеств берутся из некоторого одного множества U (своего для каждого слу-
чая), которое называется универсальным множеством.
Геометрическая интерпретация множеств – диаграммы Венна
Определение. Объединением множеств А и В называется множество, состоящее из всех тех эле-
ментов, которые принадлежат хотя бы одному из множеств А или В. А В х х А или х В
Определение. Пересечением множеств А и В назы-
вается множество, состоящее из всех тех и только тех элементов, которые принадлежат одновременно как множеству А, так и множеству В.
А В х х А и х В
9
Пример 1.2. Пусть А 1, 2, 3 , |
В 3, 4, 5 . Тогда |
А В 1, 2, 3, 4, 5 , |
А В 3 . |
|
|
Определение. Разностью множеств А и В называ-
ется множество всех тех и только тех элементов А,
которые не содержатся в В. А \ В = { х | х А и х В }.
Определение. Симметрической разностью мно-
жеств А и В называется множество, содержащее либо элементы множества А, либо элементы мно-
жества В, но не те и другие одновременно.
А÷В=( А \ В )( В \ А)={х| х А или х А, но х А В
}
Определение. Дополнением множества А (до уни-
версального множества) называется множество всех тех элементов из U, которые не принадлежат данному множеству А. А U \ A, где U – универ-
сальное множество.
Приоритет операций в алгебре множеств следующий:
1. A 2. А В 3. А В 4. A\B
Свойства операций пересечения, объединения и дополнения над
множествами:
1.Коммутативные законы:
АВ В А
АВ В А
АВ В А
2.Ассоциативные законы
А(В С) (А В) С
А(В С) (А В) С
10