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

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

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

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

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

МЛТА: Математическая логика и теория алгоритмов

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

Общая тема:

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

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

Часть 2

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

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

5033.7541.0000-ПЗ

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

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

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

220200: АСОИиУ: Автоматизированные системы обработки информации и управления

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

Учебная группа: АСОИ-231

Работу выполнил студент Абдрахманов Р. С.

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

Вариант задания: A020

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

2007 г.

1. Исходные положения

1.1 Исходные данные для выполнения работы

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

Исходной основой выполнения работы является структурная формула алгоритма (СФА) согласно выданному варианту задания.  

A020 = Z₂((Z₃&Z₁(Z₅&Z₄)) ­¹Z₁ V Z₂(Z₆&Z₇¯_&¹Z₂))  

Предусматривается проработка 3-х вариантов СФА (A021, A022, A023).

Данная формула представляет 3-й вариант СФА: A600 = A603.

Промежуточный 2-й вариант (A022) СФА получается удалением вертикальных стрелок ¯_&¹, ­¹ с индексами (дополнительных проходных связей):

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

Начальный 1-й вариант (A021) СФА — знак дизъюнкции V (Или) меняется на знак конъюнкции & (И), получается только конъюнктивная форма:

A021 = Z₂((Z₃&Z₁(Z₅&Z₄))Z₁ & Z₂(Z₆&Z₇Z₂))  

Комплект трех вариантов структурной формулы

В целом определяются 3 варианта СФА задания.

а) Тема 1: Базовые структуры — двухполюсные, ациклические, постоянные:

A021 = Z₂((Z₃&Z₁(Z₅&Z₄))Z₁ & Z₂(Z₆&Z₇Z₂))  

1-й вариант СФА A020

// обычные параллельные структуры с замыканием параллельных ветвей алгоритмов по конъюнкции & (логической функции И);

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

2-й вариант СФА A020

// проблемы замыкания по дизъюнкции V (логической функции ИЛИ).

б) Тема 2: Элементы многополюсных структур:

A023 = A020 = Z₂((Z₃&Z₁(Z₅&Z₄)) ­¹Z₁ V Z₂(Z₆&Z₇¯_&¹Z₂))  

3-й вариант СФА A020

СФА: Структурная формула алгоритма / У: Поток управления

ИнФ: Инфиксная форма (записи СФА)

СИнФ: Сокращенная инфиксная форма

// Неявная операция суперпозиции

Нижние (подстрочные) индексы — согласно заданию

A021 = Z₂((Z₃&Z₁(Z₅&Z₄))Z₁ & Z₂(Z₆&Z₇Z₂))  

1-й вариант СФА A020

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

2-й вариант СФА A020

Строчные индексы — рабочая форма

A021 = Z₂((Z₃&Z₁(Z₅&Z₄))Z₁ & Z₂(Z₆&Z₇Z₂)) =

= Z2((Z3&Z1(Z5&Z4))Z1 & Z2(Z6&Z7Z2))

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

= Z2((Z3&Z1(Z5&Z4))Z1 V Z2(Z6&Z7Z2))

РМУ 0.1 Пробелы между символами

Между любыми символами (лексемами) формулы допускается любое число пробелов (нуль или более). Например:

СФА: Структурная формула алгоритма

Простановка пробелов:

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

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

= Z2((Z3&Z1(Z5&Z4))Z1 V Z2(Z6&Z7Z2)) =

= Z2 ((Z3 & Z1 (Z5 & Z4)) Z1 V Z2 (Z6 & Z7 Z2))

Базисные структуры параллельных алгоритмов

1.2 Исходные структурные формулы параллельных алгоритмов

Стандартная форма формулы алгоритма

По исходной СФА строится стандартная СФА — полная инфиксная форма.

СФА: Структурная формула алгоритма / У: Поток управления

ИнФ: Инфиксная форма записи формулы

СИнФ: Сокращенная инфиксная форма // исходная форма

// Неявная операция суперпозиции

Вариант 1 (A021):

A021 = Z2 ((Z3 & Z1 (Z5 & Z4)) Z1 & Z2 (Z6 & Z7 Z2))

Вариант 2 (A022):

A022 = Z2 ((Z3 & Z1 (Z5 & Z4)) Z1 V Z2 (Z6 & Z7 Z2))

ПИнФ: Полная инфиксная форма // пошаговое построение

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

Вариант 1 (A021)

= Z2 ((Z3 & Z1 (Z5 & Z4)) Z1 & Z2 (Z6 & Z7 Z2)) =

Вариант 2 (A022)

= Z2 ((Z3 & Z1 (Z5 & Z4)) Z1 V Z2 (Z6 & Z7 Z2))=

// Последовательная запись операторов соответствует

// операция суперпозиции " — " (" ® ") — логическая связка следования "затем"

Простановка недостающих пар скобок (скобочных оболочек):

// Приоритет операции суперпозиции (®, —>, —) выше приоритета операций

// операций конъюнкции (&) и дизъюнкции (V)

Вариант 1 (A021)

= Z2 - ((Z3 & Z1 - (Z5 & Z4)) - Z1 & Z2 - (Z6 & Z7 - Z2)) =

= Z2 - ((Z3 & Z1 - (Z5 & Z4)) - Z1 & Z2 - (Z6 & (Z7 - Z2))) =

= Z2 - ((Z3 & (Z1 - (Z5 & Z4))) - Z1 & Z2 - (Z6 & (Z7 - Z2))) =

= Z2 - (((Z3 & (Z1 - (Z5 & Z4))) - Z1) & Z2 - (Z6 & (Z7 - Z2))) =

= Z2 - (((Z3 & (Z1 - (Z5 & Z4))) - Z1) & (Z2 - (Z6 & (Z7 - Z2)))) =

= (Z2 - (((Z3 & (Z1 - (Z5 & Z4))) - Z1) & (Z2 - (Z6 & (Z7 - Z2)))))

Вариант 2 (A022)

= Z2 - ((Z3 & Z1 - (Z5 & Z4)) - Z1 V Z2 - (Z6 & Z7 - Z2)) =

= Z2 - ((Z3 & Z1 - (Z5 & Z4)) - Z1 V Z2 - (Z6 & (Z7 - Z2))) =

= Z2 - ((Z3 & (Z1 - (Z5 & Z4))) - Z1 V Z2 - (Z6 & (Z7 - Z2))) =

= Z2 - (((Z3 & (Z1 - (Z5 & Z4))) - Z1) V Z2 - (Z6 & (Z7 - Z2))) =

= Z2 - (((Z3 & (Z1 - (Z5 & Z4))) - Z1) V (Z2 - (Z6 & (Z7 - Z2)))) =

= (Z2 - (((Z3 & (Z1 - (Z5 & Z4))) - Z1) V (Z2 - (Z6 & (Z7 - Z2)))))

Основная стандартная форма записи СФА

Вариант 1 (A021)

Явная операция суперпозиции:

A021 = (Z2 ® (((Z3 & (Z1 ® (Z5 & Z4))) ® Z1) & (Z2 ® (Z6 & (Z7 ® Z2)))))

Неявная операция суперпозиции:

A021 = (Z2(((Z3 & (Z1(Z5 & Z4)))Z1) & (Z2(Z6 & (Z7Z2)))))

Вариант 2 (A022)

Явная операция суперпозиции:

A022 = (Z2 ® (((Z3 & (Z1 ® (Z5 & Z4))) ® Z1) V (Z2 ® (Z6 & (Z7 ® Z2)))))

Неявная операция суперпозиции:

A022 = (Z2(((Z3 & (Z1(Z5 & Z4)))Z1) V (Z2(Z6 & (Z7Z2)))))

Контроль результатов

Выполняются обратные (контрольные) упрощения записи.

СФА: Вариант 1 (A021)

Удаление знака суперпозиции:

A021 = (Z2(((Z3 & (Z1(Z5 & Z4)))Z1) & (Z2(Z6 & (Z7Z2))))) =

Удаление внешних скобок:

= Z2(((Z3 & (Z1(Z5 & Z4)))Z1) & (Z2(Z6 & (Z7Z2)))) =

Пошаговое удаление скобок для суперпозиции:

= Z2(((Z3 & (Z1(Z5 & Z4)))Z1) & (Z2(Z6 & Z7Z2))) =

= Z2(((Z3 & Z1(Z5 & Z4))Z1) & (Z2(Z6 & Z7Z2))) =

= Z2((Z3 & Z1(Z5 & Z4))Z1 & (Z2(Z6 & Z7Z2))) =

= Z2((Z3 & Z1(Z5 & Z4))Z1 & Z2(Z6 & Z7Z2))

СФА 0.1: Вариант 2 (A022) — аналогично:

A022 = (Z2(((Z3 & (Z1(Z5 & Z4)))Z1) V (Z2(Z6 & (Z7Z2))))) =

Удаление внешних скобок:

= Z2(((Z3 & (Z1(Z5 & Z4)))Z1) V (Z2(Z6 & (Z7Z2)))) =

Пошаговое удаление скобок для суперпозиции:

= Z2(((Z3 & (Z1(Z5 & Z4)))Z1) V (Z2(Z6 & Z7Z2))) =

= Z2(((Z3 & Z1(Z5 & Z4))Z1) V (Z2(Z6 & Z7Z2))) =

= Z2((Z3 & Z1(Z5 & Z4))Z1 V (Z2(Z6 & Z7Z2))) =

= Z2((Z3 & Z1(Z5 & Z4))Z1 V Z2(Z6 & Z7Z2))

1. 2 Автоматизация построений основной схемы алгоритма

Исходные условия

Выполняется работа с программой GRAMPRAL.

В программу вводятся СФА в полном формате:

ПИнФ: Полная инфиксная форма — с явными операциями суперпозиции (—) и всеми необходимыми парами скобок (внешние скобки могут не вводиться).

Вариант 1 структурной схемы. Автоматизация построений

СФА: Структурная формула алгоритма / У: Поток управления

// Замена обозначений: "®" на "—"

A021 = (Z2 ® (((Z3 & (Z1 ® (Z5 & Z4))) ® Z1) & (Z2 ® (Z6 & (Z7 ® Z2)))))

A021 = (Z2 - (((Z3 & (Z1 - (Z5 & Z4))) - Z1) & (Z2 - (Z6 & (Z7 - Z2)))))

Набор формулы:

 

Настройки программы: ИнФ / ГИ / БСА / БФ

БСА: Блок-схема алгоритма / ГИ: Горизонтальное исполнение

Настройки: ИнФ / ГИ / ШСА / БФ

ШСА: Штрих-схема алгоритма / ГИ: Горизонтальное исполнение

 

Вариант 2 структурной схемы. Автоматизация построений

СФА: Структурная формула алгоритма / У: Поток управления

A022 = (Z2 ® (((Z3 & (Z1 ® (Z5 & Z4))) ® Z1) V (Z2 ® (Z6 & (Z7 ® Z2)))))

A022 = (Z2 - (((Z3 & (Z1 - (Z5 & Z4))) - Z1) V (Z2 - (Z6 & (Z7 - Z2)))))

Набор формулы

 

Настройки: ИнФ / ГИ / БСА / БФ

БСА: Блок-схема алгоритма / ГИ: Горизонтальное исполнение

 

Настройки: ИнФ / ГИ / ШСА / БФ

ШСА: Штрих-схема алгоритма / ГИ: Горизонтальное исполнение

 

1.4       Анализ структурной схемы

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

а) Структурный класс алгоритма:

двухполюсный постоянный ациклический алгоритм;

постоянная структура — это алгоритмическая структура с отсутствие переключательных элементов типа "если ... то", циклов с предусловием и т.п.

б) Общие структурные показатели

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

1.5       Проверочная нумерация оболочек формул и схем

 

Вложенность формульных оболочек

Для контроля правильности построений используются различные способы нумерации формульных оболочек — пар скобок " (i … )i " = " (_i … )_i "

СФА 0.2: Структурная формула алгоритма — нумерация оболочек:

а) Внешняя (пристроенная) нумерация оболочек формулы

1)    Первая строка нумерации — уровень вложенности блоков

A022 = (Z2 - ( ( (Z3 & (Z1 - (Z5 & Z4) ) ) - Z1) V (Z2 - (Z6 & (Z7 - Z2) ) ) ) )

1 234 5 6 654 3 7 8 9 98721

2)    Вторая строка нумерации — разные блоки одного уровня

A022 = (Z2 - ( ( (Z3 & (Z1 - (Z5 & Z4) ) ) - Z1) V (Z2 - (Z6 & (Z7 - Z2) ) ) ) )

1 234 5 6 654 3 3 4 5 54321

12 3 32 1 4 5 6 654

б) Внутренняя (встроенная) нумерация оболочек формулы

A022 = (1Z2-(2(3(4Z3&(5Z1-(6Z5&Z46)5)4)-Z13) V (7Z2-(8Z6&(9Z7-Z29)8)7)2)1) =

= (₁Z2 - (₂ (₃ (₄Z3 & (₅Z1 - (₆Z5 & Z4₆)₅)₄) - Z1₃) V (₇Z2 - (₈Z6 & (₉Z7 - Z2₉) ₈) ₇) ₂) ₁)

 Вложенность схемных оболочек

Соответственно нумерации формульных оболочек выполняется нумерация

схемных оболочек. Целесообразна двухсторонняя нумерация схемных блоков.

ССА 0.1: Структурная схема алгоритма

Явная операция разделения (вилки) потоков

В сопоставлении СФА со ССА выявляется неявная операция разделения (вилки) потоков — распараллеливания алгоритмических цепей:

СФА 0.3: Структурная формула алгоритма / У: Поток управления

ИнФ: Инфиксная форма записи формулы

ПИнФ: Полная инфиксная форма // пошаговое построение

Неявная операция разделения (подразумевается)

A022 = (Z2 ® (((Z3 & (Z1 ® (Z5 & Z4))) ® Z1) V (Z2 ® (Z6 & (Z7 ® Z2))))) =

Явная простановка операции разделения (вилки)

= (Z2 ® (((Z3 _#& (Z1 ® (Z5 _#& Z4))) ® Z1) _#V (Z2 ® (Z6 _#& (Z7 ® Z2))))) =

= (Z2 ® (((Z3 #& (Z1 ® (Z5 #& Z4))) ® Z1) #V (Z2 ® (Z6 #& (Z7 ® Z2)))))

Основная стандартная форма записи СФА:

Строчная индексация:

A022 = (Z2 ® (((Z3 _#& (Z1 ® (Z5 _#& Z4))) ® Z1) _#V (Z2 ® (Z6 _#& (Z7 ® Z2))))) Подстрочная индексация (нижние индексы) и упрощения записи:

A602 = (Z2 - (((Z3 #& (Z1 - (Z5 #& Z4))) - Z1) #V (Z2 - (Z6 #& (Z7 - Z2))))) =

= Z2 - (((Z3 #& (Z1 - (Z5 #& Z4))) - Z1) #V (Z2 - (Z6 #& (Z7 - Z2)))) =

= Z2(((Z3 #& (Z1(Z5 #& Z4)))Z1) #V (Z2(Z6 #& Z7Z2))) =

= Z2(((Z3 #& Z1(Z5 #& Z4))Z1) #V (Z2(Z6 #& Z7Z2))) =

= Z2((Z3 #& Z1(Z5 #& Z4))Z1 #V (Z2(Z6 #& Z7Z2))) =

= Z2((Z3 #& Z1(Z5 #& Z4))Z1 #V Z2(Z6 #& Z7Z2))

Разделение парных операций

// Выполняется только Вариант 2

Выше все три операции представлены в инфиксной форме.

Вводится комбинированные способы записи разных операций.

СФА 0.4: Структурная формула алгоритма / У: Поток управления

КоФ: Комбинированная форма записи формулы

ИнПрПоФ: Инфиксно-префиксно-постфиксная форма

// Пошаговое построение

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

A022 = (Z2 - (((Z3 #& (Z1 - (Z5 #& Z4))) - Z1) #V (Z2 - (Z6 #& (Z7 - Z2))))) =

Разносится более глубоко вложенная пара операций #&:

= (Z2 - ((#(Z3,(Z1 - #(Z5,Z4)&))& - Z1) #V (Z2 - #(Z6,(Z7 - Z2))&))) =

Разносится менее глубоко вложенная пара операций #V:

= (Z2-#((#(Z3,(Z1-#(Z5,Z4)&))&-Z1),(Z2-#(Z6,(Z7-Z2))&))V)

// Суперпозиция (®) сохраняется в инфиксе.

// Разделение (# — вилка) потоков выносится в префикс (влево).

// Соединение (сборка) по конъюнкции (&) и дизъюнкции (V)

// выносятся в постфикс (вправо).

Конечные результаты:

Строчная индексация:

A022 = (Z2-#((#(Z3,(Z1-#(Z5,Z4)&))&-Z1),(Z2-#(Z6,(Z7-Z2))&))V)

Подстрочная индексация (нижние индексы) и упрощения записи:

A022 = (Z2-#((#(Z3,(Z1-#(Z5,Z4)&))&-Z1),(Z2-#(Z6,(Z7-Z2))&))V)

A022 = (Z2#((#(Z3,(Z1#(Z5,Z4)&))&Z1),(Z2#(Z6,(Z7Z2))&))V)

A022 = (Z2#((#(Z3,(Z1#(Z5,Z4)&))&Z1),(Z2#(Z6,Z7Z2)&))V)

A022 = (Z2#((#(Z3,Z1#(Z5,Z4)&)&Z1),(Z2#(Z6,Z7Z2)&))V)

A022 = (Z2#((#(Z3,Z1#(Z5,Z4)&)&Z1),Z2#(Z6,Z7Z2)&)V)

A022 = (Z2#(#(Z3,Z1#(Z5,Z4)&)&Z1,Z2#(Z6,Z7Z2)&)V)

A022 = Z2#(#(Z3,Z1#(Z5,Z4)&)&Z1,Z2#(Z6,Z7Z2)&)V

1.6       Работа с тренажером схемных построений

Мозаичный набор схем

Используется программа TRENTEST — графический тренажер-тестер.

Выполняется мозаичный набор структурных схем.

Вариант 1

СФА 0.5: Структурная формула алгоритма

A021 = (Z2 - (((Z3 & (Z1 - (Z5 & Z4))) - Z1) & (Z2 - (Z6 & (Z7 - Z2)))))

A021 = (Z2 ® (((Z3 & (Z1 ® (Z5 & Z4))) ® Z1) & (Z2 ® (Z6 & (Z7 ® Z2)))))

ССА 0.2: Структурная схема алгоритма

ШСА 0.1: Штрих-схема алгоритма

 

Вариант 2

СФА 0.6: Структурная формула алгоритма

A022 = (Z2 - (((Z3 & (Z1 - (Z5 & Z4))) - Z1) V (Z2 - (Z6 & (Z7 - Z2)))))

A022 = (Z2 ® (((Z3 & (Z1 ® (Z5 & Z4))) ® Z1) V (Z2 ® (Z6 & (Z7 ® Z2)))))

ССА 0.3: Структурная схема алгоритма

ШСА 0.2: Штрих-схема алгоритма