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

Рефераты / Программирование, компьютеры и кибернетика / Основы дискретной математики

Const K:D = [5,9,11,17]; R:D = [1 9,13,20];

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

Var AA:A;, тогда возможна запись (тип A объявлен выше)

AA:=[Char(13), Char(7), ‘0’, ‘Q’];

Если требуется присвоить этой переменной значение «пусто», то используется такой конструктор: AA:= [];

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

Ка

к и для других типов, имеется ряд встроенных операций для типа множество. Пусть заданы следующие типы и переменные: Type Mn = set of 1 50; Var A, B, C: Mn;

Пусть переменным присвоены значения:

A:= [3,5,9,10]; B:= [1,7,9,10];

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

C:=A+B; {1,3,5,7,9,10}

Разность (A-B <> B-A)

C:=A-B; {3,5}

C:=B-A; {1,7}

Пересечение (умножение)

C:=A*B; {9,10}

Проверка эквивалентности, например в операторе IF

(A = B) {False}

Проверка неэквивалентности

(A <> B) {True}

Проверка, является ли одно множество подмножеством другого

(A>=B) {False}

(A<=B) {False}

Проверка, входит ли заданный элемент в заданное множество

(3 in A) {True}

(3 in B) {False}

Стандартные подпрограммы для выполнения некоторых действий над множествами

Exclude (A, 3); удалить из множества A элемент 3}

Include (A, 3); {вставить элемент 3 в множество A}.

2.1.5 Характеристический вектор множества

Характеристическим вектором Vx множества X, заданного на универсальном множестве I, является вектор, содержащий 0 и 1. Количество элементов в векторе Vx равно количеству элементов в универсальном множестве, причём, 1 записывается в случае, если элемент присутствует и в универсальном множестве I, и в множестве X, в противном случае записывается 0. Некоторые задачи с множествами, особенно на компьютере, удобно решать, используя характеристические векторы [1].

Действия над векторами похожи на логические операции.

Над характеристическими векторами выполняются поразрядно логические операции:

при пересечении – логическое умножение;

при объединении – логическое сложение;

при нахождении дополнения – значения в исходном векторе изменяются на противоположные.

При объединении множеств элементы характеристического вектора считают по правилу:

2) При пересечении множеств элементы характеристического вектора считают по правилу:

3) При нахождении дополнения нули меняют на единицы, единицы – на нули;

4) При нахождении симметричной разности , используют формулу:

Пример 2.5 Пусть I = {1, 2, 3, 4, 5, 6}, А={1, 2, 4, 5} и В={3, 5} Характеристическим вектором множества А является вектор а = (1, 1, 0, 1, 1, 0). Характеристический вектор множества В равен b = (0, 0, 1, 0, 1, 0).

Вычислим характеристический вектор множества A U . Он равен

а или (не b) = (1, 1, 0, 1, 1, 0) или (1, 1, 0 1, 0, 1) = (1,1,0,1,1,1).

Следовательно, A U = {1, 2, 4, 5, 6}.

Характеристический вектор множества А Δ В равен

(а и (не b)) или (b и (не а)) = ((1, 1, 0, 1, 1, 0) и (1, 1, 0, 1, 0, 1)) или

или ((0, 0, 1, 0, 1, 0) и (0, 0, 1, 0, 0, 1)) = (1, 1, 0, 1, 0, 0) или (0, 0, 1, 0, 0, 0) = (1, 1, 1, 1, 0, 0).

Таким образом, А Δ В = {1, 2, 3, 4}.

2.2 Практическая часть

2.2.1 Задание к работе

1. Изучить теоретический материал, включая и дополнительные сведения, представленные в теоретической части.

2. Задать самостоятельно универсальное множество X, множества A, B, C (или некоторые из них, т. к. в некоторых вариантах используются только два множества).

3. Cформировать характеристические векторы для исходных множеств и получить результирующее множество (по варианту), используя характеристические вектора.

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

5. Вывести результаты, полученные в пункте 3 и пункте 4.

6. Сравнить эти результаты и сделать выводы.

7. Пункты 3 и 4 выполнить двумя способами: аналитически и реализовать в виде приложения на Delphi.

Примечание:

1. Если в выражении используется операция разности или симметрической разности, то при выполнении действий с характеристическими векторами (пункт 3) заменить их другими операциями на множествах (использовать формулы из лекций и [23]).

2. При выполнении пункта 4 операцию симметрической разности заменить другими операциями, которые используются в Object Pascal.

3. В качестве дополнительного задания предлагается реализовать любой описанный в теоретической части алгоритм в виде приложения на Delphi.

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

Пример 1.

1) Задание по варианту

I:={1,2,3,4,5,6,7}

Значения векторов A, B, C берутся произвольно, но с учетом, что количество элементов не должно быть больше 7.

Найти: характеристический вектор множеств A, B и C, характеристический вектор множества D – Vd, перейти от Vd к D.

2) Создать приложение в среде Delphi, которое решит данную задачу.

3) Решить задачу аналитически.

4) К защите данной работы необходимо знать теоретический материал по данной теме из лекций и методички, а также ответить на «Вопросы для самопроверки».