Reševanje problemov in razvoj algoritmov



Uvod

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.

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 problema.

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:

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:

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.


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:

Ta algoritem je zadovoljiv za vsakodnevno uporabo, vendar mu manjkajo podrobnosti. Te vključujejo odgovore na vprašanja, kot so na primer.

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.

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, kolikor 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 :)

Le kako bi se lotili te naloge?