Учебная работа № /8779. «Контрольная Дискретная математика, вариант 4
Учебная работа № /8779. «Контрольная Дискретная математика, вариант 4
Содержание:
Номер
варианта Номера задач для контрольной работы
4 14 34 54 74 94 114 134 144
3.2. Задания для контрольной работы
В задачах 1-20 доказать тождества, используя только определения операций над множествами.
14. .
34. P1={(a,1),(a,2),(b,3),(b,4),(c,3),(c,1),(c,4)},
P2={(1,4),(2,3),(2,1),(3,4),(4,2)}.
54. Лифт, в котором поднимаются 9 пассажиров, останавливается на 10 этажах. Пассажиры выходят группами по 2,3 и 4 человека. Сколькими способами это может произойти?
В задачах 61-80 решить неоднородные рекуррентные соотношения
74. an+2=3an+1-2an+(-1)n, a0=1, a1=2.
В задачах 81-100 проверить составлением таблиц истинности, будут ли эквивалентны указанные формулы.
94. .
В задачах 111-120 определить значение высказывания, полученного из трёхместного предиката на множестве Х
114. .
Примечание: N-множество натуральных числе; Z – множество целых чисел; R – множество действительных чисел.
В задачах 121-140 по матрице смежности неориентированного графа требуется: 1) построить граф; 2) составить таблицу степеней вершин, матрицу инцидентности, матрицу расстояний; 3) найти радиус, диаметр и центр графа.
134.
В задачах 141-150 по заданной матрице весов ориентированного графа найти по алгоритму Дейкстры величину минимального пути и сам путь от вершины х1 до вершины х6.
144.
Выдержка из похожей работы
КУРСОВАЯ РАБОТА
Задачи и алгоритмы дискретной математики
Введение
Актуальность данной работы заключается в необходимости для любого программиста знаний в области дискретной математики и различных ее алгоритмов, для использования при реализации разрабатываемых программных продуктов и для решения поставленных задач,
Изучение представленных алгоритмов в теории, а так же их реализация на языке программирования высокого уровня позволяют судить об эффективности данных алгоритмов и дают важный опыт,
алгоритм программный дискретный математика
1, Потоки в сетях: алгоритм Форда-Фалкерсона
1,1 Формулировка задания
изучить теоретические аспекты вопроса построения алгоритма Форда-Фалкерсона;
ручная реализация решения задачи нахождения максимального потока в транспортной сети;
по средствам выбранного мною языка программирования C# осуществить программную реализацию алгоритма Форда-Фалкерсона,
1,2 Изучение алгоритма
Так как алгоритм Форда-Фалкерсона решает задачу нахождения максимального потока в транспортной сети, следует ввести несколько понятий,
Транспортная сеть — это ориентированный граф, ребра которого имеют определенную не отрицательную пропускную способность и поток, Выделяют две такие вершины s (исток) и t (сток), что любые другие вершины находятся на пути из s в t,
Целочисленная транспортная сеть — транспортная сеть, все пропускные способности ребер которой — целые числа,
Остаточная сеть — это сеть, состоящая из тех ребер (называемых также остаточными) исходной сети, поток по которым можно увеличить, Заметим, что остаточное ребро не обязано быть ребром исходной сети, Такие ребра образуются, когда имеется поток в обратном направлении — ведь такие потоки можно уменьшить,
Идея алгоритма Форда-Фалкерсона заключается в том, чтобы выбрать произвольный путь от источника (s) к стоку (t), найти на этом пути минимальное значение остаточных пропускных способностей и увеличиваем поток на каждом ребре этого пути на найденное значение, Такие действия проделываются для всех возможных путей,
Алгоритм Фода-Фалкерс��на способен отыскать максимальный поток, не зависимо от того, какой метод выбран для нахождения аугументальных путей, а так же независимо от того, какой путь мы найдем, он всегда оканчивается определением сечения, поток которого равен пропускной способности, а значит, равен величине потока сети, который является максимальным потоком,
Пошаговое описание алгоритма:
1, Обнуляем все потоки, Остаточная сеть изначально совпадает с исходной сетью;
2, В остаточной сети находим любой путь из источника в сток, Если такого пути нет, останавливаемся;
3, Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток;
4, На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью Cmin;
5, Для каждого ребра на найденном пути увеличиваем поток на Cmin, а в противоположном ему — уменьшаем на Cmin;
6, Модифицируем остаточную сеть, Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность, Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его;
7, Возвращаемся на шаг 2,
Для поиска пути будем использовать метод «поиска в глубину» (или DFS, от англ, Depth-first search), Для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них»
