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

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

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

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

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

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

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

Общая тема:

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

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

Часть 2

ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ.

ВРЕМЕННЫЕ ДИАГРАММЫ.

(техника построений,

параметрический расчет и анализ)

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

5033.7219.0000-ПЗ

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

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

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

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

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

Учебная группа:

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

студентка _____________ фио

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

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

Работу принял

должность _____________ Житников А.П.

2007

1                    Структурные формулы алгоритмов

1.1                Индивидуальное задание

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

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

А501 = Z₁((Z₃Z₁ V Z₅) & Z₂ (Z₄(Z₂ & Z₈) & Z₇Z₅)) 1-й вариант СФА

группы A500

A502 = Z₁((Z₃Z₁ & Z₅) & Z₂ (Z₄(Z₂ & Z₈) & Z₇Z₅)) 2-й вариант СФА

группы A500

A503 = Z₁((Z₃  ¯_&¹ Z₁ V Z₅) & Z₂ (Z₄(Z₂ & Z₈) & Z₇­¹Z₅)) 3-й вариант СФА группы A500

1.2                Восстановление стандартной формы структурных формул

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

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

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

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

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

А501 = Z1((Z3Z1 V Z5) & Z2(Z4(Z2 & Z8) & Z7Z5)) =

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

А502 = Z1((Z3Z1 & Z5) & Z2(Z4(Z2 & Z8) & Z7Z5)) =

ПИнФ: Полная инфиксная форма

Вариант 1 (A501)

= Z1 - ((Z3 - Z1 V Z5) & Z2 - (Z4 - (Z2 & Z8) & Z7 - Z5)) = Вариант 2 (A502)

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

Вариант 1 (A501)

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

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

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

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

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

Вариант 2 (A502)

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

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

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

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

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

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

Вариант 1 (A501)

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

A501 = (Z1 ® (((Z3 ® Z1) V Z5) & (Z2 ® ((Z4 ® (Z2 & Z8)) & (Z7 ® Z5))))) =

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

= (Z1(((Z3Z1) V Z5) & (Z2((Z4(Z2 & Z8)) & (Z7Z5)))))

Вариант 2 (A502)

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

A502 =(Z1 ® (((Z3 ® Z1) & Z5) & (Z2 ® ((Z4 ® (Z2 & Z8)) & (Z7 ® Z5))))) =

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

= (Z1(((Z3Z1) & Z5) & (Z2((Z4(Z2 & Z8)) & (Z7Z5)))))

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

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

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

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

A501 =(Z1(((Z3Z1) V Z5) & (Z2((Z4(Z2 & Z8)) & (Z7Z5))))) =

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

= Z1(((Z3Z1) V Z5) & (Z2((Z4(Z2 & Z8)) & (Z7Z5)))) =

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

= Z1((Z3Z1 V Z5) & (Z2((Z4(Z2 & Z8)) & (Z7Z5)))) =

= Z1((Z3Z1 V Z5) & (Z2((Z4(Z2 & Z8)) & Z7Z5))) =

= Z1((Z3Z1 V Z5) & (Z2(Z4(Z2 & Z8) & Z7Z5))) =

= Z1((Z3Z1 V Z5) & Z2(Z4(Z2 & Z8) & Z7Z5))

СФА 1.3: Вариант 2 (A502)

A502 =(Z1(((Z3Z1) & Z5) & (Z2((Z4(Z2 & Z8)) & (Z7Z5))))) =

= Z1(((Z3Z1) & Z5) & (Z2((Z4(Z2 & Z8)) & (Z7Z5)))) =

= Z1((Z3Z1 & Z5) & (Z2((Z4(Z2 & Z8)) & (Z7Z5)))) =

= Z1((Z3Z1 & Z5) & (Z2((Z4(Z2 & Z8)) & Z7Z5))) =

= Z1((Z3Z1 & Z5) & (Z2(Z4(Z2 & Z8) & Z7Z5))) =

= Z1((Z3Z1 & Z5) & Z2(Z4(Z2 & Z8) & Z7Z5))

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

2.1                                   Основная схема (без схемных оболочек). Ручные построения

Вариант 1 структурной схемы (A501). Ручные построения

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

A501 = (Z1 ® (((Z3 ® Z1) V Z5) & (Z2 ® ((Z4 ® (Z2 & Z8)) & (Z7 ® Z5)))))

A501 = (Z1(((Z3Z1) V Z5) & (Z2((Z4(Z2 & Z8)) & (Z7Z5)))))

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

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

 

БСА 2.2: Блок-схема алгоритма

ВИ: Вертикальное исполнение

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

ГИ: Горизонтальное исполнение

 

Вариант 2 структурной схемы (A502). Ручные построения

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

A502 = (Z1 ® (((Z3 ® Z1) & Z5) & (Z2 ® ((Z4 ® (Z2 & Z8)) & (Z7 ® Z5)))))

A502 = (Z1(((Z3Z1) & Z5) & (Z2((Z4(Z2 & Z8)) & (Z7Z5)))))

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

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

БСА 2.4: Блок-схема алгоритма

ВИ: Вертикальное исполнение

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

ГИ: Горизонтальное исполнение

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

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

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

A501 = (Z1 ® (((Z3 ® Z1) V Z5) & (Z2 ® ((Z4 ® (Z2 & Z8)) & (Z7 ® Z5)))))

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

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

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

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

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

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

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

A502 = (Z1 ® (((Z3 ® Z1) & Z5) & (Z2 ® ((Z4 ® (Z2 & Z8)) & (Z7 ® Z5)))))

A502 = (Z1 - (((Z3 - Z1) & Z5) & (Z2 - ((Z4 - (Z2 & Z8)) & (Z7 - Z5)))))

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

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

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

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

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

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

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

Группирование элементов схемы — оболочковые схемы

Исходные данные

Анализ структуры алгоритма проводится по СФА и ШСА с применением группирования элементов ШСА оболочками блоков (соответственно скобкам).

Вариант 1 структурной схемы.

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

A501 = (Z1 ® (((Z3 ® Z1) V Z5) & (Z2 ® ((Z4 ® (Z2 & Z8)) & (Z7 ® Z5)))))

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

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

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

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

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

Вариант 2

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

A502 = (Z1 ® (((Z3 ® Z1) & Z5) & (Z2 ® ((Z4 ® (Z2 & Z8)) & (Z7 ® Z5)))))

A502 = (Z1 - (((Z3 - Z1) & Z5) & (Z2 - ((Z4 - (Z2 & Z8)) & (Z7 - Z5)))))

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

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

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

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

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

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

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

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

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

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

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

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

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

A502 = (Z1 - (((Z3 - Z1) & Z5) & (Z2 - ((Z4 - (Z2 & Z8)) & (Z7 - Z5)))))

1 234 4 3 5 67 8 87 9 96521

1 1 2 2

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

A502 = (1 Z1 - (2(3(4 Z3 - Z1)4 & Z5)3 & (5 Z2 - (6(7 Z4 - (8 Z2 & Z8)8)7 & (9 Z7 - Z5)9)6)5)2)1 =

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

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

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

ШСА 2.9: Штрих-схема алгоритма — нумерация оболочек

3                                   Повышение взаимного соответствия
стурктурных формул и схем

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

// Выполняется только Вариант 2 (с разными типами операций)

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

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

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

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

A502 = (Z1 ® (((Z3 ® Z1) & Z5) & (Z2 ® ((Z4 ® (Z2 & Z8)) & (Z7 ® Z5)))))

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

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

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

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

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

A502 = (Z1 ® (((Z3 ® Z1) #& Z5) #& (Z2 ® ((Z4 ® (Z2 #& Z8)) #& (Z7 ® Z5)))))

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

A502 = (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₅))) =

= Z₁((Z₃Z₁ #& Z₅) #& Z₂(Z₄(Z₂ #& Z₈) #& Z₇Z₅))

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

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

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

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

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

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

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

A502 = (Z₁ - (((Z₃ - Z₁) #V Z₅) #& (Z₂ - ((Z₄ - (Z₂ #& Z₈)) #& (Z₇ - Z₅)))))=

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

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

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

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

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

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

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

A502 = (Z1 ® #((#(Z3 ® Z1) ,Z5)V ,#(Z2 ® ((Z4 ® #(Z2 , Z8)&) ,#(Z7 ® Z5) &)&)))

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

A502 = (Z₁ ® #((#(Z₃ ® Z₁) ,Z5)V ,#(Z₂ ® ((Z₄ ® #(Z₂ , Z₈)&) ,#(Z₇ ® Z₅) &)&))) =

= (Z₁ #((#(Z₃ Z₁) ,Z5)V ,#(Z₂ ((Z₄ #(Z₂ , Z₈)&) ,#(Z₇Z₅) &)&))) =

= Z₁ #((#(Z₃ Z₁) ,Z5)V ,#(Z₂ ((Z₄ #(Z₂ , Z₈)&) ,#(Z₇Z₅) &)&)) =

= Z₁ #(#(Z₃ Z₁) ,Z5)V ,#(Z₂ ((Z₄ #(Z₂ , Z₈)&) ,#(Z₇Z₅) &)&)

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

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

A502 = Z₁ #(#(Z₃ Z₁) ,Z5)V ,#(Z₂ ((Z₄ #(Z₂ , Z₈)&) ,#(Z₇Z₅) &)&)=

СФА 3.4: Структурная формула алгоритма / БФ: Бесскобочная форма

= Z₁ ##Z₃ Z₁,Z5V ,#Z₂ Z₄ #Z₂ , Z₈& ,#Z₇Z₅&&

При необходимости парные операции выделяются любым способом, например, подчеркиванием, фоном и т.п., например:

A502 = Z₁ ##Z₃ Z₁,Z5V ,#Z₂ Z₄ #Z₂ , Z₈& ,#Z₇Z₅&&=

= Z₁ ##Z₃ Z₁,Z5V ,#Z₂ Z₄ #Z₂ , Z₈& ,#Z₇Z₅&&=