Представление множеств ЭВМ

Содержание

Слайд 2

Немецкий ученый, математик, создатель теории множеств
Родился в Петербурге в 1845г.
В

Немецкий ученый, математик, создатель теории множеств Родился в Петербурге в 1845г. В
1867 г. окончил Берлинский университет
В 1872-1913 гг. – профессор университета в Галле
Сформулировал общее понятие мощности множества (1878)
Развил принципы сравнения мощностей множеств и
Систематически изложил принципы своего учения
Созданная Кантором теория множеств, некоторые идеи которой имелись у его предшественников, послужила причиной общего пересмотра логических основ математики и оказала влияние на всю современную ее структуру.

Георг Кантор
(XIX-XXвв.)

Историческая справка

Слайд 3

Цели: 1) описать способы хранения информации о принадлежности элемента множеству, 2)

Цели: 1) описать способы хранения информации о принадлежности элемента множеству, 2) описать
описать алгоритмы для вычисления результатов операций над множествами

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

Слайд 4

Один и тот же объект может быть представлен разными способами. Выбор представления

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

Слайд 5

Некоторые способы задания множеств

Некоторые способы задания множеств

Слайд 6

Булеан – множество всех подмножеств данного множества M
Обозначение: B(M)
Пример: дано множество A={a,b,c}.

Булеан – множество всех подмножеств данного множества M Обозначение: B(M) Пример: дано
Найти В(А).
B(A)={ ∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} }
Мощность булеана определяется по формуле:
|B(M)|=2 |M|
Пустое множество и само множество являются несобственными подмножествами множества М
Остальные подмножества – собственные

Булеан. Мощность булеана

Слайд 7

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

А

В

A

B

A

A

A

B

Операции над множествами А В A B A A A B

Слайд 8

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

Представление множества машинным словом или битовой шкалой Пусть универсальное множество конечно и
п его элементов не превосходит разрядности ЭВМ. Занумеруем элементы универсума, т. е. . Подмножество А универсума представляется кодом С, в котором где - это i-тый разряд кода С. Тогда, код пересечения множеств А и В есть поразрядное логическое произведение кода множества А и кода множества В. Код объединения множеств А и В есть поразрядная логическая сумма кода множества А и кода множества В. Код дополнения множеств А до универсума есть инверсия кода множества А. в большинстве ЭВМ для этих операций есть соответствующие команды. Таким образом, операции над небольшими множествами выполняются эффективно.

Слайд 9

Если универсум очень велик или бесконечен, а рассматриваемые подмножества не очень велики,

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

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

Слайд 10

Множества будем хранить как массив с нумерацией элементов, начинающейся с единицы.
Обозначим через

Множества будем хранить как массив с нумерацией элементов, начинающейся с единицы. Обозначим
i номер текущего рассматриваемого элемента в множестве A, через j – номер текущего рассматриваемого элемента множества B. Будем получать множество P, представляющее собой пересечение множеств A и B. Через k обозначим мощность множества P. Также k будет и номером последнего добавленного элемента в P

Алгоритм нахождения пересечения слиянием

Слайд 11

Положить i = j = 1 и k = 0.
Если в A

Положить i = j = 1 и k = 0. Если в
и B (одновременно) есть ещё не просмотренные элементы, выполнить:
Если A[i] = B[j], то выполнить:
Добавить A[i] в Р, то есть k := k + 1 и Р[k] := A[i]
Перейти к следующим элементам множеств A, B, то есть i := i + 1 и j := j + 1
Если A[i] < B[j], то перейти к следующему элементу множества A, то есть i := i +1
В остальных случаях (то есть когда A[i] > B[j]) перейти к следующему элементу множества B, то есть j := j + 1
Перейти к пункту 2.
Пример.
Сравниваемые пары: (1,3), (3,3), (6,4), (6,5), (6,6), (8,7)
Р 3 6

Алгоритм решения

Слайд 12

Алгоритм нахождения объединения слиянием

Обозначим через i номер текущего рассматриваемого элемента в множестве

Алгоритм нахождения объединения слиянием Обозначим через i номер текущего рассматриваемого элемента в
A, через j – номер текущего рассматриваемого элемента множества B. Будем получать множество Р, представляющее собой объединение множеств A и B. Через k обозначим мощность множества Р. Также k будет и номером последнего добавленного элемента в Р.
Имя файла: Представление-множеств-ЭВМ.pptx
Количество просмотров: 29
Количество скачиваний: 0