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

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

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

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

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

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

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

Общая тема:

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

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

Часть 1

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

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

5033.7162.0000-ПЗ

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

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

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

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

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

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

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

студент _____________ Хорев В. А.

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

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

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

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. Исходное задание

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

А391=Z₉(Z₁Z₂&(Z₇&Z₈)&(Z₄Z₉&Z₅))(Z₄&Z₉)

А392=Z₉(Z₁Z₂V(Z₇&Z₈)V(Z₄Z₉&Z₅))(Z₄&Z₉)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вариант 1

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

А391= Z₉(Z₁Z₂&(Z₇&Z₈)&(Z₄Z₉&Z₅))(Z₄&Z₉)

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

А391= 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₉) ) =

= (Z₉ — ( ( Z₁ — Z₂ ) & (Z₇ & Z₈) & ( ( Z₄ — Z₉ ) & Z₅) ) — (Z₄ & Z₉) )

Вариант 2

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

А391= Z₉(Z₁Z₂V(Z₇&Z₈)V(Z₄Z₉&Z₅))(Z₄&Z₉)

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

А391= Z₉ ( Z₁ Z₂ V (Z₇ & Z₈ ) V ( Z₄ Z₉ & Z₅ ) ) ( Z₄ & Z₉ ) =

= Z₉  — ( Z₁ — Z₂ V (Z₇ & Z₈) V ( Z₄ — Z₉ & Z₅ ) ) — ( Z₄ & Z₉ )

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

Z₉ — (Z₁ — Z₂ V (Z₇ & Z₈) V (Z₄ — Z₉ & Z₅) ) — (Z₄ & Z₉) =

= ( Z₉ — (Z₁ — Z₂ V (Z₇ & Z₈) V (Z₄ — Z₉ & Z₅) ) — (Z₄ & Z₉) ) =

= (Z₉ — ( ( Z₁ — Z₂ ) V (Z₇ & Z₈) V (Z₄ — Z₉ & Z₅) ) — (Z₄ & Z₉) ) =

= (Z₉ — ( ( Z₁ — Z₂ ) V (Z₇ & Z₈) V ( ( Z₄ — Z₉ ) & Z₅) ) — (Z₄ & Z₉) )

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

Вариант 1

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

A391 = ( Z₉ ( ( Z₁ — Z₂ ) & (Z₇ & Z₈) & ( ( Z₄ — Z₉ ) & Z₅) ) — (Z₄ & Z₉) ) =

= ( Z₉ ( ( Z₁ Z₂ ) & (Z₇ & Z₈) & ( ( Z₄ Z₉ ) & Z₅) ) (Z₄ & Z₉) )

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

A391 = ( 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₉) )

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

A391 = ( Z₉ ( Z₁ Z₂ & (Z₇ & Z₈) & ( Z₄ Z₉ & Z₅) ) (Z₄ & Z₉) ) =

= Z₉ ( Z₁ Z₂ & (Z₇ & Z₈) & ( Z₄ Z₉ & Z₅) ) (Z₄ & Z₉)

Вариант 2

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

A391 = ( Z₉ ( ( Z₁ — Z₂ ) V (Z₇ & Z₈) & ( ( Z₄ — Z₉ ) & Z₅) ) (Z₄ & Z₉) ) =

= ( Z₉ ( ( Z₁ Z₂ ) V (Z₇ & Z₈) V ( ( Z₄ Z₉ ) & Z₅) ) (Z₄ & Z₉) )

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

A391 = ( Z₉ ( ( Z₁ Z₂ ) V (Z₇ & Z₈) V ( ( Z₄ Z₉ ) & Z₅) ) (Z₄ & Z₉) ) =

= ( Z₉ ( Z₁ Z₂ V (Z₇ & Z₈) V ( ( Z₄ Z₉ ) & Z₅) ) (Z₄ & Z₉) ) =

= ( Z₉ ( Z₁ Z₂ V (Z₇ & Z₈) V ( Z₄ Z₉ & Z₅) ) (Z₄ & Z₉) )

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

A391 = ( Z₉ ( Z₁ Z₂ & (Z₇ & Z₈) & ( Z₄ Z₉ & Z₅) ) (Z₄ & Z₉) ) =

= Z₉ ( Z₁ Z₂ & (Z₇ & Z₈) & ( Z₄ Z₉ & Z₅) ) (Z₄ & Z₉)

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

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

Вариант 1

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

A391 = (Z₉ — ( ( Z₁ — Z₂ ) & (Z₇ & Z₈) & ( ( Z₄ — Z₉ ) & Z₅) ) — (Z₄ & Z₉) )

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

А391= (Z₉ — ( ( Z₁ — Z₂ ) & (Z₇ & Z₈) & ( ( Z₄ — Z₉ ) & Z₅) ) — (Z₄ & Z₉) ) =

= (Z₉ → ( ( Z₁ → Z₂ ) & (Z₇ & Z₈) & ( ( Z₄ → Z₉ ) & Z₅) ) → (Z₄ & Z₉) )

Вариант 2

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

A391 = (Z₉ ( ( Z₁ — Z₂ ) V (Z₇ & Z₈) V ( ( Z₄ — Z₉ ) & Z₅) ) — (Z₄ & Z₉) )

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

А391= (Z₉ — ( ( Z₁ — Z₂ ) V (Z₇ & Z₈) V ( ( Z₄ — Z₉ ) & Z₅) ) — (Z₄ & Z₉) ) =

= (Z₉ → ( ( Z₁ → Z₂ ) V (Z₇ & Z₈) V ( ( Z₄ → Z₉ ) & Z₅) ) → (Z₄ & Z₉) )

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

Вариант 1

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

A391 = (Z₉ — ( ( Z₁ — Z₂ ) & (Z₇ & Z₈) & ( ( Z₄ — Z₉ ) & Z₅) ) — (Z₄ & Z₉) )

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

А391= (Z₉ — ( ( Z₁ — Z₂ ) & (Z₇ & Z₈) & ( ( Z₄ — Z₉ ) & Z₅) ) — (Z₄ & Z₉) ) =

= (Z₉ ( ( Z₁ Z₂ ) & (Z₇ & Z₈) & ( ( Z₄ Z₉ ) & Z₅) ) (Z₄ & Z₉) )

Вариант 2

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

A391 = (Z₉ — ( ( Z₁ — Z₂ ) V (Z₇ & Z₈) V ( ( Z₄ — Z₉ ) & Z₅) ) — (Z₄ & Z₉) )

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

А391= (Z₉ — ( ( Z₁ — Z₂ ) V (Z₇ & Z₈) V ( ( Z₄ — Z₉ ) & Z₅) ) — (Z₄ & Z₉) ) =

= (Z₉ — ( ( Z₁ Z₂ ) V (Z₇ & Z₈) V ( ( Z₄ Z₉ ) & Z₅) ) (Z₄ & Z₉) )

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

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

Вариант 1: А391=Z₉(Z₁Z₂&(Z₇&Z₈)&(Z₄Z₉&Z₅))(Z₄&Z₉)

Вариант 2: А392=Z₉(Z₁Z₂V(Z₇&Z₈)V(Z₄Z₉&Z₅))(Z₄&Z₉)

Требуется:

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

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

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

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

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

Вариант 1

А391=Z₉(Z₁Z₂&(Z₇&Z₈)&(Z₄Z₉&Z₅))(Z₄&Z₉)

 

Вариант 2

А392=Z₉(Z₁Z₂V(Z₇&Z₈)V(Z₄Z₉&Z₅))(Z₄&Z₉)

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

Вариант 1

А391=Z₉(Z₁Z₂&(Z₇&Z₈)&(Z₄Z₉&Z₅))(Z₄&Z₉)

Вариант 2

А392=Z₉(Z₁Z₂V(Z₇&Z₈)V(Z₄Z₉&Z₅))(Z₄&Z₉)

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

Вариант 1

А391=Z₉(Z₁Z₂&(Z₇&Z₈)&(Z₄Z₉&Z₅))(Z₄&Z₉)

Вариант 2

А392=Z₉(Z₁Z₂V(Z₇&Z₈)V(Z₄Z₉&Z₅))(Z₄&Z₉)

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

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

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

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

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

A392 = ( Z₉ — ( ( Z₁ — Z₂ ) V (Z₇ & Z₈) & ( ( Z₄ — Z₉ ) & Z₅) ) — (Z₄ & Z₉) )

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