Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


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




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

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

Провести запис усіх елементів множин, у формі переліків компонентів відобразити їх діаграмами Ейлера–Венна, обчислити та надписати міцність множин та їх пересічень, проілюструвати переліками компонентів та діаграмами Ейлера–Венна усі операції над множинами та доповнення до універсаму; знайти булеан одної з множин та записати його переліком; для заданої керівником предметної сфери розробити 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 = { a1, a2, …, an };

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

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

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

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

Третий способ задания множеств – характеристическим предикатом, некоторым условием, в форме логического утверждения или функции с логическим результатом. Предполагается задание множества в виде совокупности элементов, обладающих свойством 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 – Разность множеств

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

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

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

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

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

|` |=| U\(AÈB) | = 256-30 =226;

|` |=| U\(N1ÈN2) | = 10 – 8 = 2.

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

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

a)

b)

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

 

1.1.5 Булеан

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

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

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 – Диаграмма Эйлера Венна множества из индивидуального задания.

 

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

 

По согласованию с руководителем для кодирования выбрана фраза «Белеет парус одинокий в тумане моря голубом.», служившая исходными данными для первого множества. Для рационального кодирования по Шеннону-Фано нам предстоит провести частотный анализ символов этой фразы и упорядочить их по убыванию частоты (по согласованию с руководителем большие и малые буквы [строчные и заглавные] считаются одинаковыми).

Таблица 1.1

Частоты повторения символов в кодируемой фразе

Символ А Б В Г Д Е Ж З И Й К Л М Н О П Р
Кол-во
Символ С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я _ .
Кол-во

 

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

Таблица 1.2

Частоты повторения символов в кодируемой фразе

Символ А Б В Г Д Е И Й К Л М
Кол-во
Символ Н О П Р С Т У Я _ .  
Кол-во  

Упорядочим символы по убыванию частоты:

Таблица 1.3

Упорядоченные частоты повторения символов в кодируемой фразе

Символ _ О Е М У А И Л Б Н Р
Кол-во
Символ Т В Г Д Й К П С Я .  
Кол-во  

 

Считаем статистические средние повторяемости символов:

Таблица 1.4

Статистические средние повторяемости символов в кодируемой фразе

Символ _ О Е М У А И Л Б Н Р
Кол-во 0,136 0,114 0,09 0,068 0,068 0,045 0,045 0,045 0,045 0,045 0,045
Символ Т В Г Д Й К П С Я .  
Кол-во 0,045 0,023 0,023 0,023 0,023 0,023 0,023 0,023 0,023 0,023  

 

Теперь осуществляем кодирование по Шеннону-Фано

Пробел 0,136 (0,521) (0,25) 0 (0,136)      
О 0,114 1 (0,114)      
Е 0,09 (0,271) (0,158) 0 (0,09)    
М 0,068 1 (0,068)    
У 0,068 (0,113) 0 (0,068)    
А 0,045 1 (0,045)    
И 0,045 (0,477) (0,27) (0,135) 0 (0,045)    
Л 0,045 (0.09) 0 (0,045)  
Б 0,045 1 (0,045)  
Н 0,045 (0,135) 0 (0,045)    
Р 0,045 (0,09) 0 (0,045)  
Т 0,045 1 (0,045)  
В 0,023 (0,207) (0,092) (0,046) 0 (0,023)  
Г 0,023 1 (0,023)  
Д 0,023 (0,046) 0 (0,023)  
Й 0,023 1 (0,023)  
К 0,023 (0,115) (0,046) 0 (0,023)  
П 0,023 1 (0,023)  
С 0,023 (0,069) 0 (0,023)  
Я 0,023 1 (0,046) 0 (0,023)
. 0,023 1 (0,023)

Дерево сами построите.

2. ПОСТАНОВКА ЗАДАЧИ НА ПРОГРАММИРОВАНИЕ

Задача 1

Заполнение множеств из текстовых файлов

Исходные данные:

Текстовой файл.

Алгоритм:

Файл вычитывается посимвольно, при этом формируется множество встретившихся символов. Через меню настройки – «читать все символы?», «только буквы», «латинские буквы», «русские буквы», «буквы и цифры», «различать регистры букв?», «выводить в символах или кодах», «выделять цветом какое-либо подмножество символов».

Вывод:

На экран и в файл для последующего использования полученного множества следующими программами.

Примечание:

Три из загружаемых файлов – множества из задания.

Задача 2

Построитель диаграмм Эйлера-Венна.

Исходные данные:

Из трех файлов вводится три множества символов.

Алгоритм:

На экране строится диаграмма Эйлера-Венна для введенных множеств. Через меню выбирается, что конкретно сейчас будет иллюстрировать программа пересечение, разность или симметрическую разность этих множеств. Соответствующая область выделяется цветом и/или графикой. Отдельно выводятся перечисления элементов множеств, мощности каждой из областей диаграммы.

Вывод:

Сообщение о результат расчетов выводится на экран и/или в текстовый файл (для визуальных сред обязательно копирование полученного рисунка в BMP-файл). Есть возможность сохранить в файл подмножество любой области диаграммы.

Примечание:

Три из загружаемых файлов – множества из задания.

Задача 3

Определение булеана.

Исходные данные:

Вводится множество символов из текстового файла.

Алгоритм:

На заданном множестве выбираются все возможные подмножества от пустого множества до самого исходного множества.

Вывод:

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

Задача 4

Комбинаторика.

Исходные данные:

Вводится множество из текстового файла.

Алгоритм:

Вычисляются все возможные перестановки из элементов (символов) этого множества. Через меню задается допустимость повторения элементов (повторение неограниченное).

Вывод:

На экран и в файл. Полученные слова выводить в алфавитном порядке.

Примечание:

Один из загружаемых файлов – множество из задания.


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

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

Для работы с графами мною создан собственный класс tgraf, который имеет следующую структуру:

Type

tgraf=class


Поделиться:

Дата добавления: 2015-07-26; просмотров: 160; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты