Реферат: Дискретная математика - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

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

Банк рефератов / Математика

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 39 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

Дискретная математика Введение Общество 21в . – общество информаци онное . Центр тяжести в решении задач перем естился от задач вычислительной математики к задачам на дискретных структурах . Математика нужна не как метод расчета , а как метод мышлению средство формирования и орг анизации… Такое владение математикой богатой кул ьтуры , понимание важности точных формулир овок . В дисциплине мало методов , но много определений и терминов . В основе дискретной математике 4 раздела : 1. Язык дискретной математики ; 2. Логические функции и автоматы ; 3. Теория алгоритмов ; 4. Графы и диск ретн ые экстремальные задачи. Теория алгоритмов и формальных систем является центральной в дисциплине . В настоящие время от нее возникли ответвле ния , например , разработка алгоритмических языков программирования. Одной из важнейших проблем в дискретн ой мате матики является проблема сложности вычислений. Теория сложности вычислений помогает оцен ить расход времени и памяти при решении задач на ЭВМ . Теория сложности позволяет выделить объективно сложные задачи (задачи перебора ) и неразрешимые задачи . Мы будем з аниматься решением зада ч реальной размерности с учетом ограниченност и временных и емкостных ресурсов ЭВМ. Множества и операции над ними Одно из основных понятий математики – множество. Определение : Множеством называется совоку пность , набор предметов , объ ектов или элементов. Множество обозначают : M , N ….. m 1 , m 2 , m n – э лементы множества. Символика A M – принадлежность эл емента к множеству ; А М – непринад лежность элемента к множеству. Примеры числовых множеств : 1,2,3,… множество натуральных чисел N ; … ,-2,-1,0,1,2,… - м ножество целых чисел Z . множество рациональных чисел а. I – множество ирраци ональных чисел. R – множество действительных чисел. K – множество комплексных чисел. Множество А называется подмножеством В , если всякий элемент А является элементом В. А В – А под множество В (нестрогое включение ) Множес тва А и В равны , если их элементы совпадают. A = B Если А В и А В то А В (строгое включение ). Множества бывают конечные и бесконечные. |М | - мощность множества (число ег о элементов ). Конечное множество имеет конечное количес тво элементов. Пустое множество не содержит элементов : M = . Пример : пустое множество : 1) множество действительных корней уравнения x 2 +1=0 пустое : M = . 2) множество , сумма углов которого 180 0 пустое : M = . Если дано множество Е и множество и мы рассматриваем все его подмножества, то множество Е называется униварсельны м. Пример : Если за Е взять множество книг то его подмножеств а : художественные книги , книги по математике , физики , физики … Если универсальное множество состоит из n элемен тов , то число подмножеств = 2 n . Если , состоящее из элементов E , не принадлежащих А , называется дополнен ным. Множество можно задать : 1) Списком элементов a , b , c , d , e ; 2) Интервалом 1< x <5; 3) Порождающей процеду р ой : x k = k sinx =0; Операции над множествами 1) Объединение множеств А и В (с оюз или ). Множество , состоящие из элементов , которые принадлежат хотя бы одному из множеств А или В называется объединенным. А В Отношение множеств наглядно иллюстри руется с помощью диаграмм Венна. Диаграмма Венна – это замкнутая линия , внутри которой расположены элементы множества. Объединение двух множеств Объ единение системы множеств можно записать - объединение систе мы n множ еств. Пример : объединение множе ств , когда они заданы списком. A = a , b , d B = b , d , e , h AUB = a , b , c , d , e , h 2) Пересечением множеств А и В называ ется множество , состоящие из элементов принад лежащих одновременно множествам А и В. A B Пересечение пря мой и плоскос ти 1) если прямые || пл ., то множество пересечений – единственная точка ; 2) если прямые II пл ., то M ; 3) если прямые совпадают , то множество пересечений = множество прямой. Пересече ние с истемы множеств : 4) Разностью 2-х множеств А и В называется множество , состоящее и з всех элементов А , не входящих в В. С = А \ В A \ B А \ В A = a , b , d ; B = b , c , d , h C = A \ B = a . В отличии от предыдущих операций разн ость : 1) строго двухместна ; 2) не коммутативна , т.е . A \ B B \ A . 4) дополнение E – ун иверсальное множество. -- дополнение Операции объединения , пересечения и д ополнения называются Булевы ми. Основные закон ы операций над множествами. Некоторые свойства , похожи на алгебраические операции , однако многие свойства операций над множествами все же отличают ся. Основные свойст ва 1) AUB = BUA ; A B = B A – переместител ьный закон объединения и пересечения. 2) ( А UB ) UC = AU ( BUC ); ( A B ) C = A ( B C ) – сочетательный закон . 3) А U =A, A = , A \ =A, A \ A= 1,2,3 – есть аналог в алгебре. 3.а ) \ A = - нет анал ога. 4) ; E \ A = ; A \ E= ; AUA=A; A A=A; AUE=E; A E=A; 5.а ) свойства 1-4 очевидны и не нуж даются в доказательствах. 5) A ( BUC )=( A B )( A C ) – есть аналогичный распределительный закон от носительно U . Прямые произвед ения и функции Прямым декартовым “х” множеством А и В называется множество всех пар ( a ; b ), таких , что а А , b B . С = A хВ , если А =В то С =А 2 . Прямыми “х” n множеств A 1 x ,…, xA n называется мн ожество векторов ( a 1 ,… a n ) таких , что a 1 A 1 ,… , A n A n . Через теорию множеств введем понятие функции. Подмножество F M x x M y называется функцией , если для каждого элемента х M x найдется y М у не более одного. ( x ; y ) F , y = F ( x ). Соответствие между аргументом и функцией можно изобразить с помощью диаграммы Вен на : Определение : Межд у множествами M X и M Y установлено взаимноодназночное соответст вие , если каждому х M X соответствует 1 элемент y M Y и обратное справедливо. Пример : 1) (х,у ) в круге x =2 y =2 y =2 x =2..4 не взаимноодноз начное соответств ие. 2) x = sinx R R Пусть даны две функции f : A B и g : B C , то фу нкция y : A C называ ется к омпозицией функций f и g . Y = f o g o – композиция. Способы задания функций : 1) таблицы , определены для конечных множеств ; 2) формула ; 3) графики ; Способы 1-3 частные случаи выч . процедуры. Пример процедуры , не относящейся к 3 сп особам задания фу нкций n ! Взаимнооднозначное соответствие и мощности множеств. Определение : Множ ества равномощны | A |=| B | если между ними взаимнооднозначное соо тветствие. Теорема : Если для конечного множества А мощность равна | A | то к оличество всех подмножеств 2 | A | =2 n . Множ ества равномощные N называются сче тными , т.е . в них можно выполнить нумерацию элементов . N – множество натуральных чисел . Множество N 2 – счетно. Доказательство Разобьем N 2 на классы К 1-ому классу отнесем N 1 (1; 1) Ко 2-му классу N 2 (1;2), (2;1) К i -му классу N i ( a ; b )| ( a + b = i +1 Каждый класс будет содержать i пар . Упорядоченный классы по возрастанию индек са i , а пары внутри класса упорядоченные по нап равлению первого элемента а. Занумеруем последовательность классов , что и доказывает счетность множества N 2 . Аналогично доказывается счетность множеств N 3 ,…, N k . Теорема Кантора : Множество всех действительных чисел на отрезке [0;1] не является счетным. Доказательство Допустим это множество счетно изобразим его числа десятичными дробями. 1- я 0, a 11 , a 12 …. 2-я 0, а 21 , a 22 …. …………………. Возьмем произвольное число 0, b 1 , b 2 , b 3 b 1 a 11 , b 2 a 22 , … Эта дробь не может выйти в послед овательность т.к . отличается от всех чисел , значит нельзя пронумеровать числа на отрез ке [0;1]. Множество нечетно и называется континуаль ным , а его мощность континуум. Метод , используемый при доказат ельств е , называется диагональным методом Кантора. Отношение Пусть дано R M n – n ме стное отношение на множество М. Будем изучать двухместные или бинарные отношения . Если а и b находятся в отношении R , то з аписывается а R b . П роведем отношение на множество N : А ) отношение выполняется для пар (7,9) (7,7_ Б ) (9,7) не выполняется. Пример отношения на множество R А ) отношение находится на одинаковом р асстоянии от начала координат выполняется для па р (3; 4) и (2; 21) Б ) (3; 4) и (1; 6) не выполняется. Для задания бинарных отношений можно использовать любые способы задания множеств. Для конечных множеств используют матричны й способ задания множеств. Матрица бинарног о отношения на мн ожество M = 1;2;3;4 , тогда матрица отношения С равна Отношение Е заданные единичной матрицей называется отношением равенств а. Отношением назовется обратным к отно шением R , если a j R ai тогда и только тогда , когда a j R ai обозначают R -1 . Свойства отноше ний 1. Если aRa ==> очн . рефлекси вное и матрица содержит на главной диагон али единицу если ни для какого а не … ==> отношение антирефлексивно е главная диагональ содержит нули Пр . отношнний рефлексивное < антирефлексивное 2. Если из aRb следует bRa , ==> отношение R симметричное . В матрице отношения элементы сумм C ij = C ji . Если из aRb и bRa следует a = b ==> отношение R – ант исимметричное. Пр . Если а b и b a ==> a = b 3. Если дано a , b , c из aRb и aRc следует aRC ==> отношение называемое транзитивным. 4. Отношение называется отн оше нием эквивалентности , если оно рефлекс ивно , симметрично и транзитивно. Пр . отношение равенства E 5. Отношение называется отношение м нестрогого порядка , если оно рефлексивно , антисимметрично и транзитивно . Отношение называется отношением строго го порядка , если оно антирефлексивно , антисимметрично и транзитивно. Пр . а ) отношение u для чисел отношение н естрогого б ) отношение < u > для чисел отношение строгого Эл ементы общей алгебры Операции на множествах Множество М вместе с заданной на нем совокупностью операций = 1 ,… , m , т.е . система А = М 1 ; 1 ,… , m называется алгеброй . - сигнатура. Если M 1 M и если зна чения ( M 1 ), т.е . замкнуто ==> A 1= М 1 ; 1 ,… , m подалгебра A . Пр . 1. Алгебра ( R ;+;*) – называется полем действительн ых чисел обе операции бинарные и поэтому тип этой алгебры (2;2) 2. B =(Б ; ; ) – булева алгебра . тип операций (2;2;1) Р . Свойства бинарных алгебраических операций запись a b . 1. ( a b ) c = a ( b c ) – ассоциативная операц ия Пр . +, x – сложение и умножения чисел ассо циативно 2. a b = b a – ко ммутативная операция Пр . +, x – коммутат. – ; : – некоммут. умножение мат A B B A – некоммутативно. 3. a ( b c ) = ( a b ) ( a c ) – дистрибутивность слева ( a b ) c ) = ( a с ) ( b c ) – дистрибутивность справа . Пр . ( ab ) e = a e b e – возведение в степень дистрибутивного отношения произведения справа но не a bc a b a c Гомоморфизм и изоморфизм Алгебры с р азными членами имеют различные строения . Алг ебры с одинаковыми членами имеют сход ство . Пусть даны две алгебры A =( K ; I ) и B=( M ; I ) – одинакового типа. Пусть отображение Г : K M при условии Г ( I )= I (Г ), (1) т.е . результат не зависит о т последовательности возможных операций : Или сначала вып . операции I b А и затем отображении Г , или сначала отображение Г , или сначала отображение Г и затем отображение I в В. Тогда условие (1) называется Гомоморфизмом а лгебры А в алгебру В. Когда существует взаимооднозначный гомоморфи зм его называют изоморфизмом . В этом случа е существует обратное отображе ние Г -1 . Мощности изоморфных алгебр равны. Пр . Алгебры ( Q N ; +) и ( Q 2; +) – отображение типа и условие (1) зап ишется как 2(а + b )=2а +2 b . Отношение изоморфизма является отношением эквивалентности на множестве алгебр , т.е вычисление рефлексивное , симметричнос ти и транзитивности . Изоморфизм важнейшее пон ятие в математике . Полученные соотношения в алгебре А автоматически … . на изоморфные алгебры.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Любовь — это когда ты трезвая и пьяная звонишь одному и тому же мужчине.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по математике "Дискретная математика", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru