Теория множеств



Download 0,49 Mb.
bet2/5
Sana22.02.2022
Hajmi0,49 Mb.
#94069
1   2   3   4   5
Bog'liq
Теории Множ. Унар и Бинар

Объединением (или суммой) множеств А и В называется множество, состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множеств А или В:  B = {x | x  A или x  B}.
Пересечением (или произведением) множеств А и В называется множество, состоящее из тех и только тех элементов, которые принадлежат каждому из множеств А и В:  B = {x | x  A и x  B}.
Если  B = , то множества А и В называются непересекающимися.
Разностью множеств А и В называется множество \ B , состоящее из тех и только тех элементов, которые принадлежат А, но не принадлежат В: \ B = {x | x  A и x  B}.
Симметрической разностью множеств А и В называется множествоΔ B = (A  B) \ (A  B) = {x | (x  A и B) или (x  B и A)}.
Дополнением множества А называется множество всех элементов универсального множества, не входящих в A: A = U \ A = {x | x  A}.
Операции объединения и пересечения допускают обобщение для большего количества множеств (в том числе и бесконечного). В общем случае для объединения k множеств используется обозначение , или для бесконечного числа множеств: = {x |  i  I | x  Ai}. Аналогично, для пересечения k множеств используется обозначение , или , если количество множеств бесконечно: = {x |  i  I |x  Ai }.
Н а рисунке 1.1 (справа) приведены т.н. диаграммы Эйлера-Венна, графически иллюстрирующие вышеописанные операции над множествами. Введенные операции показаны на диаграммах Венна темным цветом. Такие геометрические представления множеств часто используются при решении задач или доказательстве каких-либо утверждений.

  1. Рассмотрим два множества чисел: А = {1, 2, 3, 4}; B = {1, 3, 5, 7}. Тогда операции над этими множествами будут иметь вид:
    объединение  B = {1, 2, 3, 4, 5, 7};
    пересечение  B = {1, 3}; разность \ B = {2, 4} и \ A = {5, 7}; симметрическая разность Δ B = {2, 4, 5, 7}. Для рассмотрения дополнения A необходимо знать универсальное множество, все элементы которого за исключением элементов A и будут являться дополнением.

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

Задать представление какого-либо объекта в программе – означает описать в терминах используемой системы программирования структуру данных, используемую для хранения информации о представляемом объекте, и алгоритмы над выбранными структурами данных, которые реализуют присущие данному объекту операции.
Один и тот же объект может быть представлен различными способами, причем в разных ситуациях могут оказаться наиболее эффективными разные способы. Выбор представления зависит от целого ряда факторов: особенности представляемого объекта, состава и относительной частоты использования операций в конкретной задаче, и т.д. Хороший программист должен знать разные способы представления объекта и в каждой конкретной ситуации уметь выбрать из них наиболее подходящий.
Для конечного универсума, мощность которого не превосходит разрядности машинного слова, подмножества универсума могут представляться битовой шкалой (аналог характеристической функции – 0 или 1 для каждого элемента). Битовая шкала имеет размерность универсума, и для каждого подмножества число единиц в соответствующей ему битовой шкале определяется мощностью этого подмножества. Если элемент входит в подмножество, то ему соответствует 1, иначе 0. Тогда операции над подмножествами осуществляются посредством поразрядных логических операций.
Во многих переборных алгоритмах требуется последовательно рассмотреть все подмножества заданного множества. В случае использования битовой шкалы существуют специальные алгоритмы, которые будут рассмотрены позже.
Если универсум велик, а подмножества имеют сравнительно небольшую мощность, то использование характеристических функций невыгодно, т.к. в них будет много нулей. Для представления таких множеств обычно используют списки элементов. Элемент множества тогда может быть представлен записью с двумя полями: информационным и указателем на следующий элемент. Трудоемкость операций включения, пересечения и объединения определяется как O(mn), где m и n – мощности множеств; операции  – как O(n).
При использовании списков, упорядоченных по информационному полю, трудоемкость всех операций является линейной (О(n)). В таком случае эффективная организация всех операций над множествами основана на общем алгоритме, известном как алгоритм типа слияния.
Алгоритм типа слияния параллельно просматривает два множества, представленных упорядоченными списками, причем на каждом шаге продвижение вперед (увеличение номера рассматриваемого элемента) происходит в том множестве, в котором текущий элемент меньше. В качестве простейшей организации множеств можно использовать упорядоченный массив элементов.
1. Проверка включения AB
Вход: Два упорядоченных множества A и B (массивы).
Выход: да или нет (1 или 0, true или false).
i:=1; j:=1; // указатели на начало множеств
пока i|A|+1 и j|B|+1 цикл
если A[i] < B[j] то вернуть 0 и выход // элемент A отсутствует в B
иначе если A[i] > B[j] то j:=j+1 // переход к след. элементу B
иначе // элементы совпали – перейти к следующим
i:=i+1; j:=j+1;
конец если
конец цикла
если i=|A|+1 то вернуть 1 иначе вернуть 0.
Алгоритмы, вычисляющие объединение множеств, пересечение и дополнение устроены совершенно аналогичным образом. Общее действие – продвижение вперед (увеличение индекса) в том массиве, элемент которого меньше, и сразу в обоих, если элементы равны.
Для определения объединения в результирующее множество заносятся каждый из меньших элементов и один, если они равны. Если конец одного из множеств достигнут раньше, все оставшиеся элементы другого дописываются в конец итогового множества.
Для определения пересечения в результирующее множество заносится тот элемент, который совпал у обоих множеств. Если конец одного из множеств достигнут раньше, работа алгоритма заканчивается.

      1. Разбиения и покрытия

Пусть Ě ={Ei} для i I – некоторое семейство непустых подмножеств множества M, Ei  M. Тогда семейство Ě называется покрытием множества M, если каждый элемент множества M принадлежит хотя бы одному из Ei:

Download 0,49 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish