Prvi razred – uvod u programiranje

Algoritam

Algoritam je u matematiku uveo iranski matematičar Muhamed Al Horezmi. Napisao je knjigu Al Horezmi o indijskoj veštini računanja gde u islamsku matematiku uvodi indijske cifre i decimalni brojni sistem. Ova knjiga biva kasnije prevedena na latinski kao Algoritmi de numero indorum. Od lošeg latinskog prevoda njegovog prezimena i potiče reč algoritam, i dugo je označavala postupak za račun sa decimalnim brojnim sistemom (i indijskim odnosno, kako se kasnije pričalo, arapskim ciframa)

 Danas, algoritam je konačna i precizno definisana procedura, niz dobro definisanih pravila, kojom se ulazne vrednosti transformišu u izlazne, ili se opisuje izvršavanje nekog postupka.

Reč algoritam se često vezuje za pojam računarstva mada uopšteno algoritam možemo smatrati kao uputstvo kako rešiti neki zadatak ili problem. Tako se i uputstvo za slanje rakete u svemir i uputstvo za pravljenje ruske salate sastoji od niza koraka, postupaka, koje treba uraditi i koji vode ispunjenju cilja ili rešavanju problema. Uputstvo može sadržati korake koji se ponavljaju više puta ili korake kada treba doneti neku odluku, na osnovu nekog kriterijuma. Dobro uputstvo predviđa i postupak kada nisu svi uslovi ispunjeni npr. raketa je izgorela pri testiranju, ili nema majoneza u frižideru a počeli smo da kuvamo povrće. Korektno izvršavanje svakog koraka ne rešava zadatak ako je algoritam bio pogrešan.

Različiti algoritmi mogu rešiti isti problem različitim nizom postupaka uz manje ili više napora, za kraće ili duže vreme. Obzirom da je rezultat isti, algoritmi se mogu porediti po svojoj efikasnosti, brzini ili kompleksnosti.

Primer algoritma iz svakodnevnog života je kuvanje čaja. Svaki korak pripremanja čaja mora biti izvršen pravilno kako bi se moglo preći na sledeći i u konačnom vremenu dobili skuvan čaj.

Algoritam kuvanja čaja glasi:

Uzeti lonče i sipati vodu.

Uključiti ringlu.

Sačekati dok voda ne proključa.

Kad voda proključa, skinuti lonče i isključiti ringlu.

Staviti kesicu čaja u lonče.

Po želji, dodati kašiku šećera, mleko ili limun.

Sipati čaj u šolju.

Iz ovog jednostavnog primera može se videti postupnost i konačnost algoritma. Naime, nema previše koristi od algoritma koji se nikada ne završava ili algoritma čije se naredbe izvode nepredvidljivo ili im je rezultat nepredvidljiv.

Primer kompleksnijeg algoritma je Euklidov algoritam za određivanje najvećeg zajedničkog delioca:

• Podeliti broj a brojem b pri čemu se dobija količnik c i ostatak r
• Broj a uzima vrednost broja b
• Broj b uzima vrednost r
• Ponavljati sve dok ostatak r ne bude jednak 0. Najveći zajednički delilac je trenutna vrednost broja a

Prvi algoritam koji se može smatrati procedurom čija je namena račun na automatskoj mašini je napisala Ejda Bajron 1842. godine. U pitanju je algoritam za račun Bernulijevih brojeva na analitičkoj mašini Čarlsa Bebidža. Danas se to priznaje kao prvi računarski algoritam, a Ejda Bajron, ledi Lavlejs, je priznata kao prvi programer u istoriji. U njenu čast je i jedan od programskih jezika dobio naziv Ada.

Značajan napredak u formalizaciji uvođenja algoritma u matematiku i logiku je učinio Alan Tjuring u svojim radovima definisanjem Tjuringove mašine. To je virtuelna mašina, misaona tvorevina, ali poseduje mogućnost izvođenja nekoliko operacija koje su dovoljne za izvođenje skoro svih algoritama. Čerč-Tjuringova teza tvrdi da se svaki algoritam koji je dobro definisan može izvršiti na takvoj mašini. Tako se, i pored jednostavnosti ove mašine, začela teorija konačnih automata kao nova oblast.

Osobine

Algoritmi poseduju sledeće osobine:

Definisanost - svaki korak mora biti jednoznačno definisan, ne ostavljajući mesta za proizvoljna i nejasna tumačenja;

Diskretnost - u odvojenim koracima se izvršavaju diskretne operacije algoritma koji vode ka konačnom cilju;

Rezultativnost - označava sposobnost algoritma da posle konačnog broja koraka daje izlazne podatke;

Determinisanost - za iste ulazne podatke algoritam uvek generiše iste vrednosti na izlazima

Masovnost - algoritam je primenljiv na veći broj ulaznih vrednosti.

Algoritmi i strukture podataka

Svaki algoritam se sastoji od početka i kraja, dok se između toga nalaze elementi koji predstavljaju osnovne delove koji sadrže definisani put ka rešenju problema. Da bismo uopšte počeli sa rešavanjem problema, prvo moramo da ga definišemo i postavimo rešenje.

Algoritam može biti opisan na više načina: prirodnim jezikom, dijagramima, pseudokodom i programskim jezikom. Dijagrami su možda i najpopularniji način, jer se na jednostavan a slikovit način predstavlja problem i njegovo rešavanje. Za to vam nije potreban kompjuter, već prosto olovka i papir na kojem ćemo iscrtati algoritamsku šemu, tj. grafički prikaz algoritma.

Primer:

Nacrtati algoritam za računanje obima i površine kruga.

 Zadaci za vežbu:

1. Napisati rečima koristeći numeričko nabrajanje (numbering) niz koraka za izračunavanje obima i površine pravouglog trougla ako su mu date katete.
2. Nacrtati algoritam za računanje površine i zapremine valjka ako su nam dati poluprečnik osnove r i visina H. Možete ga uraditi u istom dokumentu gde je i prvi zadatak koristeći shapes