6343
.pdfМИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Нижегородский государственный архитектурно-строительный университет»
Прокопенко Н.Ю.
ДИСКРЕТНАЯ МАТЕМАТИКА
Учебно-методическое пособие
по подготовке к лекциям, практическим занятиям
(включая рекомендации по организации самостоятельной работы),
по выполнению контрольной работы
для обучающихся по дисциплине «Дискретная математика» по направлению подготовки 09.03.04 Программная инженерия
профиль Разработка программно-информационных систем
Нижний Новгород
2022
УДК 004.9
Прокопенко Н.Ю. / Дискретная математика: учебно-методическое пособие / Н.Ю. Прокопенко; Нижегородский государственный архитектурно-строительный университет – Нижний Новгород: ННГАСУ, 2022. – 17 с.– Текст: электронный.
В настоящем учебно-методическом пособии по дисциплине «Дискретная математика» даются конкретные рекомендации учащимся для освоения как основного, так и дополнительного материала дисциплины и тем самым способствующие достижению целей, обозначенных в учебной программе дисциплины. Цель учебно-методического пособия — это помощь в усвоении лекций, в подготовке к практическим занятиям, а также в написании контрольной работы.
Учебно-методическое пособие предназначено для обучающихся в ННГАСУ по дисциплине «Дискретная математика» по направлению подготовки 09.03.04 Программная инженерия, профиль Разработка программно-информационных систем
.
© Н.Ю. Прокопенко, 2022
© ННГАСУ, 2022
2
|
Оглавление |
|
|
1. |
Общие положения .......................................................................................................................... |
4 |
|
|
. 1.1 Цели изучения дисциплины и результаты обучения ......................................................... |
4 |
|
|
. 1.2 Содержание дисциплины ..................................................................................................... |
5 |
|
|
. 1.3 Вспомогательная литература для изучения дисциплины ................................................. |
5 |
|
2. |
Методические указания по подготовке к лекциям ..................................................................... |
7 |
|
|
. 2.1 Общие рекомендации по работе на лекциях ...................................................................... |
7 |
|
|
. 2.2 Общие рекомендации при работе с конспектом лекций ................................................... |
8 |
|
|
. 2.3 Контрольные вопросы .......................................................................................................... |
8 |
|
3. |
Методические указания по подготовке к практическим занятиям ......................................... |
10 |
|
|
. 3.1 Общие рекомендации по подготовке к практическим занятиям.................................... |
10 |
|
|
. 3.2 Примеры задач для практических занятий ....................................................................... |
10 |
|
.4. Методические указания по организации самостоятельной работы....................................... |
13 |
||
|
. 4.1 |
Общие рекомендации для самостоятельной работы ....................................................... |
13 |
|
. 4.2 |
Темы для самостоятельного изучения .............................................................................. |
15 |
5. |
Методические указания по выполнению контрольной работы (Общие рекомендации)...... |
15 |
|
|
. 5.1 |
Общие требования к оформлению контрольной работы ................................................ |
15 |
|
. 5.2 |
Примерные варианты контрольной работы...................................................................... |
16 |
1. Общие положения
. 1.1 Цели изучения дисциплины и результаты обучения
Основной целью освоения учебной дисциплины «Дискретная математика» является дости-
жение результатов обучения, предусмотренных установленным в ОПОП индикаторами достиже-
ния компетенций.
Целями освоения дисциплины являются знакомство с основными разделами теории мно-
жеств, математической логики, теории графов, комбинаторного анализа, развитие логического и алгоритмического мышления, овладение основными методами постановки математических задач,
которые необходимы для создания и эксплуатации сложных автоматизированных систем обработ-
ки информации и их компонент в области экономики, математического и программного обеспече-
ния вычислительной техники, сетей передачи данных и многих других сферах деятельности чело-
века.
В процессе освоения дисциплины студент должен Знать:
основные понятия, методы, алгоритмы, способы решения задач учебной дисциплины «Дис-
кретная математика»;
описание основных комбинаторных конфигураций; основные свойства комбинаторных объектов и чисел, методы их изучения (теоретико-множественный, алгебраический, метод рекуррентных соотношений);
основные понятия и определения теории графов, способы представления графов, типы графов и алгоритмы обхода графов;
методы математической логики, основу которых составляют булева алгебра и теория пре-
дикатов.
Уметь:
перевести содержательную задачу на теоретико-множественный язык, найти подходящий метод решения комбинаторной задачи;
применять основные эффективные алгоритмы решения задач теории графов (алгоритмы нахождения кратчайшего пути, эйлерова и гамильтонова цикла);
упрощать логические формулы, реализующие булевы функции, строить нормальные фор-
мы и соответствующие им релейно-контактные схемы, знать примеры полных и замкнутых
систем булевых функций.
Владеть:
техникой решения задач комбинаторного характера и навыками исследования теоретиче-
ских проблем комбинаторного анализа;
навыками абстрактных рассуждений, навыками решения логических задач;
навыками решения задач теории графов, связанных с построением графов и подграфов, по-
иском кратчайших маршрутов, циклов и цепей в графах специального вида и др.
. 1.2 Содержание дисциплины
Материал дисциплины сгруппирован по следующим разделам:
1. Теория множеств и отношений.
Понятие множества и подмножества. Операции над множествами и их свойства. Бинарные отношения и их свойства. Понятие функции. Свойства функций. Отношение порядка, эквивалент-
ности, предпочтения, ранжирования.
2. Комбинаторный анализ.
Правила комбинаторики и основные комбинаторные конфигурации (перестановки, размеще-
ния, сочетания с повторением и без повторения). Алгебраический метод изучения комбинаторных объектов и чисел. Комбинаторные тождества. Бином Ньютона и полиномиальная формула Свой-
ства биномиальных коэффициентов. Теоретико-множественный метод изучения комбинаторных объектов и чисел. Метод включений и исключений.
3. Теория графов.
Основные понятия теории графов. Способы задания графов. Операции над графами. Типы графов. Связность. Компоненты графа. Маршруты, цепи, циклы. Метрические характеристики графа. Эйлеровы и гамильтоновы графы. Кратчайшие пути и цепи. Деревья и их свойства. Алго-
ритмы на графах. Двухполюсные сети и потоки в сетях.
4. Алгебра логики.
Высказывания и операции над ними. Формулы алгебры высказываний, таблицы истинности,
типы формул (выполнимые, опровержимые, тавтологии, противоречия). Основные эквивалентно-
сти. Применение алгебры высказываний к решению логических задач: упрощение систем рассуж-
дений, проверка правильности рассуждений. Логическое следствие и его свойства. Приложение алгебры высказываний к релейно-контактным схемам (РКС).
Предикаты и операции на произвольных множествах. Множества истинности. Типы преди-
катов. Формулы алгебры предикатов. Основные равносильности.
5. Булевы функции.
Булевы функции. Совершенные дизъюнктивные и конъюнктивные нормальные формы. По-
5
лином Жегалкина. Полнота и замкнутость систем булевых функций. Теорема Поста. 6. Рекурсивно вычислимые функции.
Описание и примеры примитивно и частично-рекурсивных функций. Арифметические функции и операции над ними: суперпозиция, примитивная рекурсия и ограниченный оператор минимиза-
ции.
7. Машина Тьюринга и алгорифмы Маркова.
Математическое понятие алгоритма. Точное определение машины Тьюринга. Конфигурации, про-
токол вычислений и функции вычислимые по Тьюрингу. Эквивалентные машины Тьюринга, син-
тез машин Тьюринга. Нормальные алгорифмы Маркова. Тезис Черча. 8. Теория кодирования
Основные задачи кодирования. Эффективное и помехоустойчивое кодирование. Основные теоремы Шеннона о кодировании. Эффективные коды: код Шеннона–Фано, код Хаффмана, и их характеристики. Методики построения помехоустойчивых кодов: код с проверкой четности, код Хэмминга.
. 1.3 Вспомогательная литература для изучения дисциплины
Для освоения дисциплины обучающийся может использовать печатные и электронные из-
дания и методические материалы, имеющиеся в библиотеке ННГАСУ и/или размещённые в элек-
тронных библиотечных системах (ЭБС), предоставляющих право использования изданий на осно-
вании договорных отношений с университетом, а также иные общедоступные ресурсы сети «Ин-
тернет».
Печатные и электронные издания
1. Алексеев В. Е.. Графы и алгоритмы : Учебное пособие. / Алексеев В. Е., Таланов В. А. ;
В. Е. Алексеев, В. А. Таланов. – Москва, Саратов : Интернет-Университет Информационных Тех-
нологий (ИНТУИТ), Ай Пи Ар Медиа, 2020. – 153 с. – URL: URL: http://www.iprbookshop.ru/89434.html. – ISBN ISBN 978-5-4497-0366-8.
2. Дехтярь, М. И.. Дискретная математика : учебное пособие. / Дехтярь, М. И. ; М. И. Дех-
тярь. – Москва : Интернет-Университет Информационных Технологий (ИНТУИТ), Ай Пи Ар Ме-
диа, 2020. – 181 с. – URL: URL: http://www.iprbookshop.ru/94851.html. – ISBN ISBN 978-5-4497- 0549-5.
3. Дехтярь, М. И.. Сборник задач по множествам, булевым функциям и математической ло-
гике : учебное пособие. / Дехтярь, М. И., Дудаков, С. М., Карлов, Б. Н. ; М. И. Дехтярь, С. М.
Дудаков, Б. Н. Карлов. – Тверь : Тверской государственный университет, 2020. – 128 с. – URL:
6
URL: http://www.iprbookshop.ru/111569.html. – ISBN ISBN 2227-8397.
4. Хоменко, Т. В.. Дискретная математика. Отдельные методы теории множеств и матема-
тической логики. Лабораторный практикум / Хоменко, Т. В. ; Т. В. Хоменко. – Астрахань : Астра-
ханский государственный архитектурно-строительный университет, ЭБС АСВ, 2020. – 111 с. –
URL: URL: http://www.iprbookshop.ru/100830.html. – ISBN ISBN 978-5-93026-104-2.
5. Яковлев, В. П.. Практикум по дискретной математике. Ч.II : учебное пособие. / Яковлев,
В. П., Леонова, Н. Л. ; В. П. Яковлев, Н. Л. Леонова. – Санкт-Петербург : Санкт-Петербургский государственный университет промышленных технологий и дизайна, 2020. – 39 с. – URL: URL: https://www.iprbookshop.ru/118409.html. – ISBN ISBN 2227-8397.
Методические материалы по дисциплине
1.Прокопенко Наталья Юрьевна. Дискретная математика : учеб.-метод. пособие по подгот.
клекциям, практ. занятиям (включая рекомендации по орг. самостоят. работы) для обучающихся по дисциплине "Дискрет. математика по направлению подгот. 09.03.03 Приклад. информатика,
профиль Приклад. информатика в экономике. / Прокопенко Наталья Юрьевна ; Нижегор. гос. ар-
хит.-строит. ун-т. – Нижний Новгород : ННГАСУ, 2016. – 1 CD ROM. – URL: URL: http://catalog.nngasu.ru/MarcWeb2/.
2.Прокопенко Наталья Юрьевна. Дискретная математика : учеб.-метод. пособие по подгот.
клекциям, практ. занятиям (включая рекомендации по организации самостоят. работы) для обу-
чающихся по дисциплине "Дискретная математика" по направлению подгот. 09.03.04 Программ-
ная инженерия, профиль Разработка программно-информ. систем. / Прокопенко Наталья Юрьевна
; Нижегор. гос. архит.-строит. ун-т. – Нижний Новгород : ННГАСУ, 2018. – 1 CD ROM. – URL: URL: http://catalog.nngasu.ru/MarcWeb2/.
2. Методические указания по подготовке к лекциям
. 2.1 Общие рекомендации по работе на лекциях
Лекция является главным звеном дидактического цикла обучения. Ее цель – формирование основы для последующего усвоения учебного материала. В ходе лекции преподаватель в устной форме, а также с помощью презентаций передает обучаемым знания по основным, фундаменталь-
ным вопросам изучаемой дисциплины.
Назначение лекции состоит в том, чтобы доходчиво изложить основные положения изуча-
емой дисциплины, ориентировать на наиболее важные вопросы учебной дисциплины и оказать помощь в овладении необходимых знаний и применения их на практике.
При подготовке к лекционным занятиям студенты должны ознакомиться с презентаций,
7
предлагаемой преподавателем, отметить непонятные термины и положения, подготовить вопросы с целью уточнения правильности понимания. Рекомендуется приходить на лекцию подготовлен-
ным, так как в этом случае лекция может быть проведена в интерактивном режиме, что способ-
ствует повышению эффективности лекционных занятий.
. 2.2 Общие рекомендации при работе с конспектом лекций
В ходе лекционных занятий необходимо вести конспектирование учебного материала. Кон-
спект помогает внимательно слушать, лучше запоминать в процессе осмысленного записывания,
обеспечивает наличие опорных материалов при подготовке к семинару, зачету, экзамену.
Полезно оставить в рабочих конспектах поля, на которых делать пометки из рекомендован-
ной литературы, дополняющие материал прослушанной лекции, а также подчеркивающие особую важность тех или иных теоретических положений.
В случае неясности по тем или иным вопросам необходимо задавать преподавателю уточ-
няющие вопросы. Следует ясно понимать, что отсутствие вопросов без обсуждения означает в большинстве случаев неусвоенность материала дисциплины.
. 2.3 Контрольные вопросы
1.Множества. Способы задания множеств. Равные множества. Свойства включения. Сравнимость множеств.
2.Операции над множествами и их свойства. Диаграммы Эйлера-Венна.
3.Подмножества. Разбиения. Булеан множеств и его мощность.
4.Прямое произведение и его свойства.
5.Бинарные отношения и их свойства.
6.Отображения (функции) и их свойства.
7.Отношение эквивалентности и отношение порядка. Примеры.
8.Основные комбинаторные правила: правило произведения и правило сложения.
9.Перестановки с повторениями и без повторений.
10.Размещения с повторениями и без повторений.
11.Сочетания с повторениями и без повторений.
12.Треугольник Паскаля и Бином Ньютона.
13.Свойства биномиальных коэффициентов.
14.Метод включения и исключения.
15.Полиномиальная формула. Полиномиальные коэффициенты.
8
16.Ориентированные и неориентированные графы, маршруты, цепи, циклы, пути и контуры графов.
17.Представления графов матрицей смежности, матрицей инцидентности, списком ребер.
18.Ориентированные графы и их виды. Связь с бинарными отношениями.
19.Подграфы. Операции над графами.
20.Метрические соотношения в графах.
21.Эйлеровы и полуэйлеровы графы. Критерий эйлеровости графа.
22.Гамильтоновы графы. Достаточные условия гамильтоновых графов.
23.Эйлеровы и гамильтоновы цепи, циклы, пути, контуры.
24.Деревья, лес. Свойства деревьев.
25.Обходы графов: поиск в ширину и поиск в глубину.
26.Построение остова минимального веса: алгоритмы Прима и Краскала.
27.Минимальные пути в нагруженных графах. Алгоритм Дейкстры.
28.Определение логических операций.
29.Формулы алгебры логики. Основные законы алгебры логики.
30.Логическое следствие и его свойства.
31.Способы доказательства правильности рассуждений.
32.Решение логических задач.
33.Двойственные формулы. Теорема двойственности.
34.Применение алгебры логики к релейно-контактным схемам. Упрощение РКС.
35.Булевы функции их количество.
36.Представление булевой функции в совершенной нормальной дизъюнктивной форме.
37.Представление булевой функции в совершенной нормальной конъюнктивной форме.
38.Представление булевой функции в виде полинома Жегалкина.
39.Замыкание множеств булевых функций. Основные классы булевых функций Т 0 , Т1 ,S, M, L,
их замкнутость.
40.Полнота систем булевых функций. Теорема Поста.
41.Оператор минимизации.
42.Нормальные формы, свойства монотонности, самодвойственности, линейности,
принадлежности классам T0 и T1.
43.Класс примитивно рекурсивных функций. Тезис Черча.
44.Арифметические функции и операции над ними: суперпозиция, примитивная рекурсия.
45.Описание и примеры примитивно-рекурсивных функций. Ограниченная сумма и
произведение примитивно-рекурсивных функций.
9
46.Основные теоремы Шеннона о кодировании. Эффективные коды: код Шеннона–Фано
47.Помехоустойчивое кодирование.
48.Код Хаффмана и его характеристики.
49.Различные модели источников сообщений: дискретные, непрерывные. Информационные характеристики источников: энтропия, избыточность.
50.Описание нормальных схем алгоритма Маркова.
3. Методические указания по подготовке к практическим занятиям
. 3.1 Общие рекомендации по подготовке к практическим занятиям
В ходе подготовки к практическим занятиям необходимо изучать основную литературу, по-
знакомиться с дополнительной литературой. При этом необходимо учесть рекомендации препода-
вателя и требования учебной программы.
В соответствии с этими рекомендациями и подготовкой полезно дорабатывать свои конспек-
ты лекции, делая в нем соответствующие записи из литературы, рекомендованной преподавателем и предусмотренной учебной программой. Целесообразно также подготовить тезисы для возмож-
ных выступлений по всем учебным вопросам, выносимым на практическое занятие.
При подготовке к занятиям можно также подготовить краткие конспекты по вопросам темы.
Очень эффективным приемом является составление схем и презентаций.
Готовясь к докладу или реферативному сообщению, желательно обращаться за методической помощью к преподавателю. Составить план-конспект своего выступления. Продумать примеры с целью обеспечения тесной связи изучаемой теории с реальной жизнью. Своевременное и каче-
ственное выполнение самостоятельной работы базируется на соблюдении настоящих рекоменда-
ций и изучении рекомендованной литературы.
. 3.2 Примеры задач для практических занятий
1. Для заданных множеств А 1, 2, 4 , В 1, 2, 3, 5,6 , С 3, 4, 9 нужно проверить пра-
вильность следующих утверждений:
a)А \ В А С
b)А С В С
c)А С В \ С
d)А В А \ С
e)С \ А А В
10