«Способы представления последовательностей, множеств, графов и деревьев»

Министерство по развитию информационных технологий и коммуникаций
Республики Узбекистан Ташкентский университет информационных технологий имени Аль-Хорезми
Самостоятельная работа № 1
Тема: «Способы представления последовательностей, множеств, графов и деревьев»

Выполнил: Фаттаев Акбар
Студент группы: 204
Ташкент- 2022

Основные понятия
Создатель теории множеств Г.Кантор определил понятие множества и элемента множества следующим образом: ”Под множеством мы понимаем собрание определенных отличных друг от друга объектов (реальных или воображаемых), называемых элементами множества, в их общности”. Обычно множества обозначают прописными буквами латинского алфавита, а их элементы – строчными буквами или числами.
Количество элементов в множестве А называется мощностью множества А и обозначается |А| . Если каждому элементу множества А можно поставить в соответствие единственный элемент множества В и каждому элементу множества В можно поставить в соответствие единственный элемент множества А , то множества А и В называются равномощными и обозначается |А|=|В| .
Множество, состоящее из конечного числа элементов, называется конечным .
Множество, не являющиеся конечным, называется бесконечным . Бесконечное множество называется счетным , если оно равномощно множеству N всех натуральных чисел. Говорят, что все элементы счетного множества можно пронумеровать. В противном случае бесконечное множество называется несчетным .
Множество, не содержащее элементов, называется пустым и обозначается  или {}.
Обычно в конкретных рассуждениях элементы всех множеств берутся из некоторого одного, достаточно широкого множества U (своего для каждого случая), которое называется универсумом.
Два множества А и В называются равными, если они состоят из одних и тех же элементов (А=В).
Операции над множествами
1. Включение А в В   истинно, если каждый элемент множества А принадлежит множеству В. В этом случае А называется подмножеством В, а В – надмножеством А.
Множества А и В равны (А=В), если  . Пустое множество является подмножеством любого множества.
Универсум является надмножеством любого множества.
Множество всех подмножеств множества M называется булеан ом и обозначается  :

Для конечного множества  . Каждому подмножеству А можно сопоставить |M|-разрядный двоичный вектор С в котором:
C_i=1, если  и
C_i=0, если  , где i – элемент множества M,
С_i – i-й разряд вектора С.
Количество различных |M|-разрядных двоичных векторов равно 2^|M|, следовательно |2^М|=2^|M|.
2. Строгое включение А в В  истинно, если  . Если  , то А есть собственное подмножество В.
3. Объединение А и В (А U В) есть множество, состоящее из всех тех и только тех элементов, которые принадлежат А или В, т.е.

4. Пересечение А и В (А n В) есть множество, состоящее из всех тех и только тех элементов, которые принадлежат каждому из множеств А и В, т.е.

5. Разность А и В (А-В) есть множество, состоящее из всех тех и только тех элементов множества А, которые не принадлежат множеству В, т.е.

Для обозначения разности множеств в дискретной математике обычно используют символ “\”.
6. Симметрическая разность А и В (АΔВ) есть множество, состоящее из всех тех и только тех элементов множества А, которые не принадлежат множеству В и только тех элементов множества В, которые не принадлежат множеству А, т.е.

7. Дополнение А до универсума U ( ) есть множество, состоящее из всех тех и только тех элементов универсума U, которые не принадлежат множеству А, т.е.



Таблица 1.1 Приоритеты операций над множествами

Свойства операций над множествами
1. Идемпотентность:

2. Коммутативность:

3. Ассоциативность:

4. Дистрибутивность для пересечения и объединения:

5. Дистрибутивность для пересечения и разности:

6. Дистрибутивность для пересечения и симметрической разности:

7. Дистрибутивность для разности:

8. Поглощения:

9. Свойства нуля:

10. Свойства единицы:

11. Инвалютивность: 
12. Законы де Моргана:

13. Законы де Моргана для разности, пересечения и объединения:

14. Свойства дополнения:

15. Определение разности:

16. Определение объединения:

17. Определение пересечения:

Способы задания множеств
1. Перечислением всех элементов.
A={a,b,c} , B={b,a,c} , C={a} , D={1,2,3,5,9}. Из определения равенства множеств вытекает, что A=B.
2. Заданием характеристического свойства, выделяющего элементы данного множества среди элементов указанного или указанных других множеств.
A={x | x  N и x<10} (N – множество натуральных чисел),
B={1,2,3,4,5,6,7,8,9} , A=B.
3. Описанием порождающей процедуры с указанием множества (или множеств), которое “пробегает” параметр (или параметры) процедуры.
A={x² | x N} – множество всех квадратов натуральных чисел.
Перечислением можно задать только конечное множество, а с помощью характеристического свойства или порождающей процедуры - конечное или бесконечное множество.
Способы представления и хранения множества в памяти компьютера (ЭВМ)
Есть четыре основных варианта хранения:

• 
  Массив
  
• 
  Хэш таблица
  
• 
  Деревья
  
• 
  Списки
  

Массив — это способ хранения, при котором элементы множества расположены последовательно в ячейках.
Самый экономичный вариант, если известна мощность множества, а элементы - данные одного типа.
Список — способ хранения, при котором память выделяется для каждого элемента отдельно и ровно столько, сколько нужно.
Недостаток: необходимо хранить указатель на следующий элемент и тратить время на работу с ним.
Сложность массива и списка - линейна, O(n).