WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Государственное образовательное учреждение высшего профессионального образования САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ ДИСКРЕТНАЯ МАТЕМАТИКА Программа, методические указания и контрольное задание для самостоятельной работы студентов 2004 Составитель кандидат технических наук, доцент Л. А. Прокушев Рецензент кандидат технических наук, доцент В. П. Попов Приведены программа, методические указания и контрольные задания для самостоятельного изучения курса “Дискретная математика”.

Предназначены для студентов заочной формы обучения по специальности 2203 “Системы автоматизированного проектирования”.

Подготовлены к публикации кафедрой компьютерных систем автоматизации и рекомендованы к изданию редакционно-издательским советом Санкт-Петербургского университета аэрокосмического приборостроения.

© ГОУ ВПО СПбГУАП, 2004 Подписано к печати..04. Формат 6084 1/16. Бумага офсетная. Печать офсетная.

Усл. печ. л.. Уч. -изд. л.. Тираж экз. Заказ № Редакционно-издательский отдел Отдел электронных публикаций и библиографии библиотеки Отдел оперативной полиграфии СПбГУАП 190000, Санкт-Петербург, ул. Б. Морская, 67 ПРЕДИСЛОВИЕ Программа по учебной дисциплине «Дискретная математика» разработана в соответствии с требованиями государственного образовательного стандарта высшего профессионального образования. Изучение курса базируется на знаниях, полученных в результате освоения дисциплин «Высшая математика» и «Информатика».

Цели и задачи курса:

– ознакомить с основами таких направлений дискретной математики, как теория множеств, теория графов и теория булевых функций;

– дать представление о теоретических основах и методах дискретной математики как математических моделях для описания и исследования объектов реального мира, полезных для решения инженерных задач.

В результате изучения дисциплины студенты должны:

– получить представление о понятиях и теоретических моделях изучаемых направлений дискретной математики;

– освоить приемы применения теоретических моделей для описания предлагаемых заданий и получения результатов;

– приобрести практические навыки по отработке формализованных описаний объектов методами дискретной математики.

Лекционные занятия по данной дисциплине являются установочными, базовыми – для самостоятельной работы студентов. Каждый студент выполняет контрольную работу и проходит лабораторный практикум, завершающийся зачетом. Знания теории и практики программирования проверяются на экзамене.

Объем дисциплины Виды учебной работы Всего часов Семестр Общая трудоемкость 121 дисциплины Аудиторные занятия 36 Лекции 8 Лабораторные работы (ЛР) 16 Окончание таблицы Виды учебной работы Всего часов Семестр Индивидуальная работа с 12 преподавателем Самостоятельная работа 85 Контрольная работа Вид итогового контроля экз.

(зачет, экзамен...) 1. СОДЕРЖАНИЕ КУРСА ДИСЦИПЛИНЫ Раздел 1. Множества и их спецификации Понятие множества; основные понятия теории множеств; операции над множествами; декартово произведение; диаграммы Эйлера–Венна;

алгебра множеств.

Литература: [1, c. 5, 6].

Интуитивное понятие множества: множество есть любое собрание определенных и различимых между собой объектов нашей интуиции или интеллекта, мыслимое как единое целое. Эти объекты называются элементами, или членами множества. Множества обозначаются прописными латинскими буквами (A, B, C, …), а их элементы – строчными (a, b, c, …). Множество как совокупность дискретных объектов обозначается A = {a, b, c}. Можно использовать индексы: А1, А2, …; а1, а2, … Множества могут быть конечными (группа студентов) или бесконечными (натуральные числа). Множества, элементами которых являются тоже множества, называют классом (семейством, системой) множеств.

Для конечного множества А = {а1, a2,…, an} количество элементов n называется мощностью множества и обозначается |A| (|A| = n). По конкретному элементу а и множеству А всегда можно определить, принадлежит элемент а множеству А (а А) или не принадлежит (a A ).

Множество, состоящее из одного элемента, обозначается {a}. Множество, не содержащее элементов, называется пустым и обозначается (например, А = ).

Операции над множествами позволяют получить новые множества.

Вложенность множеств (подмножество, надмножество): операция.

Пусть А = {а, b}, B = {a, b, c}, тогда А В (А есть подмножество В, т. е. А вложено, содержится в В; В есть надмножество над А, т. е. В содержит А).

Объединение множеств: операция (сумма). Пусть А = {a, b}, B = ={b, c}, тогда А В = {a, b, c} (все элементы множеств А и В без повторения элементов).

Пересечение множеств: операция. Пусть А = {a, b}, B = {b, c}, тогда A B = {b} (элементы общие для множеств А и В).

Дополнение множеств: операция \ (разность). Пусть A = {a, b}, B = ={b, c}, тогда A \ В = {a} (все элементы множества А, не принадлежащие В, т. е. из А вычитаются элементы, общие с В).

Симметрическая разность: операция –. Пусть А = {a, b, c}, B = {a, c, d}, тогда А – В = {b, d} (все элементы А, не принадлежащие В, и все элементы В, не принадлежащие А).

Равенство множеств: операция =. A = B справедливо тогда и только тогда, когда A B и B A.

Справедливы отношения: A B A, A B B, A A B, B A B.

Например, если A B, B C, то A C, поэтому из приведенных выше соотношений следует, что A B A B. Справедливы также формулы дистрибутивности: (A B) C = (A B) (B C), (A B) C = (A C) (B C).

Диаграммы Эйлера–Венна иллюстрируют операции над множествами, что будет показано при объяснении контрольного задания.



Булеаном называется множество всех подмножеств множества М и обозначается В(М), а множество М называется универсумом, или универсальным. Каждое множество М имеет, по крайней мере, два различных элемента: само М и. Пусть М = {x, y, z}, тогда его булеан В(М) = {, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, M}. Мощность булеана от универсума |B(M)| = 2|M |. Например |M| = 3, |B(M)| = 23 = 8.

Алгебра множеств определяет правила выполнения операций над множествами. Множество М вместе с заданной на нем совокупностью операций О = {o1, o2, …,om}, т. е. система А = (М; o1, o2, …, om} называется алгеброй; М называется основным множеством (носителем) алгебры А.

Пусть задано универсальное множество U; его булеан B(U). Совокупность операций (объединения), (пересечения), (дополнения, отрицания) называются булевыми операциями. Алгебра B = (B(U);,, ) называется булевой алгеброй множеств над U. Элементами основного множества этой алгебры являются подмножества А, В, С, … множества U. Операция А эквивалентна операции дополнения U \ A.

Для универсума U и его подмножеств при использовании булевых операций выполняются следующие свойства (тождества алгебры множеств):

Идемпотентность (удаление одинаковых операндов):

а) А А = А; б) А А = А.

Коммутативность (перестановка операндов):

а) А В = В А; б) А В = В А.

Ассоциативность (возможность бесскобочной записи):

а) (А В) С = А (В С); б) (А В) С =.А (В С).

Дистрибутивность (раскрытие скобок):

а) относительно :б) относительно :

А (В С ) = (А В ) (А С); А (В С ) = (А В ) (А С).

Поглощение:

а) А (А В ) = А; б) А (А В ) = А.

Законы (правила) де Моргана:

а) б) А В = А В ; А В = А В.

Обобщение правила де Моргана для совокупности множеств:

= ; Ai = Ai;

а) Ai Ai б) iI iI i I iI Свойства универсума:

а) A U = U;б) A U = A.

Свойства пустого множества:

а) А = А; б) А =.

Свойства дополнения (отрицания):

а) А A = U; б) А A =.

Свойства двойного дополнения (отрицания):

= A = А.

Пары свойств двойственны друг другу в том смысле, что если в одном из них заменить на, U на, и наоборот, то получим парное свойство.

С целью упрощения формул предполагается, что знак дополнения (отрицания) играет роль скобок, а при отсутствии скобок порядок выполнения операций следующий: дополнение; пересечение; объединение.

Раздел 2. Отношения на множествах Основные виды отношений; функции и отображения; свойства отношений; отношения эквивалентности и порядка.

Литература: [1, c. 7, 8].

Отношение используется как термин для обозначения связи между предметами или понятиями (а А, р делится на 2). Отношение, называемое бинарным, относится к связи пары объектов, рассматриваемых в определенном порядке, и обозначается (х, у), где х – первая, а у – вторая координата упорядоченной пары.

Бинарное (двуместное) отношение определяется как множество упорядоченных пар. Выражения (х, у) и ху взаимозаменяемы, и говорят, что х – относится к у. Для некоторых отношений (равенства, принадлежности, включения, сравнения и др.) приняты специальные обозначения (х = у, х А, A B, х < y).

Областью определения бинарного отношения (обозначается D) называется множество {x | существует у, (х, у) } (символ | читается “если”). Областью значений бинарного отношения с (обозначается R) называется множество {y | существует x, (х, у)}. Иными словами, область определения – это множество первых координат элементов из, а область значений – множество вторых координат элементов из.

Например, отношение равенства целых чисел (Z) есть множество {(x, y) | x, y Z и x = y}. Область определения D совпадает с областью значений R и является множеством целых чисел Z.

Прямое (декартово) произведение: операция. Пусть А и В – два множества. Через АВ обозначим множество, состоящее из упорядоченных пар (a, b), таких, что а А, b В. Иначе говоря, р А В тогда и только тогда, когда р есть пара (a, b), причем а А, b B. Пусть |A| = m, |B| = n – количество элементов множеств А, В, тогда |A B| = |A||B| = mn. Например, пусть A = {a, b}, B = {c, d, e}, тогда А В = {(a, c), (a, d), (a, e), (b, c), (b, d), (b, e)}.

Упорядоченным произведением множества V самого на себя (V V = V2) называется множество всех упорядоченных пар (s, t), где s V и t V. Здесь (s, t) и (t, s) рассматриваются как различные элементы, исключая случай s = =t. Если число элементов |V| = n, то |V V| = n2 упорядоченных пар. Например, пусть V = {v1, v2, v3}, тогда V V = {(v1, v1), (v1, v2), (v1, v3), (v2, v1), (v2, v2), (v2, v3), (v3, v1), (v3, v2), (v3, v3)}.

Пусть x, y R, где R – множество действительных чисел, тогда R2 = R R представляет собой множество всех пар (х, у), каждой из которых можно сопоставить точку декартовой плоскости с координатами (абсцисса, ордината).

Неупорядоченным произведением множества V самого на себя (обозначим как V&V) называется множество всех различных неупорядоченных пар [s, t], при этом пары [s, t] и [t, s] эквивалентны и так же, как при декартовом произведении, допускается совпадение элементов пары, т. е. s = t. При |V| = n мощность множества |V&V| = n(n+1)/2 различных неупорядоченных пар. Например, пусть V = {v1, v2, v3}, тогда V&V = ={[v1, v1], [v1, v2], [v1, v3], [v2, v2], [v2, v3], [v3, v3]}.

Бинарное отношение выделяет в декартовом произведении Х Y некоторое подмножество X,Y Х Y, задаваемое определяющим свойством отношения, такого, что D Х, R Y. Если с такое отношение, что Х Y, то говорят, что есть отношение из Х в Y. Если Х = Y, т. е.





Х Х, то говорят, что есть отношение на множестве Х.

Бинарные отношения можно представлять различными способами:

перечислением пар, таблицей, ориентированным графом, графиком на координатной плоскости, функцией.

Функция и отображение. Пусть f – отношение из X в Y такое, что x X (x, y) f и (x, z) f y = z (символ означает “любой”, означает “следует”). Такое свойство отношения называется однозначностью, или функциональностью. Само отношение называется отображением из X в Y, или функцией, и обозначается f : XY или y = f(x), где х – аргумент, у – значение функции.

Область определения функции: fX = {x X | y Y y = f(x)}; область значения функции: fY = {y Y | x X y = f(x)} (символ означает “существует”). Если fX = Х, т. е. для каждого элемента х имеется один элемент у вида (x, y) f, то функция называется полностью определенной, а если fX Х – частично определенной.

Образ и прообраз. Пусть f : XY, Х1 Х, Y1 Y, тогда множество f(Х1) = {y Y | x X1 y = f(x)} называется образом множества Х1, а множество f –1(Y1) = {x X | y Y1 y = f(x)} – прообразом множества Y1.

В записи у = f(x) значение у является образом элемента х при отображении f, при этом аргумент х – прообразом элемента у. Отображение называется взаимнооднозначным, если f(X)=Y и для любого y Y множество f –1({y}) состоит из одного элемента f –1({y}) = {x}. Тем самым определено отображение f –1 : Y X.

Свойства бинарных отношений. Отношение называется рефлексивным, если (x, x) ; антирефлексивным, если (x, x) ; симметричным, если (x, y) (y, x) с; антисимметричным, если (x, y) и (y, x) x = y; асимметричным, если (x, y) (y, x) ; транзитивным, если (x, y) и (y, z) (x, z) ; линейным, если (x, y) или (y, x).

Из множества всех отношений выделяется класс отношений, одновременно симметричных, транзитивных и рефлексивных. Такие отношения называются отношениями эквивалентности.

К отношениям порядка относятся: а) отношение квазипорядка, обладающее свойствами рефлексивности, транзитивности; б) отношение частичного порядка на множестве Х (часто обозначаемое <= или >=), обладающее свойствами рефлексивности, антисимметричности, транзитивности; в) отношение строгого порядка на множестве Х (часто обозначаемое < или >), обладающее свойствами антирефлексивности, асимметричности, транзитивности; г) отношение линейного (полного) порядка, обладающее наряду со свойствами отношения частичного порядка свойством линейности.

Раздел 3. Основные понятия теории графов Понятие графа как математической модели; геометрическое и абстрактное представление графов; типы графов (неориентированный и ориентированный); понятие смежности и инцидентности; матрицы смежности.

Литература: [1, c. 8 –10, 21, 24].

Теория графов, являясь разделом дискретной математики, используется для описания и изучения отношений между дискретными объектами. При этом объекты геометрически можно представить в виде множества точек, называемых вершинами графа (V = {vi}), а отношения между ними представляются самонепересекающимися линиями, связывающими вершины. Если линии не ориентированы, то их называют u ребрами ( ), а сам граф – неориентированным (рис. 1, а), а если линии ориентированы, то их называют дугами (u), а граф – ориентированным (рис. 1, б), или орграфом. Если множество вершин и ребер (или дуг) конечно, то граф называется конечным.

Вершины, соединенные ребром или дугой, называются смежными.

Ребра, имеющие общую вершину, также смежны между собой. Говорят, а) б) v2 uvvuu vuu u uvuuu vvРис. 1. Геометрическое представление графов:

а) неориентированный граф; б) ориентированный граф что ребро (дуга) и его граничные точки инцидентны друг другу, иначе говоря, вершины, инцидентные ребру (дуге), являются его концевыми точками. Понятие инцидентности ребер (дуг) и их концевых вершин является фундаментальным в теории графов, которая построена с учетом именно этой особенности и не учитывает реальной природы вершин и ребер (дуг).

Структурное различие между неориентированным графом и орграфом состоит в том, что в первом случае граничные точки ребра образуют неупорядоченную, а во втором – упорядоченную пару вершин. Ребро эквивалентно противоположно направленным дугам.

Геометрическое представление графов, являясь наглядным, трудно поддается математической обработке, поэтому описание графа формализуют и представляют в общем виде:

G = (V, ) или G = (V, U), U U где V – непустое множество вершин графа vi V; – множество ребер для неориентированного графа; U – множество дуг орграфа. Любой граф в абстрактном смысле эквивалентен (по отношению к свойствам, изучаемым в теории графов) некоторому геометрическому графу.

Для удобства обработки графов с использованием ЭВМ лучше всего подходит матричная форма представления структурных свойств графа.

Матрица смежности вершин графа – это квадратная матрица || S || размера nn (n – количество вершин), где строки и столбцы соответствуют вершинам графа, а элемент sij для неориентированного графа равен числу ребер, соединяющих одновременно вершины i и j, а для орграфа sij равен количеству дуг (vi, vj).

Матрица смежности неориентированного графа без петель (ребер, замкнутых на одну вершину) симметрична относительно главной диагонали, поскольку пара вершин vi и vj соединяются одинаковыми ребрами [vi, vj] = =[vj, vi], т. е. достаточно рассматривать только половину матрицы выше главной диагонали. Очевидно, что матрица смежности графа без петель и кратных ребер является булевой матрицей, состоящей из нулей и единиц.

Pages:     || 2 | 3 | 4 | 5 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.