Рейтинг@Mail.ru
Rambler's Top100




Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ

реферат на тему: Конспект по дискретной математики

скачать реферат

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

Введение

Общество 21в. общество информационное. Центр тяжести в решении задач переместился от задач вычислительной математики к задачам на дискретных структурах. Математика нужна не как метод расчета, а как метод мышлению средство формирования и организации… Такое владение математикой богатой культуры, понимание важности точных формулировок. В дисциплине мало методов, но много определений и терминов. В основе дискретной математике 4 раздела: 1. Язык дискретной математики; 2. Логические функции и автоматы; 3. Теория алгоритмов; 4. Графы и дискретные экстремальные задачи.

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

Одной из важнейших проблем в дискретной математики является проблема сложности вычислений.

Теория сложности вычислений помогает оценить расход времени и памяти при решении задач на ЭВМ. Теория сложности позволяет выделить объективно сложные задачи (задачи перебора) и неразрешимые задачи.

Мы будем заниматься решением задач реальной размерности с учетом ограниченности временных и емкостных ресурсов ЭВМ.

Множества и операции над ними

Одно из основных понятий математики множество.

Определение: Множеством называется совокупность, набор предметов, объектов или элементов.

Множество обозначают: M,N ….. m1, m2, mn элементы множества.

Символика A M принадлежность элемента к множеству; А М непринадлежность элемента к множеству.

Примеры числовых множеств: 1,2,3,… множество натуральных чисел N; …,-2,-1,0,1,2,… - множество целых чисел Z. множество рациональных чисел а. I множество иррациональных чисел. R множество действительных чисел. K множество комплексных чисел.

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

Множества А и В равны, если их элементы совпадают.

A = B

Если А В и А В то А В (строгое включение).

Множества бывают конечные и бесконечные.

|М| - мощность множества (число его элементов).

Конечное множество имеет конечное количество элементов.

Пустое множество не содержит элементов: M = .

Пример: пустое множество:

1) множество действительных корней уравнения x2+1=0 пустое: M = . 2) множество , сумма углов которого 1800 пустое: M = .

Если дано множество Е и множество и мы рассматриваем все его подмножества, то множество Е называется униварсельным.

Пример: Если за Е взять множество книг то его подмножества: художественные книги, книги по математике, физики, физики …

Если универсальное множество состоит из n элементов, то число подмножеств = 2n.

Если , состоящее из элементов E, не принадлежащих А, называется дополненным.

Множество можно задать: 1) Списком элементов {a,b,c,d,e}; 2) Интервалом 1
Операции над множествами

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; AB=BA переместительный закон объединения и пересечения. 2) (АUB)UC = AU(BUC); (AB)C=A(BC) сочетательный закон. 3) АU=A, A=, A \ =A, A \ A= 1,2,3 есть аналог в алгебре. 3.а) \ A = - нет аналога. 4) ; E \ A =; A \ E=; AUA=A; AA=A; AUE=E; AE=A; 5.а) свойства 1-4 очевидны и не нуждаются в доказательствах. 5) A(BUC)=(AB)(AC) есть аналогичный распределительный закон относительно U.

Прямые произведения и функции

Прямым декартовым “х” множеством А и В называется множество всех пар (a;b), таких, что аА, bB.

С=AхВ, если А=В то С=А2.

Прямыми «х» n множеств A1x,…,xAn называется множество векторов (a1,…an) таких, что a1A1,…, AnAn.

Через теорию множеств введем понятие функции.

Подмножество FMx x My называется функцией, если для каждого элемента хMx найдется yМу не более одного. (x;y)F, y=F(x).

Соответствие между аргументом и функцией можно изобразить с помощью диаграммы Венна:

Определение: Между множествами MX и MY установлено взаимноодназночное соответствие, если каждому хMX соответствует 1 элемент yMY и обратное справедливо. Пример: 1) (х,у) в круге

2) x = sinx R R

Пусть даны две функции f: AB и g: BC, то функция y:AC называется композицией функций f и g.

Y=f o g o композиция.

Способы задания функций:

1) таблицы, определены для конечных множеств; 2) формула; 3) графики;

Способы 1-3 частные случаи выч. процедуры.

Пример процедуры, не относящейся к 3 способам задания функций n!

Взаимнооднозначное соответствие и мощности множеств.

Определение: Множества равномощны |A|=|B| если между ними взаимнооднозначное соответствие.

Теорема: Если для конечного множества А мощность равна |A| то количество всех подмножеств 2|A|=2n. Множества равномощные N называются счетными, т.е. в них можно выполнить нумерацию элементов. N множество натуральных чисел.

Множество N2 счетно. Доказательство

Разобьем N2 на классы К 1-ому классу отнесем N1 (1; 1)

Ко 2-му классу N2 {(1;2), (2;1)} К i-му классу Ni {(a;b)| (a+b=i+1} Каждый класс будет содержать i пар.

скачать реферат
1 2

Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ

Внимание! Студенческий отдых и мегатусовка после сессии!


Обратная связь.

IsraLux отзывы Израиль отзывы