АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. Доведення рівностей з множинами
  2. Множина іменників
  3. Множинні обміни. Інтерференція обмінів.
  4. Операції над множинами
  5. Основні поняття теорії множин Кантора
  6. Поставте слова, наведені в дужках, у формі множини. Перекладіть речення.
  7. Принцип замикання множини атрибутів
  8. Способи задання множин
  9. Фізичні основи представлення інформації у комп'ютерах.

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

Одним із найпоширеніших та найпростіших способів є зображення множин за допомогою бітових рядків. Нехай універсальна множина 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 має велику потужність, а підмножини універсальної множини не дуже потужні, то зображення за допомогою бітових рядків не є ефективним з точки зору витрат пам'яті. У такому разі для зображення множин доцільно використовувати інші структури даних – як правило, зв'язані списки, масиви або хеш-таблиці.


1 | 2 | 3 | 4 | 5 | 6 | 7 |


Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)