1. Основни понятия. Варианти на алгоритми. Влияние върху производителността. Въведение в анализа Алгоритъм



страница3/5
Дата31.12.2017
Размер0.81 Mb.
1   2   3   4   5

Селективна сортировка. Този алгор. раб. по сл. начин 1-во намира най-малкият елемент от масива и го разменя с този от 1-ва позиц. После намир 2-я най-малък ел. и го разм. с този от 2 поз. Продълж. по този нач докато целия мас. се сортира. Методът се нар.селек.сорт.защ.той раб чрез повта-рящ се избор на мин.оставащ елемент.

Пример с числа :



Програмна реализация

void selection (Item a[], int l, int r)

{ int i, j;

for (i = l; i< r; i++)

{ int min = i;

for (j = i+l; j <= r; j++)

if (less(a[j], a[min])) min = j;

exch (a[i], a[min]);

}}

Вътр. цикъл представлява само сравнение, за да провери текущия елем. с намер. наи малък. Вънщният цик. разменя елем. Броят на размените е N -1. Времето на изпълн. се доминира от бр. на размен. Този брой е пропорц на N квадр.Недостатък на сорт. е че вр. за изпълн зависи съвсем малко от вече подредените елем. Методът е добър за сортир. на фаилове с огромни елем. и малки ключове.



Сортировка чрез вмъкване:

Този метод работи по сл. начин: елем. се разглеждат един по един вмъкв. всеки от тях на подходящ. място. сред вече сортир.(запазваики ги по този начин сортирани). Необходимо е да се направи място за вмъквания елем., като преместв. по – гол. елем с 1 поз надясно и после вмъкв. елем. във вакантната. поз.



Пример с числа



Програмна реализация

void insertion(Item a[], int l, int r)

{ int i;

for (i = r; i >l; i--) compexch (a[i-1], a[i]);

for (i = l+2; l<=r; i++)

{ int j = i; Item v = a[i];

while (less(v, a[j-1]))

{ a[j] = a[j-1]; j--; )

a[j]= v; }}

Програмата първо поставя най – малкият елем.на мас. на 1 –ва поз. , така че този елем. да служи като ограничител. Във бтр цикъл тя прави просто присвояване в место размяна. Прогр. завърщ. втр. цикъл., корато вмъкв. елем. е в същата позиция. За всяко i тя сортира елем. a[i]…..a[i-1], които са по – гол. от а[i], след което поставя a[i] в подходяща позиция.



18. Сортиране по метода на мехурчето. Х-ки на елементарните сорт. Деф. Св-ва.

Преминава се през файла като разменяме съседните елем. които не са подредени,. Деиствието продължава докато фаила не се сортира. Главн. предимство на тази сорт. е лесното и реализиране. Но тя е по – бавна от селективната сорт. и сорт. чрез вмъкване.

Сортировк се извърщва на N паса.

Пример с числа.



Програмна реализация

void bubble (Item a[], int l, int r)

{ int i, j;

for (i = l; i

for (j = r; j>i; j--)

comexch(a[j-1], a[j]);

}

За всяко i от l до r-1 вътр. цикъл намира мин елем. сред елем a[i],…, a[r] чрез преминаване през тях от дясно на ляво, сравнявайки и евентуално разменяики последоват елем. и така го поставя в поз. a[i]. Най – малкият елем. минава през всички – така тои изплува като мехурче в началото на масива.



Х-р на елементар сорт.

Селект. сорт, сорт чрез вмъкване и сорт по метода на мехурчето са алгоритми с квадратично вр. за изпълн. и за най – лошия , и за ср. сл. не изискват. допълн памет. В общия сл. времето за испълн. на алгор.за сорт е пропорц на бр. на сравн. които използва, на бр. пъти за които елем. се местят или разместват. или на двете.



Св. Селективната сорт. използва около N²/2 сравнения и N размени. Времето за изпълнение на селективната сортировка при сред. сл. ( O(NlogN) обновявания на min) е нечувствително спрямо входа.

Св. Сортировката чрез вмъкване използва около N²/4 сравн и N²/4 полуразмени (преминавания) в ср. случай и двойно повече в най – лошия.

Св. Сортиров. по Метода на мехурчето използва около N²/2 сравнения и N²/2 размени за средния и наи – лошия случ.

Метод. на мехурчето и сорт. чрез вмъкване работят добре за неслучайни фаилове, които често се появяват в практиката. Общоцелеви сорт. обикновено са неизползв за такива прил.

Разгл. действието на сортировк чрез вмъкване за вече сортиран фаил. Всеки елем. моментално се определя, че е на нужното място в файла и общото време за изпълнение е линейно. Същото е вярно и за сортировка по мет. на мехурчето.

Деф. Инверсия е дв. ключове, които не са в необходим ред в файла.

Св. Сорт. чрез вмъкване и по метода на мехурчето изискват линеен брои сравнения и размени за фаилове с най – мн. константен. брой инверсии, съответни на всеки елемент.

Сортировката чрез вмъкване е подходяща за почти сортиране файлове, където трябва да се добявят няколко елем. Докато метода на мехурчето и селект. сортировка не са.



Св. Сортир. чрез вмъкване използва лин. бр. сравнения. и размени за файлове с най – многоконстант. брой. елем. имащи повече от констант. бр. съответстващи инверсии.

Св. Селективната сортировка работи за линейно време при файлове с големи елем и малки ключове.

19. Сорт. на Шел. Примери и св-ва.

Сорт. на Шел е разшир на селект. сорт, к-то печели скорост, като позволява. размяна на елем, далеч един от др. Идеята е да пренаред. фаил, за да му дад св., че вземаики всеки h елем.(като започнем от някъде), пораждаме сортиран фаил. Такъв фаил се казва че е h сортиран. h сорт. фаил представлява h независ сорт фаилове. поставени последов.

Пример: В сл. стъпката е N/2 = 4; След 1 -вата. итерация пак. сорт. с стъпка 2. и после с стъпка 1.



Програмна реализация

void shellsort (Item a[], int l, int n)

{ int i, j, h;

for ( h =1; h<=(r-l)/9; h = 3*h+1);

for (; h>0;h /=3)

for (i = l+h); i <=r; i++)

{ int j = i; Item v = a[i];

while (j > = l+h) && less(v, a[j - h]))

{ a[j] = a[j-h]; j -=h;}

a[j] = v;

Използват се ограничители и после се заменя всяко срещане на l с h в сортиров. чрез вмъкване, прог. прави h сорт. на фаил.

Един от наи сложните въпроси при Шел сортировката е каква редица на нарастване да се използва. В п-ката обикнов.се използ. редици, които намал. геометрично

Св: Резултата от h – сортир на фаил, к-то е k - нареден, е фаил, к-то e и h и k нареден.

Св: Сортировката на Шел прави по – малк от N(h-1)(k-1) /q сравнения за g – сортиран фаил, к-то е h и k подреден, ако h и k са взаимно прости числа.

Св: Сортиров на Шел прави по – малко от O(N³'²) сравн. за нарастването 1 4 13 40 121 364 и т.н.

Св. Сортиров. на Шел прави по – малко от O(N) на степен 4/3 срав. за нараст 1 8 23 77 281 1073 ...

Св: Сорт. на Шел прави по – малко от О(N(logN)²)

сравн. за нараст 1 2 3 4 6 9 8 12 18 27 16 24 36 54 81.

Сортировката на Шел е много по – бърза от елементарните сортировки. Даже когато нарастванията са степени на 2., но някой редици на нарастване могат да я ускорят 5 и повече пъти.

Сортир. на Шел работи приемливо добре в/у разнообразие от типове файлове, а не само в/у файлове от случайни числа

Сорт. на Шел е избраният метод за много сортиращи приложения защото има прием-ливо време за изпълнение даже за умерено големи файлове и изисква малко кол. код, който е лесно да се пусне в действие.

22 . Сортиране на свързани списъци. Индексно и указателно сортиране.

Свързаните списъци са едни от осн.н-ни за структуриране на данни.След.прог.дава ин-терфейс за тип данни за свърз.списък(изпо-лзваме Item за тип данни на елем.Ф-ята init изгражда списъка,вкл.задел.на необх.па-мет.Ф-ята show отпеч.ключовете в списъ-ка.Прог.за сорт.използ.less,за да сравн.елем и манипул.указ.,за да пренарежд.елем.)

typedef struct node = link;

struct node { Item item; link next; };

link NEW ( Item, link);

link init (int);

void show (link);

link sort (link);

Мд се адаптира селект.сорт.или сорт.по ме-тода на мех.или вмък.за реализ.на свърз. списъци.Селект.сорт.е проста:поддържаме вход.списък(първонач.съд.данн)и изх.спи-сък(събира сорт.резулт.)и просто четем 2-я списък,за да намерим max елем.,махаме го от вход.списък и го добавяме към нач.на изх.списък.

1 стъпка от селект.сорт на свързан списък.



Програмна реализация

link listselection(link h)

{ link max, t, out = NULL;

while (h ->next !=NULL)

{ max = findmax(h);

t = max -> next; max ->next = t->next;

t-> next = out; out = t; }

h->next = out

return (h);

Поддържа се вх. списък( сочен от h->next) и изходен списък (сочен от Out).



Индексно и указателно сортиране.

Сортирането на низ от символи има голямо значение, защото те широко се използват като сортиращи ключове.Низът е указател към символ,така че сорт.ще обработи ма-сив от указ.към символи,пренареждайки ги така,че да сочат низовете в азбучен ред.Ка-то работим с низове в С,трд заделим памет за тях,статично.Пр.указателно сорт.

# include

# include

# include

# include “Item.h”

static char buf [100000];

static int cnt = 0;

int ITEM scan (char **x)

{ int t;


*x = & buf [cnt];

t = scanf (“%s”, *x); cnt+ = strlen (*x)

return t; }

void ITEMshow (char *x)

{ printf (“%s”, x); }

1 прост подход за сорт.без мест.на елем.е да поддържаме индексен масив с ключове-те в елем.,достъпни само за сравн.Нека сорт.елем. са в масива data[0],…,data[N-1] и не искаме да ги местим.За да постигнем ефекта на сорт.,използ.втори масив а от ин-дексите на елем.Започ.с иниц.на a[i]=i, за i=0,…,N-1.Целта на сорт.е да пренаредим индекс.масив а,така че а[0] да дава индекса на елем.данни с най-малък ключ,и т.н.Така манипулираме индексите вместо записите.

Др.възмож.е да използ.указатели,т.е.реализ указателна сорт.За сорт.на масив от елем. указ.сорт.е на индексната но с адресите на масива,добавени към вс.индекс.Указ. сорт обаче е по-обща,защото указ.мд сочат навсякъде,а сорт.елем.не е необх.да са фик-сирани по размер.Ако а е масив от указ. към ключове,тогава викането на сорт.ф-я ще доведе до това,че указ.ще се пренаредят така че ако се обръщаме към тях последов., ще достигнем до ключовете в сорт.ред. Ре-ализ.сравн.като следваме указ.,а размените релиз.чрез размяна на указ.

Глав.причина да използ.индекси или указ. е да избегнем вмешателство в сорт.данни. Мд сорт.файл даже ако всичко което имаме е достъп до него само за четене.Даже с ня-колко масива от индекси или указ.мд сорт. 1 файл по няколко ключа.



28.Постъпателни алгоритми (greedy algorithms). simple scheduling problem

работят поетапно. На всеки етап се взима изглеждащото за най-добро решение, независимо от последиците. Т.е.локален оптимум. Или стратегията е “take what you can get now”.В края на алг.приемаме, че ло-кал.съвпада с глобал.оптимум. Пр.за това е стратегията на връщане на монети: връща на всеки етап монета с мак. възможна ст-ст



$17.61 à 1*$10 +1*$5 +2*$1 + 2*0.25(quarters) +1*0.1 (dime) + 1*0.01(penny).

Този алгоритъм не работи във всички монетарни системи. Друг пример: авт. трафик.



simple scheduling problem

имаме дадени задачи j1 …jN с времена на изпълнение t1…tN и 1 процесор. Искаме разпределяне с цел мин. средно време на завъшване на задача (т.е. на коя мин. средно завършва задача). (няма прекъсване на задача).



Първата завършва след 15, втората след 23, третата след 26, след 36 à общо 100 мин/4 = 25 средно ще завършва задача.

Друга подредба е показана по-долу:ср.време 17.75

Стратегията е най-късата задача – най-напред(тя участва най-много във формиране времената на следв.зад).


Това винаги дава оптимално решение. Нека първата пусната задача е j i1…j iN с времена на завършване: t i1, t i1+t i2, t i1 +t i2 +t i3.
Цената на разпределението става:

I член не зависи от подредбата, а само втория (“к”).


Ако предположим, че в подредба съществува x >y, такова че t ix<t iy, то ако разменим местата на j ix и j iy, втория член нараства и следоват. общата цена намалчва. следоват. всяка подредба в която работите не са наредени в нарастващ ред е неоптимална. Затова се дава приоритет на най-късите задачи първо.

многопоцесорен вариант
Имаме j1……jN; ti….tN и P процесора.
Подрежд. първо на късите зад. Нека Р=3:

задача време


j1 3
j2 5
j3 6
j4 10
j5 11
j6 14
j7 15
j8 18
j9 20

едно решение (започваме с къси задачи и циклим по процесори):



Общо време на завършване 165. Средно 165/9 = 18.33. Друга стратегия (когато Р дели N точно) е: за всеки 0 <= I < N/P поставяме последоват. следващите Р задачи на различен процесор.



минимизация на крайното време на завършване на всички задачи по-горе това е 40 или 38. Ето подредба с t = 34:




очевидно тази подредба не може да се подобри, защото всички са заети през цялото време. Това обаче е друга стратегия – най-късо общо завършване.

29.Кодове на Huffman(компрес.на файл.)
Нормално ASCII има 100 печатащи се символа è log100 =7 бита + 1 бит контрол по четност.Т.е. за С символа са нужни logC бита за кодиране.
Нека във файл имаме само символи a,e,I,s,t , blank, NL. Нека след статистика знаем че във файла има

10 –a; 15 e; 12 I; 3 s; 4 t; 13 blanks; 1 ML. Нужни са 174 бита за съхраняване на поредицата



буква

а

е



I

s

t



spase

NL


код

000


001

010


011

100


101

110


чест:

10

15



12

3

4



13

1


общо

30

45



36

9

12



39

3

174



Ще представим стратегия постигаща за нормален файл 25%пестене и 60%за дълги файлове.Варираме с дължи

ната на кода за разл символи. Най-честите à с най-къс код.При едн. честота – няма значение кой.Ето дърво, даващо н-н за кодировка на азбука от 7 символа:



Данни има само в листата.Кодировката е еднозначна


Ако символ c i е в дълбочина d i и се среща f i пъти, то общ.цена на кодираната инф. е ∑d I * f i.Едно подобре-ние става при свиване дълбочината за възли с 1 листо:

Общата цена става 173, което изобщо не е подобрение.


Винаги работим с пълно дърво. При символи само в листата, всяка последователност от 0 и 1 е еднозначна и мд се декодира.Това е т.нар.префиксно кодиране.
Проблемът се сведе до: намиране на full binary tree с мин. цена, в което символи има само по листата. Ето оптималното за примера (цена 146):



Буква

a

e



I

s

t



spase

NL


код

001


01

10

00000



0001

11

00001



чест

10

15



12

3

4



13

1


общо

30

30



24

15

14



26

5

146



Алгоритъм на Huffman
Имаме С символа.Правим набор дървета.Тегло за дър-во се получава от сума на честотите в листата му. С-1 пъти избираме 2 дървета Т1 и Т2 с мин. тегла и ги обе-диняваме. В нач. имаме С дървета с по 1 възел. В края на алг. имаме 1 дърво и това е оптимал. кодово дърво.
Ето за нашия пример Начало:

първо обединение ( няма значение кое е ляво, така че реализиращата процедура няма да прави връщания назад). Теглото на новополученото д-во е сума:



Реализацията в прог. е лесна: правим нов възел,устано-вяваме 2 указателя и изчисл. тегло.продължаваме:





краят ( след обединението) беше вече показан

Накратко за доказателството, че Хофмановия алгоритъм води до оптимален код:
1. полученото д-во е пълно, така че не може да се подобрява с местене възли нагоре.
2. 2 букви “а, б” с мин. честота са най-долу. Доказваме с използване на обратно твърдение: ако това не е така , (поне едното от а и б не е в най-дълбоко листо), то има някакво г (дървото е пълно) което е там. Но щом а е по-рядко срещано от г, то най-лесно ще подобрим общата цена като разменим а и г .
3. Очевидно, 2 символа във възли с еднаква дълбочина могат да се разместват без променяне на оптималния избор. Отчитаме, че може да сливаме символ – дърво с слято вече. Тогава очевидно азбуката ни се е проме-нила (напр. е,Т4,Т3). Но крайните символи изгражда-щи напр Т3 са по-дълбоко,но и по-рядко срещани от е.
Алг.е greedy,защото на всеки етап правим сливане без оглед на глобал.оптимиз., а само в локален оптимум.
**Разбира се кодиращата инф.следва да се изпрати в началото на файла при трансмисия за да е възможно декодиране.За малки файлове това е лошо(много добавена инф.).
***Алгоритъмът е двупасов – първо се събират данни за честотата, после се кодира. За големи файлове това не е добре – има подходи за обединяване задачите.

30.Проблемът пакетиране.Метод FirstFit
Тези алгоритми са бързи, но не винаги дават оптимално решение. Имаме N пакета с размери s1….s N (0 <= s i <1). Искаме да ги пакетираме в min брой торби, като всяка торба има обем 1. Ето пример:

Съществуват 2 версии на решения:on-line всяка единица се поставя преди следваща (няма връщане назад). Off-line – първо изследваме всички, тогава започваме пакетирване.


On-line алгоритми
Не винаги дават оптималното решение. Разглеждаме поредица от I1 ел.от общо М в тегло ½ -б, следвани от останалите с тегло ½+б (б е нещо малко): очевидно, всички могат да се пакетират в М (1 малка + 1 голяма). Нека алгоритъм А прави това пакетиране. Тогава А ще постави малките I1 (половината) ел. всеки в отделен чувал (а не по 2) – общо напр. в М торби. Но как ще знае че следващите са по-големите, а не обратно. Значи А винаги ползва 2М торби вместо М.
Тъй като краят (общия брой )е неизвестен , алгоритмите от този вид дават само локална гаранция.

Теорема 1 :съществуват вх. поредици, които карат всеки on-line алгоритъм да използва поне 4/3 от оптималния брой торби.
Док. Предполагаме обратното и нека М е четно. Алгоритъм А обработва входна поредица I1 от М малки ел., следвани от М големи. Вече сме обработили първите М ел. и сме използвали б торби. (оптималното е б=М/2). Значи (оптимистично )предполагаме че алгоритъмът постига :
2б/М < 4/3 à б/М <2/3
Нека всички елементи са обработени. Имаме б торби с първите б ел. (нали алгоритъмът работи оптимално и не може да оставя по 2 големи ел. за 1 торба). Тогава след края първите б торби ще имат по 2 ел. (малък и голям), а следащите - по 1 голям. За 2М ел. ще са нужни 2М – б торби. Оптимумът беще М. Следователно: (2М – б) / М < 4/3à б/М >2/3
Имаме противоречие. Следователно няма on-line алгоритъм, даващ по-добро от 4/3 спрямо оптималното решение.

Next fit
проверяваме дали следващата в поредицата може да се постави в торбата, която съдържа последния ел. ако не – нова торба.Работи с линейно време.
Ето резултат над предходната поредица:



Т2 Нека М е оптималния брой торби за пакетиране на I ел. Next fit никога не използва повече от 2М торби.
Док.
Разглеждаме съседните B j и B j+1.
Сумата от обемите в тях е >1, иначе в 1 торба. Aко направим тези разсъждение за всички съседни, виждаме че най-много ½ пространство е похабено. Използвани са най-много двукратен брой торби.
Ето най-лоша последователност на входа:нечетни si имат размер 0.5, четни – размер 2/N. Нека N се дели на 4. Оптимално пакетиране е от N/4 +1.
Реалното в този алгоритъм заема N/2. T.e почти двойно:



First Fit
Предишният алгор. създава нова торба не винаги когато това е нужно, защото разглежда само последната. Напр. за схемата горе, ел. 0.3 може да се постави в В1 или В2 а не в нова. First Fit стратегията сканира торбите подред за да установи дали може да постави новия ел.

Тъй като се сканират предходните торби, à О(N ). Може да се сведе до O(N log N) – ако сканираме както при бинар. търсене.


Видно е че във всеки момент най-много 1 торба може да е запълнена ½, тъй като ако са 2, то мегат да се поставят в 1. Значи най-много 2М спрямо оптимумът от М торби.


31,32. Проблемът пакетиране. Метод Best Fit и Offline алгоритми. Оценки
Тези алгоритми са бързи, но не винаги дават оптимално решение. Имаме N пакета с размери s1….sN (0 <= si <1). Искаме да ги пакетираме в min брой торби, като всяка торба има обем 1. Ето пример:

Best Fit
Вместо да поставяме нов елемент в първа възможна торба, го поставяме там където е възможно, но и има най-малко свободно място.Ето резултата

Елемент с тегло 0.3 е поставен в В3, а не в В2. Има подобрение, но не и за лошите поредици.

1   2   3   4   5


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница