Утицај математике на настанак и темеље рачунарства (1. део)

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

Наивно схватање појма алгоритма је да је то механички, детерминистички поступак, који полазећи од некаквих улазних података, производи некакав излаз (резултат) у коначном броју корака. Израз „детерминистички” је употребљен у значењу да тај поступак примењен више пута за исте улазне податке, производи увек исти излаз до кога стиже на потпуно исти начин са истим корацима. Међутим, испоставиће се да је употребљено значење израза „механички” много дубље, а упрошћено значи да поступак не захтева размишљање да би се обавио, већ да на основу правила поступка у свакој ситуацији знамо како да наставимо поступак, све док он не буде у потпуности завршен.

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

Неки поступци који у одређеној мери (мада не потпуно) испуњавају наведене услове, старији су од бројева. Стари пастири нису умели да броје, а имали су потребу да знају да ли су све овце на броју. Било је више поступака сличних овоме. На пример, у празну торбу се може бацати камење приликом изласка оваца из тора (за сваку овцу по један), а при враћању би се камење вадило из торбе (за сваку овцу по један). Ако у торби остане неки камен, нека овца недостаје.

У старој Грчкој су били откривени алгоритми за решавање квадратне једначине (који имају разгранату структуру, тј. има више случајева који се решавају на различите начине), алгоритам за одређивање простих бројева до неке горње границе (тзв. „Ератостеново сито” које има цикличну структуру, тј. неки кораци се понављају), алгоритми за рачунање највећег заједничког делиоца и најмањег заједничког садржаоца целих бројева или полинома (тзв. „Еуклидов алгоритам”), као и разни други.

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

Персијски научник ал-Ховаризми (780-850) написао је дело у коме је описао индијски десетични бројни систем (који данас користимо) заједно са поступцима за рачунање у том систему, који се данас уче у нижим разредима основне школе. Као аутор дела се потписао испод наслова, али је његово име збунило преводиоце, који су мислили да се ради о некој њима непознатој арапској речи а не о властитом имену, па су наслов превели као „алгоритми са индијским бројевима”. Затим су на основу садржаја покушали да схвате шта су то алгоритми. На тај начин, осим речи „алгоритам”, настала је и реч „алгоризам”, која означава управо поменуте алгоритме за вршење рачунских операција.

Након тога су у математици откривени многи алгоритми, али је до следећег кључног корака дошло тек тридесетих година двадесетог века. Наиме, савремено схватање појма рачунара је да је то машина која може да изврши програм по било ком алгоритму, тј. да програмски језик, на коме се програмира, обухвата све алгоритме. Математичари такве математичке системе зову потпуним алгоритамским системима. Да би се то остварило, неопходно је свести све алгоритме на коначан број једноставних правила.

Наставак