Комп’ютерне представлення множин

Зобразити множини у комп’ютері можна різними способами. Наприклад, накопичити елементи множини в невпорядкованому вигляді. Але тоді операції із множинами вимагатимуть значних ресурсів часу, адже щоразу необхідно буде здійснювати перегляд елементів. Тому є інші способи зображення множин у комп'ютері.

Одним із найпоширеніших та найпростіших способів є зображення множин за допомогою бітових рядків. Нехай універсальна множина U містить п елементів. Упорядкуємо довільним способом елементи універсальної множини. Тоді

Множину зображають у комп'ютері рядком із 0 та 1 довжи­ни п так: якщо , то і -й біт дорівнює 1, якщо , то і -й біт дорівнює 0.

Приклад 7.1. Нехай , , . Тоді множину A зобразимо рядком 010000110110, а множину В – рядком 110001100100. p

Після представлення множин у вигляді бітових рядків, легко робити операції над ними, адже це будуть порозрядні логічні операції над відповідними рядками.

Наприклад, перетин множин – це порозрядна кон'юнкція над бітовими рядками, а об'єднання множин – порозрядна диз'юнкція над бітовими рядками.

Логічні операції наве­дені в табл. 7.1.

Таблиця 7.1.

аi	bi

Приклад 7.2. Нехай , , . Знайдемо комп'ютерне зображення перетину множин .Виконаємо порозрядну кон'юнкцію рядків, які зображають множини А та В:

= 010000110110;

= 110001100100.

= 010000100100.

Отже, повертаючись до звичайного зображення множин, маємо .p

Приклад 7.3. Нехай , , . Знайдемо об'єднання множин . Виконаємо порозрядну диз'юнкцію рядків, які зображають множини А та В:

= 010000110110;

= 110001100100;

= 110001110110.

Отже, .p

Якщо універсальна множина U має велику потужність, а підмножини універсальної множини не дуже потужні, то зображення за допомогою бітових рядків не є ефективним з точки зору витрат пам'яті. У такому разі для зображення множин доцільно використовувати інші структури даних – як правило, зв'язані списки, масиви або хеш-таблиці.

Поиск по сайту: