27

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ “ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ” Кафедра “Системного аналізу та управління” Курсова робота Дисципліна “Дискретна математика" Тема „Множини, обчислювання на множинах. Діаграми Ейлера-Венна” (Варіант №47-57) Керівник роботи: доц. каф. САіУ, канд.техн.наук Б.Г.Акунін Виконавець: студент групи ІФ-50в Е.П.Фандорін Харків – 2005

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ “ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

Кафедра “Системного аналізу та управління”

Оцінка

________________________

голова комісії

доц. каф.САиУ

____________ /Кащеєв Л.Б./

« » ___________ 200 _ р.

КУРСОВА РОБОТА

Дисципліна: „Дискретна математика”

Тема: „Множини, обчислювання на множинах. Діаграми Ейлера-Венна” (Варіант №47-57)

Виконавець: ст. гр. ИФ-50^в Е.П.Фандорін

“ ” 200 р.

Керівник роботи: доц., канд. техн. наук Б.Г.Акунін

“ ” 200 р.

Харків 2005

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ “ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

Кафедра “Системного аналізу та управління”

Студент Е.П.Фандорін Група ИФ-50^в

ЗАВДАННЯ на науково-дослідну курсову роботу

Дисципліна: “Дискретна математика”

Тема: „Множини, обчислювання на множинах. Діаграми Ейлера-Венна” (Варіант №47-57)

Короткий зміст роботи:

а) теоретична частина

Розробка методики дослідження трьох множин, які будуть взяти з текстових файлів.

Провести запис усіх елементів множин, у формі переліків компонентів відобразити їх діаграмами Ейлера–Венна, обчислити та надписати міцність множин та їх пересічень, проілюструвати переліками компонентів та діаграмами Ейлера–Венна усі операції над множинами та доповнення до універсаму; знайти булеан одної з множин та записати його переліком; для заданої керівником предметної сфери розробити 4 множини, проілюструвати операції над ними на діаграмах Ейлера-Венна, для обраної множини створити кодову таблицю и кодовий граф-дерево для коду Шеннона-Фано.

б) програмно-розрахункова частина

Розробка програмного забезпечення, яке реалізує заповнення множин букв з текстових файлів; ілюструють операції пересичення, різності и симетрическої різності на даних множинах (з файлів та з клавіатури); знаходження булеана; усі перестановки P(n) з елементів даного множини; проілюструвати r-перестановки з необмеженими повтореннями.

Дата видачі завдання: 15.03.2007 Термін захисту: 21.05.2007

Керівник курсової роботи: / канд. техн. наук, доц. САіУ

Б.Г.Акунін/

СОДЕРЖАНИЕ

Введение …….………..………………………………………………………..5

1 Множества ..………………………………………………………………….6

1.1 Задание множеств …………………………………………………………6

1.1.1 Заполнение множеств …………………………………………...6

1.1.2 Отображение множеств диаграммами Эйлера-Венна…………..7

1.1.3 Мощность множеств …………………………..…………………8

1.1.4 Операции на множествах ………..……………………………….9

1.1.5 Булеан ……………………………………………………………..11

1.1.6 Прямое произведение множеств ……..…………..……………..11

1.2 Составление задачи на множества ……………………………………….12

1.2.1 Диаграмма Эйлера-Венна ……..…………………………………12

1.3 Кодирование кодом Шеннона-Фано ……………………….…………….15

2. Постановка задачи на программирование ………………………………..16

2.1. Постановка задачи ………………………………………………………16

2.2. Описание разработанного объекта ……………………………………..16

2.2.1. Иерархия наследования ………………………………………..16

2.2.2. Организация объекта ……………………..…………………….17

2.3. Интерфейс программы ………………………………………………….18

Заключение …………………………………………………………………...21

Список использованных источников ……………………………………….22

ВВЕДЕНИЕ

Множество – это собрание объектов любой природы, называемых его точками (или его элементами). Официально понятие множеств в математику ввел Георг Кантор (Georg Cantor, 1845-1918), разработавший теорию нечетких множеств, введший в оборот понятие мощность множества (1878). А что касается определения множества, то Кантор определял: «Множество есть многое, мыслимое нами как целое».

Рассуждения относительно «множеств» не зависят от природы объектов – это могут быть люди, числа, города, страны и др. Группа выдающихся математиков, выступающая под псевдонимом Никола Бурбаки, предлагает следующее определение: “Множество образуется из элементов, обладающих некоторыми свойствами и находящихся в некоторых отношениях между собой или с элементами других множеств”.

Поскольку материалы, представленные в данной работе, тесно связаны с программной реализацией, основная часть расчетов проводится на множестве символов, вводимых из текстовых файлов. Как принято, множества обозначают большими латинскими буквами A, B, X, …, а элементы множества – малыми латинскими буквами a, b, x,… . Множество A, элементами которого являются a, b, c, d, обозначают символом A={a, b, c, d}.

1 Множества

1.1 Задание множеств. Множества могут быть заданы:

1. перечислением (список своих элементов) – A = { a₁, a₂, …, a_n };

2. порождающей процедурой – M = { m | m = f };

3. характеристическим предикатом, описанием характерных свойств, которыми должны обладать элементы множеств – X = { x | P(x) }.

Списком можно задавать лишь конечные множества, поскольку указания вида N=1, 2, 3, ... списком не являются, и допустимы лишь в тех случаях, когда не вызывают разночтений. Обычный пример списка A={a, b, c}.

Порождающая процедура способ получения элементов из уже полученных элементов, либо из других объектов. Элементами множества считаются все объекты, которые могут быть получены с помощью этой процедуры. Примером может служить множество из чисел /2+k, где исходная область есть натуральное число и порождающая процедура. Формально можно прочитать файл букв как файл из кодов (байт), а функцию перевода в символы считать порождающей.

Третий способ задания множеств – характеристическим предикатом, некоторым условием, в форме логического утверждения или функции с логическим результатом. Предполагается задание множества в виде совокупности элементов, обладающих свойством P: A={ x/P(x) }.

В моем задании множество задается из текстового файла, используются все символы (не только буквы), на диаграммах будут отображены буквы, цифры и знаки препинания. Технические символы, типа возврат каретки, перевод строки, 0-символ на диаграммах не отображены. Заглавные буквы отличаются от строчных.

1.1.1 Заполнение множеств. В качестве тестового задания мною использованы три текстовых файла – a.txt, b.txt и c.txt, и три типизированных файла длинных целых чисел – n1.dat, n2.dat и n3.dat.

Содержимое файлов, a.txt:

Белеет парус одинокий в тумане моря голубом.

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

A = {Б,а,б,г,д,е,и,й,к,л,м,н,о,п,р,с,т,у,я,., }

Обратите внимание на символы «пробел» и «точка», которые также представляются вполне полноправными элементами множества.

Аналогичным образом наполняем множество B из файла b.txt:

Зима!.. Крестьянин, торжествуя,

На дровнях обновляет путь.

По данной строке множество будет состоять из символов:

B = {З,К,Н,а,б,в,д,е,ж,и,л,м,н,о,п,р,с,т,у,х,ь,я,.,,,!, }

Обратите внимание на символы «пробел» и «точка», которые также представляются вполне полноправными элементами множества. «Возврат каретки» и «перевод строки» осознанно во множество не включены. Заглавные буквы рассматриваются отдельно от строчных.

И, наконец, аналогичным образом наполняем множество C из файла c.txt:

Кока-кола

По данной строке множество будет состоять из символов:

C = {К,а,к,л,о,-}

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

Аналогично заполняются и числовые множества, хотя из типизированных файлов значения читаются как числа, но далее разбиваются на цифры (знак «минус» игнорируется).

Из файла n1.dat считываются числа:

177 787 8783 8673 778

Из цифр данной числовой последовательности составляем множество:

N1 = {1, 3, 6, 7, 8}.

Точно так же из чисел файла n2.dat:

8770 67724 -1776 -1232 7712

получается множество:

N2 = {0, 1, 2, 3, 4, 6, 7, 8}.

Из чисел файла n3.dat получаем третье цифровое множество:

177 177000 0 -22

N3 = {0, 1, 2, 7}.

1.1.2. Отображение множеств диаграммами Эйлера-Венна.

Для наглядной иллюстрации операций над множествами и теоретико-множественных соотношений используются круги Эйлера, названные по имени швейцарского математика Леонарда Эйлера (1707-1783), прожившего большую часть жизни в Петербурге. Их можно применять и для доказательства этих отношений. Дальнейшее развитие графические методы алгебры множеств получили в диаграммах Венна, названных по имени Джона Венна (Venn, 1834-1923) английского логика-математика, работавшего в области логики классов, для которых он и создал графический аппарат диаграмм Венна

Построение диаграмм Венна начинается с разбиения плоскости на 2n зон (ячеек) с помощью n замкнутых линий. При этом каждая последующая фигура должна иметь одну и только одну область пересечения с каждой из ранее построенных фигур. То есть можно рисовать линии «подковкой», но нельзя, чтобы замкнутая фигура дважды пересекалась с другим овалом. Принципиальное отличие диаграмм Венна от кругов Эйлера состоит в том, что диаграммы Венна имеют абсолютно все области пересечения между подмножествами (если их существование невозможно из-за противоречивых условий, области рисуются и сразу штрихуются).

Универсум отождествлялся с плоскостью, которая может отображаться замкнутой линией (как правило – это прямоугольник, но допустимы и круг, овал). В моей работе универсумом (основное множество) U является все множество ASCII-символов.

Построим соотношение двух групп заполненных множеств на диаграммах Эйлера-Венна:

а) б)

Рис.1.1 – Отображение трех множеств символов с помощью диаграмм Эйлера-Венна: а) символьные множества А,В,С; б) цифровые множества N1,N2,N3

1.1.3. Мощность множеств.

Мощность множества – обобщение на произвольные множества понятия «число элементов». Мощность множества определяется методом абстракции как то общее, что есть у всех множеств, количественно эквивалентных данному. При этом два множества называются эквивалентными (имеют одну и ту же мощность), если существует взаимнооднозначное соответствие между элементами этих множеств.

Итак, мощность множеств A и N1:

|A|=| {Б,а,б,г,д,е,и,й,к,л,м,н,о,п,р,с,т,у,я,., }|=21,

|N1| = |{1, 3, 6, 7, 8}| = 5.

Мощность множества B и N2:

|B| =| {З,К,Н,а,б,в,д,е,ж,и,л,м,н,о,п,р,с,т,у,х,ь,я,.,,,!, }|=26,

|N2| = |{0, 1, 2, 3, 4, 6, 7, 8}| = 8.

Мощность множества C и N3:

|C| =| {К,а,к,л,о,-}|=6

|N3| =|{0, 1, 2, 7}| = 4.

1.1.4. Операции на множествах

Обычно рассматриваются следующие операции над множествами:

объединение (все операции мы рассмотрим на примере множеств A и B)

AB={Б,З,К,Н,а,б,в,г,д,е,ж,и,й,к,л,м,н,о,п,р,с,т,у,х,ь,я,.,!,,, }, |AB|=30;

N1N2 = { 0, 1, 2, 3, 4, 6, 7, 8}, |N1N2| = |{0, 1, 2, 3, 4, 6, 7, 8}| = 8.

Рис.1.2 – Объединение множеств

пересечение множеств:

A∩B={а,б,д,е,и,л,м,н,о,п,р,с,т,у,я,., }

/A∩B/=18

N1∩N2 = { 1, 3, 6, 7, 8},

|N1∩N2| = |{ 1, 3, 6, 7, 8}| = 5.

Рис.1.3 – Пересечение множеств

разность множеств:

A\B={Б,г,й }, /A\B/=3;

N1\N2 ={}; |N1\N2| =0 .

Рис.1.4 – Разность множеств

симметрическая разность

AB={Б,г,й,к,К,З,Н,в,ж,х,ь,!,,}; | A  B |=13;

N1 N2 = { 0, 2, 4 }; | N1 N2 | = 3.

Рис.1.5 – Симметрическая разность множеств

Дополнение множества А до универсума (и аналогично множества N1)

| |=| U\(AB) | = 256-30 =226;

| |=| U\(N1N2) | = 10 – 8 = 2.

Рис.1.6 – Дополнение множеств до универсума

Проанализировав операции над множествами, надпишем мощность всех элементов пересечений на рис.1.1.

1. 

Рис.1.7 – Мощности подмножеств на диаграмме Эйлера-Венна

1.1.5 Булеан

Множество всех подмножеств множества М называется булеаном и обозначается 2^M.

Рассмотрим булеан множества С (оно имеет наименьшую мощность).

2^М_С={{}, {К}, {а}, {к}, {л}, {о}, {-}, {К,а}, {К,к}, {К,л}, {К,о}, {К,-}, {а,к}, {а,л}, {а,о}, {а,-}, {к,л}, {к,о}, {к,-}, {л,о}, {л,-}, {о,-}, {К,а,к}, {К,а,л}, {К,а,о}, {К,а,-}, {К.к,л},{К,к,о},{К,к,-},{К,л,о}, {К,л,-}, {К,о,-}, {а,к,л}, {а,к,о}, {а,к,-}, {к,л,о}, {к,л,-}, {л,о,-}, {К,а,к,л}, {К,а,к,о}, {К,а,к,-}, {а,к,л,о}, {а,к,л,-}, {к,л,о,-}, {К,а,к,л,о}, {К,а,к,л,-}, {а,к,л,о,-}, {К,а,к,л,о,-}}

Аналогично булеан множества N3 (имеющего наименьшую мощность из цифровых множеств):

2^М_N1={{}, {0}, {1}, {2}, {7}, {0,1}, {0,2}, {0,7}, {1,2}, {1,7}, {2,8}, {0,1,2}, {0,1,7}, {1,2,3}, {0,1,2,7}}.

1.1.6. Прямое произведение множеств

Декартовым произведение двух множеств A и B называется множество упорядоченных пар, в котором первый элемент каждой пары принадлежит A, а второй – принадлежит B:

A  B = { (a,b) | a  A & b  B}

В моей работе я приведу пример декартова произведения C  C (поскольку именно третье множество у меня имеет наименьшую мощность, а потому при вычислении декартова произведения вручную даст относительно небольшой результат).

C  C = { (К,К), (К,а), (К,к), (К,л), (К,о), (К,-), (а,К), (а,а), (а,к), (а,л), (а,о),

(а,-), (л,К), (л,а), (л,к), (л,л), (л,о), (л,-), (о,К), (о,а), (о,к), (о,л), (о,о), (о,-), (-,К), (-,а), (-,к), (-,л), (-,о), (-,-)}

|AB|=|A||B|

|CC|=36

N1  N1 = { (0,0), (0,1), (0,2), (0,7), (1,0), (1,1), (1,2), (1,7), (2,0), (2,1), (2,2),

(2,7), (7,0), (7,1), (7,2), (7,7) }

|N1N1|=16

1.2. Составление задачи на множества.

1.2.1. Диаграмма Эйлера-Венна.

По согласованию с руководителем мне было поручено разработать четыре характеристических предиката, которые бы разбивали задачный универсум на подмножества в соответствии с данной диаграммой Эйлера-Венна. При этом требовалось представить перечень элементов множества, подобранных так, чтобы по крайней мере по одному элементу попадало в каждую область диаграммы.

Задание в виде диаграммы Эйлера-Венна имело вид, рис.1.8.

Рис.1.8 – Диаграмма Эйлера-Венна подмножеств индивидуального

задания

Универсум – животные харьковского зоопарка.

Представленной диаграмме, на мой взгляд, на данном универсуме соответствуют такие подмножества (определяемые их характеристическими предикатами):

A – копытные;

В – полосатые;

С – хищники;

D – семейства кошачьих.

Зададим множество перечислением:

U = { тигр, лев, волк, пони, зебра, осел, енот, кролик, дикобраз}.

Изобразим это множество диаграммой Эйлера-Венна, рис.1.8.

Рис.1.9 – Диаграмма Эйлера Венна множества из индивидуального задания.