Uticaj matematike na nastanak i temelje računarstva (1. deo)

Fundamentalna matematička istraživanja tridesetih godina dvadesetog veka omogućila su nastanak računara i ukazala su na granice njihove primenjivosti, koje se ni danas ne dovode u pitanje. Štaviše, rezultati tih istraživanja i danas predstavljaju stub teorijskog računarstva. Neki od problema koji još uvek nisu rešeni, od velike su važnosti za kriptografiju i očekuje se da njihovo rešavanje dovede do nove epohe u ovoj nauci.

Naivno shvatanje pojma algoritma je da je to mehanički, deterministički postupak, koji polazeći od nekakvih ulaznih podataka, proizvodi nekakav izlaz (rezultat) u konačnom broju koraka. Izraz „deterministički” je upotrebljen u značenju da taj postupak primenjen više puta za iste ulazne podatke, proizvodi uvek isti izlaz do koga stiže na potpuno isti način sa istim koracima. Međutim, ispostaviće se da je upotrebljeno značenje izraza „mehanički” mnogo dublje, a uprošćeno znači da postupak ne zahteva razmišljanje da bi se obavio, već da na osnovu pravila postupka u svakoj situaciji znamo kako da nastavimo postupak, sve dok on ne bude u potpunosti završen.

Algoritmi se javljaju kod vrlo starih naroda, koji su zbog potreba premeravanja površine zemljišta i zapremine ambara i sudova imali postupke za računanje površine figura i zapremina tela. Osim toga, u tom računu su morali nekako da predstavljaju brojeve i vrše operacije sa njihovim predstavljanjem, za šta su im opet nekakvi postupci bili neophodni.

Neki postupci koji u određenoj meri (mada ne potpuno) ispunjavaju navedene uslove, stariji su od brojeva. Stari pastiri nisu umeli da broje, a imali su potrebu da znaju da li su sve ovce na broju. Bilo je više postupaka sličnih ovome. Na primer, u praznu torbu se može bacati kamenje prilikom izlaska ovaca iz tora (za svaku ovcu po jedan), a pri vraćanju bi se kamenje vadilo iz torbe (za svaku ovcu po jedan). Ako u torbi ostane neki kamen, neka ovca nedostaje.

U staroj Grčkoj su bili otkriveni algoritmi za rešavanje kvadratne jednačine (koji imaju razgranatu strukturu, tj. ima više slučajeva koji se rešavaju na različite načine), algoritam za određivanje prostih brojeva do neke gornje granice (tzv. „Eratostenovo sito” koje ima cikličnu strukturu, tj. neki koraci se ponavljaju), algoritmi za računanje najvećeg zajedničkog delioca i najmanjeg zajedničkog sadržaoca celih brojeva ili polinoma (tzv. „Euklidov algoritam”), kao i razni drugi.

Iako su otkrivani razni algoritmi, prošli su vekovi dok pojam algoritma nije uočen kao zaseban pojam i dok nije dobio svoje ime. To se dogodilo zbog jedne prevodilačke greške.

Persijski naučnik al-Hovarizmi (780-850) napisao je delo u kome je opisao indijski desetični brojni sistem (koji danas koristimo) zajedno sa postupcima za računanje u tom sistemu, koji se danas uče u nižim razredima osnovne škole. Kao autor dela se potpisao ispod naslova, ali je njegovo ime zbunilo prevodioce, koji su mislili da se radi o nekoj njima nepoznatoj arapskoj reči a ne o vlastitom imenu, pa su naslov preveli kao „algoritmi sa indijskim brojevima”. Zatim su na osnovu sadržaja pokušali da shvate šta su to algoritmi. Na taj način, osim reči „algoritam”, nastala je i reč „algorizam”, koja označava upravo pomenute algoritme za vršenje računskih operacija.

Nakon toga su u matematici otkriveni mnogi algoritmi, ali je do sledećeg ključnog koraka došlo tek tridesetih godina dvadesetog veka. Naime, savremeno shvatanje pojma računara je da je to mašina koja može da izvrši program po bilo kom algoritmu, tj. da programski jezik, na kome se programira, obuhvata sve algoritme. Matematičari takve matematičke sisteme zovu potpunim algoritamskim sistemima. Da bi se to ostvarilo, neophodno je svesti sve algoritme na konačan broj jednostavnih pravila.

Nastavak