Задача 1. Построить таблицу истинности для заданной формулы.
|
|
|
|
|
|
|
|
0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 |
1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
Задача 2. Преобразовать данную формулу так, чтобы она содержала только операции тесного отрицания, дизъюнкции и конъюнкции. Пользуясь свойствами операций дизъюнкции и конъюнкции, привести формулу к виду, не содержащему скобок.
Приводим к формуле, содержащей только операции тесного отрицания, дизъюнкции и конъюнкции.
Приводим формулу к виду, не содержащему скобок.
Задача 3. Из колоды в 36 карт вынимают 8 карт. Указать число наборов, содержащих ровно 4 карты бубновой масти и 2 карты пиковой масти. Рассмотреть случаи выбора с возвращением и без возвращения.
Без возвращения карт в колоду.
С возвращением.
Задача 4. Пользуясь алгоритмом Дейкстры, найти кратчайшие расстояния из вершины 
неориентированного взвешенного графа в другие вершины графа. Указать кратчайший маршрут из вершины 
в вершину 
.
|
|
|
|
|
|
|
|
|
|
3 | 2 | 2 | 1 | 3 | 1 | 1 | 6 | 4 | 3 |
Используя алгоритм Дейкстры пометим все вершины графа.
Вершина 
- начало пути, ее пометка:
, пометки всех остальных вершин временные и равны бесконечности.
Данные вершины получают временные пометки, выбираем вершину с минимальной пометкой, сделаем эту пометку постоянной
( кратчайшее расстояние из вершины 
в вершину 
)
Продолжаем помечать вершины, начиная с 
.
( кратчайшее расстояние из вершины 
в вершину 
)
Продолжаем помечать вершины, начиная с 
.
( кратчайшее расстояние из вершины 
в вершину 
)
( кратчайшее расстояние из вершины 
в вершину 
)
Кратчайший маршрут из вершины 
в вершину 
:
.
( кратчайшее расстояние из вершины 
в вершину 
)
Задача 5. Схема дорог, соединяющих населенные пункты, показана на рисунке. В таблице каждому ребру графа поставлен в соответствие вес, характеризующий стоимость прокладки дороги, соединяющей данные населенные пункты. При помощи алгоритма Краскала построить схему дорог, соединяющих данные населенные пункты, при наименьшей стоимости проекта.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 | 2 | 1 | 2 | 1 | 3 | 1 | 2 | 1 | 1 | 3 | 1 | 1 | 2 | 1 | 3 |
Переупорядочиваем ребра в порядке увеличения их веса:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 | 3 |
Добавляем ребра в схему, начиная с ребер наименьшего веса, так чтобы каждое следующее ребро не образовывало цикла, с ранее введенными.
Стоимость, получившейся сети дорог:1+1+1+1+1+1+1+1=8
Задача 6. Выяснить, применима ли машина Тьюринга, заданная программой P к слову S, и если применима, то указать результат применения машины Тьюринга к данному слову.
для первого символа(1), результат 
, машина переходит вправо. Выполняется 
для второго символа(1), результат 
, машина переходит вправо. Выполняется 
для третьего символа(1), результат 
, машина переходит влево. Выполняется 
для второго символа(0), результат 
, машина остается на месте. Последний шаг будет выполняться бесконечно, машина зациклится.
Вывод: данная программа не применима к этому слову.
