По дисциплине: Дискретная математика - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Непрерывная математика Дискретная математика 3 1314.78kb.
Перечень вопросов для подготовки к зачету по дисциплине «Дискретная... 1 13.02kb.
Экзаменационные вопросы по дисциплине «Дискретная математика» для... 1 34.55kb.
Литература по математике (алгебра, геометрия, математический анализ... 1 224.35kb.
Программа дисциплины «Дискретная математика» 1 283.06kb.
«Математический анализ I», «Алгебра и геометрия», «Дискретная математика»... 1 18.09kb.
Учебная программа По учебной дисциплине «математика» 2 571.82kb.
Учебно-методический комплекс по дисциплине выбору «Информационная... 2 597.08kb.
Учебно-тематические планы лекционных занятий по дисциплине «Математика» 1 38.7kb.
Методические указания к практическому занятию по дисциплине «Математика»... 1 201.38kb.
Рабочая программа по дисциплине ен. Ф. 1 «Математика» 3 452.04kb.
Ковальчук С. С. Пояснительная записка к учебному плану аоно лицей... 1 109.68kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

По дисциплине: Дискретная математика - страница №1/1

По дисциплине: Дискретная математика



Выполнил: ___________

Группа: _______

Вариант: 10


Проверил: ___________________

Новосибирск, 20__г


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

а)  (A\B)  (AC) = A\(B\C)

Это иллюстрация доказывает равенства (геометрическое доказательство).

Теперь докажем аналитически

Доказано.

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

б)  (AB)(CD)=(AC)(BC)(AD)(BD).

Доказано.

Проиллюстрируем

Обозначим, пусть



e:\sciensjobs\jobs\акима степан\заново\дискретная математика\1.jpg

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

P= {(a,3),(a,2),(b,2),(b,3),(c,1),(c,4)};

P= {(1,1),(1,2),(2,2),(3,3),(4,1),(4,4)}.

Решение:

P1 и P2 представлены на рисунках.



c:\documents and settings\администратор\рабочий стол\doc1_1.jpgc:\documents and settings\администратор\рабочий стол\doc1_11.jpg

Найти P = (P2◦P1)–1.

Тогда


По свойствам инверсии композиций бинарных отношений


Область определения отношений

Область значения отношений

Матрица бинарных отношений

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

Все диагональные элементы равны единицы, значить является рефлексивным.

Так как матрица не симметричная, то отношение тоже является не симметричным.

Так как матрица не антисимметричная, то отношение тоже является не антисимметричным.

Так как


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



Отношение является транзитивным.

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

Решение:


Отношение определено на всем множестве , т.к. для любого можно найти такое , что .



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

Бинарное отношение P перепишем в эквивалентной форме

P  R2, P = {(x,y) | x2 -y 0}.

По сути x2 -y 0 есть область плоскости, которая «лежит на верху» от параболы y=x2 , причем саму параболу включает в себе. (смотреть рисунок)

Очевидно, что область определения , область значений .

Проверяем симметричность

По определению бинарное отношение Р называется симметричным, если для

выполняется.

Простыми словами должны быть равными. Но это не так.

Отношению соответствует совсем другой график




Теперь проверим антисимметричность.

Бинарное отношение P на множестве Х называется антисимметричным, если для пары элементов множества x,y выполнение отношений aPb и bPa влечет x=y. В нашем случае это не выполняется, это значит, что отношение не антисимметрично.

Очевидно, что

Антисимметричность выполняется только при.

Бинарное отношение P на множестве Х называется рефлексивным, если для любого . В нашем случае это условие не выполняется, значит P не рефлексивно.



При Таким образом, при условие рефлективности нарушается.

Бинарное отношение P на множестве Х называется транзитивным, если для любых трёх элементов множества a,b,c выполнение отношений aRb и bRc влечёт выполнение отношения aRc.

В нашем случае можно найти такое z, что P = {(x,z) | x2  z} и P = {(z,y) | z2  y}, отсюда следует P = {(x,y) | x2  y}. Напомним, что между любыми двумя числами a и c (предположим ) найдется число b, что выполняется. Но, при такое число нельзя найти. Таким образом, P не является транзитивным.

4 Доказать утверждение методом математической индукции:


1·2 + 2·5 + 3·8 + … + n·(3·n–1) = n2·(n+1).

Решение:



Базис:

n = 0; 0=0

предположим при k равенство выполняется

Проверим для (k + 1):

Или

Выполняется, значит утверждение верно.



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

Решение:


Число студентов - , число предметов - .

Пусть на первый предмет идут два студента, на второй тоже два, а остальные - на третий предмет. Количество такой комбинации есть .

На первый предмет идут два студента, на второй три, а остальные - на третий предмет. Количество такой комбинации есть .

На первый предмет идут два студента, на второй четыре, а остальные - на третий предмет. Количество такой комбинации есть.

И так далее. Эти комбинации складываем:



Количество таких комбинаций – 40950. – Ответ.

Теперь рассмотрим комбинацию усаживания за столы.

Число студентов - , число столов - .

Используем число Стирлинга 2-го рода

Ответ.

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

Решение:

а) числа, делящиеся на числа 8, 20 или 25.

Здесь самое старшее число 25.

Трехзначные числа, делящиеся на 25, есть:

. (1)

Количество таких чисел.



Трехзначные числа, делящиеся на 20, есть:

Количество таких чисел

Трехзначные числа, делящиеся на 8, есть:

(3)


Количество таких чисел –.

В последовательности (1) четные числа, которые делятся на 20:

.

Из этих чисел только следующие делятся на 8: . – Ответ.



б) числа, делящиеся ровно на одно из этих трех чисел.

Трехзначные числа, которые делятся на 25. Количество таких чисел. – Ответ.

Трехзначные числа, которые делятся на 20. Количество таких чисел –– Ответ.

Трехзначные числа, которые делятся 8. Количество таких чисел –– Ответ.

Опять решаю вторым способом, хотя ответ тот же.

Количество чисел, которые делятся на 8

Количество чисел, которые делятся на 20

Количество чисел, которые делятся на 25

Количество чисел, которые делятся на 8 и на 20

Количество чисел, которые делятся на 8 и на 25

Количество чисел, которые делятся на 20 и на 25

Количество чисел, которые делятся на 8, на 20 и на 25

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

Решение:


По формуле бинома Ньютона найдем: ,

где

Тогда

Или (1)

Согласно

Ответ.

Согласно

Эта система не имеет решения. Поэтому в разложении член отсутствует. – Ответ.

Согласно



Ответ.

Отсюда коэффициенты при а=x3·y2·z3

Отсюда коэффициенты при b=x2·y2·z2

Так как степени х могут быть , то коэффициенты при b=x2·y2·z2, равняется к нулю.

Отсюда коэффициенты при c=x6·z4

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

Решение:

Очевидно, что

Можно писать .

Найдем:



Далее



Теперь эти члены перепишем в другом виде:



Или


Или


Пишем в общем виде:





Ответ. (1)

Решаем вторым способом, результат один и тот же.

Составим характеристический многочлен

Найдем корни характеристического уравнения



Следовательно, общее решение рекуррентного соотношения имеет вид:


Используем начальные условия

;
Из этих двух уравнение найдем с1 и с2:

Тогда общий вид рекуррентного соотношения
(2)
Формулы (1) и (2) дает абсолютно идентичные результаты.

9 Орграф задан матрицей смежности. Необходимо:


а) нарисовать граф;
б) выделить компоненты сильной связности;
в) заменить все дуги ребрами и в полученном неориентированном графе найти Эйлерову цепь (или цикл).

Решение:

а) нарисовать граф;

На рисунке изображен наш пример: направленный орграф с петлями, при этом длины ребер считаются равными.

б) выделить компоненты сильной связности;

На нашем примере найдены все три компоненты сильной связности (закрашенные области, обведенные пунктиром).

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

Начнем с вершины 1.



Компоненты

в) заменить все дуги ребрами и в полученном неориентированном графе найти Эйлерову цепь (или цикл).

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

Критерий Эйлера: В связном графе существует эйлеров путь тогда и только тогда, когда в нем не более 2-х нечетных вершин, а эйлеров цикл - тогда и только тогда, когда в нем все вершины четные. В несвязном графе очевидно, что эйлерова пути существовать не может (но он существует в тех компонентах связности, которые удовлетворяют критерию).

Сначала найдем самые простые эйлеров циклы:

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

Решение:


Рисуем взвешенный граф согласно матрице смежности. Сначала (для понимания неандертальцев) меняем матрицу промежности.

Если в пересечении столбца и строки стоит бесконечность (ну такой знак есть – лежачая восьмерка. Эту лежачую восьмерку меняем на ноль), то соответствующего ребра не существует.

Для нахождения остовного дерева минимального веса используем алгоритм Крускала. Пропуская все подробности алгоритма скажем, что:
а) остовное дерево минимального веса;

Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном, взвешенном, неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.

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

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

Вес остова W=1+1+2+1+2=7

На рисунке остов выделен утолщенными ребрами красного цвета.



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

Примечание. Алгори́тм Де́йкстры (Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Поэтому и есть сравнение расстояний (эквивалентно весов или суммы весов ребер).

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

Вершины снабжаем пометками, и в графе будут присутствовать метки (∞,0), пока не найден путь. Вершины, которые будут становиться постоянными и их выделяем заливкой. Вершина A стала постоянной (Рис 10 а).e:\sciensjobs\jobs\акима степан\заново\дискретная математика\1.jpg

Первый шаг.

Смежные вершины с А - В, С и D.

Для них нашли расстояния (это 3, 2 и 4), заменили метки на (3,А), (2,А) и (4,A). Минимальное из расстояний 2.Вершина D(2,А) становится постоянной. Вершина D становится постоянной (Рис 10 б).

Второй шаг.

С вершины D вычислим расстояния до смежных вершин (кроме А) B,C,E.

До вершины B: 2+4=6, Это расстояние больше текущего. Поэтому метка вершины не меняется

До вершины C: 2+1=3, Это расстояние меньше текущего. Поэтому метка вершины меняется на C(3,D).

До вершины E: 2+5=7, Поставим метку E(5,D). (Рис. 10 в).

Третий шаг

Посещаем вершину С:

С вершины C вычислим расстояния до смежных вершин (кроме постоянных) E,F.

До вершины E: 3+1=4, Это расстояние меньше текущего. Поэтому метка вершины меняется на E(4,C).

До вершины F: 3+2=5, Метка вершины будет F(5,C). Вершина C становится постоянной (рис. 10 г).

e:\sciensjobs\jobs\акима степан\заново\дискретная математика\4.jpg

Четвертый шаг

Помешаем вершину Е

С вершины E вычислим расстояния до смежных вершин (кроме постоянных) F.

До вершины F: 4+3=7, Это расстояние больше текущего. Поэтому метка вершины не меняется.

Вершина C становится постоянной (рис. 10 д).

Пятый шаг

Помешаем вершину B

С вершины B вычислим расстояния до смежных вершин (кроме постоянных) F.

До вершины F: 3+1=4, Это расстояние меньше текущего. Поэтому метка вершины меняется на F(4,B).

Вершины F и B становятся постоянными (Рис 10 е).

Таким образом, все вершины пройдены.

Наикротчайшее расстояние от вершины до:

1. Вершины B: 3, путь AB;

2. Вершины C: 3, путь ADC;

3. Вершины D: 2, путь AD;

4. Вершины E: 4, путь ACE;

5. Вершины F: 4, путь ABF;

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

Фрагмент из отвергнутого ответа.



(Рис 10 г). Это и есть ответ.


izumzum.ru