Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2007
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Теорiя алгоритмiв i математичнi основи представленння знань
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України.
Національний університет “Львівська політехніка”
Кафедра АСУ
Звіт
про виконання
Лабораторних робіт № 1,2,3,4
з курсу: “Теорія алгоритмів і математичні основи представлення
знань”
Мета лабораторної роботи : 1) експериментально дати оцінку складності елементарних арифметичних функцій мов програмування типу Паскаль; 2)забезпечити засобами мови Паскаль або Си емуляцію арифметичних операцій додавання, віднімання, множення i ділення натуральних чисел багатократної точності й оцінити їх складність.
I. ЗАГАЛЬНІ ПОЛОЖЕННЯ
Практично важливим напрямком, що вивчає теорія алгоритмів є дослідження й аналіз їх, складності [2,4].
1. Однією із задач аналізу алгоритмів є необхідність отримання оцінок для об'єму часу, що необхідно алгоритму для обробки конкретних даних. Досить часто, тільки на практиці програміст переконується, що його програма в змозі обробити вхідні дані тільки через декілька діб безперервної роботи ЕОМ. Крім того, необхідно порівнювати ефективність, складність (час роботи, пам'ять) алгоритмів, що ров"язують одну й ту ж задачу.
Нехай А - алгоритм для розв"язування задач деякого класу К, а число n - розмірність окремої задачі з К (кількість змінних, слів у тексті і т.п.) Визначимо fа(n) як функцію складності, що визначає верхню межу для максимальної кількості основних операцій (додавання, порівняння і т.п.), які повинен виконати алгоритм А для розв"язку будь якої задачі розмірності n.
Будемо користуватися наступним критерієм оцінки складності А. Алгоритм А має поліноміальну складність, коли fa(n) зростає не швидше, ніж поліном від n, у протилежному випадку алгоритм А експоненційний. Цей критерії базується на часі роботи у найгіршому випадку. Основою для цього критерію складнсті є машинні експерименти, що продемонстрували, що реальні послідовні або паралельні ЕОМ більш меньш здатні сприймати і ефективно реалізовувати поліноміальні алгоритми для великих задач, а експоненційні алгоритми вони не в змозі "реалізувати" за практично сприйнятний час.
Більш формально, функцію складності fa(n) визначають як O(g(x)) і кажуть, що вона має порядок g(n) для великих n, якщо
f(n)
lim ------- = constanta = a, a>0.
n->g(n)
Це позначується, як f(n) = O(g(n)). Функція h(n) є o(z(n)) для великих n, якщо
h(n)
lim ------- = 0.
n-> z(n)
Змістовно, якщо 1) fa(n) є O(g(x)), то ці дві функції , по суті, зростають з однаковою швидкістю; 2) якщо fa(n) є o(g(x)), то g(n) зростає набагато швидше, ніж fa(n).
Іншими словами, функція f(x) має порядок O(g(x)), якщо знайдеться константа С і f(x) <= C*g(x) для всіх x, крім скінченної (можливо, пустої) множини значень, або, що те саме, завжди знайдеться таке n 40 0, що f(x) <= C*g(x) для всіх x, де x >= n 40 і x > 0.
Розвиток теорії складності обчислень йшов по чотирьом напрямкам :
1) абстрактна (машино-незалежна) складність: 2) машинно-залежна складність;3) складність конкретних задач і алгоритмів; 4)експерементальна (ЕОМ-залежна) складність.
У першому із них обчислювальні моделі і міри складності визначаються аксиоматично і вивчаються найбільш загальні властивості складності алгоритмічних функцій. Доведені теореми про "стискування" і "прискорення". Перша із них стверджує про існування функцій будь якої складності, що оптимально реалізуються. Друга стверджує про існування функцій, кожне обчислення яких можна "прискорити", тобто функцій, для яких не існють оптимальні обчислення.
Другий напрям пов"язаний з дослідженням складності обчислень на конкретних моделях обчислювальних пристроїв и реальних ЕОМ. В цій галузі однією із дуже відомих невирішених проблем є проблема " Р – і NP - складності": чи співпадає клас P функцій, що обчислюються за поліноміальний час на машинах Тюрінга (послідовних ЕОМ), з класом NP функцій, що обчислюються за поліноміальний час на недетермінованих машинах Тюрінга (по суті, паралельних ЕОМ).
Із теорії алгоритмів відомо, що якщо задача Z належить класу NP, то вона завжди реалізується детермінованою машиною Тюрінга з часовою складністю O(k 5Pz(n) 0), де k - константа, а P(n) - поліном, що залежить від Z.
Відмітемо, що до класу P входять класичні комбінатрні проблеми :
а) проблема входження ("ідентифікації") слів, яка полягає у визначенні для двох слів x і y, чи входить x як підслво в y, функція складності якої має порядок O(n), де n - сумарна довжина слів x і y;
б) задача сортування має порядок O(n*log(n));
в) задача множення матриць має порядок складнсті O(n 52.49..0).
По проблематиці третього напрямку наведемо декілька понять і результатів про складність конкретних алгоритмів. Задача Z називається А-повню для класу задач КА, якщо Z належить КА і по будь якому алгоритму, що рзв"язує Z за час T(n), і довільної задачі Z1 із КА можна ефективно побудувати алгоритм В, який розв"язує Z1 за час T(pb(n)), де pb(n) деякій поліном, що залежить від В.
Задача Z називається NP-повною, якщо вона NP-повна для класу NP. На даний час відомо декілька тисяч NP-повних задач, серед яких можна назвати задачі булівського програмування, комівояжера і т.п. для яких відомо, що вони обчислюються за поліноміальний час на недетермінованих машинах Тюрінга. Але не відомо, чи ці NP-повні задачи належать класу P.
Цікаво, що задача ізоморфізму графів належить класу NP,але досі невідомо : 1) чи належить вона класу Р; 2) чи є вона NP-повною ?
Четвертий, експериментальний напрямок пов"язаний з "прокруткою" програми П на скінченній множині вхідних даних, заміром часу її роботи і прямою побудовою по цих замірах функції складності fп(n).
Такий підхід найбільш поширений при оцінці ефективності роботи паралельних, багатопроцесорних ЕОМ і мереж із розподіленою обробкою інформації, але широко і для звичайних послідовних програм, а саме, для виміру реальної швидкодії ЕОМ при реалізації задач практики відносно великої розмірності, так як оцінка ЕОМ по тактовій швидкодії є дуже "грубою".
Тому необхідно, щоб мати уявлення про те, які задачі можуть бути практично реалізовані на конкретному класі ПЕОМ, провести обчислювальні експерименти по оцінці швидкодії ПЕОМ, що і відображено в завданні на дану лабораторну роботу.
2. Завершуючи даний розділ зауважимо, що в теорії алгоритмів широко використовуються дуже великі цілі числа. Так геделiвська нумерація послідовності (x1,x2,..xk) кодусться числом p0 5x1 * p1 5x2 0 * ...pk 5xk 0,де pi - це i-е просте число, а ^ - операцiя пiднесення у степiнь.
В той же час, цілочислові типи даних , що вбудовані в мови програмування, можуть працювати не більше ніж з 10-розрядними числами. Тому для потреб теорії алгоритмів необхідно реалізувати алгоритми емуляції на ЕОМ арифметичних операцій над багаторозрядними числами, одночасно проаналізувавши практичну цінність теоретичних побудов.
Зрозуміло, що актуальними є проблеми експериментальної оцінки складності алгоритмі в багатократної точності.
II. ПОРЯДОК РОБОТИ
1. Вивчити поняття складності алгоритмів.
2. Використовуючи функцію типу get time , скласти програми на одній із мов програмування, що дадуть можливість наближено оцінити складність основних цілочислових арифметичних операцій.
3. На основі машинних експериментів спробувати апроксимувати функції складності для цих операцій.
4.1 Вибрати i створити необхідні типи даних для реалізації арифметичних операцій багатократної точності над натуральними числами.
4.2 На основі відомих із шкільного курсу алгоритмів додавання, віднімання, множення та ділення DIV ( "у стовпчик") натуральних чисел із N в десятковій системі числення, а також функцій піднесення у степінь і залишку від ділення MOD над N, розробити машинно-орiентований алгоритм для цих операцій та функцій над багаторозрядними натуральними числами.
4.3 Засобами мови Паскаль або Си реалізувати i вiдлагодити відповідні процедури для багаторозрядних чисел.
5.1 Використовуючи функцію типу time із ДОС, скласти програми , що дадуть можливість наближено оцінити складність основних цілочислових операцій арифметики багатократної точності.
5.2 На основі машинних експериментів спробувати апроксимувати функції складності для цих операцій.
6. Здати викладачеві розроблені процедури, продемонструвавши їх працездатність на конкретних багаторозрядних числах.
7. Проаналізувати результати лабораторної роботи .
8. Оформити звіт з лабораторної роботи.
III. ЗМІСТ ЗВІТУ
Звіт повинен містити:
1) назву роботи;
2) мету роботи;
3) короткий теоретичний вступ;
4) завдання до лабораторної роботи;
5) тексти розроблених і відлагоджених програм;
6) результати машинних експериментів із функціями складності;
7) аналіз результатів та висновки.
IV.КОНТРОЛЬНІ ЗАПИТАННЯ
1. Що таке функції складності алгоритму (програми) ?
2. Поліноміальні та експоненційні функції складності.
3. Якій критерій практичної обчислювальності програм?
4. Що означають О(g(х)) i o(h(x)) ?
5. Напрямки теорії складності.
6. Чи кожну функцію можна обчислити за оптимально можливий час?
7. Р- і NP- складності : проблеми.
8. Приклади задач із Р.
9. NP-повні задачи. Приклади.
10. Статус задачі ізоморфізму графів.
11. Практичний підхід до оцінки швидкодії ПЕОМ.
12. Арифметичні операції багатократної кратності: мотивація.
РЕКОМЕНДОВАНА ЛІТЕРАТУРА
1. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций.- М.: ,Мир, 1983.
2. Ахо А.,Хопкрофт Д.,Ульман Д. Пострение и анализ вычислительных алгоритмов.-М.: Мир, 1979.-536с.
3. Мальцев А.И. Алгоритмы и рекурсивные функции.-М.,Наука, 1965.
4. Гудман С.,Хидетниеми С. Введение в разработку и анализ алгоритмов.-М.: Мир, 1981.-368с.
Хід роботи
Приклад:
Лабораторна робота
Лабораторна робота №1 Швидкодія
unit main;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, XPMan, Grids, ExtCtrls, ComCtrls, TabNotBk;
type
TfrmMain = class(TForm)
XPManifest: TXPManifest;
edtX: TEdit;
edtY: TEdit;
cbxOperations: TComboBox;
btnOperations: TButton;
stxResult: TStaticText;
strgrdPerfomance2: TStringGrid;
btnPerfomance2: TButton;
Label1: TLabel;
btnPerfomance: TButton;
lbledtCounter: TLabeledEdit;
strgrdPerfomanceResult: TStringGrid;
procedure btnPerfomanceClick(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure btnOperationsClick(Sender: TObject);
function Add(a,b:string):string;
function Sub(a,b:string):string;
function Mul(a,b:string):string;
function Div_(a,b:string):string;
procedure btnExitClick(Sender: TObject);
procedure btnPerfomance2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
frmMain: TfrmMain;
implementation
{$R *.dfm}
procedure TfrmMain.btnPerfomanceClick(Sender: TObject);
Var time : integer;
i,j,k : longint;
r,ir,jr : double;
begin
Screen.Cursor:=crHourGlass;
//Integer numbers
k:=12345;
time:=GetTickCount();
for i:=1 to StrToInt(lbledtCounter.Text) do
j:=time + k;
time:=getTickCount()-time;
strgrdPerfomanceResult.Cells[1,1]:=FloatToStrF(StrToInt(lbledtCounter.Text)/time*1000,ffExponent,4,2);
time:=GetTickCount();
for i:=1 to StrToInt(lbledtCounter.Text) do
j:=time - k;
time:=getTickCount()-time;
strgrdPerfomanceResult.Cells[1,2]:=FloatToStrF(StrToInt(lbledtCounter.Text)/time*1000,ffExponent,4,2);
time:=GetTickCount();
for i:=1 to StrToInt(lbledtCounter.Text) do
j:=time * k;
time:=getTickCount()-time;
strgrdPerfomanceResult.Cells[1,3]:=FloatToStrF(StrToInt(lbledtCounter.Text)/time*1000,ffExponent,4,2);
time:=GetTickCount();
for i:=1 to StrToInt(lbledtCounter.Text) do
j:=time div k;
time:=getTickCount()-time;
strgrdPerfomanceResult.Cells[1,4]:=FloatToStrF(StrToInt(lbledtCounter.Text)/time*1000,ffExponent,4,2);
//Real numbers
r:=123143454.34233; ir:=213.34;
time:=GetTickCount();
for i:=1 to StrToInt(lbledtCounter.Text) do
jr:=r + ir;
time:=getTickCount()-time;
strgrdPerfomanceResult.Cells[2,1]:=FloatToStrF(StrToInt(lbledtCounter.Text)/time*1000,ffExponent,4,2);
time:=GetTickCount();
for i:=1 to StrToInt(lbledtCounter.Text) do
jr:=r - ir;
time:=getTickCount()-time;
strgrdPerfomanceResult.Cells[2,2]:=FloatToStrF(StrToInt(lbledtCounter.Text)/time*1000,ffExponent,4,2);
time:=GetTickCount();
for i:=1 to StrToInt(lbledtCounter.Text) do
jr:=r * ir;
time:=getTickCount()-time;
strgrdPerfomanceResult.Cells[2,3]:=FloatToStrF(StrToInt(lbledtCounter.Text)/time*1000,ffExponent,4,2);
time:=GetTickCount();
for i:=1 to StrToInt(lbledtCounter.Text) do
jr:=r / ir;
time:=getTickCount()-time;
strgrdPerfomanceResult.Cells[2,4]:=FloatToStrF(StrToInt(lbledtCounter.Text)/time*1000,ffExponent,4,2);
Screen.Cursor:=crDefault;
end;
procedure TfrmMain.FormCreate(Sender: TObject);
begin
strgrdPerfomanceResult.Cells[1,0]:='Ö³ë³';
strgrdPerfomanceResult.Cells[2,0]:='ijéñí³';
strgrdPerfomanceResult.Cells[3,0]:='Ö³ë³ áàãàòîðîçðÿäí³';
strgrdPerfomanceResult.Cells[0,1]:='+';
strgrdPerfomanceResult.Cells[0,2]:='-';
strgrdPerfomanceResult.Cells[0,3]:='*';
strgrdPerfomanceResult.Cells[0,4]:='div, /';
strgrdPerfomance2.Cells[1,0]:='+';
strgrdPerfomance2.Cells[2,0]:='-';
strgrdPerfomance2.Cells[3,0]:='*';
strgrdPerfomance2.Cells[4,0]:='div';
strgrdPerfomance2.Cells[0,1]:='10';
strgrdPerfomance2.Cells[0,2]:='20';
strgrdPerfomance2.Cells[0,3]:='40';
strgrdPerfomance2.Cells[0,4]:='80';
end;
procedure TfrmMain.btnOperationsClick(Sender: TObject);
begin
case cbxOperations.ItemIndex of
0:stxResult.Caption:=Add(edtX.Text,edtY.Text);
1:stxResult.Caption:=Sub(edtX.Text,edtY.Text);
2:stxResult.Caption:=Mul(edtX.Text,edtY.Text);
3:stxResult.Caption:=Div_(edtX.Text,edtY.Text);
end;
end;
function TfrmMain.Add(a, b: string):string;
var
i,j,k,r : integer;
begin
r:=0; Result:='';
k:=length(a);
if length(b)>length(a) then
k:=length(b);
for i:=length(a)+1 to length(b) do
a:='0'+a;
for i:=length(b)+1 to length(a) do
b:='0'+b;
for i:=k downto 1 do
begin
j:=StrToInt(a[i])+StrToInt(b[i])+r;
r:=j div 10;
Result:=IntToStr(j mod 10)+Result;
end;
if r<>0 then Result:=IntToStr(r)+Result;
end;
function TfrmMain.Sub(a, b: string): string;
var
i,j,k,r : integer;
begin
r:=0; Result:='';
k:=length(a);
if length(b)>length(a) then
k:=length(b);
for i:=length(a)+1 to length(b) do
a:='0'+a;
for i:=length(b)+1 to length(a) do
b:='0'+b;
for i:=k downto 1 do
begin
if StrToInt(a[i])>=StrToInt(b[i])+r then
begin
j:=StrToInt(a[i])-StrToInt(b[i])-r;
r:=0;
end else begin
j:=10+StrToInt(a[i])-StrToInt(b[i])-r;
r:=1;
end;
Result:=IntToStr(j mod 10)+Result;
end;
while (Result[1]='0') and (Length(Result)<>1) do delete(Result,1,1);
end;
function TfrmMain.Mul(a, b: string): string;
var
Results:array of string;
i,j,r,t : integer;
s : string;
begin
if length(a)<length(b) then
begin
s:=a; a:=b; b:=s;
end;
SetLength(Results,length(b));
r:=0; Result:='';
for i:=length(b) downto 1 do
begin
for j:=length(b)-1 downto i do
Results[length(b)-i]:=Results[length(b)-i]+'0';
for j:=length(a) downto 1 do
begin
t:=StrToInt(b[i])*StrToInt(a[j])+r;
r:=t div 10;
Results[length(b)-i]:=IntToStr(t mod 10)+Results[length(b)-i];
end;
if r<>0 then Results[length(b)-i]:=IntToStr(r)+Results[length(b)-i];
r:=0;
end;
s:='0';
for i:=0 to length(b)-1 do
s:=Add(s,Results[i]);
Result:=s;
end;
function TfrmMain.Div_(a, b: string): string;
function Equ(a0, b0: string): boolean;
var
i : integer;
r : boolean;
begin
r:=False; Result:=False;
if a0<>'' then
while (a0[1]='0') and (Length(a0)<>1) do
delete (a0,1,1);
if Length(a0)<Length(b0) then
Result:=True;
if Length(a0)=Length(b0) then
begin
i:=1;
repeat
if (a0[i]>b0[i]) then
r:=True;
if (a0[i]<b0[i]) then
begin
Result:=True;
r:=True;
end;
inc(i);
until r or (i=Length(a0)+1);
end;
end;
var
R1,index,k : integer;
s : string;
begin
Result:='';
s:=''; index:=0;
repeat
k:=0;
while Equ(s,b) and (index<length(a)) do
begin
inc(index);
s:=s+a[index]; inc(k);
if k>1 then Result:=Result+'0';
end;
R1:=0;
while not Equ(s,b) do
begin
inc(R1);
s:=Sub(s,b);
end;
if s[1]='0' then s:='';
Result:=Result+IntToStr(R1);
until index=length(a);
while (Result[1]='0') and (Length(Result)<>1) do delete(Result,1,1);
end;
procedure TfrmMain.btnExitClick(Sender: TObject);
begin
frmMain.Close;
end;
procedure TfrmMain.btnPerfomance2Click(Sender: TObject);
const
counter = 2500;
Var time : integer;
i,j : longint;
sa,sb,sc : string;
begin
Randomize;
Screen.Cursor:=crHourGlass;
//j:=0; k:=12345;
for i:=1 to 4 do
begin
sa:=''; sb:='';
for j:=1 to i*10-1 do
begin
sa:=sa+IntToStr(Random(10));
sb:=sb+IntToStr(Random(10));
end;
sa:='5'+sa;
sb:='3'+sb;
// +
time:=GetTickCount();
for j:=1 to counter do
sc:=Add(sa,sb);
time:=GetTickCount()-time;
strgrdPerfomance2.Cells[1,i]:=FloatToStrF(counter/time*1000,ffExponent,4,2);
// -
time:=GetTickCount();
for j:=1 to counter do
sc:=Sub(sa,sb);
time:=GetTickCount()-time;
strgrdPerfomance2.Cells[2,i]:=FloatToStrF(counter/time*1000,ffExponent,4,2);
// *
time:=GetTickCount();
for j:=1 to counter do
sc:=Mul(sa,sb);
time:=GetTickCount()-time;
strgrdPerfomance2.Cells[3,i]:=FloatToStrF(counter/time*1000,ffExponent,4,2);
// div
time:=GetTickCount();
for j:=1 to counter do
sc:=Div_(sa,sb);
time:=GetTickCount()-time;
strgrdPerfomance2.Cells[4,i]:=FloatToStrF(counter/time*1000,ffExponent,4,2);
end;
Screen.Cursor:=crDefault;
end;
end.
Висновок: на цій лабораторній роботі я дослідив швидкодію основних математичних операцій над цілими, дійсними числами, а також над багато розрядними числами, для точної роботи з якими необхідно застосовувати спеціальні методи роботи (наприклад числа зображати як послідовність символів). Для сьогоднішніх комп'ютерів виконання простих арифметичних операцій не складає ніякої проблеми - продуктивність сучасних процесорів така, що ми не помічаємо різниці між різними типами дій. Щодо багато розрядних чисел - то з ними робота набагато повільніша, і розряд тут грає вирішальну роль. Моя програма універсальна - дозволяє обчислювати операції над числами розрядності, яка обмежується доступними ресурсами ПК. Тут ми бачимо що при виконання операцій +, - час виконання при збільшенні розрядів збільшується лінійно, а при операції множення - експоненційно, що і не дивно, адже необхідно кожен раз рахувати суми.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора