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

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

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

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

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

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

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

Общая тема:

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

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

Часть 1

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

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

5033.7491.0000-ПЗ

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

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

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

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

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

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

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

студент Манаев Р. Н.

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

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

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

2007

Оглавление:

1. Исходное задание 3

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

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

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

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

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

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

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

8

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

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

5.2. Нумерация и группирование формульных оболочек схемы 11

6. Повышение взаимно однозначного соответствия структурных схем и структурных формул. 12

6.1. Введение явной операции fork. 12

6.2. Разделение парных операций fork и join. 13

6.3 Бесскобочная запись формул. 13

7.1. Блок-схема алгоритма – горизонтальное исполнение 14

(автоматизированное построение) 14

7.2. Штрих-схема алгоритма(автоматизированное построение) 15

1. Исходное задание

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

А581=Z₇((Z₁ &Z₆(Z₀&Z₃Z₆))&Z₇(Z₄ &Z₅)Z₇)

А582= Z₇((Z₁ &Z₆(Z₀&Z₃Z₆))VZ₇(Z₄ &Z₅)Z₇)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Восстановление стандартной сфа

Вариант 1

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

А581=Z₇((Z₁ &Z₆(Z₀&Z₃Z₆))&Z₇(Z₄ &Z₅)Z₇)

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

А581=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

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

А582=Z₇((Z₁&Z₆(Z₀&Z₃Z₆))VZ₇(Z₄ &Z₅)Z₇)

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

А582=Z₇ ((Z₁ &Z₆ (Z₀ &Z₃ Z₆ ))VZ₇ (Z₄ &Z₅ )Z₇ )=

= Z₇ –((Z₁ &Z₆ –(Z₀ &Z₃ –Z₆ ))VZ₇ – (Z₄ &Z₅ )–Z₇ )

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

Z₇ – ((Z₁ &Z₆ – (Z₀ &Z₃ –Z₆ ))VZ₇ – (Z₄ &Z₅ ) –Z₇ ) =

= (Z₇ – ((Z₁ &Z₆ – (Z₀ &Z₃ –Z₆ ))VZ₇ – (Z₄ &Z₅ ) –Z₇ )) =

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