Учебно-методический комплекс по дисциплине дискретная математика Специальность
| скачать ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА государственное образовательное учреждение высшего профессионального образования «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ» (МИИТ) УТВЕРЖДЕНО: Проректором по учебно-методической работе – директором РОАТ «_27_» _____10___20 г. Кафедра Высшая и прикладная математика Автор Сперанский Д.В. УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ПО ДИСЦИПЛИНЕ Дискретная математика Специальность: 220100 «Вычислительные машины, комплексы, системы и сети (ЭВМ)».
Москва 2010 г. Автор-составитель: Сперанский Д.В., доктор технических наук, профессор кафедры «Высшая и прикладная математика» Учебно-методический комплекс по дисциплине «Дискретная математика» составлен в соответствии с требованиями Государственного образовательного стандарта высшего профессионального образования по специальности: 220100 «Вычислительные машины, комплексы, системы и сети (ЭВМ)». Дисциплина входит в федеральный компонент цикла математических и естественнонаучных дисциплин и является обязательной для изучения. ^ государственное образовательное учреждение высшего профессионального образования ^ ПУТЕЙ СООБЩЕНИЯ» (МИИТ)
Кафедра Высшая и прикладная математика Автор Сперанский Д.В., д.т.н., проф. ^ Дискретная математика Специальность: 220100 «Вычислительные машины, комплексы, системы и сети (ЭВМ)»
Москва 2010г. ^ 1.1. Целью дисциплины «Дискретная математика» является изучение указанных в рабочей программе глав дискретной математики, необходимых при изучении дисциплин, входящих в учебный план по специальности 220100 «Вычислительные машины, комплексы, системы и сети (ЭВМ)». Изучение дискретной математики способствует развитию логического и алгоритмического мышления студентов, освоению ими приемов исследования и решения математически формализованных задач, выработке умения самостоятельно проводить анализ прикладных задач и расширять в случае необходимости свои математические знания. 1.2. Задачи изучения дисциплины. Изучив дисциплину, студент должен: 1.2.1. Знать базовые понятия дискретной математики. 1.2.2. Владеть основами комбинаторики, теории множеств, теории графов, теории конечных автоматов и теории кодирования. 1.2.3. Уметь решать типовые задачи. 1.2.4. Иметь представление об использовании полученных знаний при решении инженерных задач. ^ 2.1. Элементы комбинаторики. Перестановки, размещения и сочетания. Бином Ньютона. Свойства биномиальных коэффициентов. Полиномиальная формула. Понятие о комбинаторном анализе. Литература: [1; 2]. ^ их спецификации. Понятие множества. Четкие множества и нечеткие подмножества. Операции над четкими множествами. Диаграммы Эйлера-Венна. Степень принадлежности элемента множеству. Операции над нечеткими подмножествами. Нечеткое включение и равенство множеств. Четкие конечные множества и нечеткие подмножества. Число подмножеств данного четкого конечного множества. Упорядоченные четкие конечные множества. Множество всех нечетких подмножеств и его свойства. Четкие алгебраические структуры (группы, кольца и поля). Нечеткие алгебраические структуры (нечеткий группоид и нечеткий моноид). Нечеткая внешняя композиция. Литература: [1; 2; 3; 7; 10; 12; 13]. ^ Четкие и нечеткие отношения на множествах. Четкие бинарные отношения и их свойства. Отображения множеств. Специальные бинарные отношения (эквивалентности, порядка, доминирования). Проекция нечеткого отношения. Носитель нечеткого отношения. Свойства нечетких бинарных отношений. Симметрия, рефлективность, транзитивность. Нечеткие отношения предпорядка, подобия, асимметрии, порядка, сходства и различия и их свойства. Литература: [1; 2; 6; 8; 10; 11; 12]. ^ Предмет теории четких и нечетких графов. Четкие неориентированные и ориентированные графы. Задание четких графов с помощью матриц. Цепи и циклы в четких графах. Достижимость и связность в четких графах. Операции над четкими графами. Деревья и прадеревья. Свойства деревьев. Древовидные структуры. Цикломатическое число графа. Разбиения и обходы графов. Эйлеровы и гамильтоновы графы. Плоские и пленарные графы. Формула Эйлера. Матрицы смежности и инцидентности для четких графов. Нечеткие графы. Основные свойства и характеристики. Задание нечетких графов с помощью матриц. Маршруты в четких конечных и нечетких графах. Транспортные сети. Задача о наибольшем потоке. Приложения четких и нечетких графов в вычислительных алгоритмах. Литература: [1; 2; 3; 4; 8; 13; 14; 15]. ^ Понятие нечеткого числа. Операции над нечеткими числами. Нечеткие целые положительные числа. Экспоненциальные, геометрические и гауссовы нечеткие целые числа и их свойства. Литература: [9; 13; 14]. ^ Определение кода. Прямые, обратные и дополнительные коды. Коды с исправлением ошибок. Линейные коды. Матричное кодирование. Коды Хемминга и групповые коды. Литература: [1; 7]. ^ Различные подходы к определению конечного автомата: микроподход и макроподход. Виды конечных автоматов. Функция перехода. Функция выхода. Способы описания конечного автомата: таблица состояний, диаграмма состояний. Примеры конечных автоматов. Минимизация конечного автомата. Литература: [1; 2; 11]. ^ Курс — II, семестр — III. Всего часов — 140 ч. Лекционные занятия— 8 ч. Практические занятия —12 ч. Число контрольных работ — 1. Самостоятельная работа — 105 ч. Экзамен— 1.     Литература
^ Методические указания предназначены для студентов II курса специальности ЭВМ. Для решения задач контрольной работы необходимы некоторые теоретические сведения, которые представлены перед типовым решением каждой упомянутой задачи. Для глубокого изучения теоретического материала и развития навыков по решению задач в конце методических указаний приведен список рекомендуемой литературы. Задание № 1 Следующая формула называется биномом Ньютона:  . (1)Числа  в этой формуле называются биномиальными коэффициентами и равны количеству различных k–элементных подмножеств n–элементного множества. Вычисление биноминальных коэффициентов осуществляется по формуле , где  .Отметим, что в каждом из k-элементных подмножеств порядок расположения его элементов безразличен. Каждая такая комбинация называется сочетанием из n элементов по k. Например, найдем число всех сочетаний из 5 элементов a, b, c, d, e по три:  .Перечислим эти сочетания: abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde. Пример 1. В разложении  найти член, содержащий  .По формуле (1) находим, что этот член имеет вид  . Степень b равна 4, так как сумма степеней произведения  должна равняться n (в нашем примере n=10, n– i =6, i=4). Таким образом получаем:  .Пример 2. В разложении  найти члены, содержащие  .Введем следующие обозначения:  и  . Тогда исходный бином примет вид  . Ясно, что член, содержащий в исходном биноме, равен члену нового бинома, содержащего  . Легко видеть, что этот член таков: .Задание № 2 Понятие множества является основным, неопределяемым понятием, поэтому мы можем его только пояснить: под множеством ^ понимается любое собрание определенных и различимых между собой объектов, мыслимое как единое целое. Эти объекты называются элементами множества S. Множества A и B считаются равными, если они состоят из одних и тех же элементов. Этот факт записывается A=B. Если A и B различны, то это записывается  .Множество, элементами которого являются объекты a, b, c,…,z и только они, обозначают  . Порядок расположения объектов в этой записи не имеет значения.Конечное множество можно описать простым перечислением его элементов. Описание многоэлементных или бесконечных множеств обычно основано на интуитивном понятии «формы от x» (обозначается  ). Для множества A, определяемого формой , принято обозначение  .Например, множество  можно описать, используя форму , в виде « x – положительное целое число, меньшее 9».А={x | x – положительное целое число, меньшее 9}. Для получения новых множеств из уже существующих используются различные операции. Определим некоторые из них. Объединением множеств А и В называется множество  , все элементы которого являются элементами множеств А или В:  .Здесь символ «  » обозначает принадлежность элемента множеству.Пересечением множеств А и В называется множество  , элементы которого являются элементами обоих множеств А и В:  .Дополнением множества А до множества Х называется множество всех тех элементов множества Х, которые не принадлежат множеству А:  .Поясним эти определения на примерах. Пусть заданы три следующих множества:  ,  ,  .Тогда  ,  ,  .Обычно принято считать, что все рассматриваемые множества являются подмножествами некоторого универсального множества U. Для наглядного представления отношений между подмножествами универсального множества используются диаграммы Эйлера-Венна. В этом случае множества обозначаются областями на плоскости и внутри этих областей условно располагаются элементы множества. Если элемент принадлежит более чем одному множеству, то на диаграмме области, отвечающие таким множествам, должны перекрываться, чтобы общий элемент мог одновременно находиться в соответствующих областях. Проиллюстрируем определенные выше операции на диаграммах.  А В       Пример 1. Проверить тождество с помощью диаграмм Эйлера-Венна:  .Для решения задачи сначала (возможно поэтапно) построим с помощью диаграмм множество, стоящее в левой части множества. Затем аналогичное построение выполним для правой части тождества. Если полученные в результате этих построений диаграммы совпадут, то тождество справедливо. Для нашего примера диаграмма множества левой части тождества такова: Для правой части тождества имеем: В А     Поскольку диаграммы множеств для обеих частей тождества совпадают, то тождество справедливо. Пример 2. Проверить тождество  . Пусть исходные множества таковы:А В С  Выполним поэтапно операции для левой части тождества:  А В С     Выполним поэтапно операции для правой части тождества:  В С  А     Поскольку диаграммы множеств для обеих частей тождества совпадают, то тождество справедливо. Задание №3 Для характеристики принадлежности любого элемента множества  некоторому его подмножеству А введем так называемую характеристическую функцию Так, например, если  , то  Расширим понятие принадлежности элемента х множества его подмножеству А, считая, что  может принимать любые значения на отрезке [0,1]. Такое подмножество (его обозначают  ) называется нечетким и записывается в виде перечня элементов  , входящих в это подмножество. Величину  называют степенью принадлежности элемента х подмножеству А и записывают в виде  . Введем операции над нечеткими подмножествами. Объединением нечетких подмножеств и  называется нечеткое подмножество  такое, что для любого х из  .Пересечением нечетких подмножеств и называется нечеткое подмножество  такое, что для любого х из  .Два нечетких подмножества  и  называют взаимно дополнительными, если  для всех x из E. В этом случае пишут  или  .Дизъюнктивной суммой нечетких подмножеств и , обозначаемой  , называется подмножество  .Проиллюстрируем эти операции на примерах. Пример 1. Пусть  .  .Для этих нечетких подмножеств получаем:  , , , , , , .Пример 2. Пусть  .  .Для этих нечетких подмножеств получаем:  , , , , .Задание №4 Пусть задано универсальное конечное множество E и два нечетких его подмножества  и  , содержащие по n элементов. Расстоянием Хемминга между этими подмножествами назовем число  , (2)где  – элементы и (i=1,…,n).Понятно, что для любых подмножеств и справедливо неравенство  .Обычное (четкое) подмножество A будем называть ближайшим к нечеткому подмножеству , если для него  Обычное (четкое) подмножество  будем называть подмножеством  -уровня  нечеткого подмножества  , если  Проиллюстрируем приведенные выше понятия на примерах. Пример 1. Пусть универсальное множество E содержит 6 элементов  . Пусть заданы два его нечетких подмножества , .Найдем расстояние Хемминга между этими подмножествами, используя формулу (2):  Найдем ближайшие четкие подмножества к нечетким подмножествам и : ,  .Найдем ближайшие четкие подмножества  -уровня (пусть  ) к нечетким подмножествам и :  ,  .Пример 2. Пусть универсальное множество  . Пусть его нечеткие подмножества и таковы: , Найдем расстояние Хемминга между этими подмножествами:  Найдем ближайшие четкие подмножества к нечетким подмножествам и : ,  .Найдем ближайшие четкие подмножества -уровня при  к нечетким подмножествам и :  ,  .Задание №5 Пусть даны два множества  и  . Декартовым произведением множеств X и Y (обозначается  ) называется множество всевозможных пар вида  , где  , а  .Нечетким графом  будем называть матрицу, соответствующую нечеткому подмножеству элементов  с функцией принадлежности  . Пусть, например,  и  . Тогда  . Если функция принадлежности  имеет значения      ,  то она определяет нечеткое подмножество  , которое можно представить в виде следующей матрицы:  Представленная матрица и является нечетким графом .Понятие декартова произведения  двух множеств очевидным образом обобщается на n множеств:  . Тогда нечетким графом называют матрицу, соответствующую нечеткому подмножеству элементов  с функцией принадлежности  , где  Нечетким n-арным отношением называется нечеткое подмножество множества  , значения которых принадлежат множеству ^ , определенному выше.Например, нечеткое бинарное отношение (n=2) множеств и может задаваться следующей матрицей: Понятно, что этому нечеткому отношению соответствует конечный нечеткий граф.Введем понятие проекции нечеткого отношения. Первой проекцией нечеткого отношения в  называется максимум функции принадлежности  .Второй проекцией нечеткого отношения в называется максимум функции принадлежности  .Глобальной проекцией  нечеткого отношения  в называется вторая проекция первой проекции (или наоборот – первая проекция второй): .Носителем  нечеткого отношения называют четкое множество упорядоченных пар , для которых функция принадлежности отлична от нуля.Проиллюстрируем введенные понятия на примере. Пример. Пусть нечеткое отношение задано матрицей Для этой матрицы получаем следующие результаты:  , , , , , .Аналогично получаем вторую проекцию:  ;  ;  .Наконец, вычислим глобальную проекцию заданного нечеткого отношения:   .Определим носитель нечеткого отношения, заданного приведенной матрицей. Поскольку здесь единственная пара  имеет нулевое значение функции принадлежности, то носителем рассматриваемого отношения будут все остальные пары декартова произведения , число которых равно 17.Задание №6 Любой конечный автомат может быть задан тремя различными способами:
Все перечисленные виды задания автоматов эквивалентны между собой и выбираются, исходя из удобства применения для конкретной ситуации. Переход от одной формы задания автомата к любой другой осуществляется достаточно просто. В качестве примера проиллюстрируем переход от задания автомата с помощью таблиц переходов и выходов к заданию этого автомата с помощью диаграмм (или, что то же самое, графов). Пусть  – множество состояний автомата,  и  – входной и выходной алфавиты соответственно,  и  – функции выходов и переходов автомата  . Функционирование автомата с использованием таблиц переходов и выходов задается следующим образом:
К примеру, записи во второй строке таблицы переходов  означают следующее: если автомат находится в состоянии  и на его вход подается входной сигнал  , то он переходит в следующее состояние  . Записи во второй строке таблицы выходов  означают, что при подаче на вход автомата входного символа  он, осуществив переход из состояния в состояние , выдаст выходной сигнал  , где  Опишем теперь способ перехода от этого способа задания автомата к заданию с помощью диаграммы (графа). Граф этот имеет столько вершин, сколько состояний имеет автомат. Каждая вершина графа взаимно-однозначно соответствует некоторому состоянию. Будем считать, что вершина графа помечена символом соответствующего ей состояния. Если на пересечении  ой строки (она соответствует состоянию  ) и m-го столбца таблицы переходов (он соответствует входному сигналу  ) стоит состояние  , то на диаграмме из вершины проводится стрелка в вершину . Далее над этой стрелкой надписывается пара , где  - входной сигнал автомата, а  -выходной сигнал, стоящий на пересечении l-ой строки и m-го столбца таблицы выходов. Аналогичные действия осуществляются для всех других пар  . Полученный в результате граф и является графом (или диаграммой) этого автомата.Пример. Пусть автомат задан следующими таблицами переходов и выходов:
Здесь  ,  ,  .Диаграмма переходов автомата, заданного этой таблицей, имеет следующий вид:  ^ Действующая с 2002 года по настоящее время программа по дисциплине «Дискретная математика» содержит 7 разделов. Что касается раздела « 2.6. Элементы теории кодирования», то он дублирует знания, которые освоить студенты по дисциплине «Теория информации и кодирования». По этой причине этот раздел из программы по дискретной математике целесообразно исключить. Остальные разделы программы содержат вопросы, касающиеся как четких, так и нечетких объектов и связанных с ними понятий (множества, подмножества, отношения, графы). Для студентов специальности ЭВМ существенно востребованными являются знания по классическим (четким) объектам и понятиям. Именно эти понятия широко применяются при логическом проектировании дискретных устройств, их минимизации, анализе архитектуры устройств и т.п. К сожалению, в российской инженерной практике в настоящее время почти не используются понятия, связанные с нечеткими объектами. В связи с этим при освещении вопросов дисциплины «Дискретная математика» основное внимание следует уделить «четким» объектам и понятиям. Сведения о «нечетких» объектах безусловно расширяют кругозор студентов и в этом отношении не яляются бесполезными, но не более того. Среди всех прочих разделов программы разделы 2.1. Элементы комбинаторики, 2.2. Обычные (четкие) множества и нечеткие подмножества, их спецификации, 2.3. Обычные (четкие) отношения , 2.5. Нечеткая арифметика следует рассматривать как вспомогательные. Центральными с точки зрения возможности практического приложения являются разделы 2.4. Теория обычных (четких) и нечетких графов и 2.7. Элементы тории конечных автоматов. Так, методы теории графов имеют широкие приложения в задачах размещения компонентов на плате, трассировки путей, задачах оптимального размещения компонетов устройств по критерию минимальности числа каналов , связывающих эти компоненты, и т.п. Что касается теории автоматов, то она имеет широкие приложения при логическом проектировании дискретных устройств. Отметим прежде всего, что автоматы (как абстрактные, так и структурные) используются в качестве моделей реальных цифровых устройств. На основе использования таких моделей решаются задачи оптимизации структур дискретных устройств, их контролепригодного проектирования, и т.п. Особо следует отметить приложения теории автоматов к проблемам технической диагностики дискретных устройств, где эта теория служит базой для разработки методов диагностики и контроля современных устройств , изготовленных с использование БИС, СБИС и микропроцессоров. Изложенные обстоятельства дают основания рекомендовать акцентировать внимание преподавателей на изложении в рамках установочных лекций упомянутых двух разделов программы. Отмети также и еще одно обстоятельство. В последнее десятилетие возникло и успешно развивается новое направление прикладного характера, именуемое автоматным программированием. В рамках этого нового перспективного направления разрабатываются методы эффективного создания современных программных систем. С момента введения в действие в 2002 году обсуждаемой учебной программы по дисциплине «Дискретная математика» прошло более 8 лет, поэтому список литературы (как основной, так и дополнительный) нуждается в обновлении. В методических указаниях для студентов по специальности ЭВМ по выполнению контрольных работ, изданных кафедрой в 2009 году, булла указана новая современная литература из пяти наименований. Особо следует отметить полезность еще одной монографии для студентов именно этой специальности – Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Логические основы проектирования дискретных устройств.-М.: ФИЗМАТЛИТ, 2007.- 592 с. В ней последовательно вводятся базовые понятия всех разделов существующей рабочей программы. ^ Экзаменационные билеты Билет № 1 1.Элементы комбинаторики: перестановки, размещения и сочетания. Основное правило комбинаторики. 2.Определение конечного автомата. Способы задания автоматов. Постановка задачи минимизации автомата и метод ее решения. 3.Задачи. а) Имеется 10 различных книг для подарков. Сколькими способами можно скомпоновать комплекты из 3 книг? б) Имеется дискретное устройство, осуществляющее суммирование по модулю 3 единичных импульсов , поступающих на его вход. Построить математическую модель этого устройства в виде конечного автомата. Билет № 2
Дано бинарное отношение ρ на множестве всех подмножеств универсального множества : {А, В}   А В. Показать, что ρ есть отношение порядка и определить его тип.Билет №3 1.Понятие множества. Операции над множествами .Способы задания множеств. Понятие равномощности множеств. Счетные множества. Привести примеры. 2.Определение ориентированного и неориентированного графов. Способы их задания. Матрицы смежности и инциденций. Понятия достижимости и связности в графах. Определение графа-дерева и его свойства. Проиллюстрировать упомянутые понятия примерами. 3.Задача. Даны множества Х={1,2,3,4,5} и его разбиение П={1,2.3}, {4,5}. Построить отношение эквивалентности, которое определяется этим разбиением. Билет №4 1.Нечеткие множества. Степень принадлежности элемента множеству. Способы задания нечетких множеств. Операции над нечеткими множествами. Равенство нечетких множеств. Графическое изображение нечетких множеств. 2.Понятие эйлеровых и гамильтоновых графов. Примеры таких графов. Необходимое и достаточное условие существования эйлерова обхода графа. Плоские и полные графы. 3.Задача. На множестве жителей города N бинарное отношение  : (х, у)  N× N «х родственник у ». Проверить, является ли это отношение отношением эквивалентности. Если да, то построить класс эквивалентности, порожденный элементом «Иванов».Билет №5 1.Определение нечеткого графа. Нечеткие n- арные отношения. Маршрут и длина маршрута в нечетком графе. 1-я и 2-я глобальные проекции нечеткого отношения. Определения объединения, пересечения и алгебраического произведения нечетких отношений. 2.Определение отношения частичного и линейного порядка на множестве Х. Привести примеры таких отношений. 3. Задача. Дискретное устройство осуществляет суммирование по модулю 5 единичных импульсов, поступающих на его вход .Построить математическую модель этого устройства в виде конечного автомата. Билет №6 1.Элементы теории графов : Определение ориентированного и неориентированного графов. Способы их задания. Матрицы смежности и инциденций. Понятия достижимости и связности в графах. Сильно связные графы. Определение графа-дерева и графа-леса и их свойства. Проиллюстрировать упомянутые понятия примерами. 2.Элементы теории кодирования: определение линейного кода. Порождающая и проверочная матрицы линейного кода. Пример линейного кода. 3.Задача. Пусть А={1,2,3}. На множестве всех подмножеств множества А задано бинарное отношение  : (х,у)  Доказать, что есть отношение эквивалентности найти все его классы эквивалентности.Билет №7 1.Определить понятие стационарного потока в сети. Сформулировать задачу о максимальном потоке. Описать алгоритм решения задачи о максимальном потоке. 2.Определить понятие бинарного отношения эквивалентности и описать его свойства. Привести примеры отношений эквивалентности. Понятие класса эквивалентности, порожденного элементом a  X, где X – множество , на котором задано отношение эквивалентности.3.Задача. Даны множества A = {x׀x делится на 2}, В = { x׀x делится на 3},где A и В- подмножества множества N – натуральных чисел. Найти множества A⋃ B, A⋂B, A – B, В –А. Билет №8 1. Дать определение бинарного отношения частичного и линейного порядков, свойства этих отношений. Привести примеры соответствующих отношений. 2.Элементы кодирования : Определение кода. Код с исправлением ошибок. Код с обнаружением ошибок. Привести примеры таких кодов. Условие существования упомянутых выше кодов в терминах кодового расстояние. 3.Задача. Разложить выражение  , используя полиномиальную формулу.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
хорошо
1 