Курсовик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...

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

Административное право

Методы оценки эколого-экономической безопасности региона

Факторы эколого-экономической безопасности региона

Экологическая безопасность, как составная часть экономической безопасности региона

Информационные ресурсы библиотечной сети России

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

Теоретические основы формирования самооценки в младшем школьном возрасте

Теоретические аспекты маркетинга как функция управления

Французский язык в истории итальянской гастрономии

Понятие дискурса и гастрономического дискурса

Анализ тенденций развития российского рынка микрофинансирования

Совершенствование организационных и методических аспектов внутреннего финансового аудита

Методические и практические аспекты внутреннего финансового аудита в органах исполнительной власти

Теоретико-правовые основы внутреннего финансового аудита в государственных органах исполнительной власти

Теоретические основы экологического воспитания детей старшего дошкольного возраста

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

Внеклассная работа

Понятие метафоры. Классификация метафор Джорджа Лакоффа

Теоретические основы изучения метафорических концептов в актовом дискурсе

Теоретико-методологические подходы к изучению представлений о безопасности городской среды