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

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

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

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

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

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

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

Общая тема:

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

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

Часть 1

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

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

5033.4339.0000-ПЗ

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

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

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

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

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

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

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

студентки _____________

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

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

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

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

2004

СОДЕРЖАНИЕ

1 Введение. 5

Назначение методического руководства. 5

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

Общие цели выполнения первой части работы.. 5

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

Обобщенная концепция текстов алгоритмов. 6

Общее содержание первой части расчетно-графической работы.. 6

3 Базовые структуры алгоритмов.. 6

3.1 Подготовка задания. 6

Рабочие варианты формулы по текущему разделу. 6

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

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

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

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

3.2.2 Автоматизация построений основной схемы.. 10

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

11

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

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

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

3.2.4 Проверочная нумерация оболочек. 12

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

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

13

3.2.5 Повышение структурного соответствия формул и схем. 14

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

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

Временные диаграммы параллельных алгоритмов. 17

3.2.6 Задание длительности исполнения команд. 17

Определение массива данных. 17

3.2.7 Построение временной диаграммы сетевого типа. 17

Вариант 1 диаграммы (A141). Автоматизация построений. 17

Вариант 2 диаграммы (A142). Автоматизация построений. 18

3.2.8 Графический расчет длительности алгоритма. 19

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

Длина рабочей линии диаграммы.. 19

Графический расчет длины линии. 19

3.2.9 Аналитический расчет длительности алгоритма. 20

Подготовка формулы расчета длительности. 20

Расчет длительности алгоритма. 20

Вербальные тексты параллельных алгоритмов. 21

3.2.10 Общие положения. 21

Дополнительные функциональные обозначения. 21

3.2.11 ИнФ: Инфиксная форма вербального текста. 21

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

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

Автоматизация построений: Алгол (Паскаль) — подобный текст. 21

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

Автоматизация построений (СиПТ) 23

3.2.12 КоФ: Комбинированная форма вербального текста. 25

Автоматизация построений: Алгол (Паскаль) — подобный текст. 25

4 Ациклические многополюсные структуры алгоритмов.. 28

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

4.2 Комплект текстов алгоритмов (обобщенные тексты) 29

4.2.1 Стандартная полная форма структурной формулы.. 29

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

4.2.2 Структурная схема. 30

Структурная схема алгоритма. 30

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

4.2.3 Временная диаграмма исполнения алгоритма. 33

4.2.3.1 Длительности исполнения команд. 33

Подготовка массива данных. 33

4.2.3.2 Временная диаграмма сетевого типа. 33

ДИА: Диаграмма исполнения алгоритма. Ручные построения. 34

ДИА: Диаграмма исполнения. Автоматизированные построения. 34

Краткая характеристика программы.. 35

Подготовка кодирования элементов алгоритма. 36

Параметры кодирования модели. 38

Кодирование элементов алгритма. 40

Комплект файлов модели алгоритма. 41

Состав файла кодировки структуры алгоритма. 42

Заготовка кодировки. 43

Запись кодировки структурной формулы для моделирования. 44

Подготовка файлов. 47

Построение временной диаграммы.. 48

4.2.4 Графический расчет длительности алгоритма. 51

4.2.5 Аналитический расчет длительности алгоритма. 51

4.2.6 Вербальные тексты алгоритма. 52

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

Дополнительные функциональные обозначения. 52

КоФ: Комбинированная форма. 53

1          Введение

Назначение методического руководства

Данное методическое руководство предназначено для обеспечения оперативного практического освоения первичного комплекса вопросов в области параллельной алгоритмизации и реализации алгоритмов и их логико-математического обеспечения в составе разных учебных курсов по информатике, автоматизации (дискретных) технологических процессов

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

Общие цели выполнения первой части работы

Основными целями выполнения первой части расчетно-графической работы (по данной первой части руководства) является практическое освоение первичных знаний, умений и навыков параллельной алгоритмизации, включая:

·        технику структурных построений параллельных алгоритмов разных структурных классов — начиная от базовых параллельных структур;

·        сопутствующий первичный понятийно-терминологический аппарат.

Рассматривается техника полиморфных структурных построений параллельных алгоритмов:

·        структурные формулы и схемы, временные диаграммы, разных видов вербальные (словесные) тексты алгоритмов — взаимно дополнительные и взаимно обратимые формы общего полиморфного представления алгоритмов;

·        принципы полиморфного синтаксиса на конкретных примерах (без описания синтаксиса) — обеспечивается общее понимание наличия сложной полиморфной синтаксической системы;

·        доступные средства программной поддержки алгоритмических разработок

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

Обобщенная концепция текстов алгоритмов

Используется обобщенная концепция текстов алгоритмов, определяемая с позиций семиотики (теории знаков и знаковых систем):

а) Тексты — это комплексы (любых) знаков, связанные общим смыслом (в определенной системе организации: синтаксис, семантика, прагматика);

б) Виды текстов алгоритмов:

·        литерные — развернутые вербальные (словесные) тексты и компактные формулы (формульные тексты) алгоритмов, графические и табличные тексты и т.д.;

·        одномерные, двухмерные, трехмерные тексты и т.п.;

·        статические тексты (например, письменные вербальные описания алгоритмов) и динамические тексты (например, устная форма введения вербального текста алгоритма в ЭВМ).

Общее содержание первой части расчетно-графической работы

Выполняется подготовка различных видов текстов заданного алгоритма, которые строятся:

·        по заданной структурной формуле алгоритма — основная исходная форма;

·        по дополнительным данным и условиям.

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

3          Базовые структуры алгоритмов

3.1       Подготовка задания

Исходная формула алгоритма

Задана исходная формула алгоритма:

A470 = Z₁ (Z₂¯_&¹Z₁& Z₇& Z₃ ­¹Z₁)( Z₄ V (Z₂Z₁& Z₃ )))

РМУ 3.1 Задается некоторый функционально абстрактный алгоритм:

Рабочие варианты формулы по текущему разделу

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

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

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

РМУ 3.2 Выписать рабочие варианты СФА согласно исходному заданию

// 1-й и 2-й варианты СФА

A471 = Z₁ (Z₂Z₁& Z₇& Z₃Z₁)( Z₄ & (Z₂Z₁& Z₃ ))) 1-й вариант СФА A470

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

РМУ 3.3 Выровнять индексы текста формулы

A471 = Z₁ (Z₂Z₁& Z₇& Z₃Z₁)( Z₄ & (Z₂Z₁& Z₃ )))=

= Z 1(Z 2Z 1& Z 7& Z 3Z 1)( Z 4& (Z 2Z 1& Z 3 ))

A472 = Z₁ (Z₂Z₁& Z₇& Z₃Z₁)( Z₄ V (Z₂Z₁& Z₃ )))=

= Z 1(Z 2Z 1& Z 7& Z 3Z 1)( Z 4 V (Z 2Z 1& Z 3 ))

// Данные СФА задают постоянные ациклические двухполюсные структуры параллельных алгоритмов — в сокращенной инфиксной форме записи.

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

A470 = Z₁(Z₂Z₁& Z₇&Z₃Z₁)(Z₄V(Z₂Z₁& Z₃ )))=

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

 Z1(Z2Z1&Z7&Z3Z1)(Z4V(Z2Z1&Z3))=

Z1 (Z2 Z1 & Z7 & Z3 Z1 ) ( Z4 V (Z2 Z1 & Z3 ) )

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

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

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

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

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

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

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

 A471 =Z 1(Z 2Z 1& Z 7& Z 3Z 1)( Z 4& (Z 2Z 1& Z 3 ))

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

A472 = Z 1(Z 2Z 1& Z 7& Z 3Z 1)( Z 4 V (Z 2Z 1& Z 3 ))=

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

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

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

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

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

=Z 1 — (Z 2—Z 1& Z 7& Z 3—Z 1) — ( Z 4& (Z 2—Z 1& Z 3 ))=

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

= Z 1— (Z 2—Z 1& Z 7& Z 3—Z 1) — ( Z 4 V (Z 2—Z 1& Z 3 ))=

// Простановка недостающих пар операционных скобок:

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

// конъюнкции (&) и дизъюнкции (V)

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

=Z 1 — (Z 2—Z 1& Z 7& Z 3—Z 1) — ( Z 4& (Z 2—Z 1& Z 3 ))=

= (Z 1 — ((Z 2—Z 1)& Z 7& (Z 3—Z 1)) — ( Z 4& ((Z 2—Z 1)& Z 3 )))=

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

= Z 1—((Z 2—Z 1)& Z 7& (Z 3—Z 1)) — ( Z 4 V ((Z 2—Z 1)& Z 3 ))

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

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

A471= (Z 1 ® ((Z 2®Z 1)& Z 7& (Z 3®Z 1)) ® ( Z 4& ((Z 2®Z 1)& Z 3 )))=

= (Z 1((Z 2Z 1)& Z 7& (Z 3Z 1))( Z 4& ((Z 2Z 1)& Z 3 )))

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

A472= (Z 1® ((Z 2®Z 1)& Z 7& (Z 3®Z 1)) ® ( Z 4 V ((Z 2®Z 1)& Z 3 )))=

= (Z 1 ((Z 2Z 1)& Z 7& (Z 3Z 1))( Z 4 V ((Z 2Z 1)& Z 3 )))

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

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

Вариант 1:

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

= (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 — аналогично:

= (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 ₃ ))

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

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

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

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

A471= (Z 1 ® ((Z 2®Z 1)& Z 7& (Z 3®Z 1)) ® ( Z 4& ((Z 2®Z 1)& Z 3 )))

A471= (Z 1 — ((Z 2—Z 1)& Z 7& (Z 3—Z 1)) — ( Z 4& ((Z 2—Z 1)& Z 3 )))

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

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

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

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

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

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

РМУ 3.5 Замена обозначений: "®" - "—"; "V" — "|"

A472= (Z 1® ((Z 2®Z 1)& Z 7& (Z 3®Z 1)) ® ( Z 4 V ((Z 2®Z 1)& Z 3

A472= (Z 1 — ((Z 2—Z 1)& Z 7& (Z 3—Z 1)) — ( Z 4 | ((Z 2—Z 1)& Z 3 )))

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

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

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

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

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

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

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

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

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

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

РМУ 3.6 Схемные оболочки на ССА задаются строго соответственно скобочным оболочкам в ПИнФ СФА.

3.2.4    Проверочная нумерация оболочек

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

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

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

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

// переключить редактор на шрифт Courier New — постоянный шаг текста

A472= (Z1—((Z2—Z1)&Z7&(Z 3—Z1))—(Z4 V((Z2—Z1)&Z3)))

1 23 3 3 32 2 34 4 321

1 1 1 2 2 1 2 3 32

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

A472=(₁Z 1—(₂₁(₃₁Z 2—Z 1) ₃₁& Z 7& ₃₂ (Z 3—Z 1) ₃₂) ₂₁—(₂₂ Z 4V(₃₃ (₄Z 2—Z 1) ₄& Z 3 ) ₃₃) ₂₂) ₁

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

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