Учебная работа № /6972. «Контрольная Дискретная математика. 6 заданий
Учебная работа № /6972. «Контрольная Дискретная математика. 6 заданий
Содержание:
«Расчетно-графическое задание 8 3
Дан алгоритм поведения человека, необходимо изобразить алгоритм графически, подробно описать выполнение алгоритма. Для этого использовать текстовый редактор.
Условие.
Галя действует по следующему алгоритму:
Шаг 1. Пройти 9 метров прямо.
Шаг 2. Повернуть направо и пройти еще 5 метров.
Шаг 3. Повторять шаг 2, пока не будет пройдено всего 64 метра.
Шаг 4. Остановиться.
Определить расстояние между точками старта и финиша.
Расчетно-графическое задание 18 5
Дан алгоритм Евклида.
Шаг 1. Если a = b, то работа алгоритма закончена; иначе выполняется шаг 2.
Шаг 2. Если a > b, то переменной а присваивается значение a — b; иначе переменной b присваивается значение b — a.
Шаг 3. Выполняется шаг 1 данного алгоритма.
Значениями переменных a и b являются натуральные числа. Определить значение переменной а, описать все шаги алгоритма.
Условие.
a = 70, b = 42.
Расчетно-графическое задание 28 6
Дана блок-схема. Описать работу алгоритма по шагам и записать полученное решение.
Расчетно-графическое задание 38 7
Представить числа в двоичной системе.
9986, 338, 98.
Расчетно-графическое задание 48 9
Выполнить сложение и умножение и вычитание следующих чисел в двоичной системе, результат проверить в десятичной системе.
111110 и 100001
Расчетно-графическое задание 68 11
Алгоритм шифрования заключается в следующем:
1) Найти по таблице 4 порядковый номер первой буквы данного сообщения;
2) из порядкового номера первой буквы данного сообщения вычесть цифру 3;
3) полученное число является порядковым номером буквы в расшифрованном сообщении;
4) используя шаги 1-3, расшифровать все буквы данного сообщения.
Данное задание выполнить в виде таблицы, созданной в Microsoft Word, заголовок таблицы закрасить цветом, а текст в таблице сделать жирным курсивом.
Список литературы 14»
Выдержка из похожей работы
КУРСОВАЯ РАБОТА
Задачи и алгоритмы дискретной математики
Введение
Актуальность данной работы заключается в необходимости для любого программиста знаний в области дискретной математики и различных ее алгоритмов, для использования при реализации разрабатываемых программных продуктов и для решения поставленных задач,
Изучение представленных алгоритмов в теории, а так же их реализация на языке программирования высокого уровня позволяют судить об эффективности данных алгоритмов и дают важный опыт,
алгоритм программный дискретный математика
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), Для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них»
