Algoritem je navodilo, kako rešimo nek
določen problem. Običajno je zapisan kot seznam korakov, ki nas
pripeljejo do rešitve problema. V tem pogledu lahko najdemo
analogijo z iskanjem poti iz labirinta (kar je seveda spet
problem).
Nekdo, ki se pred takimi problemi
prvič znajde, bo imel več težav, kot nekdo z izkušnjami. Zato naj
bi veljalo, da se lotimo najprej bolj preprostih problemov
(oziroma programov) in se šele kasneje lotimo bolj zamotanih.
Kasneje se bomo navadili tudi, da lahko v naše programe
vključujemo delčke kode starejših, že uporabljenih programov.
Pomislimo nato, kako bi nalogo
razdelili v manjše naloge oziroma faze ali korake. Pomislimo na
kuharske recepte, kjer potekajo stvari prav tako korak za korakom.
Naučimo se osnovnih postopkov za razvoj rešitve problema. Nič v tem
poglavju ne terja prav uporabe računalnika za rešitev problema. Ta
pnačin lahko uporabimo za reševanje številnih problemov, vključno s
tistimi, ki nimajo nič skupnega z računalniki.
Problemi, reševanje, orodja
Če je pred mano nek problem, ki ga moram rešiti, si pri tem pomagam s
primernim orodjem. To samo po sebi ne reši problema. Še vedno sem
jaz tisti, ki moram opraviti nalogo. Običajno v sebi sestavim načrt,
kako bom nalogo opravil. Tako tudi računalnik sam od sebe ne reši
problema. Jaz sem tisti, ki moram računalnik uporabiti kot orodje.
Računalnik
je orodje, ki ga lahko uporabimo za izvedbo načrta za reševanje
problema.
Računalniški
program je niz navodil za računalnik. V teh navodilih so opisani
koraki, ki jih mora računalnik upoštevati pri izvajanju načrta.
Algoritem
je načrt za reševanje problema.
Nekdo
mora načrtovati algoritem.
Nekdo
mora prevesti algoritem v računalniški program.
To naj bo
naše stališče za iskanje rešitev nekaterih problemov. Tudi tistih, ki jih
zapišemo v nekem programskem jeziku.
Proces razvoja algoritma
Vsako reševanje problema se začne z načrtom. Ta načrt imenujmo algoritem.
Algoritem je načrt za reševanje problema.
Obstaja veliko načinov za zapis algoritma. Nekateri so zelo neformalni,
nekateri so precej formalne in matematične narave, nekateri pa so precej
grafični. Navodila za priključitev DVD predvajalnika na televizor so
algoritem. Matematična formula, kot je πr2, je poseben primer
algoritma. Oblika ni posebej pomembna, če zagotavlja dober način za
opisovanje in preverjanje logike načrta.
Razvoj algoritma (načrta) je ključni korak pri reševanju problema. Ko
imamo algoritem, ga lahko prevedemo v računalniški program v nekem
programskem jeziku. Naš proces razvoja algoritmov je sestavljen iz petih
glavnih korakov.
1. korak: Problem opišimo.
2. korak: Problem analizirajmo.
3. korak: Razvijmo grob načrt (algoritem) za rešitev probklema.
4. korak: Če je potrebno, izboljšajmo algoritem z dodajanjem podrobnosti.
5. korak: Preverimo algoritem.
Korak 1: Problem opišimo
Ta korak je veliko težji, kot se zdi. V nadaljevanju označimo z besedo
naročnik nekoga, ki želi najti rešitev za problem, in z besedo
razvijalec nekoga, ki najde način za rešitev problema. Razvijalec mora
ustvariti algoritem, ki bo rešil naročnikov problem.
Naročnik je odgovoren za opis problema, vendar je to pogosto najšibkejši
del procesa. Povsem običajno je, da opis problema trpi zaradi ene ali več
naslednjih vrst napak:
opis temelji na napačnih predpostavkah,
opis je dvoumen,
opis je nepopoln ali
opis ima notranja protislovja.
Te napake so redko posledica nepazljivosti naročnika. Bolj verjetno so
posledica dejstva, da so naravni jeziki (angleščina, francoščina,
korejščina itd.) precej nenatančni. Del odgovornosti razvijalca je tudi
odkrivanje napak v opisu problema in delo z naročnikom za odpravo teh
napak.
Korak 2: Analizirajmo problem
Namen
tega koraka je določiti začetno in končno točko za reševanje problema.
Ta proces je analogen matematiku, ki določa, kaj je podano in kaj mora
biti dokazano. Dober opis problema olajša izvedbo tega koraka.
Pri
določanju izhodišča moramo najprej poiskati odgovore na naslednja
vprašanja:
Kateri podatki so na voljo?
Kje so ti podatki?
Katere formule se nanašajo na problem?
Katera pravila obstajajo za delo s podatki?
Kakšna razmerja obstajajo med podatkovnimi vrednostmi?
Pri
določanju končne točke moramo opisati značilnosti rešitve. Z drugimi
besedami, kako bomo vedeli, kdaj končamo? Postavljanje naslednjih
vprašanj pogosto pomaga določiti končno točko.
Katera nova dejstva bomo imeli?
Katere stvari se bodo spremenile?
Kakšne spremembe bodo narejene za te stvari?
Katerih stvari ne bo več?
Korak 3: Razvijmo algoritem na visokem nivoju
Algoritem
je načrt za reševanje problema, vendar načrti prihajajo v več stopnjah
podrobnosti. Ponavadi je bolje, da začnemo z grobim algoritmom
(algoritmom na visokem nivoju), ki vključuje večji del rešitve, vendar
pustimo podrobnosti pozneje.
Oglejmo
si koncept grobega (visokonivojskega) algoritma na vsakodnevnem primeru:
Problem:
Poslati moram pozdrav svojemu prijatelju Janezu.
Analiza: Nimam razglednice. Moral jo boim kupiti.
Grob algoritem:
Pojdi
v trgovino, ki prodaja razglednice
Izberi
razglednico
Kupi
razglednico
Pošlji
razglednico po pošti
Ta algoritem je zadovoljiv za vsakodnevno uporabo, vendar mu manjkajo
podrobnosti. Te vključujejo odgovore na vprašanja, kot so na primer.
"Katero
trgovino bom obiskal?"
"Kako
bom prišel tja: sprehod, vožnja, vožnja s kolesom, avtobus?"
"Kakšno
razglednico ima Janez najraje: duhovito, z rožami, s pokrajino?"
Takšne
podrobnosti obravnavamo v naslednjem koraku našega procesa.
Korak 4: Izboljšajmo algoritem z dodajanjem podrobnosti
Grob
algoritem prikazuje glavne korake, ki jih je treba upoštevati pri
reševanju problema. Zdaj moramo dodati podrobnosti tem korakom, toda
koliko podrobnosti moramo dodati? Odgovor na to vprašanje je odvisen
od situacije. Razmisliti moramo, kdo (ali kaj) bo izvedel algoritem in
koliko ta oseba (ali stvar) že ve, kako to storiti. Če bo nekdo drug
kupil razglednico v mojem imenu, se morajo moja navodila prilagoditi glede
na to, ali je ta kupec seznanjen s trgovinami v bližini in kako dobro
kupec pozna prijateljev okus.
Ko je naš cilj razviti algoritme, ki bodo vodili do računalniških
programov, moramo upoštevati zmožnosti računalnika in zagotoviti dovolj
podrobnosti, da bi lahko nekdo drug uporabil naš algoritem za pisanje
računalniškega programa, ki sledi korakom v našem algoritmu. Tako kot pri
problemu z razglednico moramo prilagoditi raven podrobnosti, da bo
ustrezala zmožnostim programerja. Če smo v dvomih, je bolje imeti preveč
podrobnosti, kot pa premalo.
Vsakič dodamo še več podrobnosti prejšnjemu algoritmu. Ustavimo se,
ko ne vidimo več koristi od nadaljnih izpopolnitev. Taki tehniki
prehajanja od grobega do bolj podrobnega algoritma pogosto pravimo
postopno izboljševanje algoritma.
Korak 5: Preverimo algoritem.
Končno
moramo algoritem pregledati. Kaj iščemo? Najprej se moramo
pomikati po algoritmu korak za korakom, da ugotovimo, ali bo rešil
prvotni problem ali ne. Ko smo prepričani, da algoritem zagotavlja
rešitev problema, začnemo preverjati druge stvari.
Naslednja
vprašanja so tipično tista, na katere moramo odgovoriti pri preverjanju
algoritma. Tako tudi razvijamo spretnosti, ki jih bomo lahko uporabili
pri naslednjih problemih.
(1)
Ali ta algoritem rešuje zelo specifičen problem ali pa rešuje
splošnejši problem? Če rešuje zelo specifičen problem, ali ga je možno
posplošiti?
Primer:
algoritem, ki izračuna obseg kroga s polmerom 5 cm metra (formula 2*π
* 5), reši zelo specifičen problem, vendar algoritem, ki izračuna
obseg katerega koli kroga (formula 2*π *r), rešuje splošnejši problem.
(2) Ali je mogoče ta algoritem poenostaviti?
Primer: Formula za izračun obsega
pravokotnika je: dolžina + širina + dolžina + širina
Enostavnejša formula bi bila: 2 * (dolžina + širina)
(3) Ali je ta rešitev podobna rešitvi kakšnega drugega
problema? Kako sta si podobni? Kako se razlikujeta?
Primer: Imejmo dve naslednji formuli:
ploščina pravokotnika = dolžina * širina
Ploščina trikotnika = 0,5 * osnovnica* višina
Podobnosti: Vsaka od obeh formul računa
ploščino. Vsaka od obeh formul opravi produkt dveh podatkov.
Razlike: Uporabljamo različne podatke. Formula
s trikotnikom vsebuje faktor 0,5.
Ugotovitev: Vsaka formula vključuje množenje dveh podatkov.
Praktičen
primer: Razvrščanje kvadrov po velikosti
1. korak: Problem opišimo.
Imamo 9 kvadrov različnih dolžin.
Pomešani so, radi bi jih razvrstili po velikosti
2. korak: Problem analizirajmo.
Poznamo število kvadrov in njihove velikosti. Vsak kvader ima položaj.
V začetku so kvadri v pomešanem vrstnem redu
Na koncu naj bi bili kvadri razvrščeni po velikosti, levo naj bi bil
najmanjši, desno naj bi bil največji.
Dva kvadra primerjamo po velikosti in upoštevamo njuna položaja.
Večji kvader naj bi bil na desnem položaju, manjši na levem
Kvadre bomo risali kot pravokotnike v različnih barvah.
3. korak: Razvijmo algoritem na visokem nivoju.
Najprej poglejmo korake, ki so
potrebni za razporejanje dveh posamičnih kvadrov:
Pogledamo velikost levega kvadra in si zapomnimo njegov
položaj
Pogledamo velikost desnega kvadra in si zapomnimo njegov
položaj,
Če je levi kvader manjši (ali enak desnemu), ostaneta kvadra,
kjer sta
Če je levi kvader večji, ga prestavimo na desno, večjega pa na
levo
Animacija na levi prikazuje razvoj
grobega algoritma
4. korak: Izboljšajmo algoritem z dodajanjem podrobnosti.
Sedaj znamo razporediti dva kvadra. Kaj pa, če jih je v vrsti
več? Kvadre spet pomešajmo in naredimo algoritem, da bo največji
kvader potisnjen skrajno desno, ostali pa ostanejo tam, kjer so.
Algoritem bi sedaj bil tak:
Vzamemo skrajni levi kvader in ga primerjamo oziroma
razvrstimo glede na naslednjega
Sedaj bi večji od obeh kvadrov na desnem položaju.
Postopek (primerjavo in razvrščanje) ponavljamo z naslednjim
desnim kvadrom v polju
To ponavljamo, dokler ne pridemo do skrajno desnega kvadra.
Na koncu bo največji kvader končal na skrajni desni
Dodatna izboljšava: Tako smo doslej potisnili (razvrstili)
največji kvader skrajno desno. Ostali so še nerazporejeni.
Ponovimo postopek s preostalimi kvadri in to tolikokrat,
koilikor je še nerazporejenih kvadrov. Vsakokrat potisnemo
največji kvader v preostanku skupine skrajno desno.
5. korak: Preverimo algoritem
Ugotovimo, da razviti algoritem reši naš problem. Kvadri so na koncu
urejeni po velikosti od najmanjšega na levi do največjega na desni.
A imeli smo opravka le z 9 kvadri. Če bi jih bilo veliko, bi bil ta
algoritem preveč zamuden. Uporabiti bi morali boljše strategije.
Podoben problem srečamo na primer, če je naša naloga sestaviti
vse pare v veliikeeem kupu pomešanih nogavic :)
