Xreferat.com » Рефераты по информатике и программированию » Основы дискретной математики

Основы дискретной математики

R:integer);

var

i, j:integer;

x, y:integer;

begin

i:=L;

j:=2*L;

x:=a[L];

if (j<R) and (a[j]<a [j+1]) then j:=j 1;

while (j<=R) and (x<a[j]) do begin y:=a[i];

a[i]:=a[j];

a[j]:=y;

a[i]:=a[j];

i:=j;

j:=2*j;

if (j<R) and (a[j]<a [j+l]) then j:=j+l;

end;

end;

begin

n:=strtoint (edit1. Text);

 // задание искомого массива

for k:=1 to n do

a[k]:=StrToInt (StringGrid1. Cells [0, k 1]);

 // алгоритм сортировки с помощью дерева

 // построение пирамиды

L:=(n div 2)+1;

R:=n;

while L>1 do begin L:=L 1;

SIFT (L, R);

end;

 // сортировка

while R>1 do begin x:=a[l];

a[l]:=a[R];

a[R]:=x;

R:=R 1;

SIFT (1, R);

end;

 // вывод отсортированного массива

for k:=1 to n do

stringgrid2. Cells [0, k 1]:=inttostr (a[k]);

end;

procedure TForm1. Button8Click (Sender: TObject);

var

n:integer;

a:array [1..15] of integer;

i, j, x:integer;

begin

n:=strtoint (edit1. Text);

 // задание искомого массива

for i:=1 to n do

a[i]:=StrToInt (StringGrid1. Cells [0, i 1]);

 // алгоритм пузырьковой сортировки

for i:=2 to n do for j:=n downto i do begin

if a [j 1]>a[j] then begin x:=a [j 1];

a [j 1]:=a[j];

a[j]:=x;

end;

end;

 // вывод отсортированного массива

for i:=1 to n do

stringgrid2. Cells [0, i 1]:=inttostr (a[i]);

end;

procedure TForm1. Button9Click (Sender: TObject);

var

n:integer;

a:array [1..15] of integer;

i, j, k, L, R, x: integer;

begin

n:=strtoint (edit1. Text);

 // задание искомого массива

for i:=1 to n do

a[i]:=StrToInt (StringGrid1. Cells [0, i 1]);

 // алгоритм шейкерной сортировки

L:=2;

R:=-n;

k:=n;

repeat

for i:=2 to n do

for j:=-R downto L do begin

if a [j 1]>a[j] then begin x:=a [j 1];

a [j 1]:=a[j];

a[j]:=x;

k:=j;

end;

end;

L:=k+1;

for i:=2 to n do

for j:=L to R do begin

if a [j 1]>a[j] then begin x:=a [j 1] end else

a [j 1]:=a[j];

a[j]:=x;

k:=-j;

end;

R:=k 1;

until L>R;

 // вывод отсортированного массива

for i:=1 to n do

stringgrid2. Cells [0, i 1]:=inttostr (a[i]);

end;

procedure TForm1. Button10Click (Sender: TObject);

var

n:integer;

a:array [1..15] of integer;

i:integer;

procedure sort (L, R: integer);

var

i, j:integer;

x, y:integer;

begin

i:=L;

j:=R;

x:=a[(L+R) div 2];

repeat

while a[i]<x do i:=i+l;

while x<a[j] do j:=j 1;

if i<=j then begin y:=a[i];

a[i]:=a[j];

a[j]:=y;

i:=i+l;

j:=j-l;

end;

until i>j;

if L<j then SORT (L, j);

if i<R then SORT (i, R);

end;

begin

n:=strtoint (edit1. Text);

 // задание искомого массива

for i:=1 to n do

a[i]:=StrToInt (StringGrid1. Cells [0, i 1]);

 // алгоритм быстрой сортировки

 // рекурсивная процедура

SORT (1, n);

 // вывод отсортированного массива

for i:=1 to n do

stringgrid2. Cells [0, i 1]:=inttostr (a[i]);

end;

procedure TForm1. Button17Click (Sender: TObject);

begin

AboutBox.showmodal;

end;

end.

1.3.3 Пример выполнения

Задание: заданы два одномерных массива А и В, содержащие по n элементов каждый. Объединить эти два массива в один, исключив повторяющиеся элементы. Считать, что массивы А и В отсортированы по убыванию.

Теоретическое описание метода

Метод пузырька, как таковой, не требует глубокого рассмотрения. Смысл метода заключается в том, что мы находим в определённой области максимальный (или минимальный элемент) и помещаем его в начало исследуемой области, далее уменьшаем область поиска на 1 и повторяем те же действия, не имеет худшего случая, всегда O(n2).


Основы дискретной математики

Рисунок 1.15 – Форма с результатами расчета


Код программы на Delphi:

const n=5;

var

a:array [1..n] of Byte;

b:array [1..n] of Byte;

c: array of Byte;

i:byte;

implementation

procedure TForm1. Button1Click (Sender: TObject);

var m, x:byte;

begin

randomize;

for i:=1 to n do begin

a[i]:=random(200);

b[i]:=random(200);

end;

for m:=n downto 2 do begin

for i:=1 to m 1 do begin

if a[i]<a [i+1] then begin

x:=a[i];

a[i]:=a [i+1];

a [i+1]:=x;

end;

if b[i]<b [i+1] then begin

x:=b[i];

b[i]:=b [i+1];

b [i+1]:=x;

end;

end;

end;

for i:=1 to n do begin

StringGrid1. Cells [i – 1,0]:=IntToStr (a[i]);

StringGrid2. Cells [i – 1,0]:=IntToStr (b[i]);

end;

end;

procedure TForm1. Button2Click (Sender: TObject);

label m1;

var k, l, x:byte;

begin

k:=1;

l:=1;

x:=0;

SetLength (c, 1);

while (k<=n) or (l<=n) do begin

m1: if a[k]>b[l] then begin

x:=x+1;

SetLength (c, x);

c [x 1]:=a[k];

k:=k+1;

goto m1;

end;

if a[k]<b[l] then begin

x:=x+1;

SetLength (c, x);

c [x 1]:=b[l];

end;

l:=l+1;

end;

For i:=0 to high(c) do ListBox1. Items. Add (IntToStr(c[i]));

end;

end.


1.3.4 Варианты заданий

Варианты 1 – 27 имеют пояснения к выполнению решений в [7].

1) Для заданного массива A размером n требуется выполнить проверку на упорядоченность. Результат присвоить переменной строкового типа (сделать вывод, каким именно образом упорядочен массив, если он окажется упорядоченным: по возрастанию, по убыванию, по неубыванию, по невозрастанию). Пояснения в [7], стр. 245.

2) Выполнить поиск заданного элемента в упорядоченном массиве. Пояснения в [7], стр. 246.

3) Требуется объединить два упорядоченных по возрастанию массива A и B одного размера N (N – заданное натуральное число) в один массив размером 2N также упорядоченный по возрастанию. Пояснения в [7], стр. 247.

4) Требуется объединить два упорядоченных по убыванию массива A и B одного размера N (N – заданное натуральное число) в один массив размером 2N также упорядоченный по убыванию. Пояснения в [7], стр. 247.

5) Требуется объединить два массива A и B одного размера N (N – заданное натуральное число) в один массив размером 2N, упорядоченный по возрастанию. [7], стр. 247.

6) Требуется объединить два массива A и B одного размера N (N – заданное натуральное число) в один массив размером 2N, упорядоченный по убыванию. Пояснения в [7], стр. 247.

7) Требуется объединить два упорядоченных массива A и B одного размера N (N – заданное натуральное число) по возрастанию в один массив размером 2N, упорядоченный по неубыванию. [7], стр. 247; [9], стр. 75.

8) Требуется объединить два упорядоченных массива A и B одного размера N (N – заданное натуральное число) по убыванию в один массив размером 2N, упорядоченный по невозрастанию. Пояснения в [7], стр. 247.

9) Требуется определить количество совпадающих элементов двух упорядоченных по убыванию массивов A и B. Размеры массивов не обязательно одинаковые. Пояснения в [7], стр. 248.

10) Требуется определить количество совпадающих элементов двух неупорядоченных массивов A и B. Размеры массивов не обязательно одинаковые. Пояснения в [7], стр. 248.

11) Требуется определить количество совпадающих элементов двух упорядоченных по убыванию массивов A и B. Размеры массивов одинаковые. Пояснения в [7], стр. 248.

12) Требуется определить количество совпадающих элементов двух неупорядоченных массивов A и B. Размеры массивов одинаковые. Пояснения в [7], стр. 248.

13) Требуется определить количество совпадающих элементов двух упорядоченных по возрастанию массивов A и B. Размеры массивов не обязательно одинаковые. Пояснения в [7], стр. 248.

14) Фамилии участников соревнований по фигурному катанию после короткой программы расположены в порядке, соответствующем занятому месту. Составить список участников в порядке их стартовых номеров для произвольной программы (участники выступают в порядке, обратном занятым местам). Пояснения в [7], стр. 255.

15) Японская радиокомпания провела опрос 250 радиослушателей по трём вопросам:

1) Какое животное Вы связываете с Японией и японцами?

2) Какая черта характера присуща японцам больше всего?

3) Какой неодушевлённый предмет или понятие Вы связываете с Японией?

Большинство опрошенных прислали ответы на все или на часть вопросов. Составить программу получения первых пяти наиболее часто встречающихся ответов по каждому вопросу и доли (в%) каждого такого ответа. Предусмотреть необходимость сжатия столбца ответов в случае отсутствия ответов на некоторые вопросы. Пояснения в [7], стр. 264.

16) В памяти компьютера хранится список фамилий абонентов в алфавитном порядке их номеров телефонов. Составить программу, обеспечивающую быстрый поиск фамилии абонента по номеру телефона. Пояснения в [7], стр. 266.

17) В памяти ЭВМ хранятся списки номеров телефонов и фамилий абонентов, упорядоченные по номерам телефонов, для каждого из пяти телефонных узлов города. Один телефонный узел включает несколько АТС (не более 10). Номера АТС (первые две цифры номера телефона), относящихся к каждому телефонному узлу, также хранятся в памяти ЭВМ. Составить программу, обеспечивающую быстрый поиск фамилии абонента по заданному номеру телефона (количественные данные по телефонной сети не относятся к г. Москва). Пояснения в [7], стр. 266

18) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по возрастанию методом пузырька.

19) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по убыванию методом пузырька.

20) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по возрастанию методом Шелла.

21) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по убыванию методом Шелла.

22) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по возрастанию методом прямого включения. Пояснения в [9], стр. 78 – стр. 80.

23) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по возрастанию методом прямого выбора. Пояснения в [9], стр. 79 – стр. 80.

24) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по убыванию методом прямого включения. Пояснения в [9], стр. 78.

25) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по убыванию методом прямого выбора. Пояснения в [9], стр. 79 – стр. 80.

26) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по убыванию методом сортировки прямым обменом (шейкерная сортировка).

27) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по убыванию методом улучшенной сортировки разделением (быстрая сортировка с рекурсией).

28) Составить программу сортировки, используя деревья сортировки (улучшенная сортировка выбором – сортировка с помощью дерева).

29) Составить программу сортировки в файле (сортировка последовательного файла).

30) Составить программу сортировки в файле (сортировка последовательного файла слиянием).

31) Дан одномерный массив А, состоящий из N элементов (N – заданное натуральное число). Если элементы массива А составляют строго монотонную последовательность, то все положительные элементы массива заменить единицей, иначе отсортировать массив по возрастанию.

32) Дан одномерный массив А, состоящий из N элементов (N – заданное натуральное число). Если имеется хотя бы одна пара совпадающих элементов, то упорядочить элементы этого массива по неубыванию, иначе записать элементы этого массива в обратном порядке.

33) Заданы два одномерных целочисленных массива А и В, состоящие из N элементов каждый (N – заданное натуральное число). Объединить элементы этих двух массивов в один и упорядочить их по неубыванию, удалив из него элементы, являющиеся четными положительными числами.

34) Дан одномерный целочисленный массив А, состоящий из N элементов (N – заданное натуральное число). Присвоить переменной F значение 1, если элементы массива составляют строго возрастающую последовательность, F=-1, если строго убывающую, F=2, если элементы массива составляют знакочередующуюся последовательность, F=0, если она не является строго монотонной или знакочередующейся.

35) Дан одномерный массив А, состоящий из N элементов (N – заданное натуральное число). Упорядочить массив А по неубыванию, воспользовавшись следующим алгоритмом сортировки. Отыскивается максимальный элемент и переносится в конец. Затем этот алгоритм применяется ко всем элементам кроме последнего и т. д.

36) Даны два одномерных целочисленных массива А и В, состоящих из N элементов каждый (N – заданное натуральное число). Сформировать массив, элементы которого являются пересечением указанных массивов, и расположить его элементы по неубыванию. Одинаковые значения заносить только один раз. Если пресечение массивов есть пустое множество, то выдать соответствующее текстовое сообщение.

37) Даны два одномерных целочисленных массива А и В, состоящих из N элементов каждый, N – заданное натуральное число. Сформировать массив С, элементы которого являются объединением указанных массивов, и расположить его элементы по неубыванию. Одинаковые значение заносить только один раз.

38) Дан одномерный массив А, состоящий из N элементов (N – заданное натуральное число). Присвоить переменной F=1, если элементы массива составляют строгую возрастающую арифметическую прогрессию, и F=-1, если строго убывающую арифметическую прогрессию.

39) Дан одномерный целочисленный массив А, состоящий из N элементов, N – заданное натуральное число. Пусть МАХ – наибольшее, а MIN – наименьшее значения среди элементов массива. Составить одномерный массив В из простых чисел из сегмента [MIN, МАХ], которые не являются элементами массива А, записав его элементы в порядке неубывания. Если таких элементов нет, то выдать соответствующее текстовое сообщение.

40) Каждый из 12 магазинов имеет свой список товаров с известными ценами и в известном количестве. Число товаров в каждом списке различно и заранее не определено. Подсчитать, на какую сумму денег имеет товаров каждый магазин, расположив список в порядке убывания этой суммы.

41) Каждая из 30 групп студентов имеет свой процент успеваемости (от 0 % до 100 %). Составить список номеров групп, которым необходимо повысить успеваемость до среднего уровня. Список расположить в порядке убывания процента успеваемости этих групп.

42) В магазине имеются товары различных наименований. В течение дня каждый из М покупателей (М – заданное число) сообщил о своем намерении приобрести определенное количество товара одного из наименований. Требуется определить суммарный спрос на товары каждого наименования, расположив товары в порядке убывания дневного спроса на них.

43) Опросили 200 подписчиков. Каждый из них назвал три любимые газеты. Напечатать пронумерованный список первых 10 наиболее популярных газет, расположив названия газет в списке в порядке уменьшения числа поданных за них голосов. Предусмотреть, что каждый из опрошенных должен назвать три разные газеты, а общее число названных газет может быть как больше, так и меньше 10.

44) Каждый из X магазинов в течение месяца работал Di дней (N и Di – заданные числа, где i=l, 2,…, X). Известна прибыль каждого магазина в каждый день его работы. Необходимо напечатать упорядоченный по месячным доходам список названий магазинов, имеющих прибыль в пересчете на один день работы выше средней дневной прибыли по всем магазинам.

45) В гостинице N этажей по M номеров на этаже (N и М заданы, а нумерация гостиничных номеров сплошная). Требуется для каждого номера ввести его стоимость и информацию о том, свободен он, занят или забронирован, а затем получить ведомости всех свободных, занятых и забронированных номеров в порядке возрастания их стоимости с указанием стоимости проживания, этажа и номера гостиницы.

46) В итоговой таблице первого круга футбольного чемпионата, каждая из N команд (N и названия команд заданы) представлена количеством забитых и пропущенных голов в каждой из встреч с противниками. Перечислить команды, которые в сумме забили в чужие ворота голов больше, чем пропустили в свои, в порядке убывания разности забитых и пропущенных голов.

47) По результатам опроса прошлого года известен список 10 политических деятелей в порядке убывания их популярности. Проведен новый опрос. Каждый из N журналистов (N – заданное число) назвал три различные фамилии из этого списка. Требуется получить новый список в порядке убывания популярности политических деятелей и показать место, которое занимал каждый деятель в предыдущем опросе. Предусмотреть проверку: каждый из опрошенных журналистов называл разные фамилии и только из имеющихся в старом списке.

48) Опросили 30 кинологов, каждый из которых 3 раза назвал одну породу собак или разные породы собак в любом сочетании, как самую популярную (популярные) по его мнению. Вывести на экран список пород, попавших в первую десятку в порядке убывания популярности, с указанием числа полученных ими голосов опрошенных.

49) Каждая из М библиотек района (М – задано) составляет заявку на приобретение книг. Заявка содержит перечень книг, состоящий из не более 20 наименований. Каждая библиотека в каждой строке заявки указывает название книги, фамилию автора, а также количество экземпляров. Определить суммарный спрос на каждую из указанных книг, и напечатать общий список книг в порядке убывания спроса.

50) 200 учеников шести школ города (номера школ заданы) принимают участие в тестировании по математике. Правильные численные ответы к пяти предложенным задачам даны. О каждом ученике известно: фамилия, номер школы и пять ответов на задачи. Сведения об учениках не имеют определенной упорядоченности. Составить списки учеников по школам, расположив в каждом списке фамилии в порядке убывания количества решенных задач. Предусмотреть возможный ответ «не решил».

51) Каждое из М садоводческих товариществ (М – заданное число) направляет на базу свой список-заявку с указанием наименований требуемых и семян и их количества в кг. Число наименований семян в заявке для каждого товарищества не превышает 20 ти. Составить суммарный запрос на базу, указав общее необходимое количество семян каждого вида, расположив наименования в списке в порядке убывания спроса.

52) В массив размерности N (N – заданное натуральное число) ввести слова длиной не более 15 символов каждое. Вывести на экран эти слова в порядке увеличения их длины с указанием количества букв «i» в каждом из них. Выполнить проверку вводимой информации.

53) Имеются сведения о каждом рейсе Аэрофлота с номерами от 1 до 100: пункт назначения и количество перевезенных пассажиров. Определить количество пунктов назначения и построить списки номеров рейсов для каждого из них в порядке уменьшения числа пассажиров, перевезенных этими рейсами.

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

55) Ввести произвольные числа в два одномерных массива одинакового размера N (N – заданное натуральное число). Переставить элементы первого массива так, чтобы его максимальный элемент находился на месте, расположения максимального элемента из второго массива, а каждый очередной по убыванию элемент из первого массива располагался на месте, соответствующем расположению очередного по убыванию элемента второго массива. Напечатать модифицированный массив.

56) В массив заданного размера N (от 3 до 10) ввести произвольные числа. Изменить порядок следования элементов в нем на обратный отдельно до и отдельно после К-го элемента массива (К задано). Напечатать модифицированный массив. При вводе данных осуществить проверку.

57) В массив заданного размера N (от 3 до 10) ввести произвольные числа. Не изменяя состояния этого массива и используя лишь один дополнительный массив, напечатать номера элементов исходного массива, соответствующие порядку убывания значений элементов. При вводе данных осуществить проверку.

58) В два одномерных массива одинакового размера N (N – заданное натуральное число) ввести произвольные числа. Не изменяя исходных массивов, сформировать из элементов первого массива третий массив так, чтобы максимальный элемент первого массива в третьем находился на месте, соответствующем расположению максимального во втором, а каждый очередной по убыванию элемент из первого массива располагался в третьем на месте, соответствующем расположению очередного по убыванию элемента второго массива. Напечатать все три массива.

59) Напечатать в возрастающем порядке все четырехзначные натуральные числа, все цифры которых являются соседями в натуральном ряду. Примерами таких чисел являются 4756 и 7645. Найти количество и среднее арифметическое этих чисел.

60) Ввести числовую матрицу размером NxM (N, M заданы). Найти максимальный элемент среди расположенных в тех строках матрицы, которые являются упорядоченными (либо по возрастанию, либо по убыванию), или сообщить, что такого элемента нет.


1.4 Вопросы для самопроверки


1) Какими свойствами обладает отношение частичного порядка? Приведите примеры этого отношения.

2) Дайте определение отношения линейного порядка.

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

4) В чём заключается преимущество отсортированных (упорядоченных) данных?

5) Как рассматривается задача сортировки с точки зрения программирования?

6) От каких факторов зависит эффективность алгоритма сортировки?

7) Перечислите наиболее часто используемые на практике методы поиска и сортировки.

8) Каким образом могут быть представлены данные при поиске и сортировке?

9) Перечислите основные операции при работе с данными.

10) В чём заключается алгоритм линейного поиска?

11) В чём заключается алгоритм бинарного поиска?

12) Опишите кратко поиск в бинарных деревьях.

13) Какие функции используются при оценке времени исполнения алгоритма?

14) В чём заключается метод сортировки вставками?

15) В чём заключается метод сортировки с помощью включения, прямого включения?

16) В чём заключается метод Шелла?

17) Опишите сортировку с помощью обменов.

18) Опишите алгоритм быстрой сортировки, предложенный Ч. Хоаром (QuickSort).



Практическая работа № 2. Представление множеств в компьютере


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


2.1 Теоретическая часть


2.1.1 Множества и операции над ними

Множество – это совокупность объектов, называемых элементами множества. Например:

• {Эссекс, Йоркшир, Девон};

• {2, 3, 5, 7, 11}.

В этом примере элементы каждого множества заключены в фигурные скобки. Чтобы обеспечить возможность ссылок, мы будем обозначать множества прописными латинскими буквами. Например,

S = {3, 2, 11, 5, 7} – множество, содержащее целые числа. Заметим, что множество S совпадает с одним из множеств, выписанных выше, поскольку порядок, в котором записываются элементы множества, значения не имеет.

В общем случае запись аОсновы дискретной математикиS означает, что объект а – элемент множества S. Часто говорят, что а принадлежит множеству S. Если объект а не принадлежит S, то пишут: аОсновы дискретной математики S.

В современных языках программирования требуется, чтобы переменные объявлялись как принадлежащие к определенному типу данных. Тип данных представляет собой множество объектов со списком стандартных операций над ними. Определение типа переменных равносильно указанию множества, из которого переменным присваиваются значения [22].

Существует несколько способов конструирования нового множества из двух данных. Опишем коротко эти операции на множествах. Прежде всего, отметим, что все элементы некоторых множеств принадлежали другим большим множествам. Например, все элементы множества С = {0, 1, 4, 9, 16,…} содержатся в множестве

Z = {0, ±1, ±2, ±3,…}.


Основы дискретной математики

Рисунок 2.1 – Диаграмма Венна подмножества А Основы дискретной математикиS


Объединением двух множеств А и В называется множество

АОсновы дискретной математикиВ = {х: х Основы дискретной математики А или х Основы дискретной математики В}.

Оно состоит из тех элементов, которые принадлежат либо множеству A, либо множеству В, а возможно и обоим сразу. Диаграмма Венна объединения показана на рисунке 2.2.

Пересечением двух множеств А и В называется множество

А Основы дискретной математики В = {х: х Основы дискретной математики А и х Основы дискретной математикиВ}.

Оно состоит из элементов, которые принадлежат как множеству А, так и множеству B. Диаграмма Венна пересечения приведена на рисунке 2.3.


Основы дискретной математики Основы дискретной математики

Рисунок 2.2 – Диаграмма Венна Рисунок 2.3 – Диаграмма Венна для объединения множеств для пересечения множеств


Дополнением множества В до множества А называется


AВ = {х: х Основы дискретной математики А и x Основы дискретной математикиВ}.

Дополнение А В состоит из всех элементов множества А, которые не принадлежат В (см. рисунок 2.4). Если мы оперируем подмножествами некоего большого множества U, мы называем U универсальным множеством для данной задачи. На наших диаграммах Венна прямоугольник как раз и символизирует это универсальное множество. Для подмножества А универсального множества U можно рассматривать дополнение А до U, т. е. U А. Поскольку в каждой конкретной задаче универсальное множество фиксировано, множество U А обычно обозначают Основы дискретной математики и называют просто дополнением множества А. Таким образом, понимая, что мы работаем с подмножествами универсального множества U можно записать


Основы дискретной математики = {х: не (хОсновы дискретной математики А)} у Основы дискретной математики = {х: х Основы дискретной математики A}.


Диаграмма Венна дополнения изображена на рисунке 2.5.


Основы дискретной математики

Рисунок 2.4 – Диаграмма Венна разности А В

Основы дискретной математики


Рисунок 2.5 – Диаграмма Венна дополнения Основы дискретной математики


Симметрической разностью двух множеств А и В называют множество А Δ В = {х: (х Основы дискретной математики А и х Основы дискретной математики В) или (х Основы дискретной математики В и х Основы дискретной математики А)}.

Оно состоит из всех тех и только тех элементов универсального множества, которые либо принадлежат А и не принадлежат В, либо наоборот, принадлежат В, но не А. Грубо говоря, симметрическая разность состоит из элементов, лежащих либо в А, либо в В, но не одновременно. Диаграмма Венна, иллюстрирующая симметрическую разность, начерчена на рисунке 2.6.

Основы дискретной математики

Рисунок 2.6 – Диаграмма Венна симметрической разности А Δ В


2.1.2 Представление множеств и отношений в программах

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

Следует подчеркнуть, что, как правило, один и тот же объект может быть представлен многими разными способами, причем нельзя указать способ, который является наилучшим для всех возможных случаев. В одних случаях выгодно использовать одно представление, а в других – другое. Выбор представления зависит от целого ряда факторов: особенностей представляемого объекта, состава и относительной частоты использования операций в конкретной задаче и т. д. Умение выбрать наиболее подходящее для данного случая представление является основой искусства практического программирования. Хороший программист отличается тем, что он знает много разных способов представления и умело выбирает наиболее подходящий.

Множества и задачи информационного поиска

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: