Алгоритам

Прост пример за алгоритам при решевање на проблемо со расипана лампа

Мухамед ел-Хорезми на советска поштенска марка

Алгоритам — определен број на јасно дефинирани кратки и прости инструкции за извршување на одредена задача, или решавање на зададен проблем. Пишувањето на програми може да биде тежок процес, посебно ако се прави без да се следаат добри препораки или упатства. Структурното програмирање е еден принцип за развој на програми кои го „разбива“ кодот на помали делови што соосдветствува на решавањето на сложен проблем со негово делење на поедноставни проблеми. Со овој процес се дава одредена структура на развојот на програми, од каде потекнува и името на овој пристап. Информациите кои треба да бидат обработени од страна на програмот се чуваат во податочни структури - Data structures (arrays, records, lists, stacks, trees, и files) поддржани од соодветниот програмски јазик. Податочните структури ги групираат податоците. Добар избор на податолни структури може да поедностави изработка на некоја програма и обратно. Изборот на податочната структура влијае на јасноста, проширливоста, брзината и мемориските побарувања за одредено програмско решение.

За изумител на првобитниот алгоритам се смета персискиот математичар и научник Мухамед ел-Хорезми (780-850), додека пак алгоритамот во денешна смисла прв го изложил Давид Хилберт во 1928 г.

Пример: Споредувањето на наоѓање на телефонски број за позната адреса или наоѓање на адреса за познат телефонски број искључиво со користење на хартиен телефонски именик. Податочните структури можат да бидат статични (да трпат промени само на вредностите како arrays или records) и динамични (да трпат промени и во изгледот, посебно големината – како stack, lists, trees, и files). Типични акции кои се извршуваат над податочните структури се: изнајдување, пребарување, пребројување, вметнување, сортирање и бришење. Ако не се знае како да се реши некој проблем, тогаш е сосема извесно дека нема да се знае ниту да се напише програм кој ќе го решава тој проблем.

H. L. Mencken: "Every complex problem has a simple easy-to-understand wrong answer." Пред да се започне со пишување на програм треба да се разбере проблемот и да се создава чекор по чекор решение или алгоритам. За да биде корисен, алгоритамот треба да нуди решение за генерален, добро специфициран проблем. Алгоритамски гледано еден проблем се специфицира со утврдување на сите можни влезни податоци со кои тој алгоритам ќе работи, поведениа или постапки за обработка на истите, како и сите можни излезни податоци кои алгоритмот ќе ги создава. Битно е да се направи разлика помеѓу правилно поведение за група влезни податоци и правилно поведение за сите можни влезни податоци. Според тоа алгоритам е процес кој прима било кој можен влез и го трансформира во посакуван излез. За да се опишат алгоритмите потребно е да се користи некаква нотација за опишување на последователните чекори кои треба да се извршат при реализација на алгоритамот. Такви нотации може да бидат: говорен јазик – македонски, англиски; псевдокод; програмски јазик. Псевдокод може да се дефинира како програмски јазик кој не води сметка за синтаксата. Тој е попрецизен од говорните јазици, но понепрецизен од програмските јазици. Еден можен пристап за опис на алгоритам би бил: опишување на идејата во говорен јазик, опишување на концептот на алгоритмот во псевдокод, детализирање на алгоритмот во конкретен програмски јазик.

Ефикасност и квалитет

Алгоритмите треба да бидат коректни, ефикасни и лесни за имплементација. Коректноста на алгоритмите треба да се докаже (со неможност да се најде валиден влезен податок за кој алгоритмот не работи правилно, со потврда дека спротивниот алгоритам дава грешни резултати, со математичка индукција). Важно е да се разбере дека изказот “решението е очигледно“ најчесто води во заблуда и создавање на грешни алгоритми. Не постои алгоритам за наоѓање на алгоритми. Смислувањето на алгоритам е обично многу потешко од пишување на програм (за познат алгоритам). Искусен дизајнер на алгоритми е всушност експерт за ефикасност на алгоритмите. Ефикасни се оние коректни алгоритми кои за дадени влезни податоци завршуваат побрзо од други коректни алгоритми кои работат со истите влезни податоци. При тоа треба се напомене дека наоѓањето на најефикасен алгоритам не е секогаш од пресудно значење. Имено статистички гледано само 20% од кодот на даден програм се извршува 80% од времето додека тој програм е стартуван. Од тука следи дека на вкупната ефикасност на програмот значително влиае само 20% од кодот, па доволно е само тој да се оптимизира. Иако брзината на извршување на некој алгоритам реално зависи од хардверот над кој тој се извршува, па забрзување на алгоритмот може да се постигне со негово извршување на побрз хардвер, тоа може да биде лимитирано со технички ограничувања (не постоење на побрз хардвер). Од претходното следи, дека за да се подобрат перформансите на алгоритмот мора да се напише подобар алгоритам. За да се споредат алгоритмите потребно е да се користи модел на извршување кој не зависи од хардверот. Вообичаено се препоставува дека алгоритмите се извршуваат на хипотетички компјутер наречен “Random Access Machine“ или RAM. При тоа се претпоставува дека:

• Секоја едноставна операција (+, *, -, =, if, call) се извршува во една временска единица.
• Јамките (циклусите), процедурите и функциите се извршуваат во онолку временски единии колку што содржат итерации.
• Постои неограничена меморија.

Во овој модел времето потребно за извршување на алгоритмот за дадени влезни податоци е еднакво со бројот на извршување на едноставните операции при обработката на дадените влезни податоци.