Упрощение логической схемы алгоритма

Московский технический университет связи и информатики

Контрольная работа

по дисциплине Техника микропроцессорных систем в коммутации

Москва 2015 г.

Задача 1.

По заданной в таблице 1 логической схеме алгоритма (ЛСА0 необходимо:

1) построить граф-схему алгоритма ГСА;

2)      получить матричную схему алгоритма МСА;

)        получить схему формул переходов ФП и упростить ЛСА;

4)      записать упрощенную ЛСА ;

)        доказать эквивалентность ЛСА и , вычислив значение ЛСА на всех наборах значений логических условий;

)        по заданному в таблице 1 распределению сдвигов упростить ЛСА  и получить ЛСА ;

)        используя заданную в таблице 1 ЛСА , объединить частные ЛСА  и  в общую ЛСА , где .

Номер варианта определяется последней цифрой номера студенческого билета.

Таблица 1

Решение:

1. Построим граф-схему алгоритма ГСА по ЛСА:

2. Получим матричную схему алгоритма МСА:

Рис. 1

3. Получим систему формул переходов ФП и упростим ЛСА.

φ ₁

Все формулы переходов входящие в систему являются элементарными и поэтому не упрощаются. Невозможность упрощения ЛСА видна и по ГСА, так как алгоритм достаточно простой.

. Используя заданную ЛСА , объединить частные ЛСА ₁ и  в общую ЛСА , где

 Матричная схема алгоритма  у нас уже есть.

 Получим матричную схему алгоритма .

 По частным МСА составим объединенную .

Чтобы различить принадлежность определенного перехода, логическое выражение  умножаем на определяющую функцию “r”, а для  на определяющую функцию “”.

φ ₀

Преобразуем общую ЛСА .

φ ₀

 На рисунке 2 покажем наглядно полученную ЛСА с помощью ГСА.

Рис. 2

Задача 2

Дано:

Таблица 2 Отношение 1: R_Абонент 1

Таблица 3 Отношение 2: R_Абонент 2

Выполняемая операция: “Пересечение”.

Требуется:

Выполнить заданную операцию над заданными отношениями базы данных. Результат выполнения представить в виде соответствующего отношения.

Решение:

Результат пересечения содержит только те кортежи первого отношения, которые есть во втором.

Таблица 4

Задача 3.

Разместить N страниц виртуальной памяти в оперативном запоминающем устройстве (ОЗУ) и во внешних запоминающих устройствах (ВЗУ) ЭУС при наличии:

 S₀ свободных сегментов в ОЗУ,

 S_Д свободных сегментов в накопителе на магнитных дисках (НМД),

 S_Л свободных сегментов в накопителе на магнитных лентах (НМЛ).

А также составить таблицу страниц с указанием доступности страниц при заданной активности страниц.

Показать на рисунке принцип взаимосвязи страниц виртуальной памяти с сегментами ОЗУ и ВЗУ через таблицу страниц.

Дано:

Таблица 5

7000         1500      2500      8000