Дискретная математика - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Дискретная математика. Доклад-сообщение содержит 92 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Введение

Слайд 2

Описание слайда:

Плаксина Юлия Геннадьевна Плаксина Юлия Геннадьевна Доцент кафедры электронных вычислительных машин 8(3466)-267-90-50 plaksinayg@yandex.ru ЮУрГУ, 811/3б корпус

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

Дискретная математика также изучает Дискретная математика также изучает некоторые алгебраические системы: - группы; - кольца; - поля; - частично упорядоченные множества; - решетки.

Слайд 6

Описание слайда:

Разделы дискретной математики: Математическая логика. Математическая кибернетика. Теория функциональных систем. Общая алгебра. Комбинаторика. Теория графов. Машинная арифметика. Теория алгоритмов. Теория игр. Теория кодирования. 11. Теория искусственного интеллекта.

Слайд 7

Описание слайда:

Разделы дискретной математики: 12. Теория конечных автоматов. 13. Теория множеств. 14. Теория формальных грамматик. 15. Теория булевых функций. 16. Логическое программирование. 17. Функциональное программирование. 18. λ - исчисление. 19. Булева алгебра. 20. Комбинаторная логика. 21. Математическая лингвистика.

Слайд 8

Описание слайда:

В дискретной математике нет понятия В дискретной математике нет понятия - бесконечного множества, - предельного перехода, - непрерывности, - дифференцируемости.

Слайд 9

Описание слайда:

Любое понятие дискретной математики можно определить с помощью понятия множества.

Слайд 10

Описание слайда:

Основателем теории множеств является Георг Кантор немецкий математик

Слайд 11

Описание слайда:

Определение Г. Кантором понятия «множество» Под «множеством» мы понимаем соединение в некое целое M определённых хорошо различимых предметов m нашего созерцания или нашего мышления (которые будут называться «элементами» множества M). Unter einer ‚Menge‘ verstehen wir Zusammenfassung M von bestimmten wohlunterschiedenen Objecten m unsere Anschauung order unseres Denkens (welche die ‚Elementen‘ von M genannt werden) zu einem Ganzen.

Слайд 12

Описание слайда:

Определения понятия «множество» Под множеством понимается некоторая, вполне определенная совокупность объектов или элементов. Множество – совокупность некоторых (произвольных) объектов, объединенных по какому-либо признаку. Множество - это совокупность определенных различаемых объектов, причем таких, что для каждого можно установить, принадлежит этот объект данному множеству или нет.

Слайд 13

Описание слайда:

Таким образом: Множество – любая совокупность объектов, которая обладает следую-щими свойствами: Элементы множества представляют собой попарно различимые объекты. Элементы и состав множества не меняются с течением времени.

Слайд 14

Описание слайда:

Объекты, составляющие множество, называются элементами множества и обозначаются маленькими латинскими буквами (например, x, a, b, bi, cij).

Слайд 15

Описание слайда:

Множества обычно обозначаются заглавными латинскими буквами (например, A, B, C, D)

Слайд 16

Описание слайда:

Для некоторых множеств приняты специальные обозначения: Для некоторых множеств приняты специальные обозначения: N – множество натуральных чисел; {1,2,3,…,100,101,…} Z – множество целых чисел; {0,1, -1, 2, -2, …}

Слайд 17

Описание слайда:

Q – множество рациональных чисел. Q – множество рациональных чисел. Целые и дробные числа (обыкновенные дроби, конечные десятичные дроби и бесконечные периодические дроби). ! Бесконечные периодические дроби НЕ входят в множество рациональных чисел.

Слайд 18

Описание слайда:

Число «ПИ» ( п=3.ю14…), основание натурального логарифма e (e = 2,718…) или не являются рациональными числами. Число «ПИ» ( п=3.ю14…), основание натурального логарифма e (e = 2,718…) или не являются рациональными числами.

Слайд 19

Описание слайда:

Слайд 20

Описание слайда:

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

Слайд 21

Описание слайда:

Слайд 22

Описание слайда:

R – множество действительных чисел; R – множество действительных чисел;

Слайд 23

Описание слайда:

Для некоторых множеств приняты специальные обозначения: Для некоторых множеств приняты специальные обозначения: C – множество комплексных чисел. Комплексное число – это выражение вида , где a и b – действительные числа, а i – мнимая единица.

Слайд 24

Описание слайда:

Мнимая единица – символ, квадрат которого равен -1, т.е

Слайд 25

Описание слайда:

Число а – действительная часть, b – мнимая часть комплексного числа Число а – действительная часть, b – мнимая часть комплексного числа ! Действительные числа – частный случай комплексных чисел. Если b=0, z=a+0i = a.

Слайд 26

Описание слайда:

Пример {1,2.3,4} – множество, содержащее натуральные числа 1,2,3 и 4.

Слайд 27

Описание слайда:

а А (а принадлежит А) а А (а не принадлежит А)

Слайд 28

Описание слайда:

Пример 3 {1,2,3,4} 5 {1,2,3,4}

Слайд 29

Описание слайда:

- «тогда и только тогда, когда»; - «существует х такой, что»; - «для всякого х»; - «следует» или «вытекает».

Слайд 30

Описание слайда:

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

Слайд 31

Описание слайда:

Пример Элементы конечного множества А можно обозначить через a1, a2, …, a5: А = {a1, a2, …, a5}.

Слайд 32

Описание слайда:

Пример Бесконечными являются множества всех натуральных (N), целых (Z), действительных (R) чисел.

Слайд 33

Описание слайда:

Понятие «счетного множества» Счетное множество – это множество А, все элементы которого могут быть занумерованы в бесконечную последовательность а1, а2, а3, …, аn.. так, чтобы при этом каждый элемент получил лишь один номер n и каждое натуральное число n было бы номером лишь одного элемента множества А. ссылка

Слайд 34

Описание слайда:

Например. Дано множество , тогда . Различия между отношениями принадлежности и включения: если , то , если , то и .

Слайд 35

Описание слайда:

Понятие «мощность множества» Мощностью множества А называется количество входящих в его состав различных элементов и обозначается через |А|.

Слайд 36

Описание слайда:

Пример A = {a, b, c, d} |A|=4 B = {a, b, {a, b}, a} |B|=3 C = {a1, a2, …, an} |C|=n D = {N, 1, {1, 2}} |D|=3 E = {a} |E|=1

Слайд 37

Описание слайда:

Понятие равномощного множества Множества А и В называются равномощными, если между их элементами существует взаимно-однозначное соответствие.

Слайд 38

Описание слайда:

Взаимно-однозначное соответствие предполагает, что каждому элементу множества B поставлен в соответствие ровно один элемент множества A.

Слайд 39

Описание слайда:

Графическое представление взаимно-однозначное соответствие

Слайд 40

Описание слайда:

Пример Множества {0, 1, 2} и {лошадь, корова, телевизор} - равномощны, Множества {0, 1, 2} и {лошадь, корова} - неравномощны.

Слайд 41

Описание слайда:

Пример Множество N и множество четных чисел также равномощны: N: 1 2 3 4 5 6 … ↨ ↨ ↨ ↨ ↨ ↨ Четные числа: 2 4 6 8 10 12 …

Слайд 42

Описание слайда:

Два множества равны, тогда и только тогда, когда они состоят из одних и тех же элементов. Равенство двух множеств А и В обозначается А = В.

Слайд 43

Описание слайда:

Примеры Множества А = {2,4,6} и В = {2,6,4} равны. Так как состоят из одних и тех же элементов. Множества {{a,d},{d,c}} и {a,d,c} не равны. Так как первое состоит из элементов {a,d} и {d,c}, а второе из a,d,c. Множества {{1,2}} и {1,2} не равны. Так как первое множество одноэлементное, а второе - двухэлементное.

Слайд 44

Описание слайда:

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

Слайд 45

Описание слайда:

Способы задания множеств 1.Табличная форма или перечисление элементов. А = { a1, a2, …, an }

Слайд 46

Описание слайда:

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

Слайд 47

Описание слайда:

Способы задания множеств 2. Описание признака или свойства элементов множества. Множество = {х | х обладает свойством Р}

Слайд 48

Описание слайда:

Понятие свойства Под свойством предмета Х будем понимать такое повествовательное предложение, в котором нечто утверждается относительно предмета Х и которое можно характеризовать как истинное или ложное по отношению к Х.

Слайд 49

Описание слайда:

Пример 1. Свойство «быть квадратом целого числа» задает (бесконечное) множество всех квадратов целых чисел: A = {y| x Z & y=x2}. 2. Свойство «делиться на число 2 без остатка» задает множество четных чисел: B = {y | x Z & y=2*x}. 3. Свойство «рост студента 180 см» задает множество студентов: С = {х | х – студент рост, которого 180 см}

Слайд 50

Описание слайда:

Способы задания множеств 3. С помощью порождающей процедуры. Каждый последующий элемент множества определяется на основании предшествующих элементов.

Слайд 51

Описание слайда:

Примеры 1. Каждый последующий элемент есть сумма двух предыдущих, задается следующим образом: D = {xk | x0=0, x1=1, xk=xk-2+xk-1}. 2.

Слайд 52

Описание слайда:

Способы задания множеств 4.) Графическое задание множеств с помощью диаграмм Эйлера-Венна.

Слайд 53

Описание слайда:

Таким образом, 1. Способ задания множества должен быть адекватным, т.е. полностью определять множество. Это возможно, если объекты множества перечислены. 2. К описанию свойств естественно предъявить требования точности и недвусмысленности.

Слайд 54

Описание слайда:

Понятие «пустое множество» Пустое множество - множество, не содержащее ни одного элемента. Оно обозначается Ø и его мощность равна нулю (|Ø|=0). Пустое множество единственно.

Слайд 55

Описание слайда:

Множества {Ø} и {{Ø}} неравномощные. В множестве {Ø} нет ни одного элемента, а в множестве {{Ø}} есть один элемент пустое множество.

Слайд 56

Описание слайда:

Понятие универсального множества Универсальное множество U: есть множество, обладающее таким свойством, что все рассматриваемые множества являются его подмножеством.

Слайд 57

Описание слайда:

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

Слайд 58

Описание слайда:

Теоретико-множественные отношения

Слайд 59

Описание слайда:

Отношение нестрогого включения Множество А называют подмножеством множества В, если каждый элемент множества А является также элементом множества В. То, что множество А является подмножеством множества В обозначают так:

Слайд 60

Описание слайда:

Диаграмма Эйлера-Венна При этом множество В называется надмножеством множества А.

Слайд 61

Описание слайда:

Пример Множество всех четных чисел является подмножеством множества всех целых чисел, множество {0, 1, 2} – подмножеством множества {0, 1, 2, 3}. Множество должностных преступлений – подмножеством множества всех преступлений.

Слайд 62

Описание слайда:

Если А не является подмножеством В это записывается как А В Если А не является подмножеством В это записывается как А В Пример: {1,2,3} {1,2,3,4}, {1,2,5,} {1,2,3,4}, поскольку существует элемент А не принадлежащий В.

Слайд 63

Описание слайда:

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

Слайд 64

Описание слайда:

Любое множество является подмножеством самого себя, т.е. для любого множества А справедливо включение

Слайд 65

Описание слайда:

Отношение равенства Два множества называются равными, если каждый элемент любого из них необходимо является элементом другого. А = В тогда и только тогда, когда

Слайд 66

Описание слайда:

Слайд 67

Описание слайда:

Отношение строгого включения Подмножество А строго включается во множество В , если оно нестрого включается во множество В и при этом они не равны друг другу (А≠В).

Слайд 68

Описание слайда:

В этом случае А называется собственным подмножеством или собственной частью множества В.

Слайд 69

Описание слайда:

Любое множество, отличное от несобственного, называется собственным подмножеством данного множества.

Слайд 70

Описание слайда:

Пример Множество А = {а, b, c} является собственным подмножеством множества В = {а, b, c, d. e}.

Слайд 71

Описание слайда:

Верна цепочка включений числовых множеств: Верна цепочка включений числовых множеств: множество натуральных чисел N является подмножеством множества целых чисел Z, которое является подмножеством множества рациональных чисел Q множества вещественных чисел R, множества комплексных чисел C.

Слайд 72

Описание слайда:

Выводы: 1. Пустое множество является подмножеством любого множества. 2. Любое множество является подмножеством самого себя. 3. У любого множества есть обязательно хотя бы два подмножества: пустое множество и само множество.

Слайд 73

Описание слайда:

Выводы: 4. У пустого множества нет собственных подмножеств. 5. Оба несобственных подмножества равны между собой. 6. У любого одноэлементного множества нет собственных подмножеств. Его несобственные подмножества различны.

Слайд 74

Описание слайда:

Если А ={3,5}, то собственными подмножествами множества А будут являться множества {3} и {5}

Слайд 75

Описание слайда:

Отношение включения и отношение принадлежности

Слайд 76

Описание слайда:

Если так, тогда операции включения и отношение принадлежности суть одно и то же? Нет. Принадлежность - это принадлежность элемента множеству. Включение - это включение подмножества в множество. Например, если мы возьмем множество из каких-нибудь трех элементов, то , , , , , , , , , , . Кстати, знак вводится для удобства, а на самом деле строка - это сокращение для формулы .

Слайд 77

Описание слайда:

Очень важно не смешивать отношения принадлежностии включения: если {а}М, то аМ, и наоборот; но из {a}М не следует {а}М. Так, например, если М = {1, 2}, то это означает, что 1М и 2М, но для всех других объектов х справедливо хМ; для включения же правильны следующие утверждения: М, {1}М, {2}М., {1, 2}М. Другой пример. Пустое множествоне имеет элементов хM для любого объекта х. Между темсодержит одно подмножество, а именно само себя.

Слайд 78

Описание слайда:

Слайд 79

Описание слайда:

Понятие булеана множества Количество всех подмножеств (множество всех подмножеств) некоторого множества А называется его булеаном, или множеством-степенью, и обозначается через и равно 2 |A| , где |A| - мощность множества А.

Слайд 80

Описание слайда:

Пример А = {1, 3, 5}, Р(А) = {Ø, {1}, {3}, {5}, {1,3}, {1,5}, {3,5}, {1,3,5}}.

Слайд 81

Описание слайда:

Пример Пусть A = { 1,2,3,4,...,n }, |A | = n. Найдем мощность множества Р(A).

Слайд 82

Описание слайда:

Для определения Р(A) воспользуемся биномиальными коэффициентами (число сочетаний из n по k)

Слайд 83

Описание слайда:

Перечислим по порядку, начиная с пустого множества, все подмножества множества A: Перечислим по порядку, начиная с пустого множества, все подмножества множества A: пустому подмножеству множества A поставим в соответствие число 1 = булеан содержит одноэлементные подмножества: { 1 }, { 2 }, { 3 }, ..., {n}; (число одноэлементных подмножеств равно n = )

Слайд 84

Описание слайда:

Булеан содержит следующие Булеан содержит следующие двухэлементные подмножества: { 1,2 },{ 1,3 },{ 1,4 },… ,{ 1,n },{ 2,3 },{ 2,4 }, …,{ 2,n },{ 3,4 },{ 3,5 }, …,{ 3,n },…, { n - 2,n - 1 },{ n - 2,n },{ n - 1,n}. Количество двухэлементных подмножеств равно:

Слайд 85

Описание слайда:

Булеан содержит: Булеан содержит: - трехэлементных подмножеств, четырехэлементных подмножеств

Слайд 86

Описание слайда:

Таким образом, булеан содержит (n - 1)-элементных подмножеств и одно n элементное подмножество (само множество A), которому сопоставляется биномиальный коэффициент