Probleemi lahendamine ja algoritm

< 1. nädala teemad

Algoritm

Probleem

Kõigepealt oli probleem, mis vajas lahendamist. Probleem ei lahene tavaliselt ise, vaid tema lahendamiseks tuleb midagi teha: sooritada vajalikud tegevused/sammud teatud järjekorras. Sõltuvalt probleemist on võimalik need sammud ise läbi teha. Kuid on võimalik panna neid ka kedagi teist tegema. Aga sellele teisele tuleb kõik täpselt selgeks teha, nö "puust ja punaseks", sest muidu ei saa ta aru ja seetõttu ei saa hakkama.

Algoritm

Täpne selgitus ("puust ja punaseks tehtu") on algoritm ning sõltub täitjast, milliseid lauseid ehk käske kasutades on talle võimalik tegevusi või operatsioone selgitada.

Formaalsemalt:

Algoritm: on lõplik instruktsioonide hulk, mis annab täpse operatsioonide järjestuse mingi probleemide klassi lahendamiseks.

Arvutiteaduses on algoritm teatud kindel meetod probleemi lahendamiseks (problem solving), mida saab realiseerida arvutiprogrammi abil (st ta sisaldab reeglina operastioone, mida on võimalik arvutile edastada).

Sõna algoritm päritolust: 1957. a. Webster'i sõnastik sellist sõna veel ei tunne. On "vanaaegne" sõna "algorism - aritmeetiliste tegevuste tegemine araabia numbrite abil". Sõna algorism pärineb Pärsiast ja seondub ühe sealse matemaatika õpiku autori nimega. 1747 Leipzigis välja antud matemaatika leksikonis selgitatakse sõna algorithmus, mis on aritmeetiliste tehete tegemine. Kokkuvõttes oletatakse, et algorism ja algorithmus aeti mingil hetkel segi ja nii tekkiski "algoritm".

Donald Knuth oma raamatus "Art of computer programming" viitab algoritmi analoogidele nagu toidu valmistamise retsept, protsess, meetod, protseduur, programm. Eelnev selgitus sõna "algoritm" päristolu kohta pärineb samast allikast.

Algoritmi omadused

Algoritmil on viis olulist omadust:

Lõplikkus. Algoritmi töö peab lõppema peale lõpliku arvu sammude läbimist. Kuid see sammude arv võib olla väga suur. Kui on aga karta, et algoritmi töö lõpliku arvu sammude pärast ei lõpe, siis kutsutakse seda hoopis arvutusmeetodiks.
Ettemääratus. Algoritmi iga samm peab olema täpselt määratud. Täidetavad tegevused peavad olema määratud rangelt ja ūhemõtteliselt iga juhu jaoks.
Sisend. Algoritmil on sisendandmed, kuid nende hulk võib olla ka null. Konkreetse algoritmi sisendandmed pärinevad alati kindlat liiki objektide hulgast.
Väljund. Algoritmil on üks või mitu töötulemust/vastust, st suurust, millel on täpselt määratud seos sisendandmetega.
Efektiivsus (tulemuslikkus). Algoritm on tulemuslik, kui kõik tema operaatorid ehk sammud on nii lihtsad, et nad on lõpliku ajavahemiku jooksul paberi ja pliiatsi abil täidetavad.

Kuidas võiksid need omadused olla seotud toiduvalmistamise retseptiga?

Sisend on toiduained, mida vajatakse - nende nimed ja kogused
Väljund on toode ise, kirjeldatuna läbi nime ja ilusa pildi (mis suu vett jooksma paneb)
Nendele kirjeldus, mida komponentidega teha tuleb - mida vahustada, mida sulatada, mida segada jne. Reeglina on toodud lõplik arv samme. Ja effektiivne peaks retsept ka olema - näiteks peale määratud aja ahjus hoidmist võib toote välja võtta ja nahka panna.

Informaatikas lisandub kindlasti nõue, et algoritm peab olema määratud nii täpselt, et seda suudaks täita isegi arvuti. Üldisemalt võib aga väita, et algoritmi kirjeldusest, seal määratud sammudest, peab saama aru seade, keda või mida selle abil juhtida tahetakse. Seega retsepti ei pea mõistma arvuti, aga inimene võiks küll.

Kuna algoritm peab olema praktiliselt täidetav, siis lisandub veel üks nõue - täidetavaid samme ei tohi olla liiga palju. MIngi realistliku aja jooksul peab algoritm täidetud saama. Lisaks peab algoritm lahendama ülesande õigesti erinevate sisendandmete korral.

Algoritm on õige (correct), kui kõigi sisendite korral, mis vastavalt algoritmi kirjeldusele on lubatud, lõpetab töö ja annab tulemuse, mis rahuldab ülesande tingimusi. Öeldakse, et algoritm lahendab arvutusülesande.

Tüüpilised käsud

Edaspidi käsitleme algoritmina sellist sammude kirjeldust, mis eelkõige arvutile suunatud on ja sellest tuleneb ka teatud jäikus ja piiratus tegevuste üleskirjutamisel. Sammud peavad olema sellised, et need oleksid tõlgitavad tüüpilisse programmeerimiskeelde, et saaks moodustada programmi.

Peamised tüüpilised käsud, mis esinevad pea igas programmeerimiskeeles ja sellest tulenevalt sobivad ka algoritmis kasutada, on järgmised:

sisend (input) klaviatuurilt sisestatud andmete kättesaamiseks või ka andmefailist andmete lugemiseks
väljund (output) andmete trükkimiseks ekraanile, faili või ka mõnele muule seadmele
tehted (expression) tavaliste matemaatiliste tehete (liitmine, lahutamine ...) tegemine, võimalikud ka operatsioonid tekstidega
otsuste tegemine / tingimustele vastav täitminen (conditional execution) kontrollitakse teatud tingimuste täidetust ja sellele vastavalt täidetakse käske
tegevuste kordamine (loop, repetition) samu tegevusi tehakse mitu korda (korratakse), tavaliselt väikeste erinevustega.

Seega algoritmi leidmiseks ja programmi koostamiseks tuleb suuremad tööd jaotada väiksemateks nii, et need oleksid väljendatavad selliseid põhikäske kasutades

Algoritmi ülesmärkimine

Algoritmi saab üleskirjutada tekstina / pseudokoodina või esitada skeemina (plokkskeem, tegevusskeem). Kõik nimetatud vahendid lubavad kirjeldada algoritmi üldisemalt ja sõltumatult konkreetsest programmeerimiskeelest, millesse ta siiski lõpuks tõlgitakse.

Näide algoritmist

Probleem: Täisnurksest kolmnurgast on teada tema kaatetid. Leia kolmnurga pindala ja ümbermõõt.

Algoritmi mitte väga ametlik üleskirjutus, mille järgi ka ise toimida, võiks olla järgmine:

Anna väärtused kaatetile a ja kaatetile b
Leia pindala valemiga a * b / 2


Trüki pindala
Leia hüpotenuus c Pythagorase teoreemi abil (siin tuleks ka tegelik valem välja kirjutada)
Leia ümbermõõt liites kokku kõik küljed (a + b + c)
Trüki ümbermõõt

Veidi ametlikum variant, kus on kasutatud üheseid tähistusi muutujate jaoks, oleks järgmine:

Sisesta a, b
S = a * b / 2
c = sqrt(a^2 + b^2)
P = a + b + c
Trüki S, P

Ja lõpuks sama algoritm tegevusskeemina:
Vasakpoolsel skeemil on kõik käsud üheselt mõistetavas järjekorras kirja pandud ja niimoodi saab kindlasti töö tehtud. Parempoolsel skeemil on kasutatud tegevusskeemi komponenti paralleelsus. Paralleelselt täidetavateks tegevusteks on pindala ja ümbermõõdu leidmine. Selline algorimti esitus väljendab asjaolu, et pindala ja ümbermõõdu võib tõepoolest samaaegselt välja arvutada. Edasise lihtsama programmi jaoks aga saame välja lugeda, et paralleelselt paiknevad laused võib üksteise suhtes suvalises järjekorras täita. Oluline on vaid, et hüpotenuus enne ümbermõõtu leitakse.

Programmi elutsükkel


    
edit

Kogu programmi elutsükkel, nagu me seda edaspidi läbi teeme, võiks väljanäha järgmine

probleemi läbimõtlemine/arusaamine - siin tuleb rõhutada korrektse arusaamise vajadust; kui tarkvaralooja koostab programmi, mis ei tee kliendi poolt vajatavat tegevust või ei lahenda etteantud probleemi, siis on kogu töö läbikukkunud. Hoolimata sellest, et programm täiesti laitmatult töötab
algoritmi koostamine - peale arusaamist tuleb endale ettekujutada üksikud sammud probleem lahenduseni jõudmiseks; sammud lähtugu eelpool mainitud põhikäskudest ja sellest, kuidas sa ise sama ülesande paberil lahendaksid ... ning pane algoritm kirja
algoritmi tõlkimine programmeerimiskeelde - tulemuseks on programmi lähtekood; kui algoritmis on kasutatud sobilikke käske, on tõlkimine lihtne
programmi kompileerimine / interpreteerimine - kui läheb hästi, siis saad kohe esimest korda töötavat programmi näha; kui nii hästi ei lähe, siis tuleb veel vigade otsimisel pingutada
süntaksivigade otsimine, parandamine ja uus käivitamine, kuni interpretaator koodi õigekirja korrasolevaks loeb ning ka programmi töötamisel ei ilmne esialgu vigaseid olukordi
testimine - selleks hetkeks peaksid vead niipalju kõrvaldatud olema, et võiks süveneda programmi töö õigsusesse; programmi käivitatakse erinevate algandmetekomplektidega eesmärgiga loogika (ehk semantika) vigu leida. Kui on vigu, siis need parandatakse ja minnakse tagasi kompleerimisele-käivitamisele.

< 1. nädala teemad