From Wikipedia, the free encyclopedia
Алгоритам је опис за решавање неког проблема. Реч долази из презимена персијског математичара Ал Хорезмија. Алгоритам је био израз који описује начин рачунања децималним бројевима уведеним око 1600. године у Европи. Алгоритмичарима су се раније звали они математичари који не оперишу симболима множина представљеним на абакусу, него једним (индијским или арапским) системом знакова за бројеве (од 16. века раширеним у Европи).
У новије време, алгоритам је појам који се готово искључиво везује за информатику и, мада не постоји јединствена општеприхваћена дефиниција, подразумева се да је у питању некако описана процедура за обављање посла. У ту сврху се дефинишу алгоритамски језици. То су формализовани језици којима се релативно лако описују поступци решавања проблема представљених алгоритмом, такви су на пример програмски језици Алгол, Фортран и Кобол.
У математичкој логици је алгоритам генерализован појам и односи се на поступак за поступно претварање низова знакова.
.png)
Алгоритам је у математику увео персијски математичар Мухамед Ал Хорезми. Написао је књигу Ал Хорезми о индијској вештини рачунања где у арапску математику уводи индијске цифре и децимални бројни систем. Ова књига бива касније преведена на латински као . Од лошег латинског превода његовог презимена и потиче реч алгоритам, и дуго је означавала поступак за рачун са децималним бројним системом (и индијским односно, како се касније причало, арапским цифрама).[1][2]
Алгоритам представља шематски приказано, поступно решавање неког проблема, тока неког процеса или израде неког предмета.
Алгоритам је коначан и прецизно дефинисан процес, низ добро дефинисаних правила, којим се улазне вредности трансформишу у излазне, или се описује извршавање неког поступка.
Данас се реч алгоритам често везује за појам рачунарства мада уопштено алгоритам можемо сматрати као упутство како решити неки задатак или проблем. Тако се и упутство за слање човека на Месец и упутство за прављење руске салате састоји од низа корака, поступака, које треба урадити и који воде испуњењу циља или решавању проблема. Упутство може садржати кораке који се понављају више пута или кораке када треба донети неку одлуку, на основу неког критеријума. Добро упутство предвиђа и поступак када нису сви услови испуњени нпр. прва посада за слање на Месец изгорела при тестирању, или нема кромпира у фрижидеру а почели смо да спремамо жуманце за мајонез. Коректно извршавање сваког корака не решава задатак ако је алгоритам био погрешан.
Различити алгоритми могу решити исти проблем различитим низом поступака уз мање или више напора, за краће или дуже време. Обзиром да је резултат исти, алгоритми се могу поредити по својој ефикасности, брзини или комплексности.
Алгоритми могу бити приказани или реализовани на више начина:
Пример алгоритма из свакодневног живота је кување чаја. Сваки корак припремања чаја мора бити извршен правилно како би се могло прећи на следећи и у коначном времену добили скуван чај.
Алгоритам кувања чаја гласи:
Из овог једноставног примера може се видети поступност и коначност алгоритма. Наиме, нема превише користи од алгоритма који се никада не завршава или алгоритма чије се наредбе изводе непредвидљиво или им је резултат непредвидљив.
Пример комплекснијег алгоритма је Еуклидов алгоритам за одређивање највећег заједничког делиоца:
Први алгоритам који се може сматрати процедуром чија је намена рачун на аутоматској машини је написала Ејда Бајрон 1842. године. У питању је алгоритам за рачун Бернулијевих бројева на аналитичкој машини Чарлса Бебиџа. Та машина никад није прорадила, али је њен алгоритам оставио дубок траг. Данас се то признаје као први рачунарски алгоритам, а Ејда Бајрон, леди Лавлејс, је призната као први програмер у историји.[3][4] У њену част је и један од најкомплекснијих програмских језика добио назив Ада.
Значајан напредак у формализацији увођења алгоритма у математику и логику је учинио Алан Тјуринг у својим радовима дефинисањем Тјурингове машине. То је примитиван аутомат, мисаона творевина, али поседује могућност извођења неколико операција које су довољне за извођење скоро свих алгоритама. Черч-Тјурингова теза тврди да се сваки алгоритам који је добро дефинисан може извршити на таквој машини. Тако се, и поред једноставности ове машине, зачела теорија коначних аутомата као нова област. Истраживањем се дошло и до теоријских проблема: Тјурингов проблем заустављања, НП-тежак проблем, НП-потпун проблем и тако даље.
Алгоритми поседују следеће особине:
Решење било ког проблема који се може решити помоћу рачунара, се може изразити као суперпозиција следећих структура: секвенце, селекције и итерације.
Секвенца је уређен низ инструкција где се по извршењу i-те инструкције, може прећи на i+1 инструкцију, затим на i+2 инструкцију и тако даље.
Селекција омогућава избор једног тока којим ће се наставити извршавање инструкција. Избор тока врши се провером услова који је дефинисан као логички израз (предикат).
Разликује се следећи типови селекција:
Итерација омогућава понављање операција тела операције потребан број пута. Број понављања се контролише условом у форми предиката. Разликују се следећи типови итерације:
Алгоритам је кључни појам у рачунарској обради података јер је рачунарски програм известан алгоритам који рачунару објашњава које кораке (наредбе) и којим редоследом треба да обавља. Тако се алгоритмом може сматрати било који низ инструкција која се може урадити на Тјуринг-комплетној машини.
Типично, када се уз алгоритам везује појам обраде података, подразумева се да се податак прво учита преко улазне јединице а исписује се на излазну јединицу или чува за каснију употребу. Сачувани подаци се сматрају делом унутрашњег стања система.
За сваки рачунарски посао алгоритам мора бити јасно дефинисан; наведен на начин који подразумева све могуће ситуације које се могу појавити. Значи, сваки условни корак се мора систематично обрадити, случај по случај; услов за сваки случај мора бити јасан и израчунљив.
Пошто је алгоритам јасан низ прецизних корака, редослед израчунавања је увек критичан за функционисање алгоритма. Претпоставља се да су инструкције наведене јасно, да почињу од врха и да теку до дна. Ова идеја се формално описује контролом тока.
Код овакве формализације се унапред узимају претпоставке о императивном програмирању. Ово је најуобичајенији концепт у програмирању и описује поступке на механички начин.[тражи се извор] Јединствено за овај концепт је операција додељивања, што је давање вредности променљивој. Ово произилази из интуитивног поимања меморије као привременог складиштења односно памћења. Ниже у тексту се може наћи пример оваквог додељивања.
Постоје и другачији концепти у изградњи алгоритма, погледати функционално програмирање и логичко програмирање.
Алгоритми се реализују у облику рачунарских програма, али могу и на други начин. Сем електричних кола и механичких справа које обављају неке радње исто тако постоје и биолошке неуралне мреже каква је, на пример, мозак човека који је научио математичке операције или инсекта који премешта храну.
Анализа и проучавање алгоритама је једна област рачунарства и често се обавља апстрактно без употребе конкретног програмског језика. Налик сличним математичким дисциплинама овде се изучавају законитости и принципи алгоритама, а не конкретне имплементације. Алгоритам се ипак запише на некакав начин али је то употребом псеудокода, општег језика за опис алгоритма.
Неки аутори ограничавају дефиницију алгоритма на процедуре које се коначно завршавају.[5] Други укључују и процедуре које се извршавају заувек без заустављања, образлажући то потребом да се неке врсте послова обављају у континуитету.[6] У последњем примеру се успех извршавања не може описати у смислу заустављања уз давање излазног резултата. Уместо тога, може се дефинисати успешност рада, а да је дефинисан невезан излазни низ као резултат. На пример, алгоритам који испитује да ли у бесконачном низу случајних бинарних цифара има више јединица или нула мора радити заувек да би посао обавио до краја. Ако је имплементиран исправно алгоритам ипак даје корисне резултате: док год испитује низ цифара даје позитиван одзив док је више нула него јединица, а негативан одзив у другом случају. Успех овог алгоритма би коначно био дефинисан као давање позитивног одзива ако је број нула већи у низу, а у другим ситуацијама негативног одзива.
Постоји више начина за разврставање алгоритама, а методологија класификације је тема многих расправа.
Један начин разврставања је по методологији пројектовања или примењеном обрасцу. Постоји известан број различитих образаца како се приступа реализацији алгоритама. Даље, свака од наведених категорија садржи више различитих типова алгоритама. Неки уобичајено коришћени обрасци су:
Други начин разврставања је по имплементацији. Рекурзивни алгоритам је такав алгоритам који позива (референцира) сам себе узастопно док се неки услов не испуни, што је метода примењена код функционалног програмирања.[2] Алгоритми се обично разматрају уз претпоставку да у једном тренутку извршавају једну инструкцију једног алгоритма. Такви рачунари се понекад зову серијски рачунари. Алгоритми осмишљени за такво окружење се зову серијски или секвенцијални алгоритми, насупрот паралелним и дистрибуираним алгоритмима.[12] Паралелни алгоритми предности рачунарске архитектуре код које више процесора у истом трену решава исти проблем, док се код дистрибуираних алгоритама користи више рачунара повезаних у рачунарску мрежу. Паралелни или дистрибуирани алгоритми деле проблем у више симетрични или асиметричних потпроблема и касније састављају резултате. За ове алгоритме је поред процесорских циклуса је важна брзина комуникације између процесора.
Свако поље науке има своје проблеме и потребне су јој ефикасни алгоритми. Сродни проблеми се често проучавају заједно. Неки примери су алгоритми за претрагу, сортирање, спајање, нумеричку анализу, графове, стрингове, рачунарску геометрију, комбинаторику, машинско учење, криптографију, компресију података и технике парсирања.
Области имају тежњу да се преклапају једни са другима, а напредак алгоритма у једном пољу може да унапреди алгоритме у другим, понекад тотално несродним, областима. На пример, динамичко програмирање је првобитно намењено за оптимизацију потрошњу ресурса у индустрији, али се данас користи у решавање широког поља проблема у многим пољима.[тражи се извор]
У теорији сложености, што није исто што и теорија израчунљивости, се изучава проблематика сложености, комплексности, алгоритма, у смислу заузимања ресурса, а то су простор (количина заузете меморије) и време (количина потрошеног времена процесора). Сложеност је функција величине улазних података. Алгоритми се праве за решење општег проблема, без обзира на величину улаза, али са друге стране разне улазне величине изазивају да програми троше разне количине ресурса.
Временска сложеност алгоритма се исказује као број елементарних корака за обављање алгоритма, што је зависно од величине улаза, а која може бити изражена у битовима или неким сличним мерилом. Ако кажемо да је алгоритам (А) уређивања низа од елемената проблем временске сложености ², значи да двоструко већи број елемената захтева четири пута више времена за уређивање. Ако је, пак други алгоритам () мало пажљивије написан и бржи је двоструко, он ће радити двоструко брже за било коју величину низа. Међутим, ако се програмер намучи и осмисли суштински другачији алгоритам () за уређивање, он стварно може бити реда сложености . Алгоритми (А) и () су исте сложености, јер се у нотацији са великим О обележавају са O(²), а у говору се зову 'алгоритми квадратне сложености', док је алгоритам () 'алгоритам сложености '. Закључак: алгоритам () је најбољи са становишта коришћења времена за велике сетове улазних података.
Просторна сложеност се на исти начин односи на функцију зависности заузимања меморијског простора у зависности од величине улаза. Дешава се да је проналажење алгоритма мање временске сложености везано са повећањем просторне сложености. Обично се алгоритми деле на оне логаритамске сложености, линеарне, квадратне и уопштено полиномијалне сложености, као и оне најзахтевније, експоненцијалне сложености.
Алгоритме је могуће класификовати и према израчунљивости. Ово се обично ради тако што се разматрају класе алгоритама што омогућава смањење временских и меморијских ресурса који се користе у израчунавању. На пример, класа рекурзивних алгоритама укључује алгоритме за све функције које се могу израчунати помоћу Тјурнигове машине.
Доказ исправности, коректности, алгоритма је теоретски математички поступак доказа теореме предикатским рачуном.[тражи се извор] Алгоритам се изражава логичким изразима, дефинише се инваријанта - израз чија вредност остаје непромењена све време рада алгоритма - и доказује да израз који је важио пре почетка важи и по завршетку обраде. Потпун доказ исправности подразумева још и доказ да ће се алгоритам завршити у коначном времену, међутим то уме бити компликованије од првог дела.
Овакав, теоретски доказ исправности је комплексна, а у пракси ретко рађена процедура.[тражи се извор]
Овде је наведен један од најједноставнијих алгоритама и анализирани у корацима од представљања проблема, анализе проблема, дефинисања алгоритма и анализе исправности.
Прво се проблем исказује природним језиком, на разумљив и недвосмислен начин:
| „ | Наћи највећи број у датом, неуређеном низу бројева. | ” |
Решење захтева испитивање сваког броја из низа, али свега једном. Из овога следи једноставан предлог алгоритма изражен природним језиком:
Уобичајен начин приступања креирању алгоритма је цртањем дијаграма. Постоји више врста дијаграма.
Најпопуларнији и најраспрострањенији је стандардни дијаграм тока када се ток прати по правцу кретања стрелица (слика лево). У правоугаонике се уписују кратки описи операција и послова, а у ромбове и издужене шестоугаоника услови за гранање.
Популаризација структурног програмирања је довело до увођења нових, структурних дијаграма тока (слика десно). Цео дијаграм је у облику низа спојених правоугаоника. Они, међутим, нису широко прихваћени од програмера.
Овде је алгоритам приказан у оба облика. Десни дијаграм изгледа мањи и компактнији, али је леви ипак прегледнији. Међутим, стандардни дијаграм омогућује да се контрола из било које тачке пренесе у произвољну тачку, па и у унутрашњост петље. Тако се руши структурираност програма и представља увод у „шпагети програмирање“, што је основни показатељ лошег програмирања.
Визуелизација програмског тока и тока података су изузетно корисни за развој и разраду алгоритма. Објектно оријентисано програмирање је увело нове појмове и форме и у анализу и у пројектовање, а више врста дијаграма се користи у процесу који се назива унификовано моделовање за које је развијен и стандардизован (Обједињени језик за моделовање).
Запис овог алгоритма је ниже дат у облику псеудокода који је више формалан од природног језика или графичких дијаграма, а поред природног има и елементе симболичког, вештачког, језика: -{
Algoritam НајвећиБрој
Input: Не-празан низ бројева L.
Output: највећи број у низу L.
највећи ← -∞
for each број in низ L, do
if број > највећи, then
највећи ← број
return највећи
}- где је испис кључних речи на енглеском питање договора. Могуће их је написати и на српском, али се у рачунарским круговима целог света користи енглески као информатичког доба.
На почетку се описује простор (меморијске локације) неопходне за рад. Сем улазних и излазних локација, овде се дефинише и описује привремени простор који представља унутрашње стање. Конкретно, овде речи и означавају простор који заузимају бројеви, а посебно се речју наглашава да је то улазни податак те да је познат у време почетка рада алгоритма, а речју да ће ту бити смештен излазни податак и да ће он бити познат тек по завршетку рада алгоритма.
У другом делу следи кључни део алгоритма који се често у колоквијалном разговору зове алгоритмом. Он се састоји од набрајања конструкција које описују ток извршавања и уз примену конвенција о представљању операција над подацима. У нашем примеру имамо:
Детаљна анализа исправности алгоритма би подразумевала разматрање свих, чак и скоро немогућих ситуација, што у овом случају значи анализа рада алгоритма у ситуацији када је
Почиње се разматрањем проблема домена. То је област вредности које може узети број. Меморијски простор променљиве највећи не сме бити мањи од величине простора за сваки број из низа L. Да се десило сабирање два броја морала би бити размотрена ситуација ако би збир излазио ван домена што би изазвало прекорачење опсега. Ова врста провере је обавезна у свакој анализи алгоритма.
Следећи обавезни корак је провера почетне вредности, иницијализације. Ово се односи на дефинисање почетног унутрашњег стања система. Теоријски почетно стање мора бити познато, а практично то значи све променљиве морају бити иницијализоване. У нашем случају то значи да меморијска локација са називом највећи на почетку извршавања овог алгоритма мора имати неку вредност. Међутим, прва наредба највећи ← -∞ представља велики проблем јер би -∞ требало да излази ван домена било ког ограниченог меморијског простора. Овде се у имплементацији овог алгоритма приступа извесном прилагођавању реалним ограничењима програмског језика или на други начин заобилази дословна имплементација бесконачности. Ово показује како се наизглед потпуно исправни и добри алгоритми из теоретских ремек-дела претварају у програмерску ноћну мору.
Формална, математичка, анализа коректности би значила постављање теореме са предикатским формулама и доказ о коначности извршавања алгоритма. Веома су ретке ситуације у којима се то ради.[тражи се извор]
Већина програмера жели да зна колико одређених ресурса (време и простор су најчешћи случај) заузима алгоритам који тренутно имплементирају. Развијене су многе методе за анализу алгоритма које дају неку врсту квантитативног одговора. На пример, алгоритам изнад је временске комплексности O(), где се овакав облик обележавања назива нотација са великим О, а је величина низа. Све време рада алгоритам памти само једну вредност, највећу вредност до сада. Стога овај алгоритам има просторну комплексност O(1). Треба приметити да се величина улаза, претходно датих података, не рачуна као простор коришћен од алгоритма.
Алгоритми сами по себи обично нису подложни патентирању. У Сједињеним Америчким Државама се захтев/поступак који се састоји искључиво од простих манипулација апстрактних концепата, бројева или сигнала не сматра „процесом“ ( 2006) због чега алгоритми не подлежу патентирању (пример Gottschalk_v._Benson). Међутим, практичне примене алгоритама у неким случајевима јесу подложне патентирању. На пример, у случају Diamond v. Diehr, за примену једноставног алгоритма за коришћење повратне спреге као испомоћи при „лечењу“ синтетичке гуме је одлучено да јесте подложна патенту. Патентирање софтвера је веома контроверзно а неки патентни који укључују алгоритме су жестоко критиковани, нарочито они који се тичу алгоритама за компресију података, као што је на пример патент над Лемпел-Зев-Велч () алгоритмом компаније „Јунисис“ ().
Такође, у неким државама постоје ограничења која се тичу извоза одређених класа рачунарских алгоритама (на пример, ограничења извоза криптографије).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
