Алгоритам
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/55/LampFlowchart_sr.svg/250px-LampFlowchart_sr.svg.png)
Алгоритам је опис за решавање неког проблема. Реч долази из презимена персијског математичара Ал Хорезмија. Алгоритам је био израз који описује начин рачунања децималним бројевима уведеним око 1600. године у Европи. Алгоритмичарима су се раније звали они математичари који не оперишу симболима множина представљеним на абакусу, него једним (индијским или арапским) системом знакова за бројеве (од 16. века раширеним у Европи).
У новије време, алгоритам је појам који се готово искључиво везује за информатику и, мада не постоји јединствена општеприхваћена дефиниција, подразумева се да је у питању некако описана процедура за обављање посла. У ту сврху се дефинишу алгоритамски језици. То су формализовани језици којима се релативно лако описују поступци решавања проблема представљених алгоритмом, такви су на пример програмски језици Алгол, Фортран и Кобол.
У математичкој логици је алгоритам генерализован појам и односи се на поступак за поступно претварање низова знакова.
О настанку
[уреди | уреди извор]![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/11/1983_CPA_5426_%281%29.png/220px-1983_CPA_5426_%281%29.png)
Алгоритам је у математику увео персијски математичар Мухамед Ал Хорезми. Написао је књигу Ал Хорезми о индијској вештини рачунања где у арапску математику уводи индијске цифре и децимални бројни систем. Ова књига бива касније преведена на латински као Algoritmi de numero indorum. Од лошег латинског превода његовог презимена и потиче реч алгоритам, и дуго је означавала поступак за рачун са децималним бројним системом (и индијским односно, како се касније причало, арапским цифрама).[1][2]
Алгоритам представља шематски приказано, поступно решавање неког проблема, тока неког процеса или израде неког предмета.
Дефиниција
[уреди | уреди извор]Алгоритам је коначан и прецизно дефинисан процес, низ добро дефинисаних правила, којим се улазне вредности трансформишу у излазне, или се описује извршавање неког поступка.
Данас се реч алгоритам често везује за појам рачунарства мада уопштено алгоритам можемо сматрати као упутство како решити неки задатак или проблем. Тако се и упутство за слање човека на Месец и упутство за прављење руске салате састоји од низа корака, поступака, које треба урадити и који воде испуњењу циља или решавању проблема. Упутство може садржати кораке који се понављају више пута или кораке када треба донети неку одлуку, на основу неког критеријума. Добро упутство предвиђа и поступак када нису сви услови испуњени нпр. прва посада за слање на Месец изгорела при тестирању, или нема кромпира у фрижидеру а почели смо да спремамо жуманце за мајонез. Коректно извршавање сваког корака не решава задатак ако је алгоритам био погрешан.
Различити алгоритми могу решити исти проблем различитим низом поступака уз мање или више напора, за краће или дуже време. Обзиром да је резултат исти, алгоритми се могу поредити по својој ефикасности, брзини или комплексности.
Алгоритми могу бити приказани или реализовани на више начина:
- природним језиком (разумљив само говорницима тог језика)
- Графички, дијаграмом тока (блок-дијаграмом) или структурним дијаграмима или
- текстуално - псеудокодом, вештачким прецизно дефинисаним језиком који личи на програмски језик
- одговарајућим програмским језиком.
Примери алгоритма
[уреди | уреди извор]Пример алгоритма из свакодневног живота је кување чаја. Сваки корак припремања чаја мора бити извршен правилно како би се могло прећи на следећи и у коначном времену добили скуван чај.
Алгоритам кувања чаја гласи:
- Узети лонче и сипати воду.
- Укључити ринглу.
- Сачекати док вода не прокључа.
- Кад вода прокључа, скинути лонче и искључити ринглу.
- Ставити кесицу чаја у лонче.
- По жељи, додати кашику шећера, млеко или лимун.
- Сипати чај у шољу.
Из овог једноставног примера може се видети поступност и коначност алгоритма. Наиме, нема превише користи од алгоритма који се никада не завршава или алгоритма чије се наредбе изводе непредвидљиво или им је резултат непредвидљив.
Пример комплекснијег алгоритма је Еуклидов алгоритам за одређивање највећег заједничког делиоца:
- Поделити број a бројем b при чему се добија количник c и остатак r
- Број a узима вредност броја b
- Број b узима вредност r
- Понављати све док остатак r не буде једнак 0. Највећи заједнички делилац је тренутна вредност броја a
Историја
[уреди | уреди извор]Први алгоритам који се може сматрати процедуром чија је намена рачун на аутоматској машини је написала Ејда Бајрон 1842. године. У питању је алгоритам за рачун Бернулијевих бројева на аналитичкој машини Чарлса Бебиџа. Та машина никад није прорадила, али је њен алгоритам оставио дубок траг. Данас се то признаје као први рачунарски алгоритам, а Ејда Бајрон, леди Лавлејс, је призната као први програмер у историји.[3][4] У њену част је и један од најкомплекснијих програмских језика добио назив Ада.
Значајан напредак у формализацији увођења алгоритма у математику и логику је учинио Алан Тјуринг у својим радовима дефинисањем Тјурингове машине. То је примитиван аутомат, мисаона творевина, али поседује могућност извођења неколико операција које су довољне за извођење скоро свих алгоритама. Черч-Тјурингова теза тврди да се сваки алгоритам који је добро дефинисан може извршити на таквој машини. Тако се, и поред једноставности ове машине, зачела теорија коначних аутомата као нова област. Истраживањем се дошло и до теоријских проблема: Тјурингов проблем заустављања, НП-тежак проблем, НП-потпун проблем и тако даље.
Особине
[уреди | уреди извор]Алгоритми поседују следеће особине:
- дискретност — у одвојеним корацима се извршавају дискретне операције алгоритма који воде ка коначном циљу;
- резултативност — означава способност алгоритма да после коначног броја корака даје излазне податке;
- детерминисаност — за исте улазне податке алгоритам увек генерише исте вредности на излазима и
- масовност — алгоритам је применљив на већи број улазних вредности.
Елементи
[уреди | уреди извор]Решење било ког проблема који се може решити помоћу рачунара, се може изразити као суперпозиција следећих структура: секвенце, селекције и итерације.
Секвенца је уређен низ инструкција где се по извршењу i-те инструкције, може прећи на i+1 инструкцију, затим на i+2 инструкцију и тако даље.
Селекција омогућава избор једног тока којим ће се наставити извршавање инструкција. Избор тока врши се провером услова који је дефинисан као логички израз (предикат).
Разликује се следећи типови селекција:
- IF услов THEN операција (ако је услов испуњен тада изврши операцију)
- IF услов THEN операција1 ELSE операција2 (ако је услов испуњен, тада изврши операцију 1, у супротном изврши операцију 2)
- CASE услов OF
- вредност1: операција1
- вредност2: операција2
- ...
- ELSE операцијаn (ако услов има вредност1 изврши операцију1, ако услов има вредност2, изврши операцију2... у супротном изврши операцијуn)
Итерација омогућава понављање операција тела операције потребан број пута. Број понављања се контролише условом у форми предиката. Разликују се следећи типови итерације:
- итерације са изласком на врху
- WHILE услов DO операција (све док је услов испуњен, ради операцију)
- FOR почетак TO крај DO операција (од почетне вредности до крајње вредности, ради операцију)
- итерације на изласку на дну
- REPEAT операција UNTIL услов (понављај операцију све док се не испуни услов)
- итерације са изласком у средини (слабо синтаксно подржане, имају углавном теоријски значај)
Формализација
[уреди | уреди извор]Алгоритам је кључни појам у рачунарској обради података јер је рачунарски програм известан алгоритам који рачунару објашњава које кораке (наредбе) и којим редоследом треба да обавља. Тако се алгоритмом може сматрати било који низ инструкција која се може урадити на Тјуринг-комплетној машини.
Типично, када се уз алгоритам везује појам обраде података, подразумева се да се податак прво учита преко улазне јединице а исписује се на излазну јединицу или чува за каснију употребу. Сачувани подаци се сматрају делом унутрашњег стања система.
За сваки рачунарски посао алгоритам мора бити јасно дефинисан; наведен на начин који подразумева све могуће ситуације које се могу појавити. Значи, сваки условни корак се мора систематично обрадити, случај по случај; услов за сваки случај мора бити јасан и израчунљив.
Пошто је алгоритам јасан низ прецизних корака, редослед израчунавања је увек критичан за функционисање алгоритма. Претпоставља се да су инструкције наведене јасно, да почињу од врха и да теку до дна. Ова идеја се формално описује контролом тока.
Код овакве формализације се унапред узимају претпоставке о императивном програмирању. Ово је најуобичајенији концепт у програмирању и описује поступке на механички начин.[тражи се извор] Јединствено за овај концепт је операција додељивања, што је давање вредности променљивој. Ово произилази из интуитивног поимања меморије као привременог складиштења односно памћења. Ниже у тексту се може наћи пример оваквог додељивања.
Постоје и другачији концепти у изградњи алгоритма, погледати функционално програмирање и логичко програмирање.
Имплементација
[уреди | уреди извор]Алгоритми се реализују у облику рачунарских програма, али могу и на други начин. Сем електричних кола и механичких справа које обављају неке радње исто тако постоје и биолошке неуралне мреже каква је, на пример, мозак човека који је научио математичке операције или инсекта који премешта храну.
Анализа и проучавање алгоритама је једна област рачунарства и често се обавља апстрактно без употребе конкретног програмског језика. Налик сличним математичким дисциплинама овде се изучавају законитости и принципи алгоритама, а не конкретне имплементације. Алгоритам се ипак запише на некакав начин али је то употребом псеудокода, општег језика за опис алгоритма.
Неки аутори ограничавају дефиницију алгоритма на процедуре које се коначно завршавају.[5] Други укључују и процедуре које се извршавају заувек без заустављања, образлажући то потребом да се неке врсте послова обављају у континуитету.[6] У последњем примеру се успех извршавања не може описати у смислу заустављања уз давање излазног резултата. Уместо тога, може се дефинисати успешност рада, а да је дефинисан невезан излазни низ као резултат. На пример, алгоритам који испитује да ли у бесконачном низу случајних бинарних цифара има више јединица или нула мора радити заувек да би посао обавио до краја. Ако је имплементиран исправно алгоритам ипак даје корисне резултате: док год испитује низ цифара даје позитиван одзив док је више нула него јединица, а негативан одзив у другом случају. Успех овог алгоритма би коначно био дефинисан као давање позитивног одзива ако је број нула већи у низу, а у другим ситуацијама негативног одзива.
Класификација алгоритама
[уреди | уреди извор]Постоји више начина за разврставање алгоритама, а методологија класификације је тема многих расправа.
Подела према парадигми програмирања
[уреди | уреди извор]Један начин разврставања је по методологији пројектовања или примењеном обрасцу. Постоји известан број различитих образаца како се приступа реализацији алгоритама. Даље, свака од наведених категорија садржи више различитих типова алгоритама. Неки уобичајено коришћени обрасци су:
- Подели па владај алгоритми смањују степен сложености проблема поделом на два или више мањих проблема од исте врсте (обично рекурзивно), док од проблема не остане толико мали део да се може једноставно решити.[7]
- Динамичко програмирање. Када проблем показује оптималну подструктуру, у смислу да се оптимално решење проблема може конструисати из оптималног решења потпроблема, и преклапањем потпроблема, што значи да се исти потпроблем користи за решавање више различитих примера проблема, можемо решити брзо користећи динамичко програмирање, приступ који избегава поновно израчунавање решења која су већ израчуната. На пример, најкраћи пут до циља из чвора тежинског графа може бити нађен користећи најкраћи пут до циља од свих оближњих чворова.[8]
- Похлепни алгоритам. Алгоритам лакомости је сличан динамичком програмирању, али је разлика у томе што решења потпроблема не морају бити позната у сваком тренутку. Стога, при тражењу решења је могуће направити и 'лаком' избор онога што изгледа најбоље у том тренутку.[9]
- Линеарно програмирање. Проблем се решава коришћењем линеарног програмирања када постоји више линеарних неједначина а задатак је наћи максимум (или минимум) по неком критеријуму. Многи реални проблеми (као што је максимизирање протока у усмереном графу) могу бити исказани на овај начин, а онда решени неким 'генеричким' алгоритмом, као што је Симплекс алгоритам.[10]
- Претрага и нумерација. Многи проблеми (као што је играње шаха) могу бити моделовани као проблеми графа. Алгоритам претраживања графа даје правила кретања кроз граф и користан је баш за овакве проблеме. Ова категорија обухвата и алгоритме претраживања и повратка кроз стабло одлучивања (бектрекинг).[11]
- Хеуристички алгоритми и алгоритми случајности не одговарају у потпуности строгој дефиницији алгоритма
- Алгоритми случајности праве у неким ситуацијама случајан (или псеудо случајан) избор; за неке проблеме се стварно може доказати да се до најбржег решења може доћи само увођењем извесног степена случајности.
- Генетички алгоритам покушава да нађе решење проблема имитирајући биолошки еволуциони процес, који у низу случајних мутација даје узастопне генерације 'решења'. Тако рачунар симулира размножавање и 'преживљавање најприлагођенијих'. У генетичком програмирању је овај приступ проширен на алгоритме.
- Хеуристички алгоритми су такви алгоритми чија је основна намена налажење оптималног решења, у ствари приближног решења, јер време или меморијски простор за извршавање алгоритма за налажење тачног најбољег решења није практично могуће. Пример алгоритама који су оваквог типа су за локално претраживање, табу претраживање или алгоритам симулираног отпуштања, врста хеуристичког алгоритма случајности који варира решење проблема у случајним износима. Назив симулација отпуштања алудира на металуршки процес супротан каљењу када се метал греје па споро хлади ради отклањања дефекта у материјалу. Намера случајног варирања је тражење што ближег решења општем оптималном решењу, а не једноставно локално оптимално решење. Идеја је да се амплитуда случајне величине смањује како се приближавамо решењу.
Подела према имплементацији
[уреди | уреди извор]Други начин разврставања је по имплементацији. Рекурзивни алгоритам је такав алгоритам који позива (референцира) сам себе узастопно док се неки услов не испуни, што је метода примењена код функционалног програмирања.[2] Алгоритми се обично разматрају уз претпоставку да у једном тренутку извршавају једну инструкцију једног алгоритма. Такви рачунари се понекад зову серијски рачунари. Алгоритми осмишљени за такво окружење се зову серијски или секвенцијални алгоритми, насупрот паралелним и дистрибуираним алгоритмима.[12] Паралелни алгоритми предности рачунарске архитектуре код које више процесора у истом трену решава исти проблем, док се код дистрибуираних алгоритама користи више рачунара повезаних у рачунарску мрежу. Паралелни или дистрибуирани алгоритми деле проблем у више симетрични или асиметричних потпроблема и касније састављају резултате. За ове алгоритме је поред процесорских циклуса је важна брзина комуникације између процесора.
Подела према областима рада
[уреди | уреди извор]Свако поље науке има своје проблеме и потребне су јој ефикасни алгоритми. Сродни проблеми се често проучавају заједно. Неки примери су алгоритми за претрагу, сортирање, спајање, нумеричку анализу, графове, стрингове, рачунарску геометрију, комбинаторику, машинско учење, криптографију, компресију података и технике парсирања.
Области имају тежњу да се преклапају једни са другима, а напредак алгоритма у једном пољу може да унапреди алгоритме у другим, понекад тотално несродним, областима. На пример, динамичко програмирање је првобитно намењено за оптимизацију потрошњу ресурса у индустрији, али се данас користи у решавање широког поља проблема у многим пољима.[тражи се извор]
Подела према сложености
[уреди | уреди извор]У теорији сложености, што није исто што и теорија израчунљивости, се изучава проблематика сложености, комплексности, алгоритма, у смислу заузимања ресурса, а то су простор (количина заузете меморије) и време (количина потрошеног времена процесора). Сложеност је функција величине улазних података. Алгоритми се праве за решење општег проблема, без обзира на величину улаза, али са друге стране разне улазне величине изазивају да програми троше разне количине ресурса.
Временска сложеност алгоритма се исказује као број елементарних корака за обављање алгоритма, што је зависно од величине улаза, а која може бити изражена у битовима или неким сличним мерилом. Ако кажемо да је алгоритам (А) уређивања низа од n елемената проблем временске сложености n², значи да двоструко већи број елемената захтева четири пута више времена за уређивање. Ако је, пак други алгоритам (B) мало пажљивије написан и бржи је двоструко, он ће радити двоструко брже за било коју величину низа. Међутим, ако се програмер намучи и осмисли суштински другачији алгоритам (C) за уређивање, он стварно може бити реда сложености n·log(n). Алгоритми (А) и (B) су исте сложености, јер се у нотацији са великим О обележавају са O(n²), а у говору се зову 'алгоритми квадратне сложености', док је алгоритам (C) 'алгоритам сложености n·log(n)'. Закључак: алгоритам (C) је најбољи са становишта коришћења времена за велике сетове улазних података.
Просторна сложеност се на исти начин односи на функцију зависности заузимања меморијског простора у зависности од величине улаза. Дешава се да је проналажење алгоритма мање временске сложености везано са повећањем просторне сложености. Обично се алгоритми деле на оне логаритамске сложености, линеарне, квадратне и уопштено полиномијалне сложености, као и оне најзахтевније, експоненцијалне сложености.
Подела према израчунљивости
[уреди | уреди извор]Алгоритме је могуће класификовати и према израчунљивости. Ово се обично ради тако што се разматрају класе алгоритама што омогућава смањење временских и меморијских ресурса који се користе у израчунавању. На пример, класа рекурзивних алгоритама укључује алгоритме за све функције које се могу израчунати помоћу Тјурнигове машине.
Доказ исправности
[уреди | уреди извор]Доказ исправности, коректности, алгоритма је теоретски математички поступак доказа теореме предикатским рачуном.[тражи се извор] Алгоритам се изражава логичким изразима, дефинише се инваријанта - израз чија вредност остаје непромењена све време рада алгоритма - и доказује да израз који је важио пре почетка важи и по завршетку обраде. Потпун доказ исправности подразумева још и доказ да ће се алгоритам завршити у коначном времену, међутим то уме бити компликованије од првог дела.
Овакав, теоретски доказ исправности је комплексна, а у пракси ретко рађена процедура.[тражи се извор]
Пример рачунарског алгоритма
[уреди | уреди извор]![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/6a/Sorting_quicksort_anim.gif/220px-Sorting_quicksort_anim.gif)
Овде је наведен један од најједноставнијих алгоритама и анализирани у корацима од представљања проблема, анализе проблема, дефинисања алгоритма и анализе исправности.
Исказ проблема
[уреди | уреди извор]Прво се проблем исказује природним језиком, на разумљив и недвосмислен начин:
„ | Наћи највећи број у датом, неуређеном низу бројева. | ” |
Разрада
[уреди | уреди извор]Решење захтева испитивање сваког броја из низа, али свега једном. Из овога следи једноставан предлог алгоритма изражен природним језиком:
- Погледај сваки елемент у низу. Ако је већи од било ког до сада виђеног, забележи га.
- Последњи забележен број је највећи у низу када се поступак заврши.
Дијаграми
[уреди | уреди извор]![](http://upload.wikimedia.org/wikipedia/sr/thumb/e/eb/%D0%A1%D1%82%D0%B0%D0%BD%D0%B4%D0%B0%D1%80%D0%B4%D0%BD%D0%B8_%D0%B4%D0%B8%D1%98%D0%B0%D0%B3%D1%80%D0%B0%D0%BC_%D1%82%D0%BE%D0%BA%D0%B0.png/300px-%D0%A1%D1%82%D0%B0%D0%BD%D0%B4%D0%B0%D1%80%D0%B4%D0%BD%D0%B8_%D0%B4%D0%B8%D1%98%D0%B0%D0%B3%D1%80%D0%B0%D0%BC_%D1%82%D0%BE%D0%BA%D0%B0.png)
![](http://upload.wikimedia.org/wikipedia/sr/thumb/6/67/%D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%BD%D0%B8_%D0%B4%D0%B8%D1%98%D0%B0%D0%B3%D1%80%D0%B0%D0%BC_%D1%82%D0%BE%D0%BA%D0%B0.png/200px-%D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%BD%D0%B8_%D0%B4%D0%B8%D1%98%D0%B0%D0%B3%D1%80%D0%B0%D0%BC_%D1%82%D0%BE%D0%BA%D0%B0.png)
Уобичајен начин приступања креирању алгоритма је цртањем дијаграма. Постоји више врста дијаграма.
Најпопуларнији и најраспрострањенији је стандардни дијаграм тока када се ток прати по правцу кретања стрелица (слика лево). У правоугаонике се уписују кратки описи операција и послова, а у ромбове и издужене шестоугаоника услови за гранање.
Популаризација структурног програмирања је довело до увођења нових, структурних дијаграма тока (слика десно). Цео дијаграм је у облику низа спојених правоугаоника. Они, међутим, нису широко прихваћени од програмера.
Овде је алгоритам приказан у оба облика. Десни дијаграм изгледа мањи и компактнији, али је леви ипак прегледнији. Међутим, стандардни дијаграм омогућује да се контрола из било које тачке пренесе у произвољну тачку, па и у унутрашњост петље. Тако се руши структурираност програма и представља увод у „шпагети програмирање“, што је основни показатељ лошег програмирања.
Визуелизација програмског тока и тока података су изузетно корисни за развој и разраду алгоритма. Објектно оријентисано програмирање је увело нове појмове и форме и у анализу и у пројектовање, а више врста дијаграма се користи у процесу који се назива унификовано моделовање за које је развијен и стандардизован UML (Обједињени језик за моделовање).
Псеудокод алгоритма
[уреди | уреди извор]Запис овог алгоритма је ниже дат у облику псеудокода који је више формалан од природног језика или графичких дијаграма, а поред природног има и елементе симболичког, вештачког, језика:
Algoritam НајвећиБрој Input: Не-празан низ бројева L. Output: највећи број у низу L. највећи ← -∞ for each број in низ L, do if број > највећи, then највећи ← број return највећи
где је испис кључних речи на енглеском питање договора. Могуће их је написати и на српском, али се у рачунарским круговима целог света користи енглески као lingua franca информатичког доба.
Објашњење псеудокода
[уреди | уреди извор]На почетку се описује простор (меморијске локације) неопходне за рад. Сем улазних и излазних локација, овде се дефинише и описује привремени простор који представља унутрашње стање. Конкретно, овде речи Input и Output означавају простор који заузимају бројеви, а посебно се речју Input наглашава да је то улазни податак те да је познат у време почетка рада алгоритма, а речју Output да ће ту бити смештен излазни податак и да ће он бити познат тек по завршетку рада алгоритма.
У другом делу следи кључни део алгоритма који се често у колоквијалном разговору зове алгоритмом. Он се састоји од набрајања конструкција које описују ток извршавања и уз примену конвенција о представљању операција над подацима. У нашем примеру имамо:
- "for each — in — do" је конструкција која значи "за сваки — од — уради" и представља начин за опис итерације, вишеструког понављања.
- "if — then је начин означавања селекције, питалице. Известан низ инструкција ће се извршити условно, у зависности од критеријума.
- "←" је скраћеница за „додељује се“. На пример, са "највећи ← број", значи да је највећи назив за меморијски простор у који ће бити ископирана вредност из меморијског простора који смо назвали број.
- "return" завршава алгоритам и иза себе оставља вредност (у меморијском простору коме је дат назив највећи) као излаз.
Анализа исправности
[уреди | уреди извор]Детаљна анализа исправности алгоритма би подразумевала разматрање свих, чак и скоро немогућих ситуација, што у овом случају значи анализа рада алгоритма у ситуацији када је
- дат празан низ бројева,
- у низ уписана и нека вредност која није број
Почиње се разматрањем проблема домена. То је област вредности које може узети број. Меморијски простор променљиве највећи не сме бити мањи од величине простора за сваки број из низа L. Да се десило сабирање два броја морала би бити размотрена ситуација ако би збир излазио ван домена што би изазвало прекорачење опсега. Ова врста провере је обавезна у свакој анализи алгоритма.
Следећи обавезни корак је провера почетне вредности, иницијализације. Ово се односи на дефинисање почетног унутрашњег стања система. Теоријски почетно стање мора бити познато, а практично то значи све променљиве морају бити иницијализоване. У нашем случају то значи да меморијска локација са називом највећи на почетку извршавања овог алгоритма мора имати неку вредност. Међутим, прва наредба највећи ← -∞ представља велики проблем јер би -∞ требало да излази ван домена било ког ограниченог меморијског простора. Овде се у имплементацији овог алгоритма приступа извесном прилагођавању реалним ограничењима програмског језика или на други начин заобилази дословна имплементација бесконачности. Ово показује како се наизглед потпуно исправни и добри алгоритми из теоретских ремек-дела претварају у програмерску ноћну мору.
Формална, математичка, анализа коректности би значила постављање теореме са предикатским формулама и доказ о коначности извршавања алгоритма. Веома су ретке ситуације у којима се то ради.[тражи се извор]
Анализа сложености
[уреди | уреди извор]Већина програмера жели да зна колико одређених ресурса (време и простор су најчешћи случај) заузима алгоритам који тренутно имплементирају. Развијене су многе методе за анализу алгоритма које дају неку врсту квантитативног одговора. На пример, алгоритам изнад је временске комплексности O(n), где се овакав облик обележавања назива нотација са великим О, а n је величина низа. Све време рада алгоритам памти само једну вредност, највећу вредност до сада. Стога овај алгоритам има просторну комплексност O(1). Треба приметити да се величина улаза, претходно датих података, не рачуна као простор коришћен од алгоритма.
Алгоритам са правног становишта
[уреди | уреди извор]Алгоритми сами по себи обично нису подложни патентирању. У Сједињеним Америчким Државама се захтев/поступак који се састоји искључиво од простих манипулација апстрактних концепата, бројева или сигнала не сматра „процесом“ (USPTO 2006) због чега алгоритми не подлежу патентирању (пример Gottschalk_v._Benson). Међутим, практичне примене алгоритама у неким случајевима јесу подложне патентирању. На пример, у случају Diamond v. Diehr, за примену једноставног алгоритма за коришћење повратне спреге као испомоћи при „лечењу“ синтетичке гуме је одлучено да јесте подложна патенту. Патентирање софтвера је веома контроверзно а неки патентни који укључују алгоритме су жестоко критиковани, нарочито они који се тичу алгоритама за компресију података, као што је на пример патент над Лемпел-Зев-Велч (Lempel-Zev-Welch, LZW) алгоритмом компаније „Јунисис“ (Unisys).
Такође, у неким државама постоје ограничења која се тичу извоза одређених класа рачунарских алгоритама (на пример, ограничења извоза криптографије).
Познати примери
[уреди | уреди извор]- Еуклидов алгоритам: рачунски поступак за изналажење највећег заједничког делиоца два броја и, уопштено, два полинома.
- Гаусов алгоритам: метод за поступно разрешавање система линеарних једначина путем редукције броја непознатих као и броја једначина.
Види још
[уреди | уреди извор]- Списак алгоритама
- Временска оса алгоритама
- Најпознатији алгоритми
- Нумерички алгоритми
- Графички алгоритми
Референце
[уреди | уреди извор]- ^ Daffa, Ali Abdullah al- (1977). The Muslim contribution to mathematics. London: Croom Helm. ISBN 978-0-85664-464-1.
- ^ а б Иветић 2004
- ^ „Augusta Ada King, countess of Lovelace”. J J O'Connor and E F Robertson. 2002. Архивирано из оригинала 13. 12. 2012. г. Приступљено 25. 4. 2009.
- ^ „The Babbage Engine”. Computer History Museum. Приступљено 25. 4. 2009.
- ^ Kleene 1952.
- ^ Knuth 1997.
- ^ Dunne, Paul E. „Algorithm Design Paradigms - Divide-and-Conquer”. Приступљено 30. 5. 2009.
- ^ Dunne, Paul E. „Algorithm Design Paradigms - Dynamic Programming”. Приступљено 30. 5. 2009.
- ^ Dunne, Paul E. „Algorithm Design Paradigms - Greedy Algorithms”. Приступљено 30. 5. 2009.
- ^ Reveliotis, Spyros. „An Introduction to Linear Programming and the Simplex Algorithm”. Архивирано из оригинала 03. 09. 2011. г. Приступљено 30. 5. 2009.
- ^ Ian Parberry & William Gasarch. „Problems on Algorithms” (PDF). стр. 116—135. Архивирано из оригинала (PDF) 10. 07. 2009. г. Приступљено 30. 5. 2009.
- ^ Barney, Blaise. „Introduction to Parallel Computing”. Lawrence Livermore National Laboratory. Архивирано из оригинала 29. 06. 2013. г. Приступљено 9. 11. 2007.
Литература
[уреди | уреди извор]- Daffa, Ali Abdullah al- (1977). The Muslim contribution to mathematics. London: Croom Helm. ISBN 978-0-85664-464-1.
- Algorithms + Data Structures = Programs, Niklaus Wirth - Прва књига структурираног програмирања
- The Art of Computer Programming, Donald Knuth - Рачунарска библија
- Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest - Добра књига за учење о алгоритмима
- The Design and Analysis of Computer Algorithms, Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman - Изузетна књига, популарна међу професионалцима
- Algorithms, Robert Sedgewick, Једноставнија, али новија књига од Ахове
- Програмски језици и методе програмирања, Јозо Дујмовић - Домаћа, ретка, али вредна књига
- Иветић, Драган (2004). Структурирани приступ програмирању/Инжењеринг, алгоритми и програмски језици. ISBN 978-86-7991-139-1.
- Kleene, Stephen C. (1952). Introduction to Metamathematics. North-Holland Publishing Company.
- Knuth, Donald (1997). Fundamental Algorithms (3. изд.). Reading, Massachusetts: Addison-Wesley. ISBN 978-0-201-89683-1.
Спољашње везе
[уреди | уреди извор]- Примери програма из књиге Приручник о алгоритмима и структурама података Gaston H. Gonnet и Ricardo Baeza-Yates. Слободан изворни код многих алгоритама.
- Листинг алгоритама за рачунарско програмирање
- Све о алгоритмима и још понечему на dmoz.org
- Чланци о неким алгоритмима
- elitesecurity::forumi Архивирано на сајту Wayback Machine (19. август 2005) О алгоритмима и програмирању на најпознатијем домаћем порталу
- Дефиниција алгоритма
- Класификација алгоритама