Министерство образования Российской Федерации

Уфимский государственный авиационный технический университет

Факультет ИРТ: Информатика и робототехника

Кафедра ПСИ: Проектирование систем информатики

Учебная дисциплина:

Математическая логика и теория алгоритмов

РГР: Расчетно-графическая работа

Общая тема:

ПАРАЛЛЕЛЬНЫЕ ЛОГИКО-АЛГОРИТМИЧЕСКИЕ СИСТЕМЫ

(алгоритмы и логика, аппаратная и программная реализация)

Часть 1

ТЕХНИКА ПОЛМОРФНЫХ СТРУКТУРНЫХ ПОСТРОЕНИЙ
ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ

Пояснительная записка

5033.7491.0000-ПЗ

Направление подготовки:

654600: ИВТ: Информатика и вычислительная техника

Специальность:

230104: Системы автоматизированного проектирования

Курс обучения: II

Учебная группа: САПР-230

Работу выполнил

студент Манаев Р. Н.

Зачетная книжка №

Вариант задания: А580

Работу принял _____________ Житников А. П.

2007

Оглавление:

1. Исходное задание. 3

2. Восстановление стандартной СФА.. 3

2.1. Контрольная проверка. 4

2.2 Восстановление СФА с явной записью суперпозиции. 5

2.3 Восстановление СФА с неявной записью суперпозиции. 5

3. Основная структурная формула алгоритма. 6

3.1. Блок-схема алгоритма — горизонтальное исполнение. 7

3.2. Блок-схема алгоритма — вертикальное исполнение. 8

3.3. Штрих-схема алгоритма. 9

4. Общие данные структуры алгоритма: 10

5.2. Нумерация и группирование формульных оболочек схемы.. 11

6. Повышение взаимно однозначного соответствия структурных схем и структурных формул. 12

6.1. Введение явной операции fork. 12

6.2. Разделение парных операций fork и join. 13

6.3 Бесскобочная запись формул. 13

1. Исходное задание

Задан комплект структурных формул алгоритмов:

А581=Z₇((Z₁ & Z₆(Z₀&Z₃Z₆))& Z₇(Z₄ & Z₅)Z₇)

А582= Z₇((Z₁ & Z₆(Z₀&Z₃Z₆)) V Z₇(Z₄ & Z₅)Z₇)

Выполнить следующие задания:

1) По исходной формуле восстановить:

a) Стандартную СФА: полную инфиксную форму

b) Сокращенную СФА с явной записью суперпозиции

с) Сокращенную СФА с неявной записью суперпозиции

2) Провести контрольную проверку результатов.

3) Составить основнкю структурную схему алгоритма в виде:

a) БСА (ГИ): блок-схемы алгоритма (горизонтальное исполнение)

b) БСА (ВИ): блок-схемы алгоритма (вертикальное исполнение)

c) ШСА: штрих-схемы алгоритма

4) Составить таблицу общих данных штрих-схемы.

5) Составить оболочковую штрих-схему алгоритма.

6) Провести проверочную нумерацию блоков-оболочек СФА и отметить оболочки на ШСА

7) Повысить взаимно однозначное соответствие структурных формул и схем:

a) Путем введения явной операции fork.

b) Путем разделения парных операций fork-join.

с) Путем использования бесскобочной записи формул.

2. Восстановление стандартной СФА

Вариант 1

Исходная формула:

А581=Z₇((Z₁ & Z₆(Z₀&Z₃Z₆))& Z₇(Z₄ & Z₅)Z₇)

Поэтапная простановка операторов суперпозиции:

А581=Z₇ (( Z₁ & Z₆ ( Z₀ & Z₃ Z₆ )) & Z₇ ( Z₄ & Z₅ ) Z₇ )=

= Z₇ — (( Z₁ & Z₆ — ( Z₀ & Z₃ — Z₆ )) & Z₇ — ( Z₄ & Z₅ ) — Z₇ )

Простановка недостающих пар скобок: операторов объединения.

Z₇ — (( Z₁ & Z₆ — ( Z₀ & Z₃ — Z₆ )) & Z₇ — ( Z₄ & Z₅ ) — Z₇ ) =

= ( Z₇ — (( Z₁ & Z₆ — ( Z₀ & Z₃ — Z₆ )) & Z₇ — ( Z₄ & Z₅ ) — Z₇ ) ) =

= ( Z₇ — (( Z₁ & (Z₆ — ( Z₀ & ( Z₃ — Z₆ )))) & ( Z₇ — ( Z₄ & Z₅ ) — Z₇ )))

Вариант 2

Исходная формула:

А582=Z₇((Z₁& Z₆(Z₀&Z₃Z₆)) V Z₇(Z₄ & Z₅)Z₇)

Поэтапная простановка операторов суперпозиции:

А582=Z₇ (( Z₁ & Z₆ ( Z₀ & Z₃ Z₆ )) V Z₇ ( Z₄ & Z₅ ) Z₇ )=

= Z₇ — (( Z₁ & Z₆ — ( Z₀ & Z₃ — Z₆ )) V Z₇ — ( Z₄ & Z₅ ) — Z₇ )

Простановка недостающих пар скобок: операторов объединения.

Z₇ — (( Z₁ & Z₆ — ( Z₀ & Z₃ — Z₆ )) V Z₇ — ( Z₄ & Z₅ ) — Z₇ ) =

= ( Z₇ — (( Z₁ & Z₆ — ( Z₀ & Z₃ — Z₆ )) V Z₇ — ( Z₄ & Z₅ ) — Z₇ ) ) =

= ( Z₇ — (( Z₁ & ( Z₆ — ( Z₀ & ( Z₃ — Z₆ )))) V ( Z₇ — ( Z₄ & Z₅ ) — Z₇ )))

2.1. Контрольная проверка

Вариант 1

Упрощение формулы - неявное задание оператора суперпозиции:

A581 = ( Z₇ — (( Z₁ & ( Z₆ — ( Z₀ & ( Z₃ — Z₆ )))) & ( Z₇ — ( Z₄ & Z₅ ) — Z₇ ))) =

= ( Z₇ (( Z₁ & (Z₆ ( Z₀ & ( Z₃ Z₆ )))) & ( Z₇ ( Z₄ & Z₅ ) Z₇ )))

Проверка результатов - пошаговое снятие скобок:

A581 = ( Z₇ (( Z₁ & (Z₆ ( Z₀ & ( Z₃ Z₆ )))) & ( Z₇ ( Z₄ & Z₅ ) Z₇ ))) =

= ( Z₇ (( Z₁ & (Z₆ ( Z₀ & Z₃ Z₆ ))) & Z₇ ( Z₄ & Z₅ ) Z₇ )) =

= ( Z₇ (( Z₁ & Z₆ ( Z₀ & Z₃ Z₆ )) & Z₇ ( Z₄ & Z₅ ) Z₇ ))

Снятие внешних скобок:

A581 = ( Z₇ (( Z₁ & Z₆ ( Z₀ & Z₃ Z₆ )) & Z₇ ( Z₄ & Z₅ ) Z₇ )) =

= Z₇ (( Z₁ & Z₆ ( Z₀ & Z₃ Z₆ )) & Z₇ ( Z₄ & Z₅ ) Z₇

Вариант 2

Упрощение формулы - неявное задание оператора суперпозиции:

A582 = ( Z₇ — (( Z₁ & ( Z₆ — ( Z₀ & ( Z₃ — Z₆ )))) V ( Z₇ — ( Z₄ & Z₅ ) — Z₇ ))) =

= ( Z₇ (( Z₁ & ( Z₆ ( Z₀ & ( Z₃ Z₆ )))) V ( Z₇ ( Z₄ & Z₅ ) Z₇ )))

Проверка результатов - пошаговое снятие скобок:

A582 = ( Z₇ (( Z₁ & ( Z₆ ( Z₀ & ( Z₃ Z₆ )))) V ( Z₇ ( Z₄ & Z₅ ) Z₇ ))) =

= ( Z₇ (( Z₁ & ( Z₆ ( Z₀ & Z₃ Z₆ ))) V Z₇ ( Z₄ & Z₅ ) Z₇ )) =

= ( Z₇ (( Z₁ & Z₆ ( Z₀ & Z₃ Z₆ )) V Z₇ ( Z₄ & Z₅ ) Z₇ ))

Снятие внешних скобок:

A582 = ( Z₇ (( Z₁ & Z₆ ( Z₀ & Z₃ Z₆ )) V Z₇ ( Z₄ & Z₅ ) Z₇ )) =

= Z₇ (( Z₁ & Z₆ ( Z₀ & Z₃ Z₆ )) V Z₇ ( Z₄ & Z₅ ) Z₇ )

Примечание: формула точно соответствует исходной - отсюда можно сделать вывод, что все преобразования равносильны, и в процессе выполнения задания не были допущены ошибки.

2.2 Восстановление СФА с явной записью суперпозиции

Вариант 1

Исходная формула:

A581 = ( Z₇ — (( Z₁ V ( Z₆ — ( Z₀ & ( Z₃ — Z₆ )))) V ( Z₇ — ( Z₄ & Z₅ ) — Z₇ )))

Формула с явным указанием операции суперпозиции:

А581= ( Z₇ — (( Z₁ V ( Z₆ — ( Z₀ & ( Z₃ — Z₆ )))) V ( Z₇ — ( Z₄ & Z₅ ) — Z₇ ))) =

= ( Z₇ → (( Z₁ V ( Z₆ → ( Z₀ & ( Z₃ →Z₆ )))) V ( Z₇ → ( Z₄ & Z₅ ) →Z₇ )))

Вариант 2

Исходная формула:

A582 = ( Z₇ — (( Z₁ & ( Z₆ — ( Z₀ & ( Z₃ — Z₆ )))) V ( Z₇ — ( Z₄ & Z₅ ) — Z₇ )))

Формула с явным указанием операции суперпозиции:

А582= ( Z₇ — (( Z₁ & ( Z₆ — ( Z₀ & ( Z₃ — Z₆ )))) V ( Z₇ — ( Z₄ & Z₅ ) — Z₇ ))) =

= ( Z₇ → (( Z₁ & ( Z₆ → ( Z₀ & ( Z₃ →Z₆ )))) V ( Z₇ → ( Z₄ & Z₅ ) →Z₇ )))

2.3 Восстановление СФА с неявной записью суперпозиции

Вариант 1

Исходная формула:

A581 = ( Z₇ — (( Z₁ V ( Z₆ — ( Z₀ & ( Z₃ — Z₆ )))) V ( Z₇ — ( Z₄ & Z₅ ) — Z₇ )))

Формула с явным указанием операции суперпозиции:

А581= ( Z₇ — (( Z₁ V ( Z₆ — ( Z₀ & ( Z₃ — Z₆ )))) V ( Z₇ — ( Z₄ & Z₅ ) — Z₇ ))) =

= ( Z₇ (( Z₁ V ( Z₆ ( Z₀ & ( Z₃ Z₆ )))) V ( Z₇ ( Z₄ & Z₅ ) Z₇ )))

Вариант 2

Исходная формула:

A582 = ( Z₇ — (( Z₁ & ( Z₆ — ( Z₀ & ( Z₃ — Z₆ )))) V ( Z₇ — ( Z₄ & Z₅ ) — Z₇ )))

Формула с явным указанием операции суперпозиции:

А582= ( Z₇ — (( Z₁ & ( Z₆ — ( Z₀ & ( Z₃ — Z₆ )))) V ( Z₇ — ( Z₄ & Z₅ ) — Z₇ ))) =

= ( Z₇ (( Z₁ & ( Z₆ ( Z₀ & ( Z₃ Z₆ )))) V ( Z₇ ( Z₄ & Z₅ ) Z₇ )))

3. Основная структурная формула алгоритма

Исходная формула:

Вариант 1: А581=Z₇((Z₁ & Z₆(Z₀&Z₃Z₆))& Z₇(Z₄ & Z₅)Z₇)

Вариант 2: А582= Z₇((Z₁ & Z₆(Z₀&Z₃Z₆)) V Z₇(Z₄ & Z₅)Z₇)

Требуется:

1)                Составить БСА (ГИ): блок-схему алгоритма в горизонтальном исполнении.

2)                Составить БСА (ВИ): блок-схему алгоритма в вертикальном исполнении.

3)                Составить ШСА: Штрих-схему алгоритма.

Для выполнения работы был использован редактор MS Paint

3.1. Блок-схема алгоритма — горизонтальное исполнение

Вариант 1

А581=Z₇((Z₁ & Z₆(Z₀&Z₃Z₆)) & Z₇(Z₄ & Z₅)Z₇)

Вариант 2

А582= Z₇((Z₁ & Z₆(Z₀&Z₃Z₆)) V Z₇(Z₄&Z₅)Z₇)

3.2. Блок-схема алгоритма — вертикальное исполнение

Вариант 1

А581=Z₇((Z₁ & Z₆(Z₀&Z₃Z₆)) & Z₇(Z₄ & Z₅)Z₇)

Вариант 2

А582= Z₇((Z₁ & Z₆(Z₀&Z₃Z₆)) V Z₇(Z₄&Z₅)Z₇)

3.3. Штрих-схема алгоритма

Вариант 1

А581=Z₇((Z₁ & Z₆(Z₀&Z₃Z₆)) & Z₇(Z₄ & Z₅)Z₇)

Вариант 2

А582= Z₇((Z₁ & Z₆Z₀&Z₃Z₆)) V Z₇(Z₄&Z₅)Z₇)

4. Общие данные структуры алгоритма

Показатели	Значения	Примечания
Общее число команд	10
Число разных команд	7	Есть повторные вхождения команд
Общее число элементов	18	Включая узлы вилки и сборки
Число пар операций распараллеливания	4	#& - 3 набора #V — 1 набор
Степень параллелизма	3	Три параллельные ветви алгоритма
Наличие дизъюнктивных сборок	вариант 1 — нет вариант 2 — есть	Нет особенностей Есть 1 особый узел

5. Группирование элементов схемы

5.1. Группирование через оболочки схемы

Выполняется только вариант 2. Структурная формула (из п. 2):

A582 = ( Z₇ — (( Z₁ & ( Z₆ — ( Z₀ & ( Z₃ — Z₆ )))) V ( Z₇ — ( Z₄ & Z₅ ) — Z₇ )))

Штрих-схема алгоритма с наложением схемных оболочек:

5.2. Нумерация и группирование формульных оболочек схемы

Структурная формула в полной инфиксной форме (из п.2):

A582 = ( Z₇ — (( Z₁ & ( Z₆ — ( Z₀ & ( Z₃ — Z₆ )))) V ( Z₇ — ( Z₄ & Z₅ ) — Z₇ )))