Контрольный тест по разделу 3

1. Найти кратчайший путь из вершины 1 в вершину 8 на графе, заданном матрицей весов:

(веса в пустых клетках равны ).

Построить остовное дерево для полученного графа.

2. Изобразить в виде графа структуру заданного языка и построить совокупность слов, порождаемых грамматикой данного языка: Алфавит . Правила грамматики: .

2. Имеется устройство с входным каналом , каналом обратной связи и выходным каналом , реализующее отображение , заданное в виде таблицы

На вход подаётся последовательность 111121. Определить последовательность на выходе, если .

4. Построить СДНФ, сокращённую и минимальную ДНФ булевой функции, заданной таблицей. Изобразить контактные схемы для исходной, сокращённой и минимальной ДНФ.