Презентация на тему: Предыдущая л екция

Предыдущая л екция
Частично упорядоченное множество (ЧУМ) – диаграмма (решетка) Хассе
Определение булевой алгебры
Решение уравнений в алгебре множеств.
Решение уравнений в алгебре множеств.
Решение уравнений в алгебре множеств.
Решение уравнений в алгебре множеств.
Решение уравнений в алгебре множеств.
Решение уравнений в алгебре множеств.
Предыдущая л екция
Предыдущая л екция
Предыдущая л екция
Предыдущая л екция
Понятие о конечных полях
Предыдущая л екция
Предыдущая л екция
Предыдущая л екция
Предыдущая л екция
Предыдущая л екция
Предыдущая л екция
Предыдущая л екция
GF (4)
Предыдущая л екция
Предыдущая л екция
GF (5)
ЭВАРИСТ ГАЛУА (1811-1832)
НИЛЬС ГЕНРИХ АБЕЛЬ (1802-1829)
А́ртур Кэ́ли (другие варианты написания фамилии Кейли, Кэйлей; англ.  Arthur Cayley ; ( 1821-1895 )
Предыдущая л екция
Предыдущая л екция
Предыдущая л екция
Предыдущая л екция
Лекция 6
С.39 -44
С.20 -28
Предыдущая л екция
Предыдущая л екция
Предыдущая л екция
Предыдущая л екция
Предыдущая л екция
Предыдущая л екция
Предыдущая л екция
Разность и симметрическая разность множеств
Предыдущая л екция
Пример комбинаторных вычислений
Предыдущая л екция
Предыдущая л екция
«Проклятие размерности»
Предыдущая л екция
Сложность комбинаторных вычислений
Основные понятия комбинаторики
Оптимизация на основе комбинаторного анализа
Оптимизация на основе комбинаторного анализа
Основополагающие правила комбинаторики
Основополагающие правила комбинаторики
Правило суммы
Правило произведения
Пример:
Понятие выборки (комбинации)
Понятие выборки (комбинации)
Размещения
Размещения
Предыдущая л екция
Предыдущая л екция
Размещения без повторений
Размещения без повторений
Вывод формулы числа размещений без повторений
Вывод формулы числа размещений без повторений
Преобразуем эту формулу, умножая и деля ее на произведение чисел 1  2  ( n - k ):
Пример размещения без повторений
Перечисление вариантов
Пример
Перестановки
Пример перестановок без повторений
Перестановки с повторениями
Пример перестановок с повторениями
Перестановки цифр в числе 010
Общая формула числа перестановок с повторениями данного состава
Пример перестановок с повторениями
Сочетания
Число сочетаний без повторений из n элементов по k
Пример сочетаний без повторений
Предыдущая л екция
Предыдущая л екция
Дерево Пифагора
Предыдущая л екция
Предыдущая л екция
Множество Мандельброта — классический образец фрактала
Предыдущая л екция
1/89
Средняя оценка: 4.9/5 (всего оценок: 63)
Код скопирован в буфер обмена
Скачать (1279 Кб)
1

Первый слайд презентации: Предыдущая л екция

Алгебра Кантора

Изображение слайда
2

Слайд 2: Частично упорядоченное множество (ЧУМ) – диаграмма (решетка) Хассе

Изображение слайда
3

Слайд 3: Определение булевой алгебры

Дистрибутивная решетка с отличными друг от друга нулем и единицей, в которой каждый элемент имеет дополнение, называется булевой алгеброй.

Изображение слайда
4

Слайд 4: Решение уравнений в алгебре множеств

При решении уравнений в алгебре множеств исходят из того, что: 1) два множества равны тогда и только тогда, когда их симметрическая разность пуста; 2) определяются условия, при которых уравнения имеют решение.

Изображение слайда
5

Слайд 5: Решение уравнений в алгебре множеств

Решение где – F 1, F 2 формулы, не содержащие X

Изображение слайда
6

Слайд 6: Решение уравнений в алгебре множеств

Полученные два уравнения и исходное уравнение имеют решение тогда и только тогда, когда

Изображение слайда
7

Слайд 7: Решение уравнений в алгебре множеств

Итак

Изображение слайда
8

Слайд 8: Решение уравнений в алгебре множеств

Легко видеть, что

Изображение слайда
9

Слайд 9: Решение уравнений в алгебре множеств

Поэтому Для конкретных соответствующих C, D можно получить множество решений.

Изображение слайда
10

Слайд 10

Итак, С  D  Х  D Пусть С={2,3,6,9}, D ={1,2,3,5,6,7,8,9}, тогда С  D ={1,5,7,8}  D Имеется множество решений, например, Х = {1,2,5,6,7,8}  D

Изображение слайда
11

Слайд 11

Изображение слайда
12

Слайд 12

Пусть С={2,3,4,6,9} при том же D ={1,2,3,5,6,7,8,9}, тогда С  D ={1,4,5,7,8} не включается в D Тогда решений нет!

Изображение слайда
13

Слайд 13

Понятие о конечных полях

Изображение слайда
14

Слайд 14: Понятие о конечных полях

Полем называют множество элементов, на котором определены две операции. Одна из них называется сложением и обозначается a + b, а другая – умножением и обозначается a · b, даже если эти операции не являются обычными операциями сложения и умножения чисел.

Изображение слайда
15

Слайд 15

Для того чтобы множество элементов, на котором заданы операции сложения и умножения, было полем, необходимо, чтобы по каждой из этих операций выполнялись все групповые аксиомы, а также выполнялся дистрибутивный закон: а ·( b + с ) = а · b + а · с и ( b + с ) · а = b ·  а + с · а.

Изображение слайда
16

Слайд 16

Кроме того, по каждой операции группа должна быть коммутативной, т. е. должно выполняться а + b = b + a а · b = b · а.

Изображение слайда
17

Слайд 17

Поля с конечным числом элементов q называют полями Галуа по имени их первого исследователя Эвариста Галуа и обозначают GF ( q ).

Изображение слайда
18

Слайд 18

Число элементов поля q называют порядком поля. Конечные поля используются для построения большинства известных кодов и их декодирования.

Изображение слайда
19

Слайд 19

Поле называют простым, если q – простое число. Для обозначения простых чисел будем использовать символ p. Простое поле образуют числа по модулю p : 0, 1, 2,…, p –1, а операции сложения и умножения выполняются по модулю p.

Изображение слайда
20

Слайд 20

Поле GF (2),или двоичное. Правила сложения и умножений для элементов GF (2):

Изображение слайда
21

Слайд 21

GF (3) –троичное поле с элементами 0, 1, 2.

Изображение слайда
22

Слайд 22: GF (4)

Изображение слайда
23

Слайд 23

видно, что для элемента 2 по операции умножения отсутствует обратный, т. е. набор чисел 0, 1, 2, 3 не является полем при введении операции по модулю 4. Такой результат объясним тем, что 4 не является простым числом

Изображение слайда
24

Слайд 24

Анализируя состав таблиц, легко убедиться, что 0 и 1 как единичные элементы по операции сложения и умножения не изменяют значения других элементов поля по соответствующей операции. Кроме того, видно, что для каждого элемента по операции сложения и для ненулевых элементов по операции умножения имеются обратные.

Изображение слайда
25

Слайд 25: GF (5)

Изображение слайда
26

Слайд 26: ЭВАРИСТ ГАЛУА (1811-1832)

Изображение слайда
27

Слайд 27: НИЛЬС ГЕНРИХ АБЕЛЬ (1802-1829)

Изображение слайда
28

Слайд 28: А́ртур Кэ́ли (другие варианты написания фамилии Кейли, Кэйлей; англ.  Arthur Cayley ; ( 1821-1895 )

Изображение слайда
29

Слайд 29

Граф Кэли

Изображение слайда
30

Слайд 30

Изображение слайда
31

Слайд 31

Изображение слайда
32

Слайд 32

Тема 2. Элементы комбинаторики

Изображение слайда
33

Слайд 33: Лекция 6

ОСНОВНЫЕ ПОНЯТИЯ КОМБИНАТОРИКИ

Изображение слайда
34

Слайд 34: С.39 -44

Изображение слайда
35

Слайд 35: С.20 -28

Изображение слайда
36

Слайд 36

Комбинаторные вычисления

Изображение слайда
37

Слайд 37

При решении теоретико-множественных задач большое значение имеет определение мощности конечных множеств. Очевидно, что | A  B |=| A |+| B |–| A  B |, т.е., когда А и В в «общем положении», т.е. пересекаются.

Изображение слайда
38

Слайд 38

A B A B I

Изображение слайда
39

Слайд 39

АВ

Изображение слайда
40

Слайд 40

|В\А|=|В|–|А|, когда А включается в В

Изображение слайда
41

Слайд 41

|В\А|=|В|–| A  B |, когда А и В в «общем положении», т.е. пересекаются

Изображение слайда
42

Слайд 42

Нетрудно заметить, что | A  B |=| A |+| B |–2| A  B |. I A B A B 1, 2 4, 5 3

Изображение слайда
43

Слайд 43: Разность и симметрическая разность множеств

I A B A\B 1, 2, 3, 4 6 5 I A B A B 1, 2 4, 5 3

Изображение слайда
44

Слайд 44

В дискретной математике имеется специальный раздел, занимающийся подсчетом и перечислением элементов в конечных множествах – комбинаторика или комбинаторный анализ. Вычисления на дискретных конечных математических структурах часто называют комбинаторными вычислениями.

Изображение слайда
45

Слайд 45: Пример комбинаторных вычислений

Пусть в базе данных имеется n записей об объектах недвижимости (например, квартирах) в виде запроса (что требуется) и предложения (что имеется)

Изображение слайда
46

Слайд 46

Требуется найти такие пары записей, в которых предложение первой записи совпадает с запросом второй и, наоборот, предложение второй записи совпадает с запросом первой (подбор вариантов «предложение - спрос»)

Изображение слайда
47

Слайд 47

Например, n =5: 1,2,3,4,5 Имеются следующие пары (1,2),(1,3),(1,4),(1,5) – 4 пары (2,3),(2,4),(2,5) – 3 пары (3,4),(3,5) -2 пары (4,5) – 1 пара; сумма пар – арифметическая прогрессия (Гаусс!): (4+1)4 / 2 = 5(5-1) / 2 То есть: n(n-1)/2

Изображение слайда
48

Слайд 48: Проклятие размерности»

Допустим, на варианта обмена тратится одна миллисекунда. Если n =100, то при указанном быстродействии, на сравнения уйдет 4,95 секунды. Но, если n =100000 (в задачах реальной размерности), то необходимо 1999950 секунд, т.е. без малого – 1389 часов!

Изображение слайда
49

Слайд 49

Столько ждать клиент вряд ли будет. Это и есть «проклятие размерности». Поэтому комбинаторные вычисления требуют предварительного анализа и ориентировочной количественной оценки исходных данных.

Изображение слайда
50

Слайд 50: Сложность комбинаторных вычислений

Здесь речь идет о сложности вычислений в смысле времени решения. В ряде задач комбинаторной сложности необходимо время, сравнимое с геологическими эпохами. Но есть еще и пространственная сложность – в смысле объема памяти. Ведь промежуточные результаты часто надо где-то хранить. В ряде задач требуется объем памяти, превышающий количество атомов во Вселенной. Основным инструментом такого анализа сложности вычислений и является комбинаторика.

Изображение слайда
51

Слайд 51: Основные понятия комбинаторики

Основная задача комбинаторики, как раздела дискретной математики, – пересчет и перечисление элементов в конечных множествах. Если требуется определить, сколько элементов, принадлежащих заданному конечному множеству, обладает некоторым свойством или заданным набором свойств, то это задача пересчета. Если необходимо выделить все элементы множества, удовлетворяющие заданным свойствам, то это задача перечисления.

Изображение слайда
52

Слайд 52: Оптимизация на основе комбинаторного анализа

В некоторых задачах на исходном конечном множестве элементов определена целевая функция, причем нас интересуют элементы множества, соответствующие минимальному или максимальному значению этой функции. В этом случае решается задача оптимизации.

Изображение слайда
53

Слайд 53: Оптимизация на основе комбинаторного анализа

При этом под решением задачи оптимизации «в сильном смысле» понимается нахождение всех элементов минимизирующих (максимизирующих) целевую функцию, а под решением задачи оптимизации «в слабом смысле» – нахождение единственного произвольного элемента

Изображение слайда
54

Слайд 54: Основополагающие правила комбинаторики

Рассмотрим основополагающие правила комбинаторики – правила суммы и произведения. Пусть Х – конечное множество, состоящее из n элементов х. Тогда говорят, что элемент х из Х может быть выбран n способами и пишут |Х|=n. Эта запись совпадает с записью мощности множества Х.

Изображение слайда
55

Слайд 55: Основополагающие правила комбинаторики

Пусть Х1,...,Х k – попарно непересекающиеся множества, т.е. Х i  Х j = , i  j. Очевидно, что в этом случае Таково комбинаторное правило суммы

Изображение слайда
56

Слайд 56: Правило суммы

Для k =2 правило суммы формулируется следующим образом. Если объект х может быть выбран n способами из множества Х, а объект y из непересекающегося с ним множества Y, – другими m способами, то выбор «х или y » может быть осуществлен n + m способами.

Изображение слайда
57

Слайд 57: Правило произведения

Правило произведения для k=2 формулируется следующим образом. Если объект х может быть выбран n способами и после каждого из таких выборов объект y в свою очередь может быть выбран m способами, то выбор упорядоченной пары – вектора (х, y ) может быть осуществлен n  m способами.

Изображение слайда
58

Слайд 58: Пример:

Например, Х:{ x 1, x 2 }, Y :{ y 1, y 2 }; Выбор одного из элементов этих множеств осуществляется 2+2 = 4 способами; Выбор упорядоченной пары ( x, y ) описывается декартовым произведением X  Y={(x 1,y 1 ),(x 1,y 2 ),(x 2,y 1 ),(x 2,y 2 )}, то есть всего дважды - два = четыре варианта.

Изображение слайда
59

Слайд 59: Понятие выборки (комбинации)

Набор элементов х i 1,..., xik из множества Х={ x 1,..., xn } (вектор) называется выборкой (комбинацией) объема k из n элементов или, иначе, ( n, k ) выборкой. Выборка называется упорядоченной, если порядок следования элементов в ней задан. Две упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными.

Изображение слайда
60

Слайд 60: Понятие выборки (комбинации)

Если порядок следования элементов не является существенным, то такая выборка называется неупорядоченной. В выборках могут допускаться и не допускаться повторения элементов, т.е. имеются выборки с повторением и выборки без повторений.

Изображение слайда
61

Слайд 61: Размещения

Упорядоченная ( n, k ) выборка, в которой элементы могут повторяться, называется ( n, k ) размещением с повторениями. Иными словами размещениями с повторениями из n элементов по k называют векторы длины k, составленные из n элементов множества Х.

Изображение слайда
62

Слайд 62: Размещения

Число размещений с повторениями из n элементов по k определяется оценкой мощности соответствующего декартова произведения n -элементного множества, обозначается А (по-видимому от английского слова Assing – назначать) и вычисляется следующим образом:

Изображение слайда
63

Слайд 63

Таким образом, первый элемент вектора длины k выбирается n способами, второй – n способами и т.д

Изображение слайда
64

Слайд 64

Пример. Сколькими способами можно оснастить две аудитории компьютерами трех типов? Каждый способ оснащения есть выборка (3,2), вектор длины 2, составленный из 3-х элементного множества типов Т={ t 1, t 2, t 3 }. Поэтому число способов оснащения – число размещений с повторениями из 3 по 2:

Изображение слайда
65

Слайд 65: Размещения без повторений

В ряде задач необходимо определить число векторов длины k из n элементов данного множества без повторения элементов. Если элементы упорядоченной (n,k) выборки попарно различны, то они называются (n,k) размещением без повторений или просто (n,k) размещением.

Изображение слайда
66

Слайд 66: Размещения без повторений

Число таких размещений без повторений обозначается

Изображение слайда
67

Слайд 67: Вывод формулы числа размещений без повторений

Каждое ( n, k ) размещение без повторения является упорядоченной последовательностью длины k, элементы которой попарно различны и выбираются из множества с n элементами.

Изображение слайда
68

Слайд 68: Вывод формулы числа размещений без повторений

Тогда первый элемент этой последовательности может быть выбран n способами, после каждого выбора первого элемента последовательности второй элемент может быть выбран n -1 способами и т.д., k -й элемент выбирается n -( k -1) способом:

Изображение слайда
69

Слайд 69: Преобразуем эту формулу, умножая и деля ее на произведение чисел 1  2  ( n - k ):

Получим:

Изображение слайда
70

Слайд 70: Пример размещения без повторений

В частности, при k =0 Очевидно, что при k > n Пример. Сколькими способами из 3-х студентов можно назначить группу на прополку картофеля в составе начальника и подчиненного? Речь идет о выборе упорядоченных двухэлементных подмножеств множества студентов, состоящего из трех элементов (K={1,2,3}), т.е. о размещениях без повторений из 3 элементов по 2, поэтому:

Изображение слайда
71

Слайд 71: Перечисление вариантов

Подробнее, в виде векторов из номеров студентов, например, по журнальному списку, первая компонента которого обозначает номер студента-начальника, вторая – подчиненного: (1,2), (1,3), (2,1), (2,3), (3,1), (3,2). Это и есть перечисление. Ясно, что здесь существенен порядок следования компонент и не может быть повторений (один студент не может быть начальником и подчиненным одновременно), поэтому это множество – подмножество декартового произведения.

Изображение слайда
72

Слайд 72: Пример

Пример 2. Сколькими способами можно провести трудоустройство 10 безработных по 3 рабочим местам? Один человек назначается на одно рабочее место. Распределение безработных– размещение без повторений из 10 элементов по 3, поэтому:

Изображение слайда
73

Слайд 73: Перестановки

Рассмотрим различные упорядочения n элементного множества Х (вектора длины n, составленные из n элементного множества). В отличие от декартова произведения, полученные при этом векторы, отличаются лишь порядком следования элементов и называются перестановками без повторений из n элементов. Число перестановок без повторений из n элементов обозначается P n. К перестановкам без повторений можно прийти, полагая, что осуществляется размещение без повторений из n элементов по n :

Изображение слайда
74

Слайд 74: Пример перестановок без повторений

Считается, что 0!=1. Сколько существует возможных последовательностей выполнения проверок финансовой деятельности трех подразделений? Требуется получить число перестановок без повторений из трех элементов, т.е. Р 3 =3!=6. Получим все эти последовательности: (1,2,3), (1,3,2), (2,3,1), (2,1,3), (3,1,2), (3,2,1).

Изображение слайда
75

Слайд 75: Перестановки с повторениями

При наличии одинаковых компонент в некотором векторе получаем задачу оценки так называемых перестановок с повторениями данного состава; Рассмотрим пример: сколько различных последовательностей – кодов можно получить, переставляя цифры в числе 010, т.е. векторов длины k=3 из 2-х элементного множества В={0,1}, содержащих два нуля;

Изображение слайда
76

Слайд 76: Пример перестановок с повторениями

Имеется всего три разряда, которые обозначим р 1, р 2, р 3. Их можно переставить р 3 =3!=6 способами. Запишем различные получаемые сочетания разрядов и соответствующие коды:

Изображение слайда
77

Слайд 77: Перестановки цифр в числе 010

Видно, что коды повторяются тогда, когда несущественен порядок следования разрядов с одинаковой цифрой 0 (р 1,р 3 ). Все это соответствует тому факту, что имеется два способа (2!) перестановки этих разрядов (р 1,р 3 ), (р 3,р 1 ) без изменения кода, т.е. неповторяющихся кодов будет меньше во столько раз, сколько имеется способов перестановки повторяющихся разрядов.

Изображение слайда
78

Слайд 78: Общая формула числа перестановок с повторениями данного состава

Р (k 1,k 2,...,k n )=

Изображение слайда
79

Слайд 79: Пример перестановок с повторениями

Сколько различных кодовых последовательностей можно получить перестановками кода 102202030? Такому вектору, составленному из элементов множеств {0,1,2,3} соответствует вектор состава (1,4,3,1), поэтому число различных кодовых комбинаций определяется как число перестановок с повторениями этого состава Р(1,4,3,1)=

Изображение слайда
80

Слайд 80: Сочетания

В ряде комбинаторных задач требуется определить число k -элементных подмножеств множества из n элементов. В этом случае порядок следования компонентов несущественен, т.е. производится неупорядоченная выборка. В результате получают так называемые сочетания без повторения. Сочетаниями без повторений из n элементов по k называются отличающиеся друг от друга хотя бы одним элементом выборки длины k, составленные из n элементного множества.

Изображение слайда
81

Слайд 81: Число сочетаний без повторений из n элементов по k

Число сочетаний без повторений из n элементов по k, обозначаемое как определяется, исходя из числа размещений без повторений с учетом того, что различных неупорядоченных векторов (подмножеств исходного множества) будет меньше в число раз, соответствующее числу перестановок без повторений из k элементов:

Изображение слайда
82

Слайд 82: Пример сочетаний без повторений

Определить число двухэлементных подмножеств множества, состоящего из трех элементов. Перечисляем все двухэлементные подмножества множества Х={х 1,х 2,х 3 }:{х 1,х 2 },{х 1,х 3 },{х 2,х 3 }. Здесь мы имеем дело с сочетаниями из 3-х по 2:

Изображение слайда
83

Слайд 83

Граф Кэли является граф, вершинами которого являются элементы группы и элемент g соединён ребром в точности с теми элементами, которые получаются домножением g на элемент из S.

Изображение слайда
84

Слайд 84

Изображение слайда
85

Слайд 85: Дерево Пифагора

Пифагор, доказывая свою знаменитую теорему, построил фигуру, где на сторонах прямоугольного треугольника расположены квадраты. В наш век эта фигура Пифагора выросла в целое дерево.

Изображение слайда
86

Слайд 86

Изображение слайда
87

Слайд 87

Фрактал (лат.  fractus  — дробленый, сломанный, разбитый) — сложная геометрическая фигура, обладающая свойством самоподобия, то есть составленная из нескольких частей, каждая из которых подобна всей фигуре целиком. В более широком смысле под фракталами понимают множества точек в евклидовом пространстве, имеющие дробную метрическую размерность

Изображение слайда
88

Слайд 88: Множество Мандельброта — классический образец фрактала

Изображение слайда
89

Последний слайд презентации: Предыдущая л екция

Изображение слайда