ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
 Скачать 4.33 Mb.
|
|
1.9. Способы представления множества в памяти ЭВМ Для представления конечного множества в памяти ЭВМ можно использовать различные способы. Будем считать, что универсум U представляет собой KU натуральных чисел U = {x | x N и x KU}. Если это не так, то элементы множества U можно пронумеровать и определить однозначное соответствие между элементами множества U и их номерами. В этом случае элементами множеств можно считать натуральные числа, которые можно сравнивать и использовать в качестве индекса элемента массива. 1. Элементы множества А хранятся в переменной А типа массив, мощность множества А — в переменной KA. Количество элементов в массиве А равно мощности универсума. Элементы массива А неупоря- дочены. 2. Элементы множества А хранятся в переменной А типа массив, мощность множества А — в переменной KA. Количество элементов в массиве А равно мощности универсума. Элементы массива А упорядочены по возрастанию. 3. Элементы множества А хранятся в переменной А типа массив, элементы которого типа boolean. Если i A, то А = true, иначе A i = false. Количество элементов в массиве А равно мощности универсума. 4. Множество А представляется двоичным кодом Св котором C i = 1, если i A и C i = 0, если i A, где С — й разряд кода СВ зависимости от мощности универсума код Сможет храниться в простой переменной или в массиве. 5. Для хранения множества можно использовать множественный тип. 1.10. Алгоритмы реализации операций надмножествами Алгоритмы реализации операций надмножествами зависят от способа представления множества в памяти ЭВМ. 1. Элементы множества А хранятся в переменной А типа массив, мощность множества А — в переменной KA. Количество элементов в массиве А равно мощности универсума. Элементы массива А неупоря- дочены. Алгоритм 1.1 (рис) вычисления включения А в В (А В Вход А — массив, хранящий элементы множества А, КА = |A|; B — массив, хранящий элементы множества B, К = |B|. Выход F = true, если А В, иначе F = false. 33 Рис. Блок-схема алгоритма вычисления включения А в В Алгоритм 1.2 (рис) вычисления равенства Аи В (А = В. Вход А — массив, хранящий элементы множества А, КА = |A|; B — массив, хранящий элементы множества B, К = |B|. Выход F = true, если А = В, иначе F = false. Рис. Блок-схема алгоритма вычисления равенства Аи В := KA KB; i:=1 А В в массиве Весть А i );i:=i+1 Конец i KA и F=true Конец F := KA = KB; А = В в массиве Весть Аи Алгоритм 1.3 (рис) вычисления объединения Аи В (А В. Вход А — массив, хранящий элементы множества А, КА = |A|; B — массив, хранящий элементы множества B, К = |B|. Выход С — массив, хранящий объединение множеств Аи, КС = С. + Рис. Блок-схема алгоритма вычисления объединения Аи В Алгоритм 1.4 (рис) вычисления пересечения Аи В (А В. Вход А — массив, хранящий элементы множества А, КА = |A|; B — массив, хранящий элементы множества B, К = |B|; пусть КА KB. Выход С — массив, хранящий пересечение множеств Аи, КС = С. + Рис. Блок-схема алгоритма вычисления пересечения Аи В С:=A; KC:=KA А В в С нет B i KC:=KC+1; C KC :=B i i:=1, KB Конец А В весть Конец 35 Алгоритм 1.5 (рис) вычисления разности Аи В (А – В. Вход А — массив, хранящий элементы множества А, КА = |A|; B — массив, хранящий элементы множества B, К = |B|. Выход С — массив, хранящий разность множеств Аи, КС = С +Рис. Блок-схема алгоритма вычисления разности Аи В Алгоритм 1.6 вычисления симметрической разности Аи В (А В. Вход А — массив, хранящий элементы множества А, КА = |A|; B — массив, хранящий элементы множества B, К = |B|. Выход С — массив, хранящий симметрическую разность множеств Аи, КС = С 1. C := A – B B - A; или C := (A B) – (A B)} 2. Конец. Алгоритм 1.7 (рис) вычисления дополнения А ( A ). Вход А — массив, хранящий элементы множества А, КА = |A|. Выход С — массив, хранящий дополнение множества А, КС = С. А – В в B нет A i KC:=KC+1; C KC :=A i i:=1, KA Конец 36 A + Рис. Блок-схема алгоритма вычисления дополнения А Элементы множества А хранятся в переменной А типа массив, мощность множества А – в переменной KA. Количество элементов в массиве А равно мощности универсума. Элементы массива А упорядочены по возрастанию. Алгоритм 1.8 (рис) вычисления равенства Аи В (А = В. Вход А — массив, хранящий элементы множества А, КА = |A|; B — массив, хранящий элементы множества B, К = |B|. Выход F = true, если А = В, иначе F = false. Рис. Блок-схема алгоритма вычисления равенства Аи В нет в A KC:=KC+1; C KC :=u u:=1, KU Конец i:=1; F:= KA=KB i≤KA и F=true Конец F := A i =B i ; i:=i+1 A = B 37 Алгоритм 1.9 (рис) вычисления включения А в В (А В. Вход А — массив, хранящий элементы множества А, КА = |A|; B — массив, хранящий элементы множества B, К = |B|. Выход F = true, если А В, иначе F = false. + + Рис. Блок-схема алгоритма вычисления включения А в В и A KA B KB i:=1; А В i KA и F=true Конец A i =B j i:=i+1 j:=j+1 A i >B j j:=j+1 F:= False 38 Алгоритм 1.10 (рис) вычисления объединения Аи В (А В. Вход А — массив, хранящий элементы множества А, КА = |A|; B — массив, хранящий элементы множества B, К = |B|. Выход С — массив, хранящий объединение множеств Аи, КС = С. + + Рис. Блок-схема алгоритма вычисления объединения Аи В j:=1; А В i KA и j KB A i =B j i:=i+1 j:=j+1 A i >B j C KC :=A i i:=i+1 C KC :=B j j:=j+1 C KC :=A i KC:=KC+1 i KA KC:=KC+1; C KC :=A i i:=i+1 j KB KC:=KC+1; C KC :=B j j:=j+1 Конец 39 Алгоритм 1.11 (рис) вычисления пересечения Аи В (А В. Вход А — массив, хранящий элементы множества А, КА = |A|; B — массив, хранящий элементы множества B, К = |B|. Выход С — массив, хранящий пересечение множеств Аи, КС = С. + + Рис. Блок-схема алгоритма вычисления пересечения Аи В j:=1; KC:=0 i KA и j KB A i =B j i:=i+1 j:=j+1 A i >B j i:=i+1 j:=j+1 Конец А В KC:=KC+1 40 Алгоритм 1.12 (рис) вычисления разности Аи В (А – В. Вход А массив, хранящий элементы множества А, КА = |A|; B — массив, хранящий элементы множества B, К = |B|. Выход С — массив, хранящий разность множеств Аи, КС = С + + Рис. Блок-схема алгоритма вычисления разности Аи В j:=1; KC:=0 i KA и j KB A i =B j i:=i+1 j:=j+1 A i >B j i:=i+1 j:=j+1 А – В KC:=KC+1 i KA Конец KC:=KC+1; C KC :=A i ; i:=i+1 41 Алгоритм 1.13 (рис) вычисления симметрической разности Аи В (А В. Вход А — массив, хранящий элементы множества А, КА = |A|; B — массив, хранящий элементы множества B, К = |B|. Выход С — массив, хранящий симметрическую разность Аи В, КС = С. + + Рис. Блок-схема алгоритма вычисления симметрической разности Аи В j:=1; KC:=0 i KA и j KB A i =B j i:=i+1 j:=j+1 A i >B j KC:=KC+1; C KC :=A i i:=i+1 А В KC:=KC+1; C KC :=B j j:=j+1 j KB Конец KC:=KC+1; C KC :=B j j:=j+1 i KA KC:=KC+1; C KC :=A i i:=i+1 42 Алгоритм 1.14 (рис) вычисления дополнения А ( A ). Вход А — массив, хранящий элементы множества А, КА = |A|. Выход С — массив, хранящий дополнение множества А, КС = С. + + Рис. Блок-схема алгоритма вычисления дополнения Аи u:=u+1 Конец 43 3. Элементы универсума нумеруются U = {u 1 ,…,u n }. Элементы множества А хранятся в переменной А типа массив, элементы которого типа boolean. Если u i A, то А = true, иначе A i = false. Количество элементов в массиве А равно мощности универсума. Алгоритм 1.15 (рис) вычисления равенства Аи В (А = В. Вход А — массив, хранящий элементы множества А B — массив, хранящий элементы множества B. Выход F = true, если А = В, иначе F = false. Рис. Блок-схема алгоритма вычисления равенства Аи В Алгоритм 1.16 (рис) вычисления включения А в В (А В. Вход А массив, хранящий элементы множества А B — массив, хранящий элементы множества B. Выход F = true, если А В, иначе F = false. А В Рис.1.17. Блок-схема алгоритма вычисления включения А в В i:=1; F:=true i≤KU и F=true Конец F := A i =B i ; i:=i+1 A = B i:=1; F:=true i KU и F=true F := A i B i ; i:=i+1 Конец 44 Алгоритм 1.17 (рис) вычисления объединения Аи В (А В. Вход А — массив, хранящий элементы множества А B — массив, хранящий элементы множества B. Выход С — массив, хранящий объединение множеств Аи. Рис. Блок-схема алгоритма вычисления объединения Аи В Алгоритм 1.18 (рис) вычисления пересечения Аи В (А В. Вход А — массив, хранящий элементы множества А B — массив, хранящий элементы множества B. Выход С — массив, хранящий пересечение множеств Аи. Рис. Блок-схема алгоритма вычисления пересечения Аи В Конец C i := A i or А В, KU Конец C i := A i and B i i:=1, KU А В 45 Алгоритм 1.19 (рис) вычисления разности Аи В (А – В. Вход А — массив, хранящий элементы множества А B — массив, хранящий элементы множества B. Выход С — массив, хранящий разность множеств Аи Рис. Блок-схема алгоритма вычисления разности Аи В Алгоритм 1.20 (рис) вычисления симметрической разности Аи В (А В. Вход А — массив, хранящий элементы множества А B — массив, хранящий элементы множества B. Выход С — массив, хранящий симметрическую разность множеств Аи. Рис. Блок-схема алгоритма вычисления симметрической разности Аи В Конец C i := A i > B i i:=1, KU А – В Конец C i := A i B i i:=1, KU А В 46 Алгоритм 1.21 (рис) вычисления дополнения А ( A ). Вход А — массив, хранящий элементы множества А Выход С — массив, хранящий дополнение множества А Рис. Блок-схема алгоритма вычисления дополнения А 4. Элементы универсума нумеруются U = {u 1 ,…,u n }. Множество А представляется кодом Св котором C i = 1, если u i A и C i = 0, если u i A, где С – й разряд кода СВ зависимости от мощности универсума код Сможет храниться в простой переменной или в массиве. Алгоритмы реализации операций при таком способе представления множества в памяти ЭВМ можно получить путем замены логических операций на побитовые в предшествующих алгоритмах и корректировкой конечного значения параметра циклов. 5. Для хранения множества можно использовать множественный тип, если он имеется в языке программирования, и выполнять предусмотренные типом операции надмножествами. Конец C i := not A i i:=1, KU A 47 Практическое занятие 1.1 Операции надмножествами Цель занятия изучить и научиться использовать операции надмножествами, изучить различные способы представления множеств в памяти ЭВМ, научиться программно реализовывать операции надмножествами и вычислять значения теоретико-множественных выражений. Задания 1. Вычислить значение выражения (см. Варианты заданий, па. Решение изобразить с помощью кругов Эйлера. 2. Записать теоретико-множественное выражение, значение которого при заданных множествах А, В и С равно множеству D (см. Варианты заданий, п. б. 3. Программно реализовать операции надмножествами, используя следующие способы представления множества в памяти ЭВМ а) элементы множества А хранятся в массиве А. Элементы массива А неупорядочены; б) элементы множества А хранятся в массиве А. Элементы массива А упорядочены по возрастанию в) элементы множества А хранятся в массиве А, элементы которого типа boolean. Если i A, то А = true, иначе A i = false. 4. Написать программы для вычисления значений выражений (см. Задания, пи п. 5. Используя программы (см. Задания, п, вычислить значения выражений (см. Задания, пи п. Варианты заданий Варианта = {2,5,6,9,10} C = {4,7,8,11,12} б) A = {1,2,8} B = {6,7} C = {2,3,4,5,7} D = {3,4,5} Варианта {3,7,8,10} б) A = {1,2,3,8} B = {3,6,7} C = {2,3,4,5,7} D = {1,3,4,5,6,8} 48 Варианта C = {4,5,6,7,9} б) A = {2,3,4,5,6} B = {1,2,4,9} C = {4,5,7,8} D = {3,6} Варианта C = {3,4,5,6,8} б) A = {1,2,3,8} B = {3,6,7} C = {2,3,4,5,7} D = {1,3,6,8} Варианта б) A = {1,2,3,4,6,7} B = {1,3,6,7} C = {3,4,5,6,8} D = {1,5,7,8} Варианта C = {4,5,7,8} б) A = {1,2,4,5,8} B = {2,3,5,6,9} C = {4,5,6,7,9} D = {2,4,6,9} Варианта {3,5,6,7} C = {2,3,4,7} б) A = {1,2,3,4,5,6,7} B = {2,5,6,9,10} C = {4,7,8,11,12} D = {2,5,6,7,4} Варианта б) A = {1,2,3,4,5,6,7} B = {2,5,6,9,10} C = {4,7,8,11,12} D = {1,3,8,9,10,11,12} Варианта б) A = {2,5,6,7,9} B = {1,4,5,9} C = {3,7,8,10} D = {1,3,4,8,10} 49 Варианта = {4,5,6,7,9} б) A = {1,2,3,4,6,7} B = {1,3,6,7} C = {3,4,5,6,8} D = {2,5,8} Варианта В – С) (С – A) A = {1,2,3,4,6,7} B = {1,3,6,7} C = {3,4,5,6,8} б) A = {1,2,3,8} B = {3,5,6,7} C = {2,3,4,7} D = {1,3,5,6,8} Варианта б) A = {2,3,4,5,6} B = {1,2,4,9} C = {4,5,7,8} D = {3,4,6,7,8} Варианта {4,5,7,8} б) A = {1,2,4,5,8} B = {2,3,5,6,9} C = {4,5,6,7,9} D = {1,3,5,7,8} Варианта C = {2,3,4,5,7} б) A = {1,2,3,4,8} B = {2,3,8} C = {3,4,5,6,7} D = {2,5,6,7,8} Варианта б) A = {1,2,3,4,8} B = {2,3,8} C = {3,4,5,6,7} D = {3,5,6,7} 50 Практическое занятие 1.2 Нормальные формы Кантора Цель занятия изучить способы получения различных нормальных форм Кантора множества, заданного произвольным теоретико-множественным выражением. Задания 1. Представить множество, заданное исходным выражением (см. табл. 1.4), в нормальной форме Кантора. 2. Получить совершенную нормальную форму Кантора множества, заданного исходным выражением. 3. Получить сокращенную нормальную форму Кантора множества, заданного исходным выражением. 4. Получить тупиковые нормальные формы Кантора множества, заданного исходным выражением. Выбрать минимальную нормальную форму Кантора. Таблица 1.4 Варианты заданий Вариант Исходное выражение 1 A B C D A B ) ) ( ( 2 D (D – C) A – B – C ∆ (B – A) 3 С A C – B (D – C) ∆ (D – A) 5 ) ( ) ( A C B C A D D 6 C ∆ (D – A) B – C (B – A)– D 7 A – (C ∆ A) B – D ∆(C – B) 8 С B A – C (D – A) ∆ (D A) 10 ((C B ) – D ∆ (C – B) ∆ A) A 11 (C∆ A) A D∆ (C B) – B 12 С (A∆(B C) D–B∆A) C 14 (D C–B∆(B A)∆C) A 15 C A B D C B A ) ( ) ( 16 (B∆(A–C) D)–A (B–C) 51 Практическое занятие 1.3 |