МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ ТЕРНОПІЛЬСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ імені Івана Пулюя Кафедра комп’ютерних наук ЛАБОРАТОРНА РОБОТА з предмету Теорія алгоритмів та математичні основи представлення знань Тема: Перетворення структури обчислювальних алгоритмів Тернопіль-2010 Лабораторна робота №4 Тема роботи: Перетворення структури обчислювальних алгоритмів. Мета роботи: Вивчення методів перетворення структури обчислювальних алгоритмів на прикладі алгоритмів фільтрації сигналів. Теоретичні відомості При практичній реадізації обчислювальних алгоритмів на ЕОМ загального призначення та спеціалізованих ЕОМ суттєвими є не тільки функція, яку реалізує алгоритм, але і його структура. Від структури алгоритму залежать швидкість виконання алгоритму, необхідний обєм пам`яті ЕОМ, необхідна кількість арифметично-логічних пристроїв (суматорів, помножувачів) при реалізації алгоритму у спеціалізованих ЕОМ, стійкість роботи алгоритму до похибок обчислень з скінченою точністю. Через це важливим є вивчення властивостей різних форм структури обчислювальних алгоритмів та методів переходу від однієї форми до іншої. Найбільш поширеними є пряма і канонічна форми структури алгоритмів. Пряма (основна) форма Канонічна форма Інші форми будуються в залежності від вимог до конкретної реалізації алгоритму. Перехід між різними формами можна здійснити проведенням тотожніх перетворень над різницевим рівнінням алгоритму або над передаточною функцією, яку отримують в результаті дискретного перетворення Фур`є або Z-перетворення різницевого рівняння. Проілюструвати проведення перетворення стрктури можна на прикладі рекурсивного алгоритму другого порядку. Різницеве рівняння алгоритму:
(1) Такий запис відповідає спруктурній схемі алгоритму у прямій формі (рис.1.а). Перехід від прямої форми до канонічної легко здійснити перетворенням передаточної функції. Z-перетворення різницевого рівняння:
Або
Передаточна функція:
Чисельник передаточної функції реалізує пряму (нерекурсивну) частину алгоритму, а знаменник – рекурсивну частину алгоритму. Передаточну функцію можна записати у вигляді:
, де
Така форма запису передаточної функції відповідає послідовному (каскадному) з’єднанню рекурсивної і нерекурсивної частин обчислювального алгоритму. Сумістивши затримки рекурсивної і нерекурсивної частин алгоритму отримаєм настутну структурну схему алгоритму (Рис.2.). У випадку, коли алгоритм заданий у вигляді структурної або граф-схеми або з допомогою системи рівнянь, зручно попередньо записати передаточну функцію а потім проводити перетворення над нею. Для того щоб звести опис алгоритму від структурної або граф схеми до передаточної функції необхідно: записати систему рівнянь для усіх внутрішніх і вихідних вузлцв схеми; виключенням змінних для внутрішніх вузлів звести систему рівнянь до одного рівняння виду у=H*x; функція H(z) , буде передаточною функцією алгоритму. Завдання до лабораторної роботи. Для алгоритму, який описується заданою системою рівнянь 7 
звести до каноннічної форми   Записати різницеве рівняння і передаточну функцію. Перейти до канонічної форми структури алгоритму. Побудувути структурну та граф-схеми алгоритму; Скласти програму реалізації такого алгоритму на ЕОМ у якій: а. операції множення та сумування реалізувати у вигляді окремих підпрограм; b. на вхід алгоритму подати послідовність з 20 відліків синусоїди; с. забезпечипи підрахунок кількості викликів підпрограм множення та додавання. Різницеве рівняння у канонічній формі: x4i=12,3x1i+4x1i–1 + 132x4i–1 – 46x4i–2 Передаточна функція у канонічній формі:
Результат роботи. Рис.1 Структурна схема алгоритму
 Рис.2 Графсхема алгоритму Блок-схема програми Текст програми unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, ComCtrls, ExtCtrls, TeeProcs, TeEngine, Chart, Series; type TForm1 = class(TForm) Button1: TButton; Chart1: TChart; Series1: TFastLineSeries; Button2: TButton; Label6: TLabel; Label7: TLabel; procedure Button1Click(Sender: TObject); function Mnogenia(m1:real; m2:extended): extended; function Dodavania(d1:extended; d2:extended): extended; procedure Button2Click(Sender: TObject); private { Private declarations } public { Public declarations } end; const n=20; var Form1: TForm1; k_dod, k_mnog:integer; i:integer; x1,x2,x3,x4,x5:extended; inx: array[1..n] of real; outx: array[1..n] of extended; implementation {$R *.dfm} procedure TForm1.Button1Click(Sender: TObject); begin inx[1]:=1; for i:=2 to n do begin inx[i]:=0; end; for i:=1 to n do begin outx[i]:= Dodavania(Dodavania(Mnogenia(12.3,inx[i]),+Mnogenia(4,inx[i-1])),Mnogenia(132,outx[i-1]))-Mnogenia(46,outx[i-2]); end; Form1.Label6.Caption:='Функція додавання викликалася '+ inttostr(k_dod); Form1.Label7.Caption:='Функція множення викликалася '+ inttostr(k_mnog); series1.Clear; for i:=1 to n do begin Series1.Add(outx[I]) ; end; end; procedure TForm1.Button2Click(Sender: TObject); begin close; end; function TForm1.Dodavania(d1:extended; d2:extended): extended; begin k_dod:= k_dod+1; Dodavania:=d1+d2; end; function TForm1.Mnogenia(m1:real; m2:extended):extended; begin k_mnog:= k_mnog+1; Mnogenia:=m1*m2; end; end. Результат роботи
Висновок: На цій лабораторні роботі я вивчив методи перетворення структури обчислювальних алгоритмів на прикладі алгоритмів фільтрації сигналів.