Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Складність алгоритмів. Реалізація на ПЕОМ цілочислових арифметичних операцій багатократної точності
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2008
Тип роботи:
Теорія
Предмет:
Інші
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет «Львівська політехніка»
Кафедра автоматизованих систем управління
Звіт
По лабораторній роботі №1
на тему:
«Складність алгоритмів. Реалізація на ПЕОМ цілочислових арифметичних операцій багатократної точності»
з дисципліни:
«Теорія алгоритмів і математичні основи представлення знань»
Львів-2008
Тема: Складність алгоритмів. Реалізація на ПЕОМ цілочислових арифметичних операцій багатократної точності.
Мета: 1) експериментально дати оцінку складності елементарних арифметичних функцій мов програмування типу Паскаль; 2)забезпечити засобами мови Паскаль або Си емуляцію арифметичних операцій додавання, віднімання, множення 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.
Четвертий, експериментальний напрямок пов"язаний з "прокруткою" програми П на скінченній множині вхідних даних, заміром часу її роботи і прямою побудовою по цих замірах функції складності fп(n).
Такий підхід найбільш поширений при оцінці ефективності роботи паралельних, багатопроцесорних ЕОМ і мереж із розподіленою обробкою інформації, але широко і для звичайних послідовних програм, а саме, для виміру реальної швидкодії ЕОМ при реалізації задач практики відносно великої розмірності, так як оцінка ЕОМ по тактовій швидкодії є дуже "грубою".
Тому необхідно, щоб мати уявлення про те, які задачі можуть бути практично реалізовані на конкретному класі ПЕОМ, провести обчислювальні експерименти по оцінці швидкодії ПЕОМ, що і відображено в завданні на дану лабораторну роботу.
2. Завершуючи даний розділ зауважимо, що в теорії алгоритмів широко використовуються дуже великі цілі числа. Так геделiвська нумерація послідовності (x1,x2,..xk) кодусться числом p0 5x1 * p1 5x2 0 * ...pk 5xk 0,де pi - це i-е просте число, а ^ - операцiя пiднесення у степiнь.
В той же час, цілочислові типи даних , що вбудовані в мови програмування, можуть працювати не більше ніж з 10-розрядними числами. Тому для потреб теорії алгоритмів необхідно реалізувати алгоритми емуляції на ЕОМ арифметичних операцій над багаторозрядними числами, одночасно проаналізувавши практичну цінність теоретичних побудов.
Завдання: Порівняти час перевірки перших N натуральних чисел на простоту строго за визначенням та з використанням оптимізованого алгоритму (перевірка часу на додавання, віднімання, множення, ділення чисел).
Лістинг програми:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <dos.h>
#define N 5
int main(void)
{
long i;
unsigned int before;
unsigned int after;
struct time t;
double time_one;
long NuM_iteration=200000000;
long b;
unsigned int Times[N];
gettime(&t);
Times[0]=t.ti_hour*3600+t.ti_min*60+t.ti_sec+t.ti_hund/1000;
for(i=0;i<NuM_iteration;i++)
b=223*523;
gettime(&t);
Times[1]=t.ti_hour*3600+t.ti_min*60+t.ti_sec+t.ti_hund/1000;
for(i=0;i<NuM_iteration;i++)
b=1000/20;
gettime(&t);
Times[2]=t.ti_hour*3600+t.ti_min*60+t.ti_sec+t.ti_hund/1000;
for(i=0;i<NuM_iteration;i++)
b=2788+5855;
gettime(&t);
Times[3]=t.ti_hour*3600+t.ti_min*60+t.ti_sec+t.ti_hund/1000;
for(i=0;i<NuM_iteration;i++)
b=5344-2456;
gettime(&t);
Times[4]=t.ti_hour*3600+t.ti_min*60+t.ti_sec+t.ti_hund/1000;
printf("\t\t\tChas vukonnania operatsiy \n");
printf("-----------------------------------------------------------------------------\n");
time_one=((double)Times[1]-(double)Times[0])/NuM_iteration;
printf("Mnogennia : %.9f\n",time_one);
printf("-----------------------------------------------------------------------------\n");
time_one=((double)Times[2]-(double)Times[1])/NuM_iteration;
printf("Dilennia : %f\.9\n",time_one);
printf("-----------------------------------------------------------------------------\n");
time_one=((double)Times[3]-(double)Times[2])/NuM_iteration;
printf("Dodavannia : %.9f\n",time_one);
printf("-----------------------------------------------------------------------------\n");
time_one=((double)Times[4]-(double)Times[3])/NuM_iteration;
printf("Vidnimannia : %.9f\n",time_one);
printf("-----------------------------------------------------------------------------\n");
getch();
clrscr();
return 0;
}
Результати машинних експериментів:
Робота з цілими числами
Робота з дійсними числами
Висновки: під час виконання даної лабораторної роботи я дослідив складність алгоритмів обчислення. Реалізував на ПЕОМ алгоритм обчислення цілочислових арифметичних операцій багатократної точності. Також слід зауважити, що запропонований спосіб вимірювання часу, не зважаючи на те, що видає значення з точністю до стананосекундного інтервалу, насправді видає значення з точністю до інтервалу квантування процессорного часу, який для ОС Windows становить за замовчуванням 0,2сек. Використання недокументованого методу зниження інтервалу квантування дозволяє підвищити точність приблизно до 15 мсек.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора