Дискретная математика - Математика курс лекций

Главная

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

Конспект лекций по дискретной математике


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Федеральное агентство по образованию РФ
6. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ И ИХ ПРИМЕНЕНИЕ В ТЕОРИИ МНОЖЕСТВ
Основная задача комбинаторики - пересчет и перечисление элементов в конечных множествах.
1. Если нас интересует, сколько элементов принадлежащих данному конечному множеству обладают некоторым свойством, то это задача пересчета .
2. Если необходимо выделить все элементы множества, об-ладающие заданными свойствами, то это задача перечисления .
Рассмотрим следующие элементы комбинаторики, позволяющие решать вышеупомянутые задачи. К таким объектам относятся:
- перестановки (с повторением и без них);
- размещения (с повторением и без них);
- сочетания (с повторением и без них);
Перестановками называют комбинации, состоящие из одних и тех же элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок обозначается (без повторений) .
Перестановки с повторениями вычисляются по формуле:
, где - число повторений элементов каждого вида.
Сочетанием называются такие комбинации элементов, которые отличаются между собой в каждой группе только самими элементами (но не порядком их расположения в группе).
Размещением называются такие комбинации элементов, которые отличаются между собой или самими элементами или порядком их расположения в группе.
7. ПРИНЦИПЫ МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ
При вычислении элементов множеств требуется приводить доказательство, по которому вычисляются последующие элементы по предыдущим. Один из алгоритмов этих доказательств - принцип математической индукции .
Этот принцип заключается в следующем:
Пусть при n =1 доказательство очевидно. Принимаем гипотезу, что оно очевидно при n = k , которое не равно 1 (). Тогда, если доказано, что требуемое равенство очевидно при k +1 , то равенство доказано при любом n .
Понятие отображения и функции выражают зависимостью одних переменных величин от других, при этом слово величина может иметь различную смысловую нагрузку. Это может быть элемент любого множества, число, вектор и т.д.
Отображение - множества x во множество y определяется тем, что каждому элементу ставится в соответствие
- графическое изображение отобра-же-ния, f - обозначение отображения. Закон, который выража-ет-ся или в виде формулы или в виде алгоритма, т.е. последова-тельность действий, которые надо предпринять, чтобы полу-чить зависимость элементов множества y от элементов x . Например: всякая нумерация счетного множества является его отображением на множество натуральных чисел N .
Так как отображение может быть истолковано как соот-ве-тствие, то для того, чтобы показать, что данный элемент x поставлен в соответствие элементу y , пишут и говорят, что y есть образ элемента x при данном отображении f .
Пусть x ` - подмножество множества x
Совокупность элементов множества x , образом которых является y , называется прообразом и обозначается
Рассмотрим частные случаи отображения одного множества в другое.
1. Если каждый элемент множества Y имеет прообраз, являя-ющийся элементом множества X ,то в этом случае отобра-жение f называется сюръективным .
2. Отображение f называется инъективным , если для каждо-го элемента существует не более одного прообраза, т.е. при любых , если .
Если отображение f сюръективно и инъективно, то оно на-зывается биеткивным или взаимооднозначным .
Рассмотрим на примере три функции, отображающие мно-жество F действительных чисел само на себя:
1) - инъективна, но не сюръективна т.к. , однако не каждый y имеет прообраз x т.к. y >0
2) - сюръективна, но не инъектина , т.к. y существует при любом x , однако для образа y существует несколько прообразов, т.к. существует несколько корней кубического уравнения
3) - биективна , т.к. x однозначно выражается через x и x однозначно выражается через y .
Два множества называются эквивалентными, если между ними можно установить биективное отображение .
Подмножество называется функцией .
Таким образом функцию можно представить в виде графика, причем множество А - область определения функции, а множество В - область значения функции.
Рассмотрим, например, взаимно однозначное отображе-ние множества R на R 1 , где R 1 есть множество всех положи-тельных чисел . Обратным ему будет отображение . Для таких отображений справедливо следующее тождество:
, то их композицией (произведением) называют , причем, если осуществляется композиция, то . В математике такое отображение называют сложной функцией, y - промежуточный аргумент.
Для композиции справедливо следующие отображения :
Квадратом множества А называется декартово произведение множества само на себя
Бинарным отношением Т в множестве А будем называть подмножество его квадрата
1. Отношение выполняется для пар (6,8) (6,6)
2. Отношение имеет общий делитель не равный 1 . Выполняется для пар (6,4) (4,2) (8,8) но не выполняется для пар (5,4) (3,8)
3. Любые элементы декартова произведения находятся в бинарном отношении, если , говорят, что связаны отношением Т .
4. Областью значений (изменением бинарного отношения) называется множество , подчиненное условию
Как известно из курса математики пару ( x , y ), где изображают на координатной плоскости точкой, тогда множество отобразится координатной плоскостью, а его подмножество, т.е. бинарное отношение отобразится соответствующими графиками этих отношений .
Бинарные отношения на плоскости можно отобразить с помощью графов. Элементы множества обозначаются вершинами графов. Если пара , то вершины а и в соединяются звеном.
Определим некоторые важные свойства бинарных отношений и рассмотрим бинарные отношения, которые обладают тремя из этих свойств и часто встречаются в математике. Такое бинарное отношение называется эквивалентностью .
1. 1.1 Пусть - бинарное отношение, - область его задания, тогда называется рефлексивным , если , граф таких отношений имеет вид петли при каждой вершине
1.2 называется антирефлексивным , если
2. 2.1 Отношение может быть симметричным , если
2.2 Антисимметричным, если (изображается ориентированным графом)
3. 3.1 Транзитивным. Отношение называется транзитивным, если (изображается транзитивным графом - все вершины пересекаются)
Если для бинарного отношения соблюдается три условия: рефлексивность, симметричность и транзитивность, то такое отношение называется эквивалентностью .
Понятие матрицы. Виды матриц. Свойства матриц. Линейные операции над матрицами. Единичные матрицы. Обратные матрицы
Матрицей называется прямоугольная таблица чисел размером , где m - число строк, а n - число столбцов.
Если m = n - матрица называется квадратной .
Все числа, входящие в матрицу называются ее элемен-тами. Если все элементы состоят их нулей, то это нулевая матрица , она играет роль нуля в матричном исчислении.
Рассмотрим некоторые линейные операции над матрицами:
Исходя из определения можно складывать и вычитать матрицы только одного размера .
2. Произведение матрицы на число называется матрица, где каждый элемент матрицы умножается на это число .
3. Матрица умножается на матрицу по правилу строка на столбец
такое правило не годится для всех матриц, а именно, количество строк во второй матрице должно равняться количеству столбцов в первой матрице.
Квадратные матрицы перемножаются только одного размера .
4. Единичной матрицей называется квадратная матрица любого размера, где по главной диагонали стоят единицы , а все остальные элементы равны нулю .
, играет роль единицы в матричном исчислении.
Если такую матрицу умножить на другую матрицу (при возможности умножения) даст исходную матрицу.
5. Обратной матрицей называется матрица, которая , заметим, что Е - квадратная, соответственно тоже квадратные.
6. (определитель), если , то обратная матрица существует, если , то матрица называется вырожденная .
2. Метод элементарных преобразований
Общая характеристика распространенных проблем поиска величины максимального потока в сети при помощи алгоритма Форда-Фалкерсона. Знакомство с задачами по дискретной математике. Рассмотрение особенностей и этапов постройки дерева кратчайших расстояний. контрольная работа [740,3 K], добавлен 09.03.2015
Граф как множество вершин (узлов), соединённых рёбрами, способы и сфера их применения. Специфика теории графов как раздела дискретной математики. Основные способы преобразования графов, их особенности и использование для решения математических задач. курсовая работа [1,8 M], добавлен 18.01.2013
Значение понятия математика. Ее роль в науке. Математика как наука основанная на разнообразие математических моделей, задачей которых является отображение реальных событий и явлений. Особенности математического языка. Известные высказывания о математике. реферат [21,7 K], добавлен 07.05.2013
Представление с помощью кругов Эйлера множественного выражения. Законы и свойства алгебры множеств, упрощение выражений. Система функций, ее возможные базисы. Минимизирование булевой функции. Метод Квайна – Мак-Класки. Определение хроматического числа. контрольная работа [375,6 K], добавлен 17.01.2011
Как высшая математика разрешает философские парадоксы. Математика в апориях Зенона. Точная математическая формулировка интуитивного физического или метафизического понятия непрерывного движения. Попытки избавления от допущений в математических выкладках. реферат [320,7 K], добавлен 05.01.2013
Эвристика и особенности применения эвристики в математике. Понятие доказательства в математике. Эвристика как метод научного познания. Эвристический подход к построению математических доказательств в рамках логического подхода, при доказательстве теорем. курсовая работа [177,2 K], добавлен 30.01.2009
Свойство, устранение и объяснение парадоксов в математике. Логический парадокс "Лжец" Эвбулида из Милета (IV в. до н.э.). Парадокс Греллинга, связанный с прилагательными. Парадоксы с множествами, парадоксы-петли. Проблемы парадоксов в математике. контрольная работа [34,1 K], добавлен 30.01.2010
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Дискретная математика курс лекций. Математика.
Сочинение Про Сентябрь 3 Класс
Контрольная работа: Стратегическое и оперативное планирование в страховых компаниях
Контрольная работа по теме Энергетические масла. Компрессорные
Реферат: Формирование чиновничества
База Данных Интернет Магазина Курсовая Работа
Воспитание Молодежи 2022 Эссе
Дипломная работа по теме Совершенствование стратегии развития предприятия (на примере ООО 'Уют')
Сочинение По Картине Зимнее Утро И Иней
Курсовая работа по теме Договор морской перевозки грузов
Сочинение По Русскому Языку Егэ 2022 Шаблон
Курсовая Работа На Тему Железобетонное Каркасное 4-Хэтажное Здание Предприятия Связи В Г. Лабинске
Курсовая работа по теме Технология строительных процессов при возведении подземной части зданий
Дипломная работа: Нарушение экспрессии D-глюкуронил С5-эпимеразы как возможная причина изменения структуры протеогликанов в опухоли молочной железы человека
Лабораторные Работы По Испытаниям Наземных Транспортных Средств
Реферат: Индуктивные умозаключения
Реферат: История развития психиатрии. Скачать бесплатно и без регистрации
Родной Русский Язык Контрольная Работа 6 Класс
Курсовая работа по теме Использование ключевых задач в процессе обучения школьников решению задач по геометрии
Место совершения нотариальных действий.
Контрольная Работа Тетрадь Рудницкая 2 Скачать
Використання властивості неперервності функції при розв'язуванні різних задач математичного аналізу - Математика контрольная работа
Разработка структуры сети с пакетной коммутацией на примере ОАО "Московская государственная телефонная сеть" - Коммуникации, связь, цифровые приборы и радиоэлектроника дипломная работа
Международные стандарты учета и финансовой отчетности - Бухгалтерский учет и аудит контрольная работа