Расчетно-графическая работа / ргрМЛТА/1часть.doc
Министерство образования Российской Федерации
Уфимский государственный авиационный технический университет
Факультет ИРТ: Информатика и робототехника
Кафедра ПСИ: Проектирование систем информатики
Учебная дисциплина:
МЛТА: Математическая логика и теория алгоритмов
РГР: Расчетно-графическая работа
Общая тема:
ПАРАЛЛЕЛЬНЫЕ ЛОГИКО-АЛГОРИТМИЧЕСКИЕ СИСТЕМЫ
(алгоритмы и логика, аппаратная и программная реализация)
Часть 1
ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ.
ТЕХНИКА СТРУКТУРНЫХ ПОСТРОЕНИЙ.
Базисные структуры алгоритмов
Пояснительная записка
5033.7220.0000-ПЗ
Направление подготовки:
654600: ИВТ: Информатика и вычислительная техника
Специальность:
230100: ИВТ: Информатика и вычислительная техника
Курс обучения:
Учебная группа:
Работу выполнила
студентка _____________ Фамилия И. О.
Зачетная книжка №
Вариант задания: A570
Работу принял
должность _____________ Фамилия И. О.
2007
1 Структурные формулы алгоритмов
1.1 Индивидуальное задание
Комплект исходных формул алгоритмов
Задан комплект A570 структурных формул алгоритмов:
A571 = Z2((Z0 & Z8)Z2 & Z3)(Z4 & Z8Z2 & Z6Z7) 1-й вариант СФА
группы A570
A572 = Z2((Z0 & Z8)Z2 & Z3)(Z4 V Z8Z2 V Z6Z7) 2-й вариант СФА
группы A570
A573 = Z2((Z0 & Z8) ¯&1Z2 & Z3)(Z41 V Z8Z2 V Z6Z7) 3-й вариант СФА
группы A570
1.2 Восстановление стандартной формы структурных формул
Стандартная форма формулы алгоритма
По исходной СФА строится стандартная СФА — полная инфиксная форма.
СФА 1.1: Структурная формула алгоритма / У: Поток управления
ИнФ: Инфиксная форма записи формулы
СИнФ: Сокращенная инфиксная форма
Вариант 1 (A571):
A571 = Z2((Z0 & Z8)Z2 & Z3)(Z4 & Z8Z2 & Z6Z7) =
Вариант 2 (A572):
A572 = Z2((Z0 & Z8)Z2 & Z3)(Z4 V Z8Z2 V Z6Z7) =
ПИнФ: Полная инфиксная форма
Вариант 1 (A571)
= Z2 — ((Z0 & Z8) — Z2 & Z3) — (Z4 & Z8 — Z2 & Z6 — Z7) =
Вариант 2 (A572)
= Z2 — ((Z0 & Z8) — Z2 & Z3) — (Z4 V Z8 — Z2 V Z6 — Z7) =
Вариант 1 (A571)
= Z2 — ((Z0 & Z8) — Z2 & Z3) — (Z4 & (Z8 — Z2) & Z6 — Z7) =
= Z2 — ((Z0 & Z8) — Z2 & Z3) — (Z4 & (Z8 — Z2) & (Z6 — Z7)) =
= Z2 — (((Z0 & Z8) — Z2) & Z3) — (Z4 & (Z8 — Z2) & (Z6 — Z7)) =
= Z2 — (((Z0 & Z8) — Z2) & Z3) — ((Z4 & (Z8 — Z2)) & (Z6 — Z7)) =
= (Z2 — (((Z0 & Z8) — Z2) & Z3) — ((Z4 & (Z8 — Z2)) & (Z6 — Z7)))
Вариант 2 (A572)
= Z2 — ((Z0 & Z8) — Z2 & Z3) — (Z4 V (Z8 — Z2) V Z6 — Z7) =
= Z2 — ((Z0 & Z8) — Z2 & Z3) — (Z4 V (Z8 — Z2) V (Z6 — Z7)) =
= Z2 — (((Z0 & Z8) — Z2) & Z3) — (Z4 V (Z8 — Z2) V (Z6 — Z7)) =
= Z2 — (((Z0 & Z8) — Z2) & Z3) — ((Z4 V (Z8 — Z2)) V (Z6 — Z7)) =
= (Z2 — (((Z0 & Z8) — Z2) & Z3) — ((Z4 V (Z8 — Z2)) V (Z6 — Z7))) =
Основная стандартная форма записи СФА
Вариант 1 (A571)
Явная операция суперпозиции:
A571 = (Z2 ® (((Z0 & Z8) ® Z2) & Z3) ® ((Z4 & (Z8 ® Z2)) & (Z6 ® Z7))) =
Неявная операция суперпозиции:
= (Z2(((Z0 & Z8)Z2) & Z3)((Z4 & (Z8Z2)) & (Z6Z7))) =
Вариант 2 (A572)
Явная операция суперпозиции:
A572 = (Z2 ® (((Z0 & Z8) ® Z2) & Z3) ® ((Z4 V (Z8 ® Z2)) V (Z6 ® Z7))) =
Неявная операция суперпозиции:
= (Z2(((Z0 & Z8)Z2) & Z3)((Z4 V (Z8Z2)) V (Z6Z7))) =
Контроль результатов
Выполняются обратные (контрольные) упрощения записи.
СФА 1.2: Вариант 1 (A571)
Удаление знака суперпозиции:
A571 = (Z2(((Z0 & Z8)Z2) & Z3)((Z4 & (Z8Z2)) & (Z6Z7))) =
Удаление внешних скобок:
= Z2(((Z0 & Z8)Z2) & Z3)((Z4 & (Z8Z2)) & (Z6Z7)) =
Пошаговое удаление скобок для суперпозиции:
= Z2(((Z0 & Z8)Z2) & Z3)((Z4 & Z8Z2) & Z6Z7) =
= Z2((Z0 & Z8)Z2 & Z3)((Z4 & Z8Z2) & Z6Z7) =
= Z2((Z0 & Z8)Z2 & Z3)(Z4 & Z8Z2 & Z6Z7)
СФА 1.3: Вариант 2 (A572)
A572 = (Z2(((Z0 & Z8)Z2) & Z3)((Z4 V (Z8Z2)) V (Z6Z7))) =
= Z2(((Z0 & Z8)Z2) & Z3)((Z4 V (Z8Z2)) V (Z6Z7)) =
= Z2(((Z0 & Z8)Z2) & Z3)((Z4 V Z8Z2) V Z6Z7) =
= Z2((Z0 & Z8)Z2 & Z3)((Z4 V Z8Z2) V Z6Z7) =
= Z2((Z0 & Z8)Z2 & Z3)(Z4 V Z8Z2 V Z6Z7)
2 Структурные схемы параллельных алгоритмов
2.1 Основная схема (без схемных оболочек). Ручные построения
Вариант 1 структурной схемы (A141). Ручные построения
СФА 2.1: Структурная формула алгоритма / У: Поток управления
A571 = (Z2 ® (((Z0 & Z8) ® Z2) & Z3) ® ((Z4 & (Z8 ® Z2)) & (Z6 ® Z7)))
A571 = (Z2 — (((Z0 & Z8) — Z2) & Z3) — ((Z4 & (Z8 — Z2)) & (Z6 — Z7)))
ССА 2.1: Структурная схема алгоритма / У: Поток управления
БСА 2.1: Блок-схема алгоритма / ГИ: Горизонтальное исполнение
|
|
|
| ||||||
БСА 2.2: Блок-схема алгоритма
ВИ: Вертикальное исполнение
ШСА 2.1: Штрих-схема алгоритма
ГИ: Горизонтальное исполнение
Вариант 2 структурной схемы (A142). Ручные построения
СФА 2.2: Структурная формула алгоритма / У: Поток управления
A572 = (Z2 ® (((Z0 & Z8) ® Z2) & Z3) ® ((Z4 V (Z8 ® Z2)) V (Z6 ® Z7)))
A572 = (Z2 — (((Z0 & Z8) — Z2) & Z3) — ((Z4 V (Z8 — Z2)) V (Z6 — Z7)))
ССА 2.2: Структурная схема алгоритма / У: Поток управления
БСА 2.2: Блок-схема алгоритма / ГИ: Горизонтальное исполнение
|
|
|
| ||||||
БСА 2.3: Блок-схема алгоритма
ВИ: Вертикальное исполнение
ШСА 2.1: Штрих-схема алгоритма
ГИ: Горизонтальное исполнение
2.2 Автоматизация построений основной схемы алгоритма
Вариант 1 структурной схемы. Автоматизация построений
СФА 2.3: Структурная формула алгоритма / У: Поток управления
A571 = (Z2 ® (((Z0 & Z8) ® Z2) & Z3) ® ((Z4 & (Z8 ® Z2)) & (Z6 ® Z7)))
A571 = (Z2 — (((Z0 & Z8) — Z2) & Z3) — ((Z4 & (Z8 — Z2)) & (Z6 — Z7)))
Набор формулы:
Настройки программы: ИнФ / ГИ / БСА / БФ
БСА 2.5: Блок-схема алгоритма / ГИ: Горизонтальное исполнение
Настройки: ИнФ / ГИ / ШСА / БФ
ШСА 2.3: Штрих-схема алгоритма / ГИ: Горизонтальное исполнение
Вариант 2 структурной схемы. Автоматизация построений
СФА 2.5: Структурная формула алгоритма / У: Поток управления
A572 = (Z2 ® (((Z0 & Z8) ® Z2) & Z3) ® ((Z4 V (Z8 ® Z2)) V (Z6 ® Z7))) A572 = (Z2 — (((Z0 & Z8) — Z2) & Z3) — ((Z4 | (Z8 — Z2)) | (Z6 — Z7)))
Набор формулы:
Настройки: ИнФ / ГИ / БСА / БФ
БСА 2.6: Блок-схема алгоритма / ГИ: Горизонтальное исполнение
Настройки: ИнФ / ГИ / ШСА / БФ
ШСА 2.4: Штрих-схема алгоритма / ГИ: Горизонтальное исполнение
2.3 Анализ структурной схемы
Вариант 1
СФА 2.6: Структурная формула алгоритма
A571 = (Z2 ® (((Z0 & Z8) ® Z2) & Z3) ® ((Z4 & (Z8 ® Z2)) & (Z6 ® Z7)))
A571 = (Z2 — (((Z0 & Z8) — Z2) & Z3) — ((Z4 & (Z8 — Z2)) & (Z6 — Z7)))
ШСА 2.5: Штрих-схема алгоритма
|
| ||||||||||
| |||||||||||
|
| ||||||||||||||
Вариант 2
СФА 2.7: Структурная формула алгоритма
A572 = (Z2 ® (((Z0 & Z8) ® Z2) & Z3) ® ((Z4 V (Z8 ® Z2)) V (Z6 ® Z7))) A572 = (Z2 — (((Z0 & Z8) — Z2) & Z3) — ((Z4 | (Z8 — Z2)) | (Z6 — Z7)))
ШСА 2.6: Штрих-схема алгоритма
|
| ||||||||||
| |||||||||||
|
| ||||||||||||||
| ||||||||||||||
|
|
Общие данные структуры алгоритма
а) Структурный класс алгоритма:
двухполюсный постоянный ациклический алгоритм;
б) Общие структурные показатели
| Показатели | Значения | Примечания |
| Общее число команд | 10 | |
| Число разных команд |