Темы рефератов по дискретной математике

Обновлено: 02.07.2024

Настоящая курсовая работа моделирует логическую задачу, состоящую из следующих частей: Изучение конкретного раздела дискретной математики, Решение 5-ти задач по изученной теме с методическим описанием, Разработка и реализация в виде программы алгоритма по изученной теме. Разработка программного интерфейса.

  • №1
  • 185,28 КБ
  • дата добавления неизвестна
  • изменен 03.05.2010 18:55

Алгоритм Краскала. Поиск максимального остового дерева

  • №2
  • 236,09 КБ
  • дата добавления неизвестна
  • изменен 04.02.2011 01:16

Алфавитное кодирование

ВГУЭС, Владивосток, 2011, 14 стр. Кодирование. Алфавитное кодирование. Префикс и постфикс слова. Таблица кодов. Разделимые схемы. Префиксные схемы. Неравенство Макмиллана. Алгоритм Хаффмана.

  • №3
  • 82,03 КБ
  • добавлен 23.12.2012 13:34
  • изменен 27.12.2012 17:39

Анализ и синтез дискретных устройств

ДВГУПС г. Хабаровск препод.: А.И. Годяев. год выполнения 2012. 17 листов Предмет: Теория дискретных устройств 307 вариант Содержание Введение Задание №1 - представить ФАЛ в соответствии с вариантом, в ДСНФ и в КСНФ. Задание №2 - произвести синтез преобразователя кодовых комбинаций, имеющего три входа a, b, c и три выхода fi, fj, fk. Выбирать значения функций fi, fj, fk.

  • №4
  • 1011,94 КБ
  • добавлен 28.06.2012 14:46
  • изменен 01.07.2012 06:57

Арифметические системы счисления

  • №5
  • 173,94 КБ
  • дата добавления неизвестна
  • изменен 02.06.2008 18:21

Арифметические системы счисления

  • №6
  • 188,48 КБ
  • дата добавления неизвестна
  • изменен 02.06.2008 18:25

Биматричные игры

  • №7
  • 237,09 КБ
  • дата добавления неизвестна
  • изменен 16.08.2011 23:38

Будильник

Уфимский государственный авиационный технический университет. Ишимбай, 2006. 16с. Целью работы является синтез функциональной схемы электронных часов по описанию их дополнительных возможностей по отношению к возможности простого отображения времени (базовый вариант). План. Цель работы. Граф управляющего автомата. Общая структурная схема. Кодирование входных и выходных.

  • №8
  • 200,12 КБ
  • дата добавления неизвестна
  • изменен 02.05.2008 14:11

Будильник

Уфимский государственный авиационный технический университет, 2010 г. Цель работы. Граф управляющего автомата. Общая структурная схема. Кодирование входных и выходных воздействий. Минимальные функции блоков F и FL. Остановка часов. Будильник. Общая функциональная схема. Функциональная схема блоков F и FL.

  • №9
  • 199,54 КБ
  • дата добавления неизвестна
  • изменен 20.03.2011 23:11

Булева алгебра, СКНФ, СДНФ, Подстановки, Навешивание кванторов, Вариант №10

ТулГУ, "Вычислительные машины, комплексы, системы и сети", 3 курс, 5 семестр. Расчётно-графическая работа на темы: Булева алгебра, СКНФ, СДНФ, Подстановки, Навешивание кванторов. 9 страниц.

  • №10
  • 921,68 КБ
  • дата добавления неизвестна
  • изменен 06.01.2010 21:14

Выделение минимального остовного дерева

Уфимский государственный авиационный технический университет, год не указан, 17 с. с блок-схемой и листингом программы. Целью данной работы является изучение и создание алгоритма решения задачи о составлении минимального остовного дерева, а так же разработка программы, реализующей этот алгоритм. Оглавление: Цель работы. Введение. Теоретическая часть. Алгоритм выделения.

  • №11
  • 88,51 КБ
  • дата добавления неизвестна
  • изменен 02.07.2008 13:15

Гамильтоновы графы, нахождение минимального пути в задаче коммивояжера

Гамильтоновы циклы. Основные понятия и определения. Условия существования гамильтонова цикла. Методы построения гамильтоновых циклов в графе. Алгебраический метод построения гамильтоновых циклов. Метод перебора Робертса и Флореса. Задача коммивояжера. Рассмотренны различные способы решения задачи коммивояжера, так же в архиве прилагается 2 программы на паскале и делфи.

  • №12
  • 360,61 КБ
  • дата добавления неизвестна
  • изменен 20.04.2010 00:48

Гамильтоновы циклы

  • №13
  • 313,20 КБ
  • дата добавления неизвестна
  • изменен 22.04.2008 22:04

Графы, Кодирование и декодирование Прюфера, Бинарное дерево поиска

  • №14
  • 276,59 КБ
  • добавлен 15.09.2011 01:49
  • изменен 18.09.2011 01:28

Детерминированные и ограниченно детерминированные функции. Вариант 4

  • №15
  • 2,80 МБ
  • дата добавления неизвестна
  • изменен 27.01.2010 22:33

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

Сложение в шестнадцатеричной, двоичной, восьмеричной и десятичной системах счисления. Минимизация логических функций методами тождественных преобразований и S-кубов. Минимизация логических функций методом карт Карно. Построение логических схем. Построение графа конечного автомата по общей таблице выходов и переходов. Моделирование работы конечного автома-та. 15 страниц ТулГУ.

  • №16
  • 237,09 КБ
  • дата добавления неизвестна
  • изменен 27.01.2011 22:08

Додавання матриць

УДУФМТ, Киев, Пркподаватель Спересенко В.В. 2010г., 20 стр. укр. яз. Основи програмування та алгоритмычні мови. Додавання матриць. Теоретичні відомості. історія виникнення. алфавіт мови, службові слова. структура програми мови Turbo Pascal. математичні операції. стандартні підпрограми і сталі. Масиви у мові Turbo Pascal. одновимірні масиви. Багатовимірні масиви.

  • №17
  • 47,14 КБ
  • добавлен 10.12.2011 02:03
  • изменен 15.12.2011 21:27

Задача коммивояжера

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

  • №18
  • 92,15 КБ
  • дата добавления неизвестна
  • изменен 02.01.2010 15:42

Задача о коммивояжере

Курсовая включает в себя: Математические основы решение задачи коммивояжера, Формулировка и некоторые свойства решений задачи коммивояжера основные понятия теории графов, Постановка задачи коммивояжера как задачи на графе, Разработка и описание алгоритма работы программы в среде Pascal.

  • №19
  • 83,34 КБ
  • дата добавления неизвестна
  • изменен 21.11.2009 21:51

Задача о максимальном потоке, алгоритм Форда-Фалкерсона

Уфимский государственный авиационный технический университет, 2010 г. Введение. Теория. Основные понятия. Постановка задачи. Реализация. Тестовый пример. Заключение. Список литературы.

  • №20
  • 426,55 КБ
  • дата добавления неизвестна
  • изменен 20.03.2011 22:59

Задача о назначениях

В данном курсовом проекте рассматривается задача о назначениях, т. е. нахождение совершенного паросочетания максимального или минимального. Задача осуществляется путем реализации венгерского алгоритма.

  • №21
  • 191,47 КБ
  • дата добавления неизвестна
  • изменен 01.05.2010 17:26

Задачи Мажордома

Введение.Рыцари короля Артура.Затруднения мажордома.Новое решение задачи мажордома .Рекуррентные таблицы.Третье решение проблемы мажордома.Разобранные задачи мажордома.Самостоятельное решение задач.Выводы по работе.Список литературы. Санкт-Петербургский Государственный Технологический Институт (СПбГТИ (ТУ)), код специальности: 220701, 2 курс, 3 семестр, 24 стр.

  • №22
  • 510,53 КБ
  • дата добавления неизвестна
  • изменен 16.08.2011 23:38

Информативное дерево, полнота систем. Вариант 25

УГАТУ. Дискретная математикя. - 7 страниц. Информативное дерево. Полнота систем. диаграмма Мура. уравнения автоматной функции. Карты карно. каноническое уравнение.

  • №23
  • 6,83 МБ
  • дата добавления неизвестна
  • изменен 08.11.2009 19:52

К вопросу о строении графа на классе сопряженных 3-элементов группы SL3(3)

Пермский национальный исследовательский политехнический университет, 2015, 41 с. Дисциплина - Дискретная математика и теория автоматов. Предварительные сведения Доказательство теоремы Из теории групп и полей Из теории графов Понятия, применяемые в формулировки теоремы Классы K и C элементов соответственно порядка 3 и 4 Доказательство теоремы Свойства подгрупп Примеры групп Из.

  • №24
  • 701,38 КБ
  • добавлен 13.12.2015 23:33
  • изменен 29.11.2018 07:37

Логика предикатов с одним переменным

Курсовая работа - Логика предикатов с одним переменным. Выполнил студент II-го курса математического факультета Бережной Андрей Витальевич. Поморский Государственный Университет им. М. В. Ломоносова. Коряжма, 1997. Введение Основные понятия Логика предикатов с одним переменным Практика по решению проблемы разрешимости формул, содержащих предикаты от одного переменного Литература

  • №25
  • 56,97 КБ
  • дата добавления неизвестна
  • изменен 20.12.2018 00:42

Математические основы дискретно - логических систем (Вариант-17)

Курсовая по предмету "Математические основы дискретно-логических систем", преп. Мугафаров М. Ф. Содержание: Введение. Постановка задачи. Построение таблицы поведения автомата. Построение графа. Кодирование данных. Нахождение системы булевых функций для возбуждения JK-триггеров, реализующих функции ψ. Определение булевой функции для реализации функции φ. Составление.

Множества и основные операции над множествами. Упорядоченные пары и прямое произведение множеств. Основные законы и формулы комбинаторики. Логика высказываний: основные понятия, формулы, логические операции, составные высказывания и законы логики.

Рубрика Математика
Вид реферат
Язык русский
Дата добавления 07.11.2015
Размер файла 86,2 K

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Департамент образования и науки Кемеровской области

Государственное бюджетное образовательное учреждение

среднего профессионального образования

студент 3 курса, гр. КСК-13

Литвинович Михаил Геннадьевич

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

1.1.1 Основные определения

1.1.2 Сравнение множеств

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

1.1.4 Свойства операций над множествами

1.2.1 Упорядоченные пары

1.2.2 Прямое произведение множеств

2.1 Основные законы комбинаторики

2.1.1 Правило суммы

2.1.2 Правило произведения

2.2 Формулы комбинаторики

3. Логика высказываний

3.2 Основные понятия

3.3 Логические операции

3.4 Составные высказывания

3.5 Формулы логики высказываний

3.6 Законы логики (свойства логических операций)

Список использованной литературы

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

Дискретная (конечная) математика - это раздел математики, не связанный с понятиями предела, непрерывности и бесконечности.

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

В отличие от Д. м., классическая математика в основном занимается изучением свойств объектов непрерывного характера. Использование классической математики или Д. м. как аппаратов исследования связано с тем, какие задачи ставит перед собой исследователь и, в связи с этим, какую модель изучаемого явления он рассматривает, дискретную или непрерывную.

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

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

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

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

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

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

Так, прикладные вопросы, требующие большой числовой обработки, стимулировали появление сильных численных методов решения задач, оформившихся затем в вычислительную математику, а анализ понятий "вычислимость" и "алгоритм" привёл к созданию важного раздела математической логики - теории алгоритмов. Растущий поток информации и связанные с ним задачи хранения, обработки и передачи информации привели к возникновению теории кодирования; экономические задачи, задачи электротехники, равно как и внутренние задачи математики, потребовали разработки теории графов; задачи конструирования и описания работы сложных управляющих систем составили теорию функциональных систем и т. д. В то же время математическая кибернетика широко использует результаты Д. м. при решении своих задач.

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

1.1.1 Основные определения

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

Понятие множество принадлежит к числу фундаментальных неопределяемых понятий математики.

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

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

q должно существовать правило, позволяющее определить, принадлежит ли некоторый элемент множеству;

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

Множества обычно обозначают большими латинскими буквами (например, A, S, D), а их элементы - строчными (например, a, s, d).

Если элемент х принадлежит множеству А, то это обозначается: хА; в противном случае говорят, что элемент не принадлежит множеству, это обозначается: хА.

1. Множество N - множество натуральных чисел. 1N. -1N.

2. Множество L - множество букв русского алфавита. фL. vL.

Множество не содержащие элементов называется пустым. Это множество обозначается .

Множества можно задавать следующими способами.

1. Перечисление элементов:

2. Задание характеристического свойства:

Степенью множества А называется его прямое произведение самого на себя.

Доказательство: первый компонент упорядоченной пары можно выбрать |А| способами, второй - |B| способами. Таким образом, всего имеется |A| |B| различных упорядоченных пар.

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

Рассмотрим элементарный жизненный пример.

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

2.1 Основные законы комбинаторики

2.1.1 Правило суммы

Задача: на блюде лежат 5 яблок и 2 груши. Сколькими способами можно выбрать один плод?

Решение: плод можно выбрать семью способами (5+2=7).

Если некоторый элемент a может быть выбран из множества элементов m способами, а другой элемент b может быть выбран n способами, причем любой выбор элемента b отличен от любого выбора элемента a, то выбрать либо a, либо b можно m + n способами.

На языке теории множеств это правило формулируется следующим образом:

Теорема 1: если пересечение конечных множеств пусто, то число элементов в их объединении равно сумме чисел элементов множеств А и В.

Разберем случай, когда множества могут иметь непустые пересечения.

Теорема 2: для любых конечных множеств верно равенство:

Задача: среди студентов первого курса 30 человек имеют дома компьютер, 35 - учебник по информатике; оказалось, что 10 студентов имеют и компьютер, и учебник по информатике. Сколько студентов на первом курсе?

Решение: пусть множество А составляют студенты, имеющие компьютер, множество В - студенты, имеющие учебник по информатике; по условию задачи:

|A| = 30 |B| = 35 | АВ | = 10 | АВ | =?

| АВ | = |A| + |B| - | АВ | = 30 + 35 - 10 = 55.

2.1.2 Правило произведения

Вторым основным правилом комбинаторики является правило произведения.

Решение: количество клеток равно

Если элемент a можно выбрать из множества элементов m способами и после каждого такого выбора элемент b можно выбрать n способами, то два элемента (упорядоченную пару) a и b можно выбрать m*n способами.

На языке множеств это правило выражается в виде следующей теоремы.

Теорема3: если множества А и В конечны, то

Следствие: если множества А1, А2, …, Аn - конечны, то

Задача: сколько номеров, состоящих из двух букв, за которыми идут три цифры можно составить, если использовать 29 букв и 10 цифр.

Решение: обозначим множество букв А, множество цифр - В; каждый номер требуемого вида является набором длины n из декартова произведения ААВВВ; по условию |А| = 29, |В| = 10, тогда по следствию из теоремы3 имеем:

| ААВВВ | = 29*29*10*10*10 = 841 000.

2.2 Формулы комбинаторики

1) Перестановки без повторений.

Перестановки - это комбинации, состоящие из одних и тех же элементов и отличающиеся только порядком расположения этих элементов. Возьмем n различных элементов a1, a2, a3, … an; будем переставлять эти элементы всевозможными способами, оставляя без изменения число элементов и меняя только порядок их расположения. Обозначим общее число полученных таким образом перестановок P(n). P - первая буква французского слова permutation - перестановка.

Составив таблицу перестановок для n элементов и применив (n - 1) раз правило произведения, получим число всех возможных перестановок:

P(n) = n * (n -1) * (n - 2) * … * 3 * 2 * 1 = n!

Такие перестановки называются перестановками без повторений (один и тот же элемент не может повториться в комбинации, все элементы различны).

Задача: шесть человек могут в разном порядке сесть за круглый стол, сколько существует способов разместить эти шесть человек за столом?

Решение: т.к. все люди различны и их комбинации различаются только порядком следования, то мы имеем перестановки без повторений. Определим их число:

Р(6) = 6! = 1 * 2 * 3 * 4 * 5 * 6 = 720.

2) Перестановки с повторениями

Рассматривая различные перестановки, мы предполагали, что все n элементов различны. Если же некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам.

Если среди n элементов есть n1 элементов одного вида, n2 элементов другого вида и т.д., nk элементов к-го вида, то имеем перестановки с повторениями, их число:

Решение: имеем перестановки с повторениями.

1) Размещения без повторений.

Размещениями называют комбинации, составленные из n данных элементов по k элементов (k 0), которые отличаются либо составом элементов, либо порядком расположения элементов. Обозначаются размещения An k . А - первая буква французского слова arrangement, что в переводе означает "размещение", "приведение в порядок". Число всех возможных размещений находится по формуле:

Задача: расписание одного дня состоит из двух пар. Определить число вариантов расписания при выборе из пяти дисциплин, если не может быть одинаковых пар.

Решение: имеем размещения без повторений из пяти элементов по два, из число:

2) Размещения с повторениями.

Пусть существуют n различных элементов. Выберем из них m штук, действуя по следующему принципу: возьмем любой элемент, но не будем устанавливать его в какой-либо ряд, а просто запишем под номером 1 его название, сам же элемент вернем к остальным элементам. Затем опять из всех n элементов выберем один, запишем его название под номером 2 и снова вернем элемент обратно. Будем выполнять эти операции, пока не получим m названий. Размещения с повторениями вычисляются по формуле:

Задача: сколько четырехзначных номеров можно составить из 10 цифр?

Решение: имеем размещения с повторениями из 10 элементов по 4, их число:

множество комбинаторика логика

1) Сочетания без повторений.

Сочетаниями называют комбинации, составленные из n различных элементов по k (k = k C - первая буква французского слова combinasion - сочетание.

Составим из n элементов всевозможные сочетания по k элементов в каждом. Их будет Cn k . Внутри каждого сочетания, состоящего из k элементов, образуем всевозможные комбинации, учитывающие порядок следования в них элементов. Таких комбинаций будет Pk, т.к. мы в нашем сочетании образовываем перестановки. Всего различных комбинаций из n элементов по k в каждой, отличающихся друг от друга либо составом (элементами), либо порядком их следования, будет Cn k * Pk . Но такие комбинации называются размещениями. Таким образом,

Задача: в шахматном турнире участвует 7 человек; сколько партий будет сыграно, если между любыми двумя участниками должна быть сыграна партия?

Решение: имеем сочетания без повторений из 7 элементов по 2; их число:

2) Сочетания с повторениями.

Если в сочетаниях некоторые элементы (или все) могут оказаться одинаковыми, то такие сочетания называются сочетаниями с повторениями. Их число определяется по формуле:

Задача: сколько наборов из 7 пирожных можно составить, если в продаже имеется 4 сорта пирожных?

Решение: имеем сочетания с повторениями из четырех по 7 по, их число:

3. Логика высказываний

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

Алгебра логики возникла в середине 19 в. в трудах Дж. Буля и развивалась затем в работах Ч. Пирса, П. С. Порецкого, Б. Рассела, Д. Гильберта и др. Создание алгебры логики представляло собой попытку решать традиционные логические задачи алгебраическими методами.

С появлением теории множеств (70-е гг. 19 в.), поглотившей часть первоначального предмета алгебры логики, и дальнейшим развитием математической логики (последняя четверть 19 в. - 1-я половина 20 в.) предмет алгебры логики значительно изменился. Основным предметом алгебры логики стали высказывания.

3.2 Основные понятия

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

Определение: повествовательное предложение, о котором можно однозначно сказать, истинно оно или ложно, называется высказыванием.

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

Определения математических понятий не являются высказываниями, т.к. это принятые соглашения.

Будем обозначать высказывания большими латинскими буквами: A, B, C,….

Элементарные, нерасчленяемые высказывания будем называть атомами.

3.3 Логические операции

Употребляемые в обычной речи логические связки "и", "или", "если. то. ", "эквивалентно", частица "не" и т. д. позволяют из уже заданных высказываний строить новые, более "сложные" высказывания.

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

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

Рассмотрим определения логических операций, соответствующих логическим связкам.

Каждому высказывания можно сопоставить его истинностное значение, обозначаемое соответственно через И (если высказывание истинно), Л (если высказывание ложно).

Истинностное значение сложных высказываний зависит от истинностных значений высказываний, составлявших слоеное высказывание.

Эта зависимость устанавливается в данных ниже определениях я стращается в таблицах истинности.

Пусть A, В - произвольные высказывания, относительно которых не предполагается, что известно их истинностные значения.

Связке "НЕ" соответствует логическая операция отрицания, обозначение операции - знак щ или .

Определение. Отрицанием высказывания A называется высказывание (щA), которое истинно, если A - ложно, и ложно, если A - истинно.

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

Общество 21в. – общество информационное. Центр тяжести в решении задач переместился от задач вычислительной математики к задачам на дискретных структурах. Математика нужна не как метод расчета, а как метод мышлению средство формирования и организации…

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

В дисциплине мало методов, но много определений и терминов. В основе дискретной математике 4 раздела:

Язык дискретной математики;

Логические функции и автоматы;

Графы и дискретные экстремальные задачи.

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

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

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

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

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

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

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

Множество обозначают: M,N …..

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

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

Примеры числовых множеств:

1,2,3,… множество натуральных чисел N;

…,-2,-1,0,1,2,… - множество целых чисел Z.

множество рациональных чисел а.

I – множество иррациональных чисел.

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

K – множество комплексных чисел.

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

А  В – А подмножество В (нестрогое включение)

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

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

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

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

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

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

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

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

2) множество , сумма углов которого  180 0 пустое: M = .

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

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

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

Объединение системы множеств можно записать

Объединение трех множеств:

2) Пересечением множеств А и В называется множество, состоящие из элементов принадлежащих одновременно множествам А и В.

Пересечение прямой и плоскости

если прямые || пл., то множество пересечений – единственная точка;

если прямые II пл., то M ;

если прямые совпадают, то множество пересечений = множество прямой.

Пересечение системы множеств:

Разностью 2-х множеств А и В называется множество, состоящее из всех элементов А, не входящих в В.

В отличии от предыдущих операций разность: 1) строго двухместна;

2) не коммутативна, т.е. A\B  B\A.

а) взаимнооднозначное соответствеие (отображение)

а) не взаимнооднозначное соответствеие (отображение)

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

Пример: 1) (х,у) в круге

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

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

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

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

таблицы, определены для конечных множеств;

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

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

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

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

Теорема: Если для конечного множества А мощность равна |A| то количество всех подмножеств 2 | A | =2 n .

Множества равномощные N называются счетными, т.е. в них можно выполнить нумерацию элементов. N – множество натуральных чисел.

Множество N 2 – счетно.

Разобьем N 2 на классы

К 1-ому классу отнесем N1 (1; 1)

1-ый элемент 1-го множества

Ко 2-му классу N2

Каждый класс будет содержать i пар.

Упорядоченный классы по возрастанию индекса i, а пары внутри класса упорядоченные по направлению первого элемента а.

Занумеруем последовательность классов, что и доказывает счетность множества N 2 .

Аналогично доказывается счетность множеств N 3 ,…,N k .

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

Допустим это множество счетно изобразим его числа десятичными дробями.

Эта дробь не может выйти в последовательность т.к. отличается от всех чисел, значит нельзя пронумеровать числа на отрезке [0;1].

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

Метод, используемый при доказательстве, называется диагональным методом Кантора.

Пусть дано RM n – n местное отношение на множество М.

Будем изучать двухместные или бинарные отношения. Если а и b находятся в отношении R, то записывается а R b.

Проведем отношение на множество N:

А) отношение  выполняется для пар (7,9) (7,7_

Б) (9,7) не выполняется.

Пример отношения на множество R

А) отношение находится на одинаковом расстоянии от начала координат выполняется для пар (3; 4) и (2; 21)

Б) (3; 4) и (1; 6) не выполняется.

Для задания бинарных отношений можно использовать любые способы задания множеств.

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

Матрица бинарного отношения на множество M=, тогда матрица отношения С равна

Отношение Е заданные единичной матрицей называется отношением равенства.

Отношением назовется обратным к отношением R, если ajRai тогда и только тогда, когда ajRai обозначают R -1 .

Если aRa ==> очн. рефлексивное и матрица содержит на главной диагонали единицу

если ни для какого а не … ==> отношение антирефлексивное

главная диагональ содержит нули

отношение R симметричное. В матрице отношения элементы

сумм Cij=Cji. Если из aRb и bRa следует a=b ==> отношение R – антисимметричное.

Пр. Если а  b и b  a ==> a=b

Если дано  a,b,c из aRb и aRc следует aRC ==> отношение называемое транзитивным.

Отношение называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Пр. отношение равенства E

5. Отношение называется отношением нестрогого порядка, если оно рефлексивно,

антисимметрично и транзитивно. Отношение называется отношением строгого порядка,

если оно антирефлексивно, антисимметрично и транзитивно.

Пр. а) отношение  u  для чисел отношение нестрогого

б) отношение для чисел отношение строгого

Элементы общей алгебры

Операции на множествах

Множество М вместе с заданной на нем совокупностью операций  = 1,…, m>, т.е. система А = 1;1,…, m> называется алгеброй.  - сигнатура.

Пр. 1. Алгебра (R;+;*) – называется полем действительных чисел обе операции бинарные и

поэтому тип этой алгебры (2;2)

B=(Б;;) – булева алгебра. тип операций (2;2;1)

Р. Свойства бинарных алгебраических операций

1. (ab)c=a(bc) – ассоциативная операция

Пр. +,x – сложение и умножения чисел ассоциативно

2. ab = ba – коммутативная операция

умножение мат AB  BA – некоммутативно.

3. a(bc) = (ab) (ac) –дистрибутивность слева

(ab)c) = (aс) (bc) –дистрибутивность справа.

Пр. (ab) e =a e b e – возведение в степень дистрибутивного отношения произведения справа

но не a bc  a b a c

Гомоморфизм и изоморфизм

Алгебры с разными членами имеют различные строения. Алгебры с одинаковыми членами имеют сходство. Пусть даны две алгебры A=(K; I) и B=(M; I) – одинакового типа.

Пусть отображение Г:KM при условии Г(I)= I(Г), (1) т.е. результат не зависит от последовательности возможных операций: Или сначала вып. операции I b А и затем отображении Г, или сначала отображение Г, или сначала отображение Г и затем отображение I в В.

Тогда условие (1) называется Гомоморфизмом алгебры А в алгебру В.

Когда существует взаимооднозначный гомоморфизм его называют изоморфизмом. В этом случае существует обратное отображение Г -1 .

Мощности изоморфных алгебр равны.

Пр. Алгебры (QN; +) и (Q2; +) – отображение типа и условие (1) запишется как 2(а+b)=2а+2b.

Отношение изоморфизма является отношением эквивалентности на множестве алгебр, т.е вычисление рефлексивное, симметричности и транзитивности. Изоморфизм важнейшее понятие в математике. Полученные соотношения в алгебре А автоматически …. на изоморфные алгебры.


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

Цены ниже, чем в агентствах и у конкурентов

Вы работаете с экспертами напрямую. Поэтому стоимость работ приятно вас удивит

Бесплатные доработки и консультации

Исполнитель внесет нужные правки в работу по вашему требованию без доплат. Корректировки в максимально короткие сроки

Если работа вас не устроит – мы вернем 100% суммы заказа

Техподдержка 7 дней в неделю

Наши менеджеры всегда на связи и оперативно решат любую проблему

Строгий отбор экспертов

computer

Требуются доработки?
Они включены в стоимость работы


Работы выполняют эксперты в своём деле. Они ценят свою репутацию, поэтому результат выполненной работы гарантирован

avatar

avatar

avatar

avatar

Буквально на следующий день Светлана предоставила выполненную работу, получила "отлично". Огромное спасибо!

Последние размещённые задания


Ежедневно эксперты готовы работать над 1000 заданиями. Контролируйте процесс написания работы в режиме онлайн

Анализ параграфов с 77 по 85 включительно

Другое, Теория и методика обучения русскому языку

Срок сдачи к 28 февр.

Срок сдачи к 28 февр.

Другое, Психология компетентного родительства

Срок сдачи к 5 мар.

Срок сдачи к 28 февр.

Диплом, Управление государственным и муниципальным сектором,государственное и муниципальное управление

Срок сдачи к 25 мар.

решить все 4 задачи, мой вариант 11.(есть всего 10 вариантов в задаче

Решение задач, Сопромат

Срок сдачи к 28 февр.

Решение задач, маркетинг территорий

Срок сдачи к 2 мар.

Решить 2 задачи

Контрольная, теоретические основы электротехники

Срок сдачи к 28 февр.

«парабансковская система. деятельность мфо

Другое, Банковское дело

Срок сдачи к 1 мар.

Решение одной задачи

Решение задач, БЖД

Срок сдачи к 12 мар.

Промоделировать работу библиотекаря. Интервалы прихода читателей

Решение задач, Моделирование систем

Срок сдачи к 27 февр.

Нужен срочный адекватный перевод несложного текста

Перевод с ин. языка, Перевести текст с русского языка на английский

Срок сдачи к 26 февр.

Воспитание и обучение детей с ДЦП

Курсовая, Дефектология (Специальная педагогика)

Срок сдачи к 18 мар.

Мгу, убийство в состоянии аффекта (107 ук рф), 20-25 страниц

Курсовая, уголовное право

Срок сдачи к 27 февр.

Курсовая, история россии

Срок сдачи к 1 мая

курсовая работа по социальной психологии

Срок сдачи к 14 мар.

Работа с фгос уо для ноо, аооп до (уо, зпр, тмнр, рас)

Поиск информации, Педагогика лиц с интеллектуальной недостаточностью

Срок сдачи к 5 мар.

на тему "Религиозное верование саков"

Срок сдачи к 27 февр.

planes
planes

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

Читайте также: