Презентация на тему: Операции с множествами. Основные понятия графов. Комбинаторика

Операции с множествами. Основные понятия графов. Комбинаторика.
Основные вопросы
Элементы и множества. Операции над множествами и их свойства.
Операции с множествами. Основные понятия графов. Комбинаторика.
Понятия теории множеств
Операции с множествами. Основные понятия графов. Комбинаторика.
Примеры множеств:
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Способы задания множеств
Примеры
Примеры
Виды множеств:
Если элементы множества можно сосчитать, то множество является КОНЕЧНЫМ
Если элементы множества сосчитать невозможно, то множество БЕСКОНЕЧНОЕ
Множество, не содержащее ни одного элемента, называется ПУСТЫМ. Символически оно обозначается знаком 
Мощность множества
Пример. Определите мощность какого из множеств A = {1, 3, 5, 7, 9} или B = {2, 4, 6, 8} больше.
Отношения между множествами
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Свойства множеств
Операции с множествами. Основные понятия графов. Комбинаторика.
Количество подмножеств
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции над множествами
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции над множествами
Операции с множествами. Основные понятия графов. Комбинаторика.
объединение
Операции над множествами
Операции над множествами
разность
Операции над множествами
Операции над множествами
Операции над множествами
Задача. Даны множества
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Задача. Каждый учащийся в классе изучает английский или французский язык. Английский язык изучают 25 учащихся, французский — 27 учащихся, а два языка — 18
Операции с множествами. Основные понятия графов. Комбинаторика.
Графы. Элементы графов. Виды графов и операции над ними
Операции с множествами. Основные понятия графов. Комбинаторика.
История возникновения графов
В основе теории лежит понятие графа.
Состав графа
Ориентированный граф -
Взвешенный граф
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Пути и маршруты в графах
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции над графами
Операции с множествами. Основные понятия графов. Комбинаторика.
Обоснование основных понятий комбинаторики: факториал, перестановки, размещения, сочетания.
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
Перестановки
Операции с множествами. Основные понятия графов. Комбинаторика.
Перестановки
Перестановки с повторениями
Операции с множествами. Основные понятия графов. Комбинаторика.
Размещения
Размещения
Операции с множествами. Основные понятия графов. Комбинаторика.
Размещения с повторениями
Размещения с повторениями
Операции с множествами. Основные понятия графов. Комбинаторика.
Сочетания
Сочетания с повторениями
Сочетания с повторениями
Операции с множествами. Основные понятия графов. Комбинаторика.
Операции с множествами. Основные понятия графов. Комбинаторика.
1/93
Средняя оценка: 4.6/5 (всего оценок: 70)
Код скопирован в буфер обмена
Скачать (1307 Кб)
1

Первый слайд презентации: Операции с множествами. Основные понятия графов. Комбинаторика

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

Слайд 2: Основные вопросы

Элементы и множества. Операции над множествами и их свойства. Графы. Элементы графов. Виды графов и операции над ними. Обоснование основных понятий комбинаторики: факториал, перестановки, размещения, сочетания.

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

Слайд 3: Элементы и множества. Операции над множествами и их свойства

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

Слайд 4

«Множество есть многое, мыслимое нами как единое» основатель теории множеств – Георг Кантор (1845—1918) — немецкий математик, логик, теолог, создатель теории бесконечных множеств, оказавшей определяющее влияние на развитие математических наук на рубеже 19— 20 вв.

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

Слайд 5: Понятия теории множеств

Понятие множества является одним из наиболее общих и наиболее важных математических понятий. Оно было введено в математику немецким ученым Георгом Кантором (1845-1918).Следуя Кантору, понятие "множество" можно определить так: Множество - совокупность объектов, обладающих определенным свойством, объединенных в единое целое.

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

Слайд 6

С понятием множества мы соприкасаемся прежде всего тогда, когда по какой-либо причине объединяем по некоторому признаку в одну группу какие-то объекты и далее рассматриваем эту группу или совокупность как единое целое. Множества принято обозначать заглавными латинскими буквами : А, В, С, D. Объекты, которые образуют множество, называют элементами множества и для обозначения элементов используют, как правило, малые буквы латинского алфавита.

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

Слайд 7: Примеры множеств:

множество учащихся в данной аудитории; множество людей, живущих на нашей планете в данный момент времени; множество точек данной геометрической фигуры; множество чётных чисел; множество корней уравнения х2-5х+6=0; множество действительных корней уравнения х2+9=0;

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

Слайд 8

Если элемент x принадлежит множеству X, то записывают x  Х (  — принадлежит). В противном случае, если a не принадлежит множеству А, будем использовать обозначение  : Если множество А является ч астью множества В, то записывают А  В (  — содержится).

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

Слайд 9

множество элемент Трапеция, параллелограмм, ромб, квадрат, прямоугольник Шар, прямоугольный параллелепипед, призма, пирамида, октаэдр Натуральные числа 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 Двузначные четные числа Множество четырехугольников Пространственные тела 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11… Квадраты чисел Цифры десятичной системы счисления 10, 12, 14, 16 … 96, 98

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

Слайд 10

Множества, элементами которых являются числа, называются числовыми множествами.

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

Слайд 11

Обозначения некоторых числовых множеств: N – множество натуральных чисел; Z – множество целых чисел; Q – множество рациональных чисел; I - множество иррациональных чисел; R – множество действительных чисел.

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

Слайд 12: Способы задания множеств

Множество может быть задано перечислением всех его элементов или списком. В этом случае элементы множества записывают внутри фигурных скобок, например: A={студент А., рабочий Л., школьник М.}. 2. Множество может быть задано описанием свойств его элементов. Чаще всего при этом используют запись, которую читают следующим образом: « A есть множество элементов b таких, что для них выполняется свойство B ». Например, а – четное натуральное число. 3. Множество может быть задано указанием характеристического свойства его элементов, то есть такого свойства, которым обладают все элементы данного множества, и только они : Здесь x  М означает, что элемент х является элементом известного множества. Запись Р(х) означает, что элемент х обладает свойством Р. Свойство Р(х) формулируется словами, символами или выражается с помощью уравнения или неравенства.

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

Слайд 13: Примеры

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

Слайд 14: Примеры

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

Слайд 15: Виды множеств:

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

Слайд 16: Если элементы множества можно сосчитать, то множество является КОНЕЧНЫМ

Пример Множество гласных букв в слове “ математика ” состоит из трёх элементов – это буквы “ а ”, “ е ”, “ и ”, причем, гласная считается только один раз, т.е. элементы множества при перечислении не повторяются.

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

Слайд 17: Если элементы множества сосчитать невозможно, то множество БЕСКОНЕЧНОЕ

Пример Множество натуральных чисел бесконечно. Пример Множество точек отрезка [0;1] бесконечно. Пример Множество атомов во Вселенной

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

Слайд 18: Множество, не содержащее ни одного элемента, называется ПУСТЫМ. Символически оно обозначается знаком 

Пример Множество действительных корней уравнения x 2 +1=0. Пример Множество людей, проживающих на Солнце.

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

Слайд 19: Мощность множества

Число элементов конечного множества называют мощностью этого множества и обозначают символом m (A) или |A|. Количество элементов в конечном множестве естественно характеризовать их числом. В этом смысле множество чисел {-2, 0, 3,8} и множество букв {с, х, ф, а} эквивалентны, так как они содержат одинаковое число элементов.

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

Слайд 20: Пример. Определите мощность какого из множеств A = {1, 3, 5, 7, 9} или B = {2, 4, 6, 8} больше

Решение. Понятие мощности конечных множеств позволяет сравнивать их по количеству элементов. Так, если A = {1, 3, 5, 7, 9}, а B = {2, 4, 6, 8}, то m (A) = 5, а m (B) = 4 и потому m (A) > m (B).

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

Слайд 21: Отношения между множествами

Наглядно отношения между множествами изображают при помощи особых чертежей, называемых КРУГАМИ ЭЙЛЕРА (или диаграммами Эйлера – Венна ). Для этого множества, сколько бы они ни содержали элементов, представляют в виде кругов или любых других замкнутых кривых (фигур)

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

Слайд 22

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

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

Слайд 23

Множество A называется подмножеством множества B, если любой элемент множества A принадлежит множеству B. Эта зависимость между множествами называется  включением. При этом пишут A  B, где  есть знак вложения подмножества.

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

Слайд 24: Свойства множеств

Любое множество является подмножеством самого себя ( рефлексивность ): A  B. Для любых множеств А,В,С справедливо свойство транзитивности : если и, то. Для всякого множества А пустое множество  является его подмножеством :   А

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

Слайд 25

Два множества А и В называются  равными ( А = В ), если они состоят из одних и тех же элементов, то есть каждый элемент множества  А   является элементом множества   В   и наоборот, каждый элемент множества   В   является элементом множества  А. Примеры 1.,. Множества и состоят из одних и тех же элементов, поэтому они равные: А = В. 2. Множество решений уравнения есть множество чисел 2 и 3, то есть. Множество В простых чисел, меньших 5, также состоит из чисел 2 и 3, то есть.

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

Слайд 26: Количество подмножеств

Если мощность множества n, то у этого множества 2 n подмножеств. А= {1,2 } Подмножества А : {  }, { 1 }, { 2 }, { 1,2 }.

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

Слайд 27

В= {1,3,5 } Подмножества В : {  }, { 1 }, { 3 }, { 5 }, { 1,3 }, { 1,5 }, { 5,3 }, {1,3,5 } С= { а,и,е,о } Подмножества С : {  }, { а }, { и }, { е }, { о }, { а,и }, { а,е }, { а,о }, { и,е }, { и,о }, { е,о }, { а,и,е }, { а,и,о }, { а,е,о }, { и,е,о }, { а,и,е,о }. Количество подмножеств

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

Слайд 28: Операции над множествами

Пересечением (произведением) множеств А и В называется множество А ∩ В, элементы которого принадлежат как множеству А, так и множеству В. А ∩В= { х│ хєА и х єВ }

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

Слайд 29

Например, если А={ a, b, c }, B={ b, c, f, e }, то А ∩ В = { b } Операции над множествами пересечение

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

Слайд 30: Операции над множествами

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

Слайд 31

Объединением (суммой) двух множеств А и В называется множество А В, которое состоит из всех элементов, принадлежащих А или В. Операции над множествами А U В= { х│хєА или х єВ }

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

Слайд 32: объединение

Например, если А={1,2,4}, B={3,4,5,6}, то А  B = {1,2,3,4,5,6} 1 2 4 А 4 3 5 6 В Операции над множествами

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

Слайд 33: Операции над множествами

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

Слайд 34: Операции над множествами

Разностью множеств А и В называется множество А- В, элементы которого принадлежат множеству А, но не принадлежат множеству В. Операции над множествами

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

Слайд 35: разность

Например, если А={1,2,3,4}, B={3,4,5}, то А\В = {1,2} 1 2 4 А 4 3 5 6 В Операции над множествами

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

Слайд 36: Операции над множествами

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

Слайд 37: Операции над множествами

Дополнение множества Часто множества A,B, C … являются подмножествами некоторого более широкого множества U, принимаемого за универсальное.

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

Слайд 38: Операции над множествами

Если А - множество параллелограммов, В - множество трапеций, С - множество ромбов, D - множество прямоугольников, E - множество квадратов, то универсальным множеством U служит множество всех четырехугольников. Если А - множество треугольников, В - множество четырехугольников и так далее, то в качестве универсального множества U можно выбрать множество всех многоугольников. Операции над множествами ПРИМЕРЫ:

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

Слайд 39: Задача. Даны множества

Найти: объединение, пересечение, разность.

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

Слайд 40

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

Слайд 41

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

Слайд 42

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

Слайд 43

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

Слайд 44

Всего 67 Английский 47 Немецкий 35 23 47-23=24 24 35-23=12 12 24+12+23=59 67- 59=8 Задача. На фирме работают 67 человек. Из них 47 знают английский язык, 35 - немецкий язык, а 23 - оба языка. Сколько человек в фирме не знают ни английского, ни немецкого языков?

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

Слайд 45: Задача. Каждый учащийся в классе изучает английский или французский язык. Английский язык изучают 25 учащихся, французский — 27 учащихся, а два языка — 18 учащихся. Сколько учащихся в классе?

Ответ: в классе 34 ученика Английский 25 Немецкий 27 Только английский 25 – 18 = 7 Только немецкий 27 – 18 = 9 7 + 9 + 18 = 34 18 7 9

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

Слайд 46

Задача. Каждая семья, живущая в нашем доме, выписывает или газету, или журнал, или и то и другое вместе. 75 семей выписывают газету, а 27 семей выписывают журнал и лишь 13 семей выписывают и журнал, и газету. Сколько семей живет в нашем доме? 46 46 Всего: 14 + 13 + 62 =89

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

Слайд 47: Графы. Элементы графов. Виды графов и операции над ними

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

Слайд 48

Теория графов представляет собой раздел математики, имеющий широкие практические приложения. Теория графов – область дискретной математики, особенностью которой является геометрический подход к изучению объектов.

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

Слайд 49: История возникновения графов

Термин " граф " впервые появился в книге венгерского математика Д. Кенига в 1936 г., хотя начальные важнейшие теоремы о графах восходят к Л. Эйлеру.

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

Слайд 50: В основе теории лежит понятие графа

Граф - совокупность конечного числа точек, называемых вершинами графа, и попарно соединяющих некоторые из этих вершин линий, называемых ребрами или дугами графа. Иногда граф в целом можно обозначать одной заглавной буквой. Графом называется пара двух конечных множеств: множество точек V и множество линий X ( ребер, дуг), соединяющих некоторые пары точек.

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

Слайд 51: Состав графа

Граф состоит из вершин, связанных линиями. Вершины графа обозначают латинскими буквами A, B, C, D или цифрами. Направленная линия ( со стрелкой ) называется дугой. Линия ненаправленная ( без стрелки ) называется ребром. Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей. А В С петля ребро дуга

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

Слайд 52: Ориентированный граф -

граф, вершины которого соединены дугами. С помощью таких графов могут быть представлены схемы односторонних отношений. Маша Юра Аня Витя Коля

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

Слайд 53: Взвешенный граф

Это граф, рёбрам или дугам которого поставлены в соответствие числовые величины (они могут обозначать, например, расстояние между городами или стоимость перевозки). Вес графа равен сумме весов его рёбер. 1 2 4 2 3 A B C D E Таблице (она называется весовой матрицей ) соответствует граф.

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

Слайд 54

Две вершины графа называются смежными, если существует инцидентное им ребро: на рисунке смежными являются вершины А и В, А и С. А С В Если ребро графа G соединяет две его вершины V и W, (т.е. ), то говорят, что это ребро им инцидентно.

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

Слайд 55

Если граф G имеет ребро, у которого начало и конец совпадают, то это ребро называется петлёй. На рисунке ребро q (С, С) – петля. С A B D E q

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

Слайд 56

Два ребра называются смежными, если они имеют общую вершину. На рисунке смежными являются, например, рёбра х 1 и х 2 с общей вершиной С. х 1 х 2 х 3 х 4 х 5 х 6 х 7 С D F A B E H G

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

Слайд 57

Рёбра, которые начинаются в одной и той же вершине, заканчиваются также в одной и той же вершине, называются кратными, или параллельными. Количество одинаковых пар вида называется кратностью ребра Число рёбер, инцидентных вершине А, называется степенью этой вершины и обозначается (от англ. degree – степень).

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

Слайд 58

На рисунке кратными являются, например, рёбра х 1 (А, В), х 2 (А, В). Вершинам А и С инцидентны рёбра х 3, х 4, х 5. Следовательно, ребро АС имеет кратность, равную 3, а ребро АВ – кратность, равную 2. А С В х 1 х 2 х 5 х 3 х 4

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

Слайд 59

На рисунке вершина А имеет степень, равную 1, вершина С – 4, вершина D – 2. Записывается это в виде: deg (A)=1, deg (C)=4, deg (D)=2. х 1 х 2 х 3 х 4 х 5 х 6 х 7 С D F A B E H G

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

Слайд 60

E Вершина графа, имеющая степень, равную нулю, называется изолированной. Граф, состоящий из изолированных вершин, называется нуль-графом. Вершина графа, имеющая степень, равную 1, называется висячей. Граф, не имеющий ребер (дуг), называется пустым. На рисунке вершина Е – изолированная: deg (E)=0. A B D C

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

Слайд 61

На рисунке вершины А, В, Е, G, H – висячие. х 1 х 2 х 3 х 4 х 5 х 6 х 7 С D F A B E H G

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

Слайд 62

Теорема 1. В графе сумма степеней всех его вершин – число чётное, равное удвоенному числу рёбер графа: где - число вершин; - число рёбер графа.

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

Слайд 63

Вершина называется чётной ( нечётной ), если её степень – чётное ( нечётное ) число. На рисунке deg (D)=2, deg (F)=3, значит у графа вершина D является чётной, а F – нечётной. х 1 х 2 х 3 х 4 х 5 х 6 х 7 С D F A B E H G

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

Слайд 64

Теорема 2. Число нечётных вершин любого графа – чётно. Следствие. Невозможно начертить граф с нечётным числом нечётных вершин. Граф G называется полным, если любые две его различные вершины соединены одним и только одним ребром.

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

Слайд 65

Дополнением графа называется граф с теми же вершинами V, что и граф G, и имеющий те и только те рёбра, которые необходимо добавить к графу G, чтобы он стал полным. На рисунке дополнением графа G 1 до графа G является граф G G 1

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

Слайд 66: Пути и маршруты в графах

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

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

Слайд 67

В качестве примера рассмотрим орграф, представленный на рисунке. Одним из существующих путей, соединяющих вершины 1 и 3, является последовательность вершин 1, 2, 1, 4, 3. Единственным простым путем для той же пары вершин является последовательность 1, 4, 3. Пути из вершины 1 в вершину 5 для того же графа не существует.

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

Слайд 68

Неориентированный гра ф называется связным, если существует хотя бы один путь между каждой парой вершин. Орграф называется связным, если связен неориентированный граф, который получается из исходного ориентированного заменой всех дуг на ребра.

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

Слайд 69

Путь называется замкнутым, если начальная и конечная вершины совпадают. Замкнутый путь называется циклом, если все его вершины (кроме начальной и конечной) различны. Рассмотрим граф. Для него путь 2, 1, 6, 5, 4, 1, 2 является замкнутым ; а путь 1, 6, 5, 4, 1 является циклом.

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

Слайд 70

Последовательность попарно смежных вершин неориентированного графа, т.е. последовательность рёбер неориентированного графа, в которой вторая вершина предыдущего ребра совпадает с первой вершиной следующего, называется маршрутом. Число рёбер маршрута называется длиной маршрута. Если начальная вершина маршрута совпадает с конечной, то такой маршрут называется замкнутым или циклом.

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

Слайд 71

На рисунке HCDFD – маршрут длиной 4. Обозначение: |HCDFD|=4. Маршрут принято задавать как последовательность рёбер, поскольку это удобно при наличии кратных рёбер. х 1 х 2 х 3 х 4 х 5 х 6 х 7 С D F A B E H G

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

Слайд 72

В графе на рисунке ( t, s, p, r ), ( u, s, t, r ) – циклы длиной 4, ( r, t, q, s, u ) – цикл длиной 5, ( t, s, u, r, t, s, p, r ) – 8- цикл, ( p, u ) – 2- цикл, петля ( q) – 1- цикл. s E A B D C t p u q r

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

Слайд 73: Операции над графами

Объединением графов и называется граф, множество вершин которого, а множество рёбер. Пересечением графов и называется граф, для которого - множество рёбер, а - множество вершин. Кольцевой суммой двух графов называется граф,порождённый множеством вершин и множеством рёбер, т.е. множеством рёбер, содержащихся либо в, либо в, но не в.

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

Слайд 74

х 3 V 2 V 1 V 3 V 4 х 4 х 7 х 4 х 6 V 2 V 1 V 3 V 4 V 5 х 3 х 1 х 5 G 2 G 1 х 2 V 2 V 1 V 3 V 4 х 4 х 7 V 2 V 1 V 3 V 4 V 5 х 3 х 1 х 5 G=G 1 UG 2 х 6 х 4 х 4 х 3 V 3 V 2 V 1 G=G 1 ∩G 2 х 2 х 2 V 2 V 1 V 3 V 4 х 7 V 5 х 1 G=G 1 G 2 V 4 х 7 х 5 х 6

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

Слайд 75: Обоснование основных понятий комбинаторики: факториал, перестановки, размещения, сочетания

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

Слайд 76

Комбинаторикой называется раздел математики, в котором исследуется, сколько различных комбинаций (всевозможных объединений элементов), подчиненных тем или иным условиям, можно составить из элементов, принадлежащих данному множеству. Слово « комбинаторика » происходит от латинского слова combinare, которое означает «соединять, сочетать».

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

Слайд 77

В частности, одним из видов комбинаторных задач являются задачи на соединения Виды соединений размещения сочетания перестановки В задачах по комбинаторике часто применяется такое понятие как факториал ( в переводе с английского « factor » – множитель) n! = 1· 2· 3· …· (n -1)n Свойство : 0!=1

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

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

Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое число (номер элемента) от 1 до n, где n – число элементов множества, так что различным элементам соответствуют различные числа. Перестановки – различные упорядоченные множества, которые отличаются лишь порядком элементов. Термин “ перестановка ” употребил впервые Якоб Бернулли в книге «Искусство предположений». Р – первая буква французского слова permutation – перестановка. Формула (число размещений «из эн по эм»): (1654-1705)

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

Слайд 79

Пример 1: В расписании сессии 3 экзамена (история, геометрия, алгебра). Сколько может быть вариантов расписаний? Решение. ( обратить внимание на его оформление! ) Основное множество: {история, геометрия, алгебра}  Соединение – вариант расписания сессии Проверим, важен ли порядок: { история, геометрия, алгебра } и { геометрия, история, алгебра } – варианты расписания сессии для разных групп  порядок важен  это последовательность  это перестановка из трех элементов. Перестановки Ответ: 6 вариантов

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

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

Пример 2 Перестановки множества А={ a, b, c } из трёх элементов имеют вид: (a, b, c); (b, c, a); (c, a, b); (a, c, b); (b, a, c); (c, b, a), т. е. P 3 = 3! = 1х2х3 = 6 перестановок. Пример 3 Сколькими способами можно разместить на полке 4 книги? P 4 = 4! = 1х2х3х4 = 24 способа. Перестановки

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

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

Рассматривая перестановки ранее, мы предполагали, что n элементов различны. Если среди n элементов есть n1 элемент одного вида, n2 элементов другого вида и т.д., nk элементов k -го вида, то имеем перестановки с повторениями, их число: Пример 4. Сколько различных «слов» можно составить из букв слова ДЕД ? n=3, k=2, n1=2, n2=1

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

Слайд 82

Пример 5. Слова и фразы с переставленными буквами называют анаграммами. Сколько анаграмм можно составить из слова « макака »? Решение. Всего в слове « МАКАКА » 6 букв ( m=6 ). Определим сколько раз в слове используется каждая буква: « М » - 1 раз ( k1=1 ) « А » - 3 раза ( k2=3 ) « К » - 2 раза ( k3=2 ) Р = m! k 1 ! k 2 ! … k n ! Р 1,3,2 = 6 ! 1 ! 3 ! 2 ! = 4*5*6 2 = 60. Перестановки с повторениями

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

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

Размещением из n элементов по m ( m ≤ n ) называется последовательность, состоящая из m различных элементов некоторого n элементного множества. Формула (число размещений «из эн по эм »): Пример 6. Сколькими способами можно рассадить 4 учащихся на 25 мест ? Два размещения из n элементов считаются различными, если они отличаются самими элементами или порядком и х расположения.

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

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

Решение: Требуется выделить упорядоченные трехэлементные подмножества множества, содержащего 40 элементов, т.е. найти число размещений без повторений из 40 элементов по 3. A = =38*39*40=59280 40! 37! 40 3 Размещения Пример 7. Сколькими способами из 40 учеников класса можно выделить актив в следующем составе: староста, физорг и редактор стенгазеты?

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

Слайд 85

Решение ( обратить внимание на его оформление! ) Основное множество: {1, 3, 5, 7, 9} – нечетные цифры  Соединение – двузначное число  Пример 8. Сколько существует двузначных чисел, в которых цифра десятков и цифра единиц различны и нечетны? Проверим, важен ли порядок: разные двузначные числа  порядок важен  это последовательность  это размещение «из пяти по два». двузначных чисел Ответ: 20 чисел. Размещения

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

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

Размещения с повторениями – соединения, содержащие n элементов, выбираемых из элементов m различных видов ( ) и отличающиеся одно от другого либо составом, либо порядком элементов. Их количество в предположении неограниченности количества элементов каждого вида равно

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

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

Пример 9. В библиотеку, в которой есть много одинаковых учебников по десяти предметам, пришло 5 школьников, каждый из которых хочет взять учебник. Библиотекарь записывает в журнал по порядку названия (без номера) взятых учебников без имен учеников, которые их взяли. Сколько разных списков в журнале могло появиться? Размещения с повторениями Решение : Так как учебники по каждому предмету одинаковые, и библиотекарь записывает лишь название (без номера),то список – размещение с повторением, число элементов исходного множества равно 10, а количество позиций – 5. Тогда количество разных списков равно = 100000. Ответ : 100000

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

Слайд 88

Сочетания Сочетанием из n элементов по m ( m ≤ n ) называется m - элементное подмножество некоторого n элементного множества. Формула (число размещений « из эн по эм »): Сочетания – конечные множества, в которых порядок не имеет значения.

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

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

Решение. ( обратить внимание на его оформление! ) Основное множество: {мак, роза, тюльпан, лилия, гвоздика}  Соединение – букет из трех цветков  Проверим, важен ли порядок : {тюльпан, лилия, гвоздика} и {лилия, тюльпан, гвоздика} – один и тот же букет  порядок неважен  это подмножество  это сочетание «из пяти по три». Ответ: 10 букетов Сочетания Пример 10. Сколькими способами можно составить букет из 3 цветов, если в вашем распоряжении 5 цветов: мак, роза, тюльпан, лилия, гвоздика ?

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

Слайд 90: Сочетания с повторениями

Сочетаниями с повторениями из m по n называют соединения, состоящие из n элементов, выбранных из элементов m разных видов, и отличающиеся одно от другого хотя бы одним элементом. Число сочетаний из m по n обозначают

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

Слайд 91: Сочетания с повторениями

Если из множества, содержащего  n  элементов, выбирается поочередно  m  элементов, причём выбранный элемент каждый раз возвращается обратно, то количество способов произвести неупорядоченную выборку – число  сочетаний с повторениями   – составляет Сочетания с повторениями

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

Слайд 92

Пример 11. Сколько костей находится в обычной игре "домино"? Решение : Кости домино можно рассматривать как сочетания с повторениями по две из семи цифр множества (0,1,2,3,4,5,6).  Число всех таких сочетаний равно

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

Последний слайд презентации: Операции с множествами. Основные понятия графов. Комбинаторика

Спасибо за внимание!

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