BAZA ZNANJA

Kurs: Strukture podataka i algoritamsko modelovanje

Modul: Algoritamsko modelovanje

Autor:

Naziv jedinice: Istorija algoritma i formalizacija

Istorija algoritama

U 9. veku naše ere persijski astronom i matematičar Muhamed Al-Horezmi, poznat kao Muhamed iz Horezma, napisao je rad "o računu pomoću indijskih brojeva", u kome je naučnik dao opis niza postupaka i preciznih pravila za razna izračunavanja. Horezmo je stara država na teritoriji današnjeg Uzbekistana. U 12. veku taj rad je preveden na latinski jezik kao Algoritmi de numero Indorum, gde je reč algoritmi trebalo da predstavlja latinizirano ime naučnika. Međutim, to je protumačeno kao množina nove reči u latinskom jeziku koja je trebalo da označi računski metod.

Definicija algoritma

Algoritam se definiše kao niz konačnih instrukcija i se često koristi za razna izračunvanja i obradu podataka. Kroz listu dobro definisanih instrukcija za završavanje određenog zadatka, algoritam stavljen u početno stanje prolazi različita, nadovezana stanja, posle određenog vremena završava sa radom, čime se dobija rezultat. Taj rezultat ne mora biti onaj koji smo očekivali. Prelazak iz jednog stanja u drugo ne mora uvek biti tačno određen. Neki algoritmi, poznati kao probabilistički u sebi sadrže i slučajne procese.

Važnost algoritma i neformalna definicija

Ne postoji opšteprihvaćena formalna definicija algoritma. Neformalna bi bila "algoritam je računarski program koji nešto izračunava". Za neke ljude program je algoritam samo ako se posle nekog vremena zaustavlja, dok je za druge ako se zaustavlja pre zadatog broja operacija.

Osnovni primer algoritma je Euklidov algoritam za izračunavanje najvećeg zajedničkog delioca: „Oduzmi manji od većeg, ponavljaj sve dok ne dobiješ nulu ili jedan". Poznato je da ovaj postupak uvek završava.
Još jedan lep primer bi bio rešavanje problema lampe koja ne radi:
„Da li je lampa uključena u struju? Ako nije, uključi je u struju, ako jeste, proveri da li je ispravna sijalica. Ako nije, zameni sijalicu, ako je ispravna, zameni lampu novom."
 

Slika 1. Jednostavan algoritam rešavanja problema lampe

Prilikom rešavanja nekog problema programer prolazi kroz razne etape razvoja programa. To su, redom, precizan opis problema, definisanje modela i izbor metoda za njegovo rešavanje, projektovanje algoritma, pisanje i testiranje programa i na kraju izrada prateće dokumentacije.

Opis problema

Aktivnosti koje se podrazumevaju pod opisom problema, bile bi:

1. definisati koje su informacije poznate i dostupne kao ulazni podaci
2. koja informacija i u kom obliku treba da se dobije kao rezultat
3. uključivanje lica koja se ne bave programiranjem (lekari, tehnolozi, ekonomisti, i dr.), dakle lica koja odlično poznaju tehnologiju problema ili ga poznaju bolje od programera

Definisanje modela i izbor metoda rešavanja

Nakon definisanja problema, prelazi se na opis problema formalnim aparatom, recimo matematičkim. Dakle, počinjemo sa korišćenjem matematičkih formula i relacija. Primer bi bio kako modelovati sistem linearnih jednačina kao tipičan matematički sistem.

Pored tačnih metoda za rešavanje, postoje i približne metode. U računarstvu se veoma često koristi aparat numeričke analize, jer se zahteva dobijanje nekog numeričkog rezultata. Postoji čitav niz problema koji se ne mogu rešiti klasičnim metodama ili je njihovo rešavanje isuviše glomazno, kao recimo problemi za rešavanje sistema jednačina velikog reda. Tom prilikom se isključivo koriste numerički metodi, a numerički metodi koriste samo osnovne aritmetičke operacije.

Projektovanje algoritma

Dobro projektovan algoritam uvek obezbeđuje neko rešenje, koje ne mora da bude ono koje se očekuje. Rezultat može da bude i da nema rešenja. Dobro projektovan algoritam mora garantovati završetak rada.

Osobine dobrog algoritma

Dobro napisan algoritam mora poštovati sledeća pravila:

• diskretnost
• determinisanost
• efektivnost ili konačnost
• rezultativnost
• masovnost
• optimalnost

Diskretnost

Algoritam se sastoji od konačnog broja posebnih koraka (algoritamski koraci). Svaki korak može zahtevati obavljanje jedne ili više operacija. U zavisnosti od toga koje operacije računar može da obavi, uvode se ograničenja za tip operacija koje se u algoritmu mogu koristiti (najčešće sabiranje, oduzimanje, množenje, deljenje).

Determinisanost

Svaki algoritamski korak mora biti strogo definisan i potpuno jasan. Na primer, izrazi tipa: "izračunaj pet podeljeno sa nulom" ili "dodaj 6 ili 7 puta" nisu dozvoljeni. Posle izvršenja tekućeg algoritamskog koraka, mora biti jednoznačno definisano koji je sledeći korak.

Efektivnost ili konačnost

Sve operacije koje se javljaju u jednom algoritamskom koraku moraju se izvršiti za konačno ili razumno kratko vreme. Vreme izvršenja celog algoritma mora biti konačno, to jest razumno dugo.

Rezultativnost

Svaki algoritam mora posle konačnog broja koraka generisati rezultat. Algoritam može imati nula ili više ulaznih podataka i može generisti jedan ili više izlaznih rezultata.

Masovnost

Svaki algoritam definiše postupak za rešavanje klase problema, a ne pojedinačnog slučaja. Na primer, rešavanje sistema jednačina bilo kog reda, množenje matrica proizvoljnog reda, itd.

Optimalnost

Ključne osobine jednog algoritma, međusobno povezane, bile bi:

• Vremenska kompleksnost - koliko brzo?
• Prostorna kompleksnost - koliko memorije?
• Kompleksnost koda  - lakoća razumevanja i snalaženja u kodu?

Pisanje algoritma

Program mora biti napisan u formi koju računar "razume". Svaki algoritamski korak se zamenjuje nizom instrukcija, jer, kao što znamo, instrukcije čine računarski program. Svaka instrukcija mora biti napisana po određenim pravilima. Ta pravila čine jezik kojim se izdaju naredbe računaru, odnosno programski jezik. Svaki programski jezik ima skup pravila kojima se definišu važeće jezičke konstrukcije i taj skup pravila se naziva sintaksa jezika. Sa druge strane, značenje ili dejstvo instrukcija čini semantiku jezika.