Контрольная работа. Вариант №10. Дискретная математика. СибГУТИ

Задача 1. Доказать равенства, используя свойства операций над множествами и определения операций. Проиллюстрировать при помощи диаграмм Эйлера-Венна. а) (A\B)  (AC) = A\(B\C)б) (AB)(CD)=(AC)(BC)(AD)(BD).
Задача 2. Даны два конечных множества: А={a,b,c}, B={1,2,3,4}; бинарные отношения P1 AB, P2 B2. Изобразить P1, P2 графически. Найти P = (P2P1)–1. Выписать области определения и области значений всех трех отношений: P1, P2, Р. Построить матрицу [P2], проверить с ее помощью, является ли отношение P2 рефлексивным, симметричным, антисимметричным, транзитивным. P1 = {(a,3),(a,2),(b,2),(b,3),(c,1),(c,4)}; P2 = {(1,1),(1,2),(2,2),(3,3),(4,1),(4,4)}.
Задача 3. Задано бинарное отношение P; найти его область определения и область значений. Проверить по определению, является ли отношение P рефлексивным, симметричным, антисимметричным, транзитивным. P R2, P = {(x,y) | x2 y}.
Задача 4. Доказать утверждение методом математической индукции:
1•2 + 2•5 + 3•8 + ... + n•(3•n–1) = n2•(n+1).
Задача 5. Десять студентов должны сдавать зачет по трем предметам: физике, английскому языку и истории. Все зачеты назначены на одно время и каждый может сдавать только один зачет, поэтому студентам нужно распределиться на группы, не менее чем по двое в каждой. Сколькими способами это можно сделать? Сколькими способами они могут разместиться после зачета за четырьмя совершенно одинаковыми столиками (не менее чем по одному) для того, чтобы отпраздновать результаты?
Задача 6. Сколько существует положительных трехзначных чисел: а) делящихся на числа 8, 20 или 25? б) делящихся ровно на одно из этих трех чисел?
Задача 7. Найти коэффициенты при a=x3•y2•z3, b=x2•y2•z2, c=x6•z4 в разложении (5•x3+3•y+2•z)6.
Задача 8. Найти последовательность {an}, удовлетворяющую рекуррентному соотношению 2•an+2 + 7•an+1 + 5•an = 0• и начальным условиям a1=6, a2=9.
Задача 9. Орграф задан матрицей смежности. Необходимо:  
а) нарисовать граф;  
б) выделить компоненты сильной связности;  
в) заменить все дуги ребрами и в полученном неориентированном графе найти эйлерову цепь (или цикл).
Задача 10. Взвешенный граф задан матрицей длин дуг. Нарисовать граф. Найти: а) остовное дерево минимального веса;
б) кратчайшее расстояние от вершины v6 до остальных вершин графа, используя алгоритм Дейкстры.

Работа сдана в 2013 году.