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

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

Содержание ▲

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

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

Слайд 1

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

Дискретная математика Гр. ИВТ-25Д Хаиртденов Т.К СФТИ НИЯУ МИФИ г.Снежинск 2016

Слайд 2

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

Справочные данные Кафедра АИВС (Автоматизированных информационных и вычислительных систем) Преподаватель Мякушко Эдуард Валерьевич Заведующий кафедрой Крушный Валерий Васильевич

Слайд 3

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

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

Слайд 4

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

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

Слайд 5

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

Информационно - измерительная система Человек

Слайд 6

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

Информационно - измерительная система Техническая

Слайд 7

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

Восприятие внешнего мира информационно – измерительными системами Объекты который присутствуют вокруг нас (внешний мир), будем воспринимать используя математический объект – множество. Мно́жество — одно из ключевых понятий математики, в частности, теории множеств и логики. Множество – соединение в некое «М» определенных, хорошо различимых предметов «m» нашего созерцания или нашего мышления (которое будет называться «Элементами множества «М»»)

Слайд 8

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

Мое личное определение, что есть множество. Множество – это совокупность различных объектов, объединенное в единое целое.

Слайд 9

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

Восприятие внешнего мира роботом

Слайд 10

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

Слайд 11

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

Формальное представление множеств А = {a, b, c, d} a ∈ A, b ∈ A, c ∈ A, d ∈ A –принадлежность элементов множеству f ∉ A, g ∉ A, h ∉ A – не принадлежность элементов множеству |А|= количество элементов множества (мощность множества) |А|= 4

Слайд 12

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

Пустое множество. Универсум. |A| = 0, множество А – пустое множество, т.к у него отсутствуют элементы. Обозначение Ø. Универсум – универсальное множество. Обозначается U, показывает границы в которых находятся все остальные множества.

Слайд 13

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

Множество. Вектор. A= {a,b,c,d},элементы множества можно перемещать. Важно наличие элемента, а не его положение. A = {b,c,a,d} A= (a,b,c,d),A – вектор, элементы вектора находятся каждый в своем месте, поэтому они называются координатами. Координаты нельзя перемещать со своего места.

Слайд 14

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

Операции над множествами. Взаимодействие множеств можем показать через операции над ними. Пересечение множеств A∩B = общие элементы

Слайд 15

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

Пример пересечения множеств. |U| = 10, |A| = 8, |B| = 5, |A ∩ B| = 3 U = {a,b,c,d,e,r,t,y,u,q} A = {a,b,c,t,r,e,y,q} B = {a,b,c,u,d} A∩B = {a,b,c}

Слайд 16

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

Объединение множеств. |U| = 10, |A| = 8, |B| = 5 |A ᴜ B| = 10 U = {a,b,c,d,e,r,t,y,u,q} A = {a,b,c,t,r,e,y,q} B = {a,b,c,u,d} A ᴜ B = {a,b,c,t,r,e,y,q,d,u}

Слайд 17

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

Дополнение. Дополнение – это элементы которые не достают до универсума |U| = 10, |A| = 8 U = {a,b,c,d,e,r,t,y,u,q} A = {a,b,c,t,r,e,y,q} ¬A = {d,u}

Слайд 18

$Разность множеств. |U| = 10, |A| = 8, |B| = 5 U = {a,b,c,d,e,r,t,y,u,q} A = {a,b,c,t,r,e,y,q} B = {a,b,c,u,d} A\B = {t,r,e,y,q} B\A = {u,d}$

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

Разность множеств. |U| = 10, |A| = 8, |B| = 5 U = {a,b,c,d,e,r,t,y,u,q} A = {a,b,c,t,r,e,y,q} B = {a,b,c,u,d} A\B = {t,r,e,y,q} B\A = {u,d}

Слайд 19

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

Симметрическая разность. |U| = 10, |A| = 8, |B| = 5 A ᴜ B = {a,b,c,t,r,e,y,q,d,u} A ∩ B = {a,b,c} A ∆ B = {t,r,e,y,q,d,u}

Слайд 20

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

Самостоятельная работа.

Слайд 21

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

Множество подмножеств.(Булеан) A = {x,y,z} β(A) – множество подмножеств β(A) = {Ø,{x},{y},{z},{xy},{xz},{yz},{x,y,z}} | β(A) | = 8 = 2n,где n – число элементов множества. Множество подмножеств - это объекты, окружающие информационно - измерительную систему(роботы) Робот воспринимает эти объекты через двоичные вектора

Слайд 22

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

Взаимно – однозначные соответствия Булеана и множества двоичных векторов β(A) = Ø↔(0,0,0) {x} ↔(1,0,0) {y} ↔(0,1,0) {z} ↔(0,0,1) {xy} ↔(1,1,0) {xz} ↔(1,0,1) {yz} ↔(0,1,1) {x,y,z} ↔(1,1,1)

Слайд 23

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

Пример A = {a,b,c,d} β(A) = Ø↔(0,0,0,0,) {a,b,c,d} ↔(1,1,1,1) {a,b} ↔(1,1,0,0) {a,c} ↔(1,0,1,0) {a,d} ↔(1,0,0,1) {b,c} ↔(0,1,1,0) {b,d} ↔(0,1,0,1) {c,b} ↔(0,1,1,0) {a} ↔(1,0,0,0) {b} ↔(0,1,0,0) {c} ↔(0,0,1,0) {d} ↔(0,0,0,1) {a,b,c} ↔(1,1,1,0) {a,b,d} ↔{1,1,0,1} {d,b,c} ↔(0,1,1,1) {a,c,d} ↔(1,0,1,1)

Слайд 24

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

Взаимодействие объектов показывается через операции над подмножествами β(A) = Ø↔(0,0,0) {x} ↔(1,0,0) {y} ↔(0,1,0) {z} ↔(0,0,1) {xy} ↔(1,1,0) {xz} ↔(1,0,1) {yz} ↔(0,1,1) {x,y,z} ↔(1,1,1) {x}∩{y} = Ø ↔ (1,0,0)*(0,1,0) = (0,0,0) {x,y}U{z,x} = {x,y,z} ↔(1,1,0)+(1,0,1) = (1,1,1) (дизъюнкция -max) ¬{z} = {x,y} ↔¬(0,0,1)=(1,1,0)(отрицание) Операции пересечения, объединения и дополнения являются Булевыми операциями над подмножествами.

Слайд 25

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

Пример №2 A = {a,b,c,d} β(A) = Ø↔(0,0,0,0) {a,b,c,d} ↔(1,1,1,1) {a,b}∩{c,d} = Ø↔(1,1,0,0)*(0,0,1,1)=(0,0,0,0) {a,c}U{b,d} = {a,b,c,d} Ø↔(1,0,1,0)*(0,0,1,1)=(0,0,0,0) ¬{d} = {a,b,c} ↔¬(0,0,0,1)=(1,1,1,0)

Слайд 26

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

Опреации над множествами(подмножествами) обладают определенными свойствами

Слайд 27

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

Взаимно – однозначные соответствия для построения цифровых технических систем (β(A), U, ∩, -) ↕ ↕ ↕ ↕ (Bn, +, *, ⌐) ↕ ↕ ↕ ↕ (P(n), +, *, ⌐) где β(A) – множество подмножеств; Bn -множество двоичных векторов длины n; P(n) - множество переменных логических функций где n - количество переменных.

Слайд 28

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

Операции над переменными логических функций.

Слайд 29

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

Отношения

Слайд 30

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

Графическое изображение отношений (граф) . . . . . . . . . . . . . . . .

Слайд 31

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

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

Слайд 32

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

Отношение на прямом произведении A×B×C

Слайд 33

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

Примеры отношения на прямом произведении A×B×C R⊆A×B×C |R|=8, R ={(a,x,p),(a,x,o),(a,x,h),(b,x,p),(b,x,o), (b,x,h),(c,x,p),(c,x,o)}

Слайд 34

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

Операции над отношениями R1⊆A×B, |A| = 5, |B| = 5, A ={a,b,c,d,e}, B = {f,i,j,h,k} R2 ⊆A×B, | R1 | = 12, | R2 | = 13

Слайд 35

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

Обратное отношение. R-1 – обозначение обратного отношения. R = {(a,b),(c,d),(e,f),(i,j)} R-1 = {(b,a),(d,c),(f,e),(j,i)} Т.о отношение осуществляется в «обратную» сторону

Слайд 36

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

Композиция отношений. R1⊆A×B R3⊆B×C R1⊆A×B R1 ◦ R3 - обозначение операции. R1 ◦ R3⊆A×С, таким образом операция композиция позволяет перейти в другой универсум («расширить» действие отношений).

Слайд 37

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

|C|= 5, C = {q,w,e,r,t}, |R3|= 14

Слайд 38

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

Графическое изображение операции композиция.

Слайд 39

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

Отношения на прямом произведении Булеана. R⊆β(A) × β(A), где А = {x,y,z}, R - пересечение

Слайд 40

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

Слайд 41

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

Контрольная работа №2 R1⊆A×B R2⊆A×B R3⊆B×C |A|=|B|=|C|=10;| R1 | = 70, | R2| = 80 | R3 | = 60 Выполнить операции над отношениями Сформировать отдельный файл (в свою папку группы) Единицы в произвольном порядке

Слайд 42

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

Переменные логических функций. Операции над переменными логических функций.

Слайд 43

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

Слайд 44

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

Любую операцию над переменными логических функций мы можем представить через Булевый базис(•, +,¬).

Слайд 45

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

Схемное изображение логических элементов.

Слайд 46

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

Слайд 47

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

Операция эквивалентность реализованная в Булевом базисе с помощью релейно-контактной схемы.

Слайд 48

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

Таблица истинности(переключательная таблица) С помощью таблиц истинности получаем результат логической функции для любого числа переменных. Пример: F(x,y,z)=x•(y→¬z)+(x≡¬y)

Слайд 49

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

Решение функций с помощью таблицы истинности. F(x,y,z)=x•(y→¬z)+(x≡¬y)

Слайд 50

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

Решение функций с помощью таблицы истинности. F(x,y,z)=x•(y→¬z)+(x≡¬y)

Слайд 51

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

Схемная реализация вычисления логической функции от 3х переменных с помощью рэлейно – контактной схемы (веник).

Слайд 52

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

Минимизация СДНФ с использованием карты Карно. Имеем логическую функцию F(x,y,z,c)=(⌐(x+c))→((z•y)))≡((⌐c)+(⌐y))

Слайд 53

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

Слайд 54

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

Слайд 55

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

Слайд 56

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

Слайд 57

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

Слайд 58

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

Логические элементы с большим количеством входов.

Слайд 59

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

Графы. Граф состоит из множества вершин и множества ребер (ребра соединяют вершины или одну вершину). Если ребра имеют ориентацию (вход и выход),значит граф ориентированный, если не имеют, значит граф не ориентированный. Граф – есть топологический объект – расположение вершин не фиксировано(располагаются где угодно), фиксируются лишь соединения вершин ребрами.

Слайд 60

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

Неориентированный граф. A={x,y,z,c,a,b,d,e} – множество вершин. B={{x,z},{x,c},{c,b},{b,e},{e,y},{y,d},{d,a},{a,z},{c,a}} – множество ребер.

Слайд 61

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

При изменении вершин топология графа не изменяется.

Слайд 62

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

Задание графа с помощью отношения смежности. Отношение смежности отношение между вершинами графа. Если вершины графа соединены ребром, они связаны отношением смежности. R - отношение смежности. R⊆A×B

Слайд 63

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

Зададим неориентированный граф через отношение смежности.

Слайд 64

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

Неориентированный мульти-граф, отношении смежности.

Слайд 65

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

Неориентированный псевдо-граф, отношении смежности.

Слайд 66

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

Ориентированный граф. A={x,y,z,c,a,b,d,e} – множество вершин. B={(z,x),(x,c),(c,b),(b,e),(e,y),(y,d),(d,a),(a,z),(c,a)(b,d)} – множество ребер.

Слайд 67

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

Зададим ориентированный граф через отношение смежности.

Слайд 68

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

Неориентированный граф. Можем задать через отношение инцидентности. A={x,y,z,c,a,b,d,e} – множество вершин. B={{x,z},{x,c},{c,b},{b,e},{e,y},{y,d},{d,a},{a,z},{c,a}} – множество ребер.

Слайд 69

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

Зададим граф с помощью отношения инцидентности. R - отношение инцидентности. R⊆A×B(отношение инцидентности -отношение между вершинами и ребрами).

Слайд 70

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

Ориентированный граф A={x,y,z,c,a,b,d,e} – множество вершин. B={(z,x),(x,c),(c,b),(b,e),(e,y),(y,d),(d,a),(a,z),(c,a)(b,d)} – множество ребер.

Слайд 71

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

Зададим орграф через отношение инцидентности.

Слайд 72

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

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

Слайд 73

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

Теорема о степенях вершин в теории графов. Сумма степеней всех вершин графа равна удвоенному количеству всех ребер. Доказательство. Степень вершины — это количество концов ребер, сходящихся в этой вершине. Поэтому сумма степеней всех вершин графа равна количеству всех концов ребер, которые есть в графе. Но у каждого ребра ровно два конца, значит общее количество ребер в два раза меньше количества концов всех ребер, откуда и получаем утверждение теоремы. Проверим на примере. Сумма степеней = 20, количество ребер умноженное на 2 = 20.

Слайд 74

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

Цикломатическое число. Цикломатическим числом графа - называется число u=N-n+p, где N- число ребер графа, n – число его вершин, P – число компонент связности. Для связного графа u=N-n+1. Компонента связности графа — некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества. Путь в графе — последовательность вершин, в которой каждая вершина соединена со следующей ребром.

Слайд 75

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

Найдем путь орг. графа (x,c,b,e,y,d,a,z,x) (x,c,a,z,x) (x,c,b,d,a,z,x)

Слайд 76

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

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

Слайд 77

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

Граф дерево используется для моделирования операций над переменными логических функций F(x,y)=x ⊕ y = ¬((¬X+Y) •(X+¬Y)) = = ¬(¬x + y)+ ¬( x+ ¬y)=(¬ ¬ x • ¬y)+(¬ x • ¬ ¬ y)= =(x • ¬y)+(¬ x • y) – выход графа – дерево.

Слайд 78

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

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

Слайд 79

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

Рассмотрим функцию сложения по модулю 2. f:An→B A – область определения функции B - область значений функции Если A=B, то f – функция, есть операция где A = {0,1} B = {0,1} F(x1, x2 , … , xn) = x1 ⊕ x2 ⊕ x3 ⊕ … ⊕ xn

Слайд 80

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

Представим функцию F(x1, x2 , … , xn) = x1 ⊕ x2 ⊕ x3 ⊕ … ⊕ xn в виде графа.

Слайд 81

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

Мажоритарная функция. Major – главный, функция принимает значение одни на тех и только тех наборах, в которых единиц больше чем нулей(функция голосования).

Теги Дискретная математика

Похожие презентации