Курсовик1
Корзина 0 0 руб.

Работаем круглосуточно

Доступные
способы
оплаты

Свыше
1 500+
товаров

Каталог товаров

Дискретная математика Вариант №7

В наличии
0 руб.

Скачать бесплатно контрольную Дискретная математика Вариант №7

После нажатия кнопки В Корзину нажмите корзину внизу экрана, в случае возникновения вопросов свяжитесь с администрацией заполнив форму

Скачать бесплатно


Дистанционное обучение

Направление “Информатика и вычислительная техника” Профиль “Программное обеспечение средств вычислительной техники и автоматизированных систем”

Дисциплина “ Дискретная математика”

Контрольная работа

Вариант №7

№1 Доказать равенства, используя свойства операций над множествами и определения операций. Проиллюстрировать при помощи диаграмм Эйлера-Венна. а) (A\C) È (B\C) = (AÈ B)\C б) (A\B)´ C=(A´ C)\(B´ C).

Решение:

а)

б) (A\B)´C=(A´C)\(B´C)

№2 Даны два конечных множества: А={a,b,c}, B={1,2,3,4}; бинарные отношения P1 Í A´ B, P2 Í B2. Изобразить P1, P2 графически. Найти P = (P2◦P1)–1. Выписать области определения и области значений всех трех отношений: P1, P2, Р. Построить матрицу [P2], проверить с ее помощью, является ли отношение P2 рефлексивным, симметричным, антисимметричным, транзитивным. P1 = {(a,1),(b,3),(b,1),(b,4),(c,3),(c,2)}; P2 = {(1,3),(1,4),(2,2),(3,3),(4,3),(4,4)}.

Решение:

Графическое представление отношения () изображено на рисунках ниже:

Суперпозицией бинарных отношений и называется множество: . Исходя из этого определения,

Инверсией бинарного отношения называется множество: . Исходя из этого определения,

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

Матрица бинарного отношения :

Отношение не рефлексивное, так как на главной диагонали матрицы есть нулевой элемент.

Отношение будет симметричным, если , однако:

поэтому отношение не симметричное.

Отношение будет антисимметричным, если поэлементное произведение , где Е - единичная матрица.

Условие не выполнено, поэтому отношение не антисимметричное.

Тразитивность:

.

Отношение транзитивное, так как выполняется соотношение :

№3 Задано бинарное отношение P Í R2; найти его область определения и область значений. Проверить по определению, является ли P рефлексивным, симметричным, антисимметричным, транзитивным., P = {(x,y) | x2 + y2 = 4}.

Решение:

Областью определения отношения является множество:

Тогда . Итак, последнее выражение имеет смысл, если . Поэтому, очевидно:

Dom P=.

Совершенно аналогично получаем, что множество значений отношения есть множество:

Im P=.

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

Отношение симметрично, если . Возьмем два числа и , сумма квадратов которых есть число 4. Так как x2 + y2 = y2 +x2, это означает что если x2 + y2 равно 4, то и y2 +x2 тоже. Поэтому истинно, что при всех х, у. Таким образом, верно, что , а значит отношение симметрично.

Отношение антисимметрично, если . Приведем простейший контрпример: пусть х=2, у=0, тогда ясно, что и , однако при этом утверждение ложь. Таким образом, отношение не антисимметрично.

Отношение транзитивно, если . Приведем простейший контрпример: пусть x=2,y=0,z=2, тогда ясно, что и , однако при этом и не находятся в отношении . Таким образом, отношение не транзитивно.

№4 Доказать утверждение методом математической индукции: для n ³ 2.

Доказательство:

  • Для тождество верно: .
  • Пусть тождество верно для : .
  • Покажем, что оно выполнено при

№5 Восемь студентов должны сдавать зачет по пяти предметам: физике, архитектуре ЭВМ, математическому анализу, английскому языку и истории. Все зачеты назначены на одно время и каждый может сдавать только один зачет, поэтому студентам нужно распределиться на группы. Сколькими способами это можно сделать? Сколькими способами они могут разместиться после зачета за двумя совершенно одинаковыми столиками (не менее чем по одному) для того, чтобы отпраздновать результаты?

Решение:

а) Распределение 8-ти студентов для сдачи 5-ти зачетов языков (каждый сдает только один зачет) есть задача размещения 8-ти предметов по 5-ти различным ящикам так, что в каждом ящике будет хотя бы один предмет. Число способов такого распределения – это число Стирлинга 1-го рода:

б) Распределение 8-ти студентов по 2-м неразличимым столикам есть разбиение множества из 8-ти предметов на 2 блока. Число способов такого распределения – это число Стирлинга 2-го рода:

.

№6 Сколько существует положительных трехзначных чисел: а) не делящихся ни на одно из чисел 5, 6, 16? б) делящихся ровно на одно из этих трех чисел?

Решение:

Всего целых положительных трехзначных чисел .

Из них делятся на 5, делятся на 6, делятся на 16, НОД(5,6)=1, делятся на 5 и 6, НОД (5,16)=1, делятся на 5 и 16, НОД(6,16)=2, делятся на 6 и 16, НОД(5,6,16)=770, делятся на 5, 6 и 16.

а) По формуле включений и исключений, количество положительных трёхзначных чисел, не делящихся ни на одно из чисел 5, 6 и 16, равно

б) По формуле включений и исключений, количество положительных трёхзначных чисел, делящихся ровно на одно из чисел 5, 6 и 16, равно

.

№7 Найти коэффициенты при a=x4·y·z3, b=x·y4·z, c=y2·z4 в разложении (3·x2+5·y+2·z)6.

Решение:

1) a=x3·y2·z соответствует член разложения .

Коэффициент при равен

2) b= x·y4·z.

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

3) c= y2·z4 соответствует член разложения .

Коэффициент при равен

.

№8 Найти последовательность {an}, удовлетворяющую рекуррентному соотношению 3·an+2 – 8·an+1 + 5·an = 0· и начальным условиям a1=10, a2=20.

Решение:

Характеристический многочлен данной возвратной последовательности

.

Общее решение данного рекуррентного соотношения

.

№9 Орграф задан матрицей смежности. Необходимо: а) нарисовать граф; б) выделить компоненты сильной связности; в) заменить все дуги ребрами и в полученном неориентированном графе найти эйлерову цепь (или цикл).

Решение:

а) Рисунок орграфа, заданного матрицей смежности.

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

в) после замены всех дуг ребрами получен следующий неориентированный граф:

Вершина

1

2

3

4

5

6

Степень

6

2

5

4

4

5

Данный граф не является эйлеровым циклом, поскольку степень вершины 3 равна 5. По теореме Эйлера граф является эйлеровым циклом тогда и только тогда, когда степень всех вершин четна.

В графе существует эйлерова цепь (по дугам по порядку номеров).

Начало цепи 3, конец 6.

Цепь – под дугам по порядку номеров.

№10 Взвешенный граф задан матрицей длин дуг. Нарисовать граф. Найти: а) остовное дерево минимального веса; б) кратчайшее расстояние от вершины v3 до остальных вершин графа, используя алгоритм Дейкстры.

Решение:

Нарисуем граф:

а) Найдем остовное дерево минимального веса. Воспользуемся алгоритмом Краскала.

Этап 1: Этап 2:

Этап 1: включаем в остовное дерево все рёбра с наименьшим весом 2, так как включение каждого последующего ребра не приводит к образованию цикла.

Этап 2: включаем в остовное дерево все рёбра с весом 3, так как включение каждого последующего ребра не приводит к образованию цикла.

Поскольку все вершины соединены, то построение остовного дерева закончено.

б) Воспользуемся алгоритмом Дейкстры поиска кратчайшего расстояния от вершины до всех остальных вершин:

- вес ребра , - окончательная метка вершины , - временная метка вершины .

На 1-м шаге вершине присваивается окончательная метка 0, остальным вершинам – временные метки , равные весам рёбер . На последующих шагах вершине с наименьшей временной меткой даётся окончательная метка , вычисляются временные метки других вершин .

1.

2.

3.

4.

5.

6.

Все вершины имеют окончательные метки.

Вершина

Кратчайшее расстояние от вершины

2

7

0

4

6

4

Путь от вершины

3-1

3-1-2

3-1-4

3-6-5

3-6

Скачать бесплатно

Loading...

Последние статьи из блога

Проблемы государственного устройства России

Понятия и принципы федерализма в России

Современные масштабы экологической катастрофы

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

Разработка системы финансового планирования (бюджетирования)

Architectonika of management system in agrarian sphere in conditions of sanction economy

Конверсия веб-сайта

Взаимодействие PHP и MYSQL

Синтаксис языка PHP

Адаптивная вёрстка сайта

Основные понятия, принципы и системы бережливого производства

Система прохождения государственной службы

Принципы служебной деятельности

Виды государственной службы

Практические рекомендации по совершенствованию поддержки малых форм хозяйствования в АПК Новосибирской области

Анализ деятельности управления развития сельских территории и инвестиций Новосибирской области в сфере поддержки АПК

Характеристика развития АПК Новосибирской области

Анализ ликвидности банковского сектора Российской Федерации

Теоретические аспекты обеспечения банковской ликвидности

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