Методические указания к выполнению лабораторных работ по дисциплине «Дискретный анализ»




Скачать 266.83 Kb.
НазваниеМетодические указания к выполнению лабораторных работ по дисциплине «Дискретный анализ»
страница1/3
Дата публикации28.03.2013
Размер266.83 Kb.
ТипМетодические указания
shkolnie.ru > Информатика > Методические указания
  1   2   3


4МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ГОУ ВПО «Дагестанский государственный технический университет»
КАФЕДРА ИНФОРМАЦИОННЫХ СИСТЕМ В ЭКОНОМИКЕ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к выполнению лабораторных работ по дисциплине

ДИСКРЕТНЫЙ АНАЛИЗ


Махачкала – 2008 г.
УДК 681.3

Методические указания к выполнению лабораторных работ по дисциплине «Дискретный анализ». Махачкала, ДГТУ, 2008. 20 с.

Методические указания предназначены для студентов дневной и заочной форм обучения по специальностям 080801 – «Прикладная информатика в экономике» и 080812 – «Прикладная информатика в юриспруденции».

Методические указания содержат краткие теоретические сведения о теории множеств, операциях над множествами, алгебре логики, о методах составления совершенных нормальных форм алгебры Буля, булевых функциях, методические примеры, индивидуальные задания к выполнению лабораторных работ.

Составители: д.э.н. профессор Абдулгалимов А.М.

ст. преп. кафедры ИСЭ, к.э.н. Мурадов М.М.

Рецензенты:


Печатается по решению Совета Дагестанского государственного технического университета от «____» ______________2008 г., № ___.

ПРЕДИСЛОВИЕ
Роль дискретной математики чрезвычайно велика при описании и изучении сложных автоматизированных систем. Автоматизированные системы состоят из разнообразных разнородных элементов, поэтому обладают ярко дискретной структурой, описание которой требует специальных математических методов. Такими являются теория множеств, теория графов и алгебра логики.

В методических указаниях даются определения понятиям множество, конечное и бесконечное множество, счетное и несчетное множество, упорядоченное множество, кортежу, представлены основные операции алгебры множеств, основные функции алгебры Буля, методы определения наименьшего пути в графе с ребрами произвольной длины.

В методических указаниях предлагается как теоретические положения теории множеств, операций над множествами, алгебры логики, методов составления совершенных нормальных форм алгебры Буля, булевых функциях, теории графов, так и методические примеры, доведенные до алгоритмов, позволяющих проводить вычисления на ЭВМ, фрагменты программ, а также индивидуальные задания

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

Решение задач ориентировано на использование ПЭВМ. Указания являются полезными при выполнении лабораторных работ по курсам:

- проектирование информационных систем;

- базы данных;

- имитационное моделирование экономических процессов.

^ Структура отчета по лабораторной работе

- постановка задачи;

- текст индивидуального задания;

- теоретические сведения;

- текст программы;

- результаты и их анализ;

- список использованной литературы или других источников.

Отчет по лабораторной работе студент пишет от руки в ученической тетради и защищает его перед преподавателем.
^ ЛАБОРАТОРНАЯ РАБОТА №1
Тема: “ Основные понятия теории множеств, основные операции алгебры множеств”

1.1. Основные теоретические положения

Понятие множества является фундаментальным неопре­деляемым понятием. Интуитивно под множеством будем понимать совокупность определенных вполне различаемых объектов, рассматриваемых как единое целое.

Отдельные объекты, из которых состоит множество, называют элементами множества. Так, число 3 — элемент множества натуральных чисел, а буква б—элемент мно­жества букв русского алфавита.

Общим обозначением множества служит пара фигур­ных скобок { }, внутри которых перечисляются элементы множества. Для обозначения конкретных множеств исполь­зуют различные прописные буквы А, S, X... или пропис­ные буквы с индексами А1, А2. Для обозначения элементов множества в общем виде используют различные строчные буквы a, s , x-... или строчные буквы с индексами а1, а2...

Для указания того, что некоторый элемент а является элементом множества S, используется символ принад­лежности множеству. Запись aS означает, что элемент а принадлежит множеству S, а запись означает, что элемент х не принадлежит множеству S.

Множества бывают конечными и бесконечными. Мно­жество называют конечным, если число его элементов ко­нечно, т. е. если существует натуральное число N, являю­щееся числом элементов множества. Множество называют бесконечным, если оно содержит бесконечное число эле­ментов.

Для того, чтобы оперировать с конкретными множест­вами, нужно уметь их задавать. Существуют два способа задания множеств: перечисление и описание. Задание мно­жества способом перечисления соответствует перечислению всех элементов, составляющих множество. Так, множество отличников группы можно задать, перечислив студентов, которые учатся на отлично, например {Иванов, Петров, Сидоров}. Для сокращения записи Х={х1, х2,.. .,хn} иногда пишут X={xi} или вводят множество индексов I={1, 2,...,п} и пишут X={xi}, iI. Такой способ удобен при рассмотрении конечных множеств, содержащих не­большое число элементов, но иногда он может применяться и для задания бесконечных множеств, например {2, 4, 6, 8...}. Естественно, что такая запись применима, если вполне ясно, что понимается под многоточием.

Описательный способ задания множества состоит в том, что указывается характерное свойство, которым обладают все элементы множества. Так, если М — множество сту­дентов группы, то множество А отличников этой группы запишется в виде

что читается следующим образом: множество ^ А состоит из элементов х множества М, обладающих тем свойством, что -X является отличником группы.

В тех случаях, когда не вызывает сомнений, из какого множества берутся элементы x, указание о принадлежно­сти x множеству М можно не делать. При этом множест­во А запишется в виде



Приведем несколько примеров задания множеств мето­дом описания:

{х| х — четное}—множество четных чисел;


Важным понятием теории множеств является понятие пустого множества. Пустым множеством называют мно­жество, не содержащее ни одного элемента. Пустое мно­жество обозначается , например:



Понятие пустого множества играет очень важную роль при задании множеств с помощью описания. Так, без по­нятия пустого множества мы не могли бы говорить о мно­жестве отличников труппы или о множестве вещественных корней квадратного уравнения, не убедившись предвари­тельно, есть ли вообще в данной группе отличники или имеет ли данное уравнение вещественные корни. Введение пустого множества позволяет совершенно спокойно опери­ровать с множеством отличников группы, не заботясь о том, есть или пет в рассматриваемой группе отличники.

Пустое множество будем условно относить к конечным множествам.

Рассмотрим теперь вопрос о равенстве множеств. Два множества называются равными, если они состоят из одних и тех же элементов, т. е. представляют собой одно и то же множество. Множества X и Y не равны (ХY), если либо в множестве X есть элементы, не принадлежа­щие Y, либо в множество Y есть элементы, не принадле­жащие X. Символ равенства множеств обладает свойст­вами:

^ Х=Х — рефлексивность;

если X=Y, то Y=X — симметричность;

если Х=Y и Y=Z, то X=Z — транзитивность.

Многие определения теории множеств удобно давать в виде математических выражений, содержащих некоторые логические символы. Для определения подмножества ис­пользуем два таких символа.

— символ, называемый квантором и означающий лю­бой, каков бы ни был, «для всех»;

— символ следствия (импликации), означающий «влечет за собой».

Определение подмножества, которое может быть сфор­мулировано в виде: для любого х, утверждение “x принадлежит Х” влечет за собой утверждение «х принадлежит Y», запишется так:

(1)

Более краткой записью выражения «^ X является под­множеством Y» будет запись

(2)

что читается как «Y содержит X». Используемый здесь символ означает включение. Если желают подчеркнуть, что Y содержит и другие элементы, кроме элементов из X, то используют символ строгого включения:

(3)

Связь между символами и дается выражением

(4)

Отметим некоторые свойства подмножества, вытекаю­щие из его определения:



Несколько труднее видеть, что для любого множества М



Действительно, пустое множество 0 не содержит эле­ментов. Следовательно, добавляя к ^ М пустое множество, мы фактически ничего не добавляем. Поэтому всегда мож­но считать, что любое множество М содержит в себе пус­тое множество в качестве подмножества.

^ Счетные и несчетные множества

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

1,2,3…..n ….

Если бесконечное множество оказывается возможным привести во взаимно однозначное соответствие с натуральным рядом чисел, то такое множество называют счетным. Следует отметить, что не все бесконечные множества являются счетными. Если бесконечное множество невозможно привести во взаимно однозначное соответствие с натуральным рядом чисел, то его называют несчетным.
^ 1.2 Операции над множествами, основные предположения

Объединение множеств

Объединением множеств X и Y называют множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств X, Y, т. е. при­надлежат множеству X или множеству Y. Объединение X и Y обозначается через. Формальное определение

(1)

Объединение множеств иногда называют суммой мно­жеств и обозначают X+Y. Однако свойства объединения множеств несколько отличаются от свойств суммы при обычном арифметическом понимании, поэтому этим терми­ном мы пользоваться не будем.

Объединение множеств можно распространить и на большее число множеств. Обозначим через совокупность n множеств X1,X2…Xn называемой системой множеств. Объединение этих множеств

(2)

Представляет собой множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств системы. Пример X={1,2,3,4,5}, Y={2,4,6,7} – {1,2,3,4,5,6,7}.

Для объединения множеств справедливы коммутативный и ассоциативный законы

(3)

(4)

Также справедливо след. Равенство

(5)
^ Пересечение множеств

Пересечением множеств X и Y называют множество, состоящее из всех тех и только тех элементов, которые принадлежат как множеству X, так и множеству Y. Пересечением множеств X и Y обозначается через . Формальное определение

(6)

Пересечение множеств иногда называют произведени­ем множеств и обозначают XY. Однако свойства пересече­ния множеств несколько отличаются от свойств произве­дения в обычном арифметическом понимании.

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

Множества X и Y называют непересекающимися, если они не имеют общих элементов.

Очевидно, что эти соотношения не исчерпывают всех возможностей. На самом деле, как вытекает из предыду­щих определений, между .множествами X и Y может быть одно из пяти отношений:

(7)

X и Y находятся в общем положении.

Понятие пересечения можно распространить и на боль­шее, чем два, число множеств. Рассмотрим систему мно­жеств. Пересечение этих множеств записы­вается в виде

(8)

и представляет собой множество, элементы которого при­надлежат каждому из множеств системы.

Нетрудно видеть, что пересечение множеств обладает коммутативным свойством (9)

и ассоциативным (10)

Заметим также, что имеет место соотношение

(11)

аналогичное соотношению a*0=0 в обычной алгебре. Со­отношение (11) совместно с соотношением (5) пока­зывает, что пустое множество играет роль нуля в алгебре множеств.

^ Разность множеств

Разностью множеств X и Y называют множество, состоящее из всех тех и только тех элемен­тов, которые принадлежат X и не при­надлежат Y. Разность множеств X и Y обозначается через X\Y. Таким образом.

X\Y = (12)
^ Универсальное множество

Если в некотором рас­смотрении участвуют только подмножества некоторого фиксированного множества I, то это самое большое мно­жество I называют универсальным множеством.

Следует отметить, что в различных конкретных случа­ях роль универсального множества могут играть различ­ные множества. Универсальное множество удобно изображать графиче­ски в виде множества точек прямоугольника. Отдельные области внутри этого прямоугольника будут означать раз­личные подмножества универсального множества. Изобра­жение множества в виде областей в прямоугольнике, представляющем универсальное множество, называют ди­аграммой Эйлера — Венна.

Универсальное множество обладает интересным свой­ством, которое не имеет аналогии в обычной алгебре, а именно для любого множества X справедливо соотно­шение

(14)

Действительно, объединение представляет собой множество, в которое входят как все элементы множест­ва ^ X, так и все элементы множества I. Но множество I уже включает в себя все элементы множества X, так что будет состоять из тех же элементов, что и I, т. е. представляет собой само универсальное множество I.

Дополнение множества

Множество определяемое из соотношения

(15)

называют дополнением множества X (до универсального множества I). На рис. множество X представляет со­бой незаштрихованную область.

Рис. 1. Дополнение множества.

Форумальное определение

Из (15) следует, что X и не имеют общих элемен­тов, так что

(16)
^ 1.3. Примеры алгоритмов и блок-схем реализации операций над множествами.
Пример 1.1. Разработать алгоритм и блок-схему определения универсального множества I для заданных множеств A,B, состоящих из натуральных чисел.

Алгоритм решения данной задачи имеет следующий вид.
1. Начало.

2. Циклический ввод элементов множеств A,B.

3. Обнуляем значения множества I.

4. Сбрасываем счетчик элементов множества I (k =0).

5. Цикл i от 1… n, где nколичество элементов множества A

Начало цикла

51. Увеличиваем счетчик элементов множества I (k =k+1).

52. Дописываем в множество ^ I значение i-го элемента множества A

Конец цикла

  1. Цикл i от 1… m, где mколичество элементов множества B

Начало цикла

61. Установка флага f=0.

62. Цикл j от 1… n, где nколичество элементов множества A

Начало цикла

Проверка условия Bi = Aj

- если да, то флаг f = 1;

- если нет, то проверка следующего элемента

^ Конец цикла

63. Проверка условия f=0

- если да, то

Увеличиваем счетчик элементов множества I (k =k+1).

Дописываем в множество I значение i-го элемента множества B;

- если нет, то проверка следующего элемента;

Конец цикла

7. Вывод полученного множества I

8. Конец

Блок-схема алгоритма представлена на рис 2.


^ 1.4. Контрольные вопросы
1. Дайте определение множества. Привести примеры множеств.

2. Что представляют собой счетные и несчетные множества.

3. Что представляют собой конечные и бесконечные множества.

4. Какие способы задания множеств существуют. Какой способ используются для бесконечных множеств. Привести пример задания одного о того же множества разными методами.

5. Алгебра множеств. Основные предположения алгебры множеств.

6. Операции над множествами.

7. Понятия универсального и пустого множества. Дополнение множества.

8. Основные тождества алгебры множеств.

^ 1.5. Задание к лабораторной работе №1


  1. Изучить теоретический материал по теме лабораторной работы.

  2. Разработать блок-схемы алгоритмов выполнения операций объединения, пересечения и разности двух заданных множеств.

  3. Разработать блок-схемы пользовательского меню для выбора операции над множествами.

  4. Реализовать на языке программирования разработанные блок-схемы.

  5. Выписать в отчет ход выполнения работы и выводы.


^ ЛАБОРАТОРНАЯ РАБОТА № 2
  1   2   3

Похожие:

Методические указания к выполнению лабораторных работ по дисциплине «Дискретный анализ» iconМетодические указания к выполнению лабораторных работ по дисциплине «Организация ЭВМ и систем»
Электронные методические указания к выполнению лабораторных работ по дисциплине «Организация ЭВМ и систем»/ Сост.: Андреева А. А.,...
Методические указания к выполнению лабораторных работ по дисциплине «Дискретный анализ» iconМетодические указания по выполнению лабораторных работ по дисциплине...
Зрюмова, А. Г. Методические указания по выполнению лабораторных работ по дисциплине «Компьютерные технологии в приборостроении» /...
Методические указания к выполнению лабораторных работ по дисциплине «Дискретный анализ» iconМетодические указания по выполнению лабораторных работ по дисциплине...
Лукьянов В. Г. Методические указания по выполнению лабораторных работ по дисциплине "Теоретические основы измерительных и информационных...
Методические указания к выполнению лабораторных работ по дисциплине «Дискретный анализ» iconМетодические указания к выполнению лабораторных работ №1 №4 по дисциплине...
Методические указания предназначены для студентов дневной и заочной форм обучения направления
Методические указания к выполнению лабораторных работ по дисциплине «Дискретный анализ» iconМетодические указания к выполнению лабораторных работ по дисциплине «Информационные системы»
Методические указания предназначены для студентов дневной и заочной форм обучения специальности 080801 «Прикладная информатика (по...
Методические указания к выполнению лабораторных работ по дисциплине «Дискретный анализ» iconМетодические указания к выполнению контрольных работ по дисциплине «Информатика»
Методические указания предназначены для студентов-заочников специальностей: 2806, 2808, 1707, 2506. Дисциплина «вычислительная техника...
Методические указания к выполнению лабораторных работ по дисциплине «Дискретный анализ» iconМетодические указания к выполнению лабораторных работ №1 - №4 по...
Методические указания к лабораторным работам №1 — №4 по дисциплине “Основы теории марковских процессов”/ Сост. Ю. В. Доронина.  — Севастополь:...
Методические указания к выполнению лабораторных работ по дисциплине «Дискретный анализ» iconМетодические указания по выполнению лабораторных работ (курс «Базы данных и знаний», часть 1)
Методические указания предназначены для студентов экономического и механико-математического факультетов. Здесь определены цели и...
Методические указания к выполнению лабораторных работ по дисциплине «Дискретный анализ» iconЗадания и методические указания к выполнению лабораторных работ по курсу
Методические указания предназначены для студентов экономического факультета, изучающих курсы «Документирование управленческой деятельности»...
Методические указания к выполнению лабораторных работ по дисциплине «Дискретный анализ» iconМетодические указания для лабораторных работ по дисциплине «Химия»
Методические указания к лабораторным работам по дисциплине «Химия». Екатеринбург, гоу впо «Рос гос проф пед университет», 2009. 43...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
shkolnie.ru
Главная страница