Дискретная математика 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.

© 2011-2024 Контрольные работы по математике и другим предметам!