Дискретная математика 02
Задача 1. Построить таблицу истинности для заданной формулы:
.
Задача 2. Преобразовать данную формулу так, чтобы она содержала только операции тесного отрицания, дизъюнкции и конъюнкции. Пользуясь свойствам операций дизъюнкции и конъюнкции, привести формулу к виду, не содержащему скобок.
Задача 3. Из колоды в 36 карт вынимают 8 карт. Указать число наборов, содержащих ровно 3 карты бубновой масти и 2 карты пиковой масти. Производится неупорядоченный выбор. Рассмотреть случаи выбора с возвращением и без возвращения.
Решение:
Всего в колоде 36/4=9 карт каждой масти. Так как производится неупорядоченный выбор, то будем применять формулу числа сочетаний.
Без возращения: выбрать 3 бубны из 9, 2 пики из 9 и 8-3-2=3 оставшихся мастей из 9*2=18 можно наборов.
С возращением: выбрать 3 бубны из 9, 2 пики из 9 и 8-4-2=2 оставшихся мастей из 9*2=18 можно наборов.
Ответ: 2467584; 344373768.
Задача 4. Пользуясь алгоритмом Дейкстры, найти кратчайшие расстояния из вершины неориентированного взвешенного графа в другие вершины графа. Указать кратчайший маршрут из вершины в вершину .
Решение:
Пусть - вес ребра , - окончательная метка вершины , - временная метка вершины .
На 1-м шаге вершине присваивается окончательная метка 0, остальным вершинам – временные метки , равные весам рёбер . На последующих шагах вершине с наименьшей временной меткой даётся окончательная метка , вычисляются временные метки других вершин .
1.
2.
3.
4.
5.
6.
Все вершины имеют окончательные метки.
Задача 5. Схема дорог, соединяющих населенные пункты, задана графом, показанным на рисунке. В таблице каждому ребру графа поставлен в соответствие вес, характеризующий стоимость прокладки дороги, соединяющей данные населенные пункты. При помощи алгоритма Краскала построить схему дорог, соединяющих данные населенные пункты, при наименьшей стоимости проекта.
Решение:
Выберем вершину, из которой выходит наибольшее число ребер с весом 1:
Включаем в остов все ребра веса 1, которые из нее выходят, и вершины, в которые эти ребра входят (циклов нигде не получится):
Из добавленных вершин также ищем ребра с весом 1 и добавляем их с конечными вершинами в остов:
Осталось включить еще одну вершину:
Итак, минимальный остов содержит 8 ребер по 1 веса каждая, итого минимальная стоимость прокладки дорог составит 8 единиц.
Задача 6. Выяснить, применима ли машина Тьюринга, заданная программой Р к слову S, и если применима, то указать результат применения машины Тьюринга к заданному слову.
Решение:
1)
Тогда в результат записываем 1; указатель остается на первом символе и в состояние .
S=111101
2)
Тогда в результат записываем 0; указатель переходит на второй символ и в состояние .
S=011101
3)
Тогда в результат записываем 1; указатель переходит на первый символ и в состояние .
S=011101
4)
Тогда в результат записываем 0; указатель переходит на второй символ и в состояние .
S=011101
Машина Тьюринга останавливается, тогда она применима к указанному слову; результат S=011101.
< Предыдущая | Следующая > |
---|