Расчетно-графическая работа №3 / РГР №3 (готово).doc

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

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

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

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

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

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

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

Общая тема:

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

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

Часть 3

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

ВЕРБАЛЬНЫЕ ТЕКСТЫ

(псевдокоды)

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

5033.7491.0000-ПЗ

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

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

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

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

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

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

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

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

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

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

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

2007

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

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

Инфиксная форма вербальных (словесных) текстов параллельных алгоритмов рассматривается на примере алгол-подобных и паскаль-подобных вербальных текстов. В данном случае они полностью совпадают.

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

АлгПТ: Алгол-подобный текст / ПасПТ: Паскаль-подобный текст

ШТА 1.1: Шаблон текста алгоритма // ИнФ: Инфиксная форма

А582 = (Z₇ ® (Z₁ & (Z₆ ® (Z₀&(Z₃ ®Z₆)))) V (Z₇ ® (Z₄ & Z₅) ® Z₇)) ТЗО 4.1: Таблица замены обозначений

Компоненты ШТА	Ai	Zi	=	(	)	®	&	V
Компоненты РТА: латиница кириллица	alg Ai алг Ai	Zi Zi	: :	( begin нач	) end кон	; ;	and и	or или

РТА 1.1: Рабочий текст алгоритма // замены обозначений

Вариант 1 подстановок — скобочные оболочки

Латиница — английский язык

alg A582: (Z₇ ; (Z₁ and (Z₆ ; (Z₀and(Z₃ ;Z₆)))) or (Z₇ ; (Z₄ and Z₅) ; Z₇))

Кириллица — русский язык

алг A582: (Z₇ ; (Z₁ и (Z₆ ; (Z₀ и (Z₃ ;Z₆)))) или (Z₇ ; (Z₄ и Z₅) ; Z₇))

Вариант 2 подстановок — вербальные оболочки

Латиница — английский язык

alg A582: begin Z₇ ; begin Z₁ and begin Z₆ ; begin Z₀ and begin Z₃ ;Z₆ end end end end or begin Z₇ ; begin Z₄ and Z₅ end ; Z₇ end end

Кириллица — русский язык

алг A582: нач Z₇ ; нач Z₁ и нач Z₆ ; нач Z₀ и нач Z₃ ;Z₆ кон кон кон кон или нач Z₇ ; нач Z₄  и Z₅ кон ; Z₇ кон кон

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

Выполняется вариант 2 подстановок — вербальные оболочки.

АлгПТ: Алгол-подобный текст / ПасПТ: Паскаль-подобный текст

// Для столбцов таблиц включить режим мелкошаговой табуляции (5 мм)

// парой горячих клавиш Ctrl + T (для рабочего шаблона TNR'-14)

ВТА 1.1: Вербальный текст алгоритма

ШТА: Шаблон текста алгоритма			РТА: Рабочий текст
1	2	3	4
A582 = ( Z7  ® ( Z1 & ( Z6 ® ( Z0 & ( Z3 ® Z6 ) ) ) ) V ( Z7 ® ( Z4 & Z5 ) ® Z7 ) )	A582= ( Z7® ( Z1& ( Z6 ® ( Z0& ( Z3 ® Z6 ) ) ) ) V ( Z7 ® ( Z4 & Z5 ) ® Z7 ) )	A582= ( Z7® ( Z1& ( Z6 ® ( Z0& ( Z3 ® Z6 ) ) ) ) V ( Z7 ® ( Z4 & Z5 ) ® Z7 ) )	alg A582: begin Z7 ; begin Z1 and begin Z6 ; begin Z0 and begin Z3 ; Z6 end end end end or begin Z7 ; begin Z4 and Z5 end ; Z7 end end

ВТА 1.2: Вербальный текст алгоритма // Дополнение к ВТА 4.1

Подстановка функций команд (операторы присваивания)

РТА: Рабочий текст
5	6
alg A582: ya580 = Fa580(xa580): begin Z7: yz7 := Fz7(xz7) ; begin Z1: yz1 := Fz1(xz1) and begin Z6: yz6 := Fz6(xz6) ; begin Z0: yz0 := Fz0(xz0) and begin Z3: yz3 := Fz3(xz3) ; Z6: yz6 := Fz6(xz6) end end end end or begin Z7: yz7 := Fz7(xz7) ; begin Z4: yz4 := Fz4(xz4) and Z5: yz5 := Fz5(xz5) end ; Z7: yz7 := Fz7(xz7) end end	alg A582: ya580 = Fa580(xa580): begin yz7 := Fz7(xz7) ; begin yz1 := Fz1(xz1) and begin yz6 := Fz6(xz6) ; begin yz0 := Fz0(xz0) and begin yz3 := Fz3(xz3) ; yz6 := Fz6(xz6) end end end end or begin yz7 := Fz7(xz7) ; begin yz4 := Fz4(xz4) and yz5 := Fz5(xz5) end ; yz7 := Fz7(xz7) end end

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

Используется программа TEXTPRAL.

СФА 1.1: Структурная формула алгоритма — общая для всех форм

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

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

Выполняются построения для АлгТП: Алгол-подобного текста алгоритма.

Для ПасПТ: Паскаль-подобного текста — в данном случае все аналогично.

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

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

Настройки: ИнФ / АлгПТ / ГИ

ВТА 1.3: Вербальный текст алгоритма

Начало

Окончание

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

Настройки: ИнФ / АлгПТ / ВИ

ВТА 1.4: Вербальный текст алгоритма

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

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

Строится неявная инфиксная форма текста алгоритма относительно знака операции суперпозиции (®).

Неявная форма строится для си-подобного текста.

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

СиПТ: Си-подобный текст

ШТА 2.3: Шаблон текста алгоритма

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

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

НИнФ: Неявная инфиксная форма

// Удаление явной связки следования (суперпозиции ®)

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

Повышение читабельности (не обязательно)

Введение пробелов

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

ТЗО 4.2: Таблица замены обозначений

Компоненты ШТА	Ai	Zi	=	(	)	&	V
Компоненты РТА:	alg Ai	Zi;	:	{	}	& (&')	$ ($')

РТА 4.2: Рабочий текст алгоритма // замены обозначений

alg A582 : {Z₇ ; {Z₁ & {Z₆ ; {Z₀ & {Z₃ ; Z₆}}}} $ {Z₇ ; {Z₄ & Z₅} ; Z₇}}

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

СиПТ: Си-подобный текст

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

// A582 = (Z₇ (Z₁ & (Z₆ (Z₀ & (Z₃ Z₆)))) $ (Z₇ (Z₄ & Z₅) Z₇))

ВТА 4.5: Вербальный текст алгоритма

ШТА: Шаблон текста алгоритма				РТА: Рабочий текст
1	2	3	4	5
A582 = ( Z7 ( Z1 & ( Z6 ( Z0 & ( Z3 Z6 ) ) ) ) V ( Z7 ( Z4 & Z5 ) Z7 ) )	A582= ( Z7 ( Z1& ( Z6 ( Z0& ( Z3 Z6 ) ) ) ) V ( Z7 ( Z4& Z5 ) Z7 ) )	A582= ( Z7 ( Z1& ( Z6 ( Z0& ( Z3 Z6 ) ) ) ) V ( Z7 ( Z4& Z5 ) Z7 ) )	A582= ( Z7 ( Z1& ( Z6 ( Z0& ( Z3 Z6 ) ) ) ) V ( Z7 ( Z4& Z5 ) Z7 ) )	A582= { Z7 { Z1& { Z6 { Z0& { Z3 Z6 } } } } V { Z7 { Z4& Z5 } Z7 } }

ВТА 4.6: Вербальный текст алгоритма // Дополнение к ВТА 4.5

Подстановка функций команд (операторы присваивания)

РТА: Рабочий текст алгоритма
6	7
A582: ya580 = Fa580(xa580): { Z7: yz7 = Fz7(xz7); { Z1: yz1 = Fz1(xz1); & { Z6: yz6 = Fz6(xz6); { Z0: yz0 = Fz0(xz0); & { Z3: yz3 = Fz3(xz3); Z6: yz6 = Fz6(xz6); } } } } V { Z7: yz7 = Fz7(xz7); { Z4: yz4 = Fz4(xz4); & Z3: yz3 = Fz3(xz3); } Z7: yz7 = Fz7(xz7); } }	A582: ya580 = Fa580(xa580): { yz7 = Fz7(xz7); { yz1 = Fz1(xz1); & { Z6: yz6 = Fz6(xz6); { yz0 = Fz0(xz0); & { yz3 = Fz3(xz3); yz6 = Fz6(xz6); } } } } V { yz7 = Fz7(xz7); { yz4 = Fz4(xz4); & yz3 = Fz3(xz3); } yz7 = Fz7(xz7); } }

Автоматизация построений: си-подобный текст

СФА 4.2: Структурная формула алгоритма — общая для всех форм (ИнФ).

Набор формулы и добавление в список — аналогично предыдущему.

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

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

ШТА 4.4: Шаблон текста алгоритма // Преобразованная формула

ВТА 4.7: Вербальный текст алгоритма

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

Настройки: ИнФ / АлгПТ / ГИ

ВТА 4.8: Вербальный текст алгоритма

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

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

АлгПТ: Алгол-подобный текст / ПасПТ: Паскаль-подобный текст

ШТА 4.5: Шаблон текста алгоритма

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

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

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

= (Z₇ ® (Z₁ #& (Z₆ ® (Z₀ #&(Z₃ ®Z₆)))) #V (Z₇ ® (Z₄ #& Z₅) ® Z₇)) ИнПрПоФ: Инфикcно-префиксно-постфиксная форма

// инфиксная по операции ®, префиксная — по #, постфиксная — по &,V($)

= #(Z₇ ® (Z₁ #& (Z₆ ® (Z₀ #&(Z₃ ®Z₆)))), (Z₇ ® (Z₄ #& Z₅) ® Z₇))V =

= #(Z₇ ® #(Z₁ , (Z₆ ® #(Z₀ , (Z₃ ®Z₆))&))&), (Z₇ ® #(Z₄ , Z₅)& ® Z₇))V

ТЗО 4.3: Таблица замены обозначений

Общие замены обозначений

Компоненты ШТА

Ai

Zi

=

(

)

®

#

&

V

Компоненты РТА:

alg Ai

Zi

:

begin

end

;

par

and

or

Специальные замены обозначений (для специальных пар знаков)