Алгоритми

Алгоритам је повезани низ елементарних правила, односно, алгоритамских корака у којима се поступно трансформишу улазне величине све док се не добије коначно решење, или се описује извршавање неког поступка.

Другим речима, алгоритам је упутство како решити неки задатак или проблем. Тако се и упутство за полетање авиона и упутство за прављење руске салате састоји од низа корака, поступака, које треба урадити и који воде испуњењу циља или решавању проблема. Упутство може садржати кораке који се понављају више пута или кораке када треба донети неку одлуку, на основу неког критеријума. Добро упутство предвиђа и поступак када нису сви услови испуњени нпр. нема довољно горива у резервоарима авиона, или нема кромпира у фрижидеру а почели смо да спремамо жуманце за мајонез. Коректно извршавање сваког корака не решава задатак ако је алгоритам био погрешан.

Различити алгоритми могу решити исти проблем различитим низом поступака уз мање или више напора, за краће или дуже време. С обзиром на чињеницу да је резултат исти, алгоритми се могу поредити по својој ефикасности, брзини или комплексности.

Алгоритми могу бити приказани, односно описани природним језиком (разумљив само говорницима тог језика) или графички. На основу написаног алгоритма пише се програм, односно низ наредбе о удговарајућем програмском језику.

Примери алгоритма

Пример алгоритма из свакодневног живота је кување кафе. Сваки корак припремања кафе мора бити извршен правилно како би се могло прећи на следећи и у коначном времену добили кафу.

Алгоритам кувања кафе гласи:

1. Узети џезву и сипати воду, по потреби додати шећер. (Овде би могли додати избор одговарајуће џезве зависно од броја кафа које се кувају, одређивање количине воде, одређивање количине шећера)
2. Укључити ринглу.
3. Сачекати док вода не прокључа. (у ствари, за праву кафу вода треба да достигне температуру око 80°C, односно треба сачекати док се не појаве први мехурићи у води)
4. Кад вода прокључа, склонити џезву са рингле, сипати одређену количину кафе, промешати и вратити на ринглу док се не подигне пена. (за праву кафу требало би најмање два пута да се подигне пена)
5. Сипати кафу у шољу, односно у шоље. (и овде би се могао додати избор да ли треба прво сипату пену, или склонити пену кашичицом…)

Из овог једноставног примера може се видети поступност и коначност алгоритма, и можда наслутити о чему све треба водити рачуна при писању алгоритама, нарочито ако замислимо да наш алгоритам треба да извршава робот! Можемо закључити да нема превише користи од алгоритма који се никада не завршава или алгоритма чије се наредбе изводе непредвидљиво или им је резултат непредвидљив.

Дакле, да поновимо:

Алгоритам је уређен, коначан скуп упутстава који у коначном броју корака даје резултате за произвољан избор допуштених улазних података.
Програм је опис алгоритма у неком програмском језику.

Сваки алгоритам има следеће особине:
одређеност – сваки алгоритамски корак мора да буде прецизно дефинисан и једнозначан,
коначност – алгоритам се мора завршити после коначно много алгоритамских корака,
масовност – алгоритам се прави тако да се може применити за решавање читаве групе сродних проблема без обзира на различите полазне величине,
ефикасност – алгоритам треба да доведе до решења за што краће време и у што мањем броју алгоритамских корака.

Урадићемо један пример да бисмо видели како тече процес настанка алгоритма.

Пре писања алгоритма потребно је формулисати проблем, односно одредити шта су улазни подаци, шта су излазни подаци и која веза постоји између њих, Такође, треба уочити да ли постоје неки услови или ограничења о којима треба водити рачуна. Проблем који преносимо на рачунар треба да решава што ширу класу сродних проблема.

Пример:
Из Београда и Новог Сада истовремено у сусрет полазе два аутомобила крећући се брзинама 63km/h и 75km/h. После ког времена и на ком месту ће се аутомобили сусрести?

Писање програма за решавање оваквог проблема на рачунару нема смисла јер се ради о појединачном проблему. Али, ако га поставимо на следећи начин:
Из два града на растојању d истовремено у сусрет полазе два аутомобила крећући се брзинама v1 и v2. После ког времена и на ком месту ће се аутомобили сусрести?
добијамо задатак који решава класу сродних проблема, јер сада могу бити у питању било која два града и аутомибили се могу кретати било којим брзинама.

Следећа фаза односи се на решавање конкретног проблема, односно на дефинисање улазних и излазних величина као и на односе међу њима. У нашем примеру познате величине су растојање између градова (d) и брзине кретања аутомобила (v1 и v2). Непознате величине су растојање од места сусрета аутомобила од градова (означимо их са d1 и d2) и време сусрета (t). Из поставке задатка следи ограничење, односно веза између величина d1 и d2: d=d1+d2.

Да бисмо решили овај проблем, потребно је знање из физике, односно веза између брзине, пређеног пута и времена:

formula1

formula2

Пошто је време t исто за оба аутомобила, заменом у прву једначину за укупно растојање d имаћемо:

formula3

Када одавде израчунамо t добићемо:

formula4 , а затим одредимо d1 и d2 према једначинама: formula1 и formula2

Као важну напомену треба рећи да у овом случају најпре мора да се израчуна t, а онда на основу израчунате вредности t и познатих (улазних величина) израчунати преостале непознате величине.

Сада је могуће написати алгоритам као низ корака:

1. Улазне величине d,v1,v2

2. Израчунати formula4

3. Израчунати formula1

4. Израчунати formula2

5. Приказати резултате t, d1, d2

Овако представљен алгоритам написан је природним језиком. Доказано је да је много прегледније представљати га графички као скуп међусобно повезаних блокова. Тако представљен алгоритам назива се дијаграм тока зато што стрелице које повезују блокове приказују ток података од корисника, кроз рачунарски систем, до излазних уређаја. Постоје различити скупови блокова, ми ћемо користити следећи скуп:

dijagram-simboli

А овај наш пример представљен графички има следећи изглед:

dijagram1

Према форми веза у шеми алгоритми могу бити:- прост линијски алгоритам – сваки алгоритамски корак се остварује тачно једном од горе на доле,- разгранати линијски алгоритам – сваки алгоритамски корак се остварује највише једном, тј. има и корака који се неће остваривати за дате полазне величине,- циклични алгоритам – постоје алгоритамски кораци који се остварују више пута,- селективни алгоритам – у зависности од датог критеријума бирају се алгоритамски кораци који ће се извршити

Advertisements

Оставите одговор

Попуните детаље испод или притисните на иконицу да бисте се пријавили:

WordPress.com лого

Коментаришет користећи свој WordPress.com налог. Одјавите се / Промени )

Слика на Твитеру

Коментаришет користећи свој Twitter налог. Одјавите се / Промени )

Фејсбукова фотографија

Коментаришет користећи свој Facebook налог. Одјавите се / Промени )

Google+ photo

Коментаришет користећи свој Google+ налог. Одјавите се / Промени )

Повезивање са %s