Историја алгоритама покрива период од настанка самог рачунања и математике до данас. Још су се древне цивилизације користиле алгоритмима, како у пројектовању значајних ствари, тако и у свакодневном животу. Сам назив је настао у 12. веку као синоним за рачунски метод. Појавом рачунара почиње формализација алгоритама, а они постају основа софтвера. Данас се они примењују у готово свакој области.
Порекло назива У 9. веку наше ере персијски математичар и астроном Мухамед ел Хорезми, често називан и оцем алгебре, написао је књигу О индијским бројевима, у којој је научник дао опис низа поступака и прецизних правила за разна израчунавања. Тај рад бива преведен у 12. веку на латински језик као , где је реч algoritmi требало да представља латинизирано презиме научника. Међутим, та реч надаље постаје синоним за рачунски метод.
Алгоритми антике
Вавилонска математика Вавилонска математика је на много начина била напреднија од египатске математике. Вавилонци су могли да израчунају квадратни и кубни корен, познавали су Питагорину теорему 1200 година пре но што је Питагора званично дефинисао, знали за број π, могли да реше полиноме осмог степена, линеарне једначине, као и разна израчувања за круг. За разлику од Грка, Вавилонски математичари су се више фокусирали на алгебру, а не на геометрију.
Вавилонски бројеви Клинасти бројеви су написани у комбинацији са два симбола: вертикалним клином за ,,1” и угаоним клином за ,,10”. Вавилонци су имали шездесетодецимални бројевни систем и користили су концепт места вредности да запишу бројеве веће од 60. Дакле, имали су 59 симбола за бројеве, од 1 до 59, а затим су те симболе понављали у различитим колонама да означе веће бројеве. На пример, ,,2” у другој колони са десне стране значи 2 x 60 = 120, а ,,2” у трећој колони са десне стране представља 2 x 602 = 7200. Бројеви од 1 до 59: центар|мини|620x620px|Слика 1: Вавилонски клинасти бројеви Да би користили шездесетодецималну нотацију у савременом језику, треба раздвајити колоне са запетама, тако да се број 7267 = 2 x 602 + 1 x 60 + 7 записује као 2,1,7. Постоје неки проблеми са овим системом. Први је тај да практично не постоји начин да се одвоје колоне осим да се убаци празнина у бројевима, пример број ,,2” изгледа слично као и ,,61” (1, 1). Још озбиљнији проблем је што нема симбол за нулу да се дода у празну колону, тако да се ,,1” неприметно разликује од ,,60”. Касније Вавилонске цивилизације су увеле нулу, тако да су они били свесни тог недостатка. Вавилонски бројни систем са базом 60 се задржао и у данашње време, јер ми и даље имамо 60 минута у сату, 60 секунди у минути, 360 степени у кругу и 60 минута у степену. Чак је 24 часовни дан наслеђе древних Вавилонаца.
Вавилонске нумеричке табеле Заједнички део Египћана и Вавилонаца су табеле које су олакшавале прорачуне. Табеле су служиле за израчунавање ствари као што су квадратни корен са великом прецизношћу коју су постизали и математичари у доба Ренесансе.
Реципрочне табеле Вавилонци нису имали посебан алгоритам за дуге бројеве при дељењу, већ су се користили чињеницом да је Они су користили реципрочне табеле конвертоване у шездесетодецималну нотацију. У нотацији која је горе наведена, користили су тачку-запету (;) да би означили децимално место. Онда се број ½ записује као (0;30) = 0(1) + 30(60−1). 60 је практична база овде зато што многи бројеви имају коначну фракцију у шездесето-базном систему, као што су ½, 1/3, ¼, 1/5, 1/6, 1/10, 1/12, 1/15, 1/20. Међутим, неки бројеви, као што су 1/7 или 1/13, имају бесконачну фракцију, и за њих је дата само приближна вредност. Штета је што Вавилонци ове бројеве нису даље разматрали, јер би дошли до периодичног понављања шездесетодецималних фракција које би могле да доведу до откривања бесконачних низова.
Табеле квадрата Вавилонски начин множења се заснива на познавању квадрата бројева. Они су за једноставно множење два броја користили формуле
Понекад је било једноставно да се помноже и саберу бројеви, као нпр. множење са 39, где се множи са 30, па са 9, и резултати се саберу, тако да нису увек користили горенаведене формуле за множење.
Квадратни и кубни корен Вавилонци су квадратни корен од два налази са разликом од 0.0000006 од праве вредности. Такође су могли да нађу и квадратне корене за друге вредности. Користили су две методе да одреде приближну вреност квадратног корена.
Прва је користила апроксимацију
која је изведена из првих правила о проширивању биномне серије.
Друга метода користи алгоритам који ће касније бити преписан Грцима.
Нека а = а1 буде почетна апрокцимација. Ако је онда . Нека боља апроксимација буде . И овај процес се понавља све док одговор не буде прецизан колико желите.
Квадратне једначине и n3 + n2 табеле Једна важна табела Вавилонске алгебре је та да је вредност од n3 + n2 за целобројне вредности n од 1 до 30. Ове табеле су служиле да се реше кубне једначине облика
Вероватно је да су Вавилонци били вешти и у решавању квадратних једначина, и за њихово решавање су користили метод сличан нашем методу за решавање квадратних једначина.
Експоненти и логаритми Код Вавилонаца су пронађени и неки проблеми степеновања и логаритмовања бројева. Међутим, они логаритамске табеле нису користили у општим израчунавањима, већ само у решавању неких специфичних проблема.
Питагорин троугао У овој табели су препознатљиве Питагорине тројке, тј. три целобројне вредности које задовољавају једначину
Египатска математика мини|253x253px|Слика 3: Египатски бројеви Древни Египћани су вероватно прва цивилизација која је практиковала науку уметности. Египћани су доминирали у медицини и примењеној математици. Постоји велики број докумената која описују њихова достигнућа у медицини, али не постоје докази како су дошли до математичких закључака. Наравно, они су имали напредније разумевање математике због њихових подвига у инжењерству, астрономији и државној управи, без кога ти подвизи не би били могући.
Египћани су имали децимални систем са 7 различитих симбола. мини|251x251px|Слика 4: Поређење египатских и децималних бројева. 1 се представља као једна линија 10 се црта као лисице за стоку 100 се представља као намотај ужета 1.000 је цртеж лотоса. 10.000 је представљено прстом. 100.000 је пуноглавац или жаба. 1.000.000 је фигура бога са подигнутим рукама изнад главе Конвенција о читању и писању бројева је једноставна; већи број је увек написан испред мањег и где је више од једног реда бројева, читање почиње од врха.
Грчка математика
Талес Грчки филозоф који се сматра оснивачем Грчке науке, математике и филозофије. Он је посетио Египат, а вероватно и Вавилон, и вратио се са знањем из астрономије и геометрије. Увео је дедуктивну математику. По њему гласи и Талесова теорема.
Еуклидов алгоритам Грчки геометар који је написао Елементе, књигу о геометрији. Књига садржи ранија знања о геометрији, и коришћена је вековима у западној Европи као уџбеник из геометрије. Еуклид је доказао оно што је опште познато као Еуклидова друга теорема: број простих бројева је бесконачан. Он је такође говорио о тзв. Еуклидовом алгоритму, методи за проналажење највећег заједничког делиоца два броја. - подели број a са b, остатак је r - замени a са b - замени b са r - настави процес док се више бројеви не могу делити. У овом случају, a је НЗД.
Није утврђена нити година нити место његовог рођења, али ни околности његове смрти, иако се зна да је живео и радио у Александрији већи део свог живота.
Архимедов алгоритам безоквира|лево За Архимеда се сматра да је највећи математичар антике. Архимед је извео бројне геометријске доказе помоћу крутих геометријских формализма од Еуклида. Он је био посебно поносан на своје открића за проналажење запремине сфере и ваљка. Исто тако важан је резултат израчунавања односа обима и пречника круга и смештање тог односа у границе између π = 3 1/7 и 3 10/71, познатије као Архимедов алгоритам за израчунавање приближне вредности броја π.
Архимед је дошао до горње и доње границе броја π цртањем правилног шестоугла унутар и изван круга, и сукцесивно удвостручавао број страна док није дошао до 96-остраног правилног полигона. Рачунајући оквире овог полигона, доказао је да је 223/71 < π < 22/7 (односно 3.1408 < π < 3.1429).
Архимед је такође био изванредан инжењер, формулисао Архимедов принцип потиска и закон полуге, као и још доста других открића. Архимед је убијен од стране римског војника у Другом пунском рату. Приповеда се да му је последња реченица била: Noli turbare circulos meos! (Не дирајте моје кругове!)
Ератостеново сито мини|370x370px|Слика 5: Ератостеново сито за проналажење простих бројева до 120. Ератостен је радио као библиотекар у великој библиотеци у Александрији, и написао разна дела из математике, географије, филозофије, и астрономије. Такође је написао песму под називом Хермесгде је описао основе астрономије у стиху. Иако је већина Ератостенових списа изгубљена, многи су очувани кроз списе народа. Међу достигнућима је прецизно мерење пречника Земље. Пошто је изгубљен оригинални рад мерења пречника Земље, детаљи Ератостенових поступка нису познати. Ератостен је увео систем земаљских координата, припремио мапу звезда која садржи 675 звезда, предложио да преступна година буде сваке четврте године, покушао да изгради прецизно датирану историју, и развио Ератостеново сито, алгоритам за проналажење простих бројева: 1. Напишите све бројеве од 2 до n 2. Почевши од првог броја на списку (двојка) прецртајте са списка све бројеве дељиве са два и упишите да је двојка прост број. 3. Понављајте поступак са следећим непрецртаним бројем m. Дакле, прецртајте све бројеве дељиве са m, а њега самог обележите да је прост.
Каснија математичка открића
Гаусов метод елиминације У линеарној алгебри, Гаусов метод елиминације је алгоритам за решавање система линеарних једначина. Овај метод је добио име по Карлу Фридриху Гаусу, иако је био познат кинеском математичару Лиу Хуиу из 3. века. Систем од n линеарних једначина се решава изједначавањем броја непознатих и броја једначина. Псеудокод:
за k = 1 ... минимално од (m,n): Пронађи k-ту тачку: i_max := argmax (i = k ... m, abs(A[i, k])) ако је A[i_max, k] = 0 грешка "Матрица је јединична!" замени редове (k, i_max) Уради за све редове испод тачке: за i = k + 1 ... m: m := A[i, k] / A[k, k] Уради за све преостале елементе у првом реду: за j = k + 1 ... n: A[i, j] := A[i, j] - A[k, j] * m Нађи најмању троугаону матрицу са нулама: A[i, k] := 0
Брамагупта Брамагупта је рођен у 598. и живео је на северозападу Индије док није умро 668. Био је астроном и математичар. Написао је метод решавања неодређене једначине ax + by = c Брамагупта је развио метод решавања неодређених једначина другог степена и правила решавања једноставних квадратних једначина различитих типова.
Брамагупта је популаризовао важан концепт у математици: број нула.
Мухамед ел Хорезми Мухамед ел Хорезми је био персијски научник, математичар, астроном и астролог. Рођен је у 780. а умро је око 840. Он се често наводи као "отац алгебре", која је добила име по делу наслова његове књиге. Дао је значајан допринос у области алгебре, тригонометрије, и географије. Са својом књигом о рачуну са индијским бројевима, промовисао је коришћење индијског система бројева на Блиском истоку, а затим и у Европи. Ова књига је преведена на латински у 12. веку под именом Algoritmi de numero Indorum, тако да је његово име на латинском грешком преведено као "Алгоритми" што је индиректно одговорно за термин алгоритам. Његове књиге су дале значајан допринос унапређењу математике (решавање линеарних и квадратних једначина, као и геометријске принципе за попуњавање круга) у Европи. Он је допринео са таблицама тригонометријских функција, прецизирања у геометријској заступљености конусних пресека, и аспектима рачуна на две грешке, као и са публикацијама о механичким уређајима као што су сат, астролаб и сунчани часовник.
Ибн ел Хаитам