Учебная работа № /7838. «Контрольная Дискретная математика. 6 заданий
Учебная работа № /7838. «Контрольная Дискретная математика. 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
2 Задание №2
3 Задание №3
4 Задание №4
5 Задание №5
Заключение
Список используемых источников
Введение
граф дискретная математика
Теория графов — раздел дискретной математики, изучающий свойства графов, В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами, В строгом определении графом называется такая пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество V?V,
В последнее время теория графов стала простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем, Это проблемы проектирования интегральных схем и схем управления, исследования логических цепей, блок-схем программ, экономики и статистики, химии и биологии, теории расписаний и дискретной математики,
Целью данной работы является практическое закрепление научно-теоретических материалов теории графов и получение навыков применения полученных знаний для решения конкретных задач,
1 Задание №1
Формулировка задания
Дана матрица смежности для графа G, На основе аналитических выражений для прямого и обратного транзитивных замыканий найти все компоненты связности для данного графа, Результаты вычислений проверить путем непосредственных преобразований матриц смежности, В отчете о выполненном задании привести два рисунка: графическое изображение исходного графа, когда его вершины в порядке возрастания номеров расположены по окружности, наподобие циферблата, и этого же графа, но разложенные на сильно связанные подграфы,
Матрица смежности представлена на рисунке 1,1,
Рисунок 1,1 — Матрица смежности исходного графа
Решение
Для начала приведем графическое изображение исходного графа, расположив его вершины по окружности в порядке возрастания номеров, Получившийся граф, представлен на рисунке 1,2,
Рисунок 1,2 — Графическое изображение исходного графа
Степени оператора прямого транзитивного замыкания для первой вершины:
G0(1) = {1};
G1(1) = {1, 2, 8, 18};
G2(1) = {1, 2, 8, 18, 6, 12, 4, 16, 5, 14};
G3(1) = {1, 2, 8, 18, 6, 12, 4, 16, 5, 14, 3, 15, 10, 13, 17};
G4(1) = {1, 2, 8, 18, 6, 12, 4, 16, 5, 14, 3, 15, 10, 13, 17, 11, 7},
Остальные степени оператора G находить не нужно, так как это не приводит к появлению во множестве Gk(1) новых вершин, Следовательно, прямое транзитивное замыкание
G+(1) = = {1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18},
Степени оператора обратного транзитивного замыкания для первой вершины:
G-1(1) = {1, 11, 12};
G-2(1) = {1, 11, 12, 3, 13, 2, 4, 7, 14, 15};
G-3(1) = {1, 11, 12, 3, 13, 2, 4, 7, 14, 15, 6, 17, 8, 5, 9, 16, 18, 10},
Остальные степени оператора не находим по той же причине, Следовательно, обратное транзитивное замыкание
G-(1) =={1,2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18},
Таким образом, компонента связности для вершины 1
C1 = G+(1)?G-(1) = {1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18},
После этих вычислений остается вершина 9, не вошедшая в компоненту, Не вычисляя G+(9) и G-(9), можно заключить, что C2 = {9},
Проверим найденные компоненты связности путем непосредственных преобразований матрицы смежности, Слева от матрицы приписываем столбец, i-й элемент которого является длиной пути из первой вершины в i-ю, Снизу приписываем строку, i-й элемент которой является длиной пути из i-й вершины в первую, Получившаяся матрица с приписанными столбцом и строкой представлена на рисунке 1,3″
