1. Осн понятия. Варианти на алг. Влия-ние в/у произв-стта. Въведение в анализа Алгоритъм
Св. Селективната сортировка работи за линейно време при файлове с големи елем и малки ключове. 23. Сорт. на Шел. Примери и св-ва
Изтегляне 0.84 Mb.
|
- Навигация на страницата:
- 26 . Сортиране на свързани списъци. Индексно и указателно сортиране.
- Индексно и указателно сортиране.
- 28.Постъпателни алгоритми (greedy algorithms). simple scheduling problem
- 30.Проблемът пакетиране.Метод FirstFit
- On - line алгоритми
- Теорема 1
- Next fit
- 31,32. Проблемът пакетиране. Метод Best Fit и Offline алгоритми. Оценки
- Off - line алгоритми
- Лема 2
- 33 .Разделяй и владей – алг. Анализ на времето на изпълнение
- 35.Теорет. подобрения с аритмет. задачи
Св. Селективната сортировка работи за линейно време при файлове с големи елем и малки ключове. 23. Сорт. на Шел. Примери и св-ва. Сорт. на Шел е разшир на селект. сорт, к-то печели скорост, като позволява. размяна на елем, далеч един от др. Идеята е да пренаред. фаил, за да му дад св., че вземаики всеки 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 и повече пъти. Сортир. на Шел работи приемливо добре в/у разнообразие от типове файлове, а не само в/у файлове от случайни числа Сорт. на Шел е избраният метод за много сортиращи приложения защото има прием-ливо време за изпълнение даже за умерено големи файлове и изисква малко кол. код, който е лесно да се пусне в действие.
Свързаните списъци са едни от осн.н-ни за структуриране на данни.След.прог.дава ин-терфейс за тип данни за свърз.списък(изпо-лзваме 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 бита за съхраняване на поредицата
Ще представим стратегия постигаща за нормален файл 25%пестене и 60%за дълги файлове.Варираме с дължи ната на кода за разл символи. Най-честите à с най-къс код.При едн. честота – няма значение кой.Ето дърво, даващо н-н за кодировка на азбука от 7 символа: 
Данни има само в листата.Кодировката е еднозначна Ако символ c i е в дълбочина d i и се среща f i пъти, то общ.цена на кодираната инф. е ∑d I * f i.Едно подобре-ние става при свиване дълбочината за възли с 1 листо: 
Общата цена става 173, което изобщо не е подобрение. Винаги работим с пълно дърво. При символи само в листата, всяка последователност от 0 и 1 е еднозначна и мд се декодира.Това е т.нар.префиксно кодиране. Проблемът се сведе до: намиране на full binary tree с мин. цена, в което символи има само по листата. Ето оптималното за примера (цена 146): 
Алгоритъм на Huffman Имаме С символа.Правим набор дървета.Тегло за дър-во се получава от сума на честотите в листата му. С-1 пъти избираме 2 дървета Т1 и Т2 с мин. тегла и ги обе-диняваме. В нач. имаме С дървета с по 1 възел. В края на алг. имаме 1 дърво и това е оптимал. кодово дърво. Ето за нашия пример Начало: 
първо обединение ( няма значение кое е ляво, така че реализиращата процедура няма да прави връщания назад). Теглото на новополученото д-во е сума: 
Реализацията в прог. е лесна: правим нов възел,устано-вяваме 2 указателя и изчисл. тегло.продължаваме: 
краят ( след обединението) беше вече показан Накратко за доказателството, че Хофмановия алгоритъм води до оптимален код:
Съществуват 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. Има подобрение, но не и за лошите поредици. Off-line алгоритми Сега можем да аналзираме цялата поредица, преди да подреждаме. Големият проблем на on-line алгоритмите е че не пакетират добре големи ел. когато те идват към края. Добре би било големите да ги сортираме отпред. Това е алгоритъмът first fit decreasing: 
В случая това е и оптимал.решение. Не винаги е така. Значи считаме, всички ел. са вече подредени намаляващо.Ще док, че ако оптимал.пакетиране изисква М торби, сега са нужни не-повече от (4М + 1)/3 Лема 1 Нека N ел. (сортирани намаляващо) с размери s1…sN могат да се подрдят оптимално в М торби.Тогава всички ел., които first fit decreasing поставя в допълнителни торби (над М) имат размер най-много 1/3. Док. Нека елемент i е първия в торба М+1. Да докажем si <=1/3. Предполагаме si >1/3. Следва s1,…si-1 >1/3 (иначе лемата е доказана). Тогава в торби В1….ВМ има най-много ел ( нали са >1/3). Тогава в първите торби има по 1 ел. а в оставащите до М по 2 ел. Ако приемем обратното: в торба Вx има 2 ел. , а в торба By à 1 el. и 1<= x < y <= M. Нека x1 и x2 са елементите в Вx и y1 е елементът в By, x1>=y1, а също и x2 >=si то: x1 +x2 >= y1 +si Значи si може да се пъхне в By, но това не беше възможно по предположение. Значи, ако si>1/3, в момента, когато го обработваме, в първите j торби има по 1 ел. а в оставащите M-j по 2 ел. Сега да покажем че няма начин всички елементи да се сложат в торби (тогава не би оставал външен <1/3) За първите j ел. няма начин 2 да се сложат в 1 торба (доказахме че в началото са по 1). Също така никой елемент до si не може да се пъхне в първите торби. Значи j торби са по 1 ел. и елементите с размери sj+1,s j+2…. S i-1 са в М-j торби.Общият брой ел. в тях е 2(М – j) Следователно, елемент si>1/3 няма начин да се вкара в първите М торби: той не може да се вкара в първите j торби, защото те съдържат по 1 ел. Не може и в оставащите M-j торби, защото в тях трябва да се появят 2(M-j) +1 елемента. Това означава в някоя торба следва да има по 3 ел (а всеки беше >1/3).Очевидно предвиж-дането в нач. беше грешно и s i <=1/3 Лема 2 Броят ел. поставени в допълнителните торби е най-много М-1 Док:Приемаме обратното: в допълнителните торби има най-малко М ел. Знаем si <= M Нека Bj е поела общо тегло Wj (1<= j <= M) Нека първите М ел. в допълнителни торби са с размер x1…xM. Тъй като елементите в първите М торби + елементите в първите М допълнителни са част от всички то: 
Това е невъзможно, тъй като тези N ел. са пакетирани в М торби. Следователно допълнителните торби са най-много М-1 Теорема Нека М е оптимал. брой торби за I елемента. First Fit decreasing никога не използва повече от (4М+1)/3 торби. Имаме М-1 допъл.ел.с макс.размер 1/3. Значи допълн. торби са най-много (М-1)/3. Общият бр. торби използвани в метода е : (4М –1) /3 <= (4М +1)3 First Fit decreasing е добър и бърз подход 33.Разделяй и владей – алг. Анализ на времето на изпълнение Анализ на времето на изпълнение: = време за изпълнение на частите + константно време на излъчване крайния резултат: T(N)= 2T(N/2) +O(N). Теорема:Реш.на уравн.T(N)=аT(N/b)+O(Nk) а>=1; b >1 (а – броят на зад.; в – частите) е: 
Това са и 3 случая на рекурентно разбиване на задача на подзад. Напр. сортировка чрез разделяне и сливане : a=b=2; k=1. Имаме втория случай и отговор: O(NlogN) Ако имаме 3 проблема и всеки е над половината данни и комбинирането за краен резултат изисква O(N) време, то a=3,b=2, k=1. log 2 3 1.59 Имаме случай 1 и O(N )= O(N ) Ако в горния пример времето за обединяване на резултата беше O(N ² ),то сме във случай 3 и: O(N²) 34.Прoблемът“на-близкостоящи точки” Имаме Р точки в равнината, p1=(x1,y1)….. Разстоянието м/ду тях :[(x1 –x2)² + (y1-y2)² ] Търсим най-близкостоящите точки. Имаме N(N-1)/2 разстояния. Пълен тест: O(N ² ) Друг подход: Нека точките са сортирани по x координатата си. Ако не са, допълнително време O(NlogN): 
Разделяме ги по вертикала на 2 равни части P L P R: 
dl и dr могат дасе изчислят рекурсивно ( O(NlogN) . Остава да изчислим dc за O(N) време и да постигнем: O(NlogN) +O(N) Нека δ=min(dl,dr). Ще изчисляваме dc само ако подобрява б. Точките в лентата са малко: една по една ( O(N) ): //points are all in the strip for(I=0;I< numPoinsInStrip; I++) for (j=I+1; j ако точките в лентата са много (почти всички), горния подход е слаб. Нека т. са сортирани в лентата по у коорд. Тогава ако у коорд на pi и pj се различават с повече от б, можем да преминем към p i+1. Ускорен вариант: for(I=0; I if (pi and pj ’coordinates differ by more than б) break; // next pi. else if(dist(pi,pj)<б) б = dist(pi,pj); само p4 и p5 се разглеждат, съобразно горната модификация: 
най-много 7 т. могат да се разглеждат в правоъгълната област б *2б: 
Времето за това < O(N). Имаме О(NlogN) от рекурсивните повиквания отляво и отдясно + O(N). За сортирането по у е нужно още O(NlogN) за всяко рекурсивно повикване или общо O(Nlog ² N). (пълно претърсване: O(N ² ). Mожем още да ускорим като предварително сортираме и по x и по у и изработим 2 списъка с точки, сортирани съответно. ( O(NlogN) време в началото ). После претърсваме списъка по x и махаме всички точки с коорд. > б. Автоматично остават само тези в линията и то сортирани по у. Това изисква O(N). общо време O(NlogN) +O(N) 35.Теорет. подобрения с аритмет. задачи * Умножение на цели числа - За малки ч-ла - линейно време. - За големи, времето става квадратично. Нека имаме N р-дни ч-ла X и Y. Знакът определяме лесно. По класически алгоритъм O(N ² ) : всяка цифра на X се умножава по всяка на Y. 
Имаме 4 умножения с N/2 цифри: T(N)= 4T(N/2) + O(N)
Каталог: lib lib -> Преводач Елена Атанасова Коректор Ива Данева Формат 84/108/32 Печатни коли 15 дф „абагар" Велико Търново ик „сова" Варна как да се използва тази книга lib -> За медитацията ошо въведение lib -> Поредица ние обичаме животните lib -> Тайната на скорпион lib -> Разчупване на оковите Победа над: Отрицателните мисли lib -> Въведение Изтегляне 0.84 Mb. Сподели с приятели:
|
