Previous Up Next

Peatükk 1  Põhimõisted

Käesolevas peatükis tutvume kõige põhilisemate mõistetega, ilma milleta ei saa rääkida ei programmeerimisest ega programmidest.

1.1  Algoritm ja programm

1.1.1  Algoritm

Algoritmiks (ingl algorithm) nimetatakse samm-sammulist eeskirja mingi tegevuse sooritamiseks või eesmärgi saavutamiseks. Kõige sagedamini kasutatakse seda terminit just matemaatilise ülesande lahendamiseks mõeldud eeskirja kohta.

Sõna `algoritm' tuleb IX sajandi araabia matemaatiku Abu Jafar Muhammad ibn Musa hüüdnimest al-Horazmi (`mees Horezmi linnast', tema sünnilinna, praeguse Usbekistani territooriumil asuva Hiiva tolleaegse nime järgi). Al-Horazmi XII sajandil ladina keelde tõlgitud tööde kaudu jõudsid Lääne-Euroopa matemaatikuteni muude Indiast ja Araabiast pärit ideede kõrval ka mitmed võrrandite lahendamise eeskirjad, mida hakatigi algoritmideks kutsuma.

Erinevate (mittematemaatiliste) algoritmidega puutume kokku iga päev: näiteks kokaraamatus olevad retseptid või sõbrale jäetud juhised kohtumispaika jõudmiseks. Algoritmid on ka koolis õpetatavad mitmekohaliste arvude kirjaliku liitmise-lahutamise-korrutamise-jagamise eeskirjad.

Eel- ja järeltingimus

Lisaks tegevuse sooritamiseks vajalike sammude loetelule on algoritmi kirjeldusel veel kaks tähtsat komponenti: eel- ja järeltingimus.

Algoritmi eeltingimuseks (ingl precondition) nimetatakse selle rakendamiseks vajalike eelduste loetelu.

Paljude algoritmide eeltingimused on nii keerulised, et nende täielik väljakirjutamine pole mõeldav. Sellisel juhul esitatakse ilmutatud kujul ainult spetsiifiliselt sellele algoritmile iseloomulikud eeldused ja jäetakse märkimata valdkonna üldisemad alused.

Näiteks kokaraamatus toodud retsepti alguses olev komponentide loetelu on selle retsepti eeltingimus --- kui kokal vajalikke aineid pole, ei saa ta seda toitu valmistada. Lisaks ilmutatud kujul üles loetud toiduainetele on vaja ka töövahendeid (pliiti või ahju, potti või panni jne), aga neid tavaliselt eraldi ei nimetata. Töövahendite vajadus selgub alles valmistamisjuhendit lugedes. Kui tegemist on köögiga, kus eksootilisemaid vahendeid (näiteks wok-panni) ei ole, peab kokk lugema läbi ka valmistamisjuhendi ja saab alles selle põhjal otsustada, kas tal on kõik vajalikud eeldused täidetud.

Sõbrale kohtumispaika jõudmiseks jäetud juhised algavad tavaliselt mingist mõlemale poolele teadaolevast kohast --- kohalejõudmise algoritmi eeltingimus on, et sõber läheb omal käel sellesse alguspunkti ja alustab juhiste järgi liikumist just sealt.

Kirjaliku jagamise algoritmi (õigupoolest mistahes jagamisalgoritmi) eeltingimus on, et jagaja ei ole null.

Algoritmi järeltingimuseks (ingl postcondition) nimetatakse lubadust, mis peab täituma, kui, alustades algoritmi eeltingimust rahuldavast olekust, sooritada kõik algoritmi sammud.

Igapäevase elu algoritmides pole järeltingimust enamasti välja toodud --- see lepitakse osapoolte vahel kokku muul moel. Näiteks retsepti järeltingimus on lubatud roa valmimine, teejuhise järeltingimus soovitud sihtpunkti jõudmine ning kirjaliku jagamise eeskirja järeltingimus jagatise ja jäägi tekkimine kindlatesse kohtadesse arvutuse tulemuste hulgas.

Vahetingimus

Algoritmi uurimisel ja eriti selle õigsuse tõestamisel on oluline ka vahetingimuse mõiste.

Algoritmi vahetingimuseks (ingl midcondition) algoritmi järjestikuste sammude Si ja Si+1 vahel nimetatakse tingimust, mis kehtib, kui algoritmi täitmine on jõudnud seisu, kus samm Si on juba lõpetatud, kuid sammu Si+1 pole veel alustatud.

Kui vaadelda sammuga Si lõppevat osa ühe algoritmina ja sammuga Si+1 algavat osa teise algoritmina, siis on nende sammude vahel kehtiv vahetingimus samaaegselt esimese osa järeltingimus ja teise osa eeltingimus.

Mitteformaalselt võib öelda, et eel- ja järeltingimus on vahetingimuse erijuhud --- eeltingimus on vahetingimus, mis kehtib enne algoritmi esimese sammu täitmist, järeltingimus on vahetingimus, mis kehtib pärast algoritmi viimase sammu täitmist.

Näiteks kohtumispaika minemise algoritmis võib olla lõik: ``...lähed kaks tänavavahet edasi ja pöörad paremale; seal on sild; lähed üle selle ja pöörad vasakule...''. Keskmine fraas ei ole ilmselt algoritmi samm --- sild kas on lubatud kohas või ei ole ja algoritmi täitja (antud juhiste järgi liikuja) ei saa seda fakti muuta. Tegemist on hoopis vahetingimusega.

Tõend

Algoritmi kirjelduses ilmutatud kujul välja toodud vahetingimust nimetatakse tõendiks (ingl assertion). Tõendid võimaldavad algoritmi täitjal kontrollida, kas algoritmi täitmine sinnamaani on olnud edukas.

Nagu eeltingimused, on ka vahetingimused sageli liiga suured, et neid täielikult välja kirjutada ja kontrollida. Mittetäielike vahetingimuste kasutamisel peab meeles pidama, et igasuguse tõendi mittekehtimine tähendab alati veaolukorda, kuid vigade puudumist tõestab ainult täieliku vahetingimuse kehtimine.

Silla puudumine eelmises näites tähendab kindlasti, et midagi on valesti läinud. Selle olemasolu ei tõesta veel, et orienteeruja on õiges kohas (ta võib olla ka mõne teise silla juures), kuid välistab siiski suure hulga valesid võimalusi (kõik need tänavad, kus pole üldse silda).

Mõnikord muudab vahetingimuse rikkumine algoritmi edasise täitmise võimatuks. Kui silda ei ole, ei saa sellest ka üle minna, seega tekiks selle algoritmi täitmisel tõrge ka ilma vahetingimust kontrollimata. Alati see siiski nii ei ole.

Näiteks juhiste ``...pöörad paremale; seal on lehekiosk; lähed kaks tänavavahet edasi ja pöörad vasakule...'' täitmist lehekioski puudumine otseselt ei sega, kuid tõenäoliselt ei jõua kord juba teelt eksinu ka õigesse kohta.

Just keerulisemates algoritmides on vahetingimuste väljatoomine väga kasulik. Vahetingimuste kontrollimine algoritmi täitmise ajal võimaldab kohe avastada, kui midagi on viltu läinud.

Diagnostikast veelgi olulisem on aga see, et vahetingimuste sõnastamine sunnib algoritmi koostajat oma loogika korralikult läbi mõtlema ja sageli jäävad vead üldse tegemata.

Algoritmi õigsus

Osutub, et vahetingimuste abil on võimalik ka algoritmi õigsust tõestada.

Olgu meil antud n-sammuline algoritm, mille sammud on S1, S2, ..., Sn, eeltingimus Te ja järeltingimus Tj. Selle algoritmi õigsuse tõestuseks (ingl proof of correctness) nimetatakse tingimuste jada T0, T1, ..., Tn, mille korral kehtivad väited Selle definitsiooni tähendus peaks olema ka intuitiivselt üsna hästi mõistetav. Algoritmi eeltingimusest alustades näitame algoritmi iga sammu juures, et selle sammu täitmine viib sammule eelneva vahetingimuse üle sammule järgnevaks vahetingimuseks. Kui viimase sammu järel saavutatav tingimus on algoritmi järeltingimus, siis ütlemegi, et algoritmi õigsus on tõestatud.

1.1.2  Programm

Programmiks (ingl program) nimetatakse algoritmi esitust mingis formaalses keeles, tavaliselt programmikeeles või masinakoodis.

Programmide näiteid on väljastpoolt arvutimaailma raske leida --- tavaliselt kasutatakse igapäevases elus eeskirjade ja juhiste esitamiseks loomulikku keelt. Muidugi võib ka inimesele täitmiseks antud tegevuskava võrrelda programmiga, kuid üldjuhul ei täida inimene talle antud korraldusi mehaaniliselt ja mõtlemata.

Arvuti seevastu täidab programmi alati täpselt nii, nagu see on kirjas, juurdlemata selle üle, mida programmi autor seda kirjutades tegelikult tahtis. See (Greeri kolmanda seaduse nime all tuntud) põhimõte on nii oluline, et väärib eraldi esiletoomist:
Arvutiprogramm teeb seda, mida te käsite tal teha,
ja mitte seda, mida te tahate, et ta teeks.1

1.1.3  Programmikeel

Programmikeeleks (ingl programming language) nimetatakse algoritmide arvutile esitamiseks loodud formaalset keelt.

Kuigi programmikeeled on esimeste programmeeritavate arvutite ajast saadik arenenud tublisti inimsõbralikumaks, ei ole inimkeeles programmeeritavaid arvuteid siiski niipea loota. Näilisele inimsõbralikkusele vaatamata sarnanevad tänapäevased programmikeeled oma jäikuse poolest pigem masina kui inimese loomulikule keelele.

Loomulik keel ei sobi algoritmide arvutile esitamiseks peamiselt kahel põhjusel: esiteks on ta tänapäeva arvutite jaoks liiga keeruline ja teiseks on ta mitmetimõistetav. Isegi kui loomuliku keele keerukus õnnestuks ületada, jääb mitmetimõistetavus ikkagi takistama selle kasutamist algoritmide piisavalt täpseks esitamiseks.

Et vältida loomuliku keele mitmetimõistetavusest kerkivaid raskusi, kasutatakse formaalseid keeli ka väljaspool arvutimaailma. Lihtsaim praktiline näide on pangas maksekorralduse vormistamiseks täidetav plank --- selle range struktuur ja piiratud väljendusvõimalused tagavad, et pangatöötaja saab üheselt aru, kellelt, kellele ja kui palju tuleb raha üle kanda. Vabas vormis kirjutatud maksekorralduse puhul ei tarvitse korralduse andja mõte üheselt arusaadav olla.

Nagu loomuliku keele puhul, tuleb ka formaalsest keelest rääkides eristada selle süntaksit ja semantikat.

Keele süntaksiks (ingl syntax) nimetatakse keele lausetele esitatavaid vormilisi nõudeid. Teiste sõnadega, keele süntaks kirjeldab, millised on selles keeles vormiliselt korrektsed laused.

Keele semantikaks (ingl semantics) nimetatakse selle keele vormiliselt korrektsetele lausetele omistatavaid sisulisi tähendusi. Süntaktiliselt vigastele lausetele tavaliselt mingit tähendust ei anta.

Seejuures väärib eraldi märkimist, et süntaktiliselt korrektne lause võib semantiliselt ikkagi ebaõige olla. Näiteks on väide ``Tartu on Eesti pealinn'' vormiliselt küll igati korrektne (kõik sõnad on õigesti kirjutatud ja lauseehitusega sobivas käändes, pärisnimed algavad suurtähega jne), kuid sisuliselt vale --- Eesti pealinn on Tallinn, mitte Tartu.

Nagu loomuliku keele lause, võib ka süntaktiliselt korrektne programm semantiliselt vigane olla. Paljud algajad programmeerijad keskendavad uue keele õppimisel kogu tähelepanu süntaksile ja unustavad, et tegelikult on peamine just semantika --- keelekonstruktsioonide sisuline tähendus.

Ilmselt soodustab seda tendentsi ka asjaolu, et arvuti on võimeline automaatselt kontrollima ainult programmeerija kirjutatud teksti vormilist korrektsust, kuid mitte selle sisu vastavust programmeerija taotlusele (see ongi Greeri kolmanda seaduse kehtimise põhjus!). Sageli ei õnnestu süntaktiliselt vigast programmi üldse käima panna, kuid semantiliselt ``logisev'' programm läheb käima ja võib vahel isegi õigeid (või esmapilgul õigetena tunduvaid) tulemusi väljastada, jättes petliku mulje, nagu oleks ülesanne lahendatud.

1.1.4  Programmikeelte liigitus

Kuigi arvutite ja programmeerimise ajaloo jooksul on loodud palju erinevaid programmikeeli, on väga vähe selliseid, mis ei sarnane ühegi teisega. Sellest lähtuvalt on loomulik, et programmikeeli jagatakse nende ülesehituse ja eesmärkide järgi mitmetesse kategooriatesse.

Programmikeeli võib klassifitseerida nende otstarbe järgi --- programmikeel võib olla kas üld- või eriotstarbeline. Üldotstarbeline (ingl general-purpose) programmikeel võimaldab kirjutada programme paljude erinevate valdkondade jaoks, eriotstarbeline (ingl special-purpose) programmikeel seevastu on orienteeritud ühe valdkonna ülesannete lahendamisele --- ``õige'' valdkonna ülesannete lahendamine on spetsialiseeritud keeles mugavam kui üldotstarbelises keeles, kuid mõne teise valdkonna ülesannete lahendamine vastavalt ebamugavam või isegi võimatu.

Eriotstarbelised programmikeeled on näiteks andmebaaside töötlemise keel SQL ja dokumentide kirjeldamise keel PostScript (vastupidiselt laialt levinud arvamusele on PostScript täievoliline programmikeel, mitte pelgalt failivorming).

Teine võimalus on liigitada programmikeeli nende keelekonstruktsioonide järgi --- keel võib olla kas imperatiivne või deklaratiivne. Deklaratiivses (ingl declarative) keeles programmeerides kirjeldab programmeerija, mida on vaja saavutada, imperatiivses (ingl imperative) keeles aga seda, kuidas soovitud tulemuseni jõuda.

Lõviosa tänapäeval kasutatavaid programmikeeli on imperatiivsed, kõige laiemalt levinud (kuigi mitte ainus praktikas kasutatav) deklaratiivne keel ongi andmebaaside töötlemise keel SQL.

Kolmas tähtsam võimalus on liigitada programmikeeli abstraktsioonitaseme järgi --- mida abstraktsem on keel, seda vähem peab programmeerija selles keeles programmeerimisel teadma konkreetse arvuti tehnilistest detailidest. Sellest liigitusest tuleb lähemalt juttu järgnevates lõikudes.

Kuigi kolme eeltoodud kriteeriumi võib pidada peamisteks, ei ammenda nad kaugeltki kõiki võimalusi programmikeeli liigitada. Täiendavaid viiteid erinevat tüüpi keeltele ja neid kirjeldavatele allikatele on õppematerjali viimases peatükis.

Masinakood

Arvuti ``loomulik keel'' koosneb ainult arvudest. Kogu informatsioon, mida arvuti töötleb, esitatakse arvuti mälus arvudena kodeeritult. Kõik käsud, mida arvuti täita oskab, kodeeritakse samuti arvudena. Programmide ja andmete sellist esitust nimetatakse masinakoodiks (ingl machine code).

Tänapäevase arvuti masinakood on peaaegu kindlasti imperatiivne keel, mis koosneb tavaliselt mõnekümnest kuni mõnesajast käsust ja on üldiselt igal arvutitüübil erinev.

Kuna masinakood on igal arvutitüübil erinev, ei ole masinakoodis kirjutatud programme üldjuhul võimalik vähese vaevaga ühelt arvutilt teisele üle viia. Kui arvutid on piisavalt erinevad, on sageli otstarbekam programm uue arvuti jaoks lihtsalt uuesti kirjutada.

Masinakoodis programmeerimine on vaevarikas ja veaohtlik tegevus --- näiteks tõenäosus, et mingit sõna esitavas arvujadas kogemata 97 asemel 98 kirjutanud inimesel oma viga märkamata jääb, on märksa suurem kui tõenäosus, et see juhtub selles sõnas `a' asemel `b' kirjutanud inimesel.

Kuigi masinakoodis programmeerimise järele pole tänapäeval enam praktilist vajadust (väga üksikud erandid välja arvatud), on arvuti töö paremaks mõistmiseks siiski kasulik tutvuda vähemalt mõne arvutitüübi masinakoodi ülesehitusega. Muude eelistuste puudumisel võiks selleks olla Donald E. Knuthi spetsiaalselt õppeotstarbeks loodud MIX2 või MMIX3.

Sümbolkeel

Sümbolkeeleks (ingl symbolic language) nimetatakse programmikeelt, milles programmeerimisel kasutatakse operatsioonidele ja andmetele viitamiseks arvuliste koodide asemel sümbolkujul nimesid. Sümbolkeeli liigitatakse kõrg- ja madalkeelteks.

Madalkeele (ingl low-level language) käsud vastavad üldiselt üsna üks-ühele masinakoodi käskudele. Seega on madalkeeles kirjutatud programm endiselt seotud konkreetse arvutitüübi masinakoodiga, kuid sümbolesitus võimaldab programmeerijal kergemini vigu vältida ning juba tehtud vigu avastada ja parandada.

Kõrgkeel (ingl high-level language) on konkreetse arvuti ja opsüsteemi ülesehitusest sõltumatu, selle asemel on kõrgkeel orienteeritud programmi loogika ja töödeldavate andmete struktuuri paremale esitamisele. Kõrgkeeles kirjutatud programmi on võimalik ka ühelt arvutitüübilt teisele üle viia.

Kompilaator ja interpretaator

Kuna arvuti sümbolkeeles kirjutatud programme otse täita ei saa, tuleb sümbolkeelne programm enne täitmist masinakoodi tõlkida. Kõige parem on lasta see tüütu töö arvutil endal ära teha. Selleks vajalikku programmi nimetatakse translaatoriks (ingl translator).

Translaatorit, mis tõlgib ja täidab programmi ühe käsu kaupa, nimetatakse interpretaatoriks (ingl interpreter); translaatorit, mis tõlgib korraga terve programmi või mooduli ja salvestab tulemuse hilisemaks kasutamiseks, nimetatakse kompilaatoriks (ingl compiler).

Praktikas on levinud ka mitmesugused hübriidlahendused. Näiteks Java kompilaator tõlgib Java-programmi spetsiaalsesse vahekeelde (nn baitkoodi), mille täitmiseks kasutatav programm (nn Java virtuaalmasin) on sisuliselt baitkoodi interpretaator.

1.2  Programmi elemendid

Valdava enamiku tänapäevaste programmikeelte süntaksi elemendid jagunevad kolme liiki: primitiivid, juhtkonstruktsioonid ja deklaratsioonid.

1.2.1  Primitiivid

Primitiivideks (ingl primitive) nimetatakse neid korraldusi, mille täitmise tulemusena tegelikult soovitud tulemus saavutatakse. Näiteks retseptis on primitiivid otseselt toiduvalmistamise operatsioonid: ``hakkida'', ``koorida'', ``keeta'' jne. Analoogiliselt on sõbrale kohtumispaika minekuks jäetud juhistes primitiivid otseselt tema liikumist suunavad fraasid: ``keera vasakule'', ``keera paremale'', ``mine N tänavavahet edasi'' jne.

Primitiivid võivad olla parameetriteta või parameetritega. Parameetriteta primitiiv koosneb ainult korraldusest midagi teha: ``istu'', ``seisa'' jne.

Parameetritega primitiiv sisaldab tegevust täpsustavaid lisandeid. Ilmselt on lihtne näha, et juhised ``mine 2 tänavavahet edasi'' ja ``mine 3 tänavavahet edasi'' on üsna sarnased, erineb ainult üks detail --- tänavavahede arv. Seda muutuvat detaili nimetataksegi üldkujulise primitiivi ``mine N tänavavahet edasi'' parameetriks (ingl parameter).

Nii loomulikes kui ka formaalsetes keeltes on parameetritega primitiive rohkem kui parameetriteta primitiive, kuigi loomuliku keele puhul pole see vahetegemine alati selge --- näiteks, kas ``keera vasakule'' ja ``keera paremale'' on kaks eraldi primitiivi või hoopis üldkujulise primitiivi ``keera suunas X'' kasutamine erinevate parameetritega? (Hiljem näeme, et selliste küsimuste lahendamisega tuleb tegeleda ka programmeerimise käigus.)

1.2.2  Juhtkonstruktsioonid

Juhtkonstruktsioonideks (ingl control structure) nimetatakse programmi elemente, mis määravad, milliseid primitiive, millises järjekorras ja kui palju kordi täidetakse.

Seni on näidetes esinenud ainult üks juhtkonstruktsioon: järjend (ingl sequence) --- kõik primitiivid täidetakse juhistes antud järjekorras, ühtegi vahele jätmata või kordamata. Järjend on enam-vähem samal kujul olemas ka kõigis programmikeeltes --- üldiselt täidetakse muude konstruktsioonide puudumisel primitiive just selles järjekorras, nagu nad programmi tekstis kirjas on.

Huvitavamate ja keerulisemate juhtkonstruktsioonide uurimisele pühendame kolm järgmist peatükki, sellepärast neil praegu pikemalt ei peatu.

1.2.3  Deklaratsioonid

Deklaratsioonid (ingl declaration) kirjeldavad objekte, millega programmis edaspidi tegemist tuleb. Deklaratsioonid ei tee otseselt midagi (selleks on primitiivid) ega suuna ka programmi käiku (selleks on juhtkonstruktsioonid).

Deklaratsioone programmis võib võrrelda tegelaste tutvustusega näidendi või filmistsenaariumi alguses või definitsioonidega matemaatikaõpikus, sest nende ülesandeks on panna paika ``tegelased'' ja fikseerida ``mõisted'', millega programm edaspidi opereerima hakkab.

1.3  Muutuja, väärtus, tüüp

1.3.1  Muutuja

Arvuti mälu koosneb nummerdatud mälupesadest. Igasse mälupessa võib salvestada ühe arvu4, mis püsib seal seni, kuni arvuti välja lülitatakse või kuni samasse mälupessa mõni teine arv salvestatakse.

Programmi töö ajal mingi väärtuse hoidmiseks eraldatud mälupesa nimetataksegi muutujaks (ingl variable).

Masinakoodis kasutab programmeerija mälupesa poole pöördumiseks selle numbrit, mis pole kuigi mugav --- on ju üsna tüütu meeles pidada, et parasjagu töödeldava arvujada minimaalne väärtus on mälupesas number 325452, maksimaalne väärtus mälupesas 325456 ja jada elemendid veel mingite muude numbritega mälupesades.

Sümbolkeeles annab programmeerija igale muutujale nime. Üldiselt peaks muutuja nimi kirjeldama selles hoitava väärtuse sisu. Näiteks võib jada minimaalse elemendi väärtuse hoidmiseks kasutatavat muutujat nimetada min ja maksimaalse elemendi väärtuse hoidmiseks kasutatavat max.

Muidugi on muutujale antava nime ja selles hoitavate andmete vastavus programmeerija asi. Arvuti sellest kinnipidamist kontrollida ei saa --- kui arvuti suudaks inimese mõtteid lugeda, oleks programmeerimine kui amet juba kadunud.

Siiski on programmeerija enda huvides muutujatele mõistlikud nimed panna, vastasel korral ei saa ta ise ka varsti aru, millised andmed kuhu salvestatud on --- rääkimata juba suurtest tarkvaraprojektidest, kus ühe programmi kirjutamisega tegeleb mitmete aastate jooksul kümneid või isegi sadu programmeerijaid.

1.3.2  Väärtus ja tüüp

Nagu eelpool öeldud, on arvuti riistvara seisukohalt mälus ainult arvud. See, et mõnda arvu tõlgendatakse arvuna, mõnda sümboli koodina ja mõnda veel mingil muul moel, on programmeerijate omavahelise kokkuleppe küsimus ja arvuti protsessor ei tea sellest üldiselt midagi.

Masinakoodis on nende vastavuste meelespidamine programmeerija mure, sümbolkeeles võtab (vähemalt osa) selle(st) vaeva(st) enda kanda translaator. Selleks, et translaator teaks, mismoodi ühe või teise mälupesa sisuga ümber käia, tuleb muutuja kirjeldamisel teatada selle tüüp (ingl type), see tähendab, öelda, millist liiki väärtusi selles muutujas hoidma hakatakse.

Tavaliselt on programmikeeltes eraldi tüübid täis- ja reaalarvude, märkide (sümbolite), tekstide (sõnede) ja tõeväärtuste esitamiseks. Paljudes keeltes on lisaks neile olemas spetsiaalsed tüübid kuupäevade, kellaaegade jmt suuruste jaoks.

Abstraktne ja konkreetne tüüp

Abstraktne andmetüüp (ingl abstract data type, ADT) koosneb väärtusvarust ja operatsioonivarust.

Andmetüübi väärtusvaru (ingl domain) näitab, milliseid väärtusi on võimalik seda tüüpi muutujasse salvestada, ja operatsioonivaru, mida on võimalike nende väärtustega peale hakata.

Näiteks Java täisarvutüüp int võimaldab salvestada täisarvulisi väärtusi lõigus -2 147 483 648 kuni 2 147 483 647 ning sooritada nende väärtustega aritmeetilisi tehteid, võrrelda neid omavahel jmt.

Konkreetne andmetüüp (ingl concrete data type) erineb abstraktsest selle poolest, et määrab kindlaks ka selle tüübi kõigi võimalike väärtuste esitamise arvuti mälus. Veidi lihtsustades võib öelda, et konkreetne tüüp seab abstraktse tüübi igale võimalikule väärtusele vastavusse arvu, millena see väärtus arvuti mällu salvestatakse.

Tavaliselt jätab kõrgkeele kirjeldus andmetüüpide väärtuste esituse translaatori kirjutaja otsustada. Sel juhul on kõrgkeele kirjelduses andmetüübid antud abstraktsete tüüpidena.

Liht- ja liittüüp

Andmetüüpi, mille võimalikud väärtused on programmikeele jaoks atomaarsed, jagamatud suurused, nimetatakse lihttüübiks (ingl simple type). Tüüpi, mille võimalikud väärtused koosnevad selgelt eristatavatest osadest, nimetatakse liittüübiks (ingl composite type).

Näiteks märgitüüp on lihttüüp --- üheski üldotstarbelises keeles ei vaadelda tähemärke kui mingitest osadest koosnevaid moodustisi, vaid ikka kui terviklikke ja jagamatuid suurusi.

Tekstitüüp seevastu on liittüüp --- kõigis üldotstarbelistes keeltes, kus tekstitüüp üldse olemas on, vaadeldakse teksti kui märgijada, millega võib manipuleerida ühe tervikuna, kuid mida saab töödelda ka üksikute märkide kaupa.

Arvutüübid on üldotstarbelistes keeltes enamasti lihttüübid, kuigi põhimõtteliselt poleks võimatu ka arvude käsitlemine numbrijadadena --- samamoodi, nagu tekste vaadeldakse märgijadadena.

Lisaks keeles olemasolevatele standardsetele tüüpidele on programmeerijal enamasti võimalik defineerida ka uusi tüüpe konkreetse ülesande andmete mugavamaks esitamiseks. Kaks levinumat konstruktsiooni uute liittüüpide moodustamiseks on massiiv ja kirje.

Massiiv

Massiiv (ingl array) on nummerdatud elementide kogum. Nagu igal teisel muutujal, on ka massiivitüüpi muutujal üks nimi; massiivi elemendi poole pöördumiseks kasutatakse massiivi nime ja elemendi järjekorranumbrit ehk indeksit (ingl index). Paljudes programmikeeltes kehtib nõue, et ühe massiivi elemendid peavad kõik sama tüüpi olema.

Massiivid võivad olla ühe- või mitmemõõtmelised. Ühemõõtmelist massiivi võib kujutada jadana, mille igal elemendil on üks indeks --- elemendi järjekorranumber jadas. Kahemõõtmelist massiivi võib kujutada tabelina, mille igal elemendil on kaks indeksit --- rea- ja veerunumber. Kuigi praktikas seda eriti tihti vaja ei lähe, lubavad programmikeeled tavaliselt kasutada ka kolme- ja enamamõõtmelisi massiive.

Kirje

Kirje (ingl record) on mitmetüübiliste elementide kogum. Kirje elemente nimetatakse väljadeks (ingl field). Erinevalt massiivi elementidest on kirje väljadel tavaliselt nimed, mitte indeksid; kirje välja poole pöördumiseks kasutatakse koos muutuja ja välja nimesid.

Keerukamad tüübid

Paljud keeled lubavad liittüüpide moodustamise konstruktsioonide korduva kasutamisega kirjeldada kuitahes keerukaid tüüpe: võib defineerida kirje, mille üks väli on massiiv, mille elemendid on omakorda kirjed jne. Suurtes programmisüsteemides pole sugugi haruldased andmestruktuurid, kus sellisel moel on üksteise sees 4-5 kihti ``organisatsiooni'' enne kui tegelike andmeteni jõutakse.

Sellist hierarhilist moodustist on igati sobilik võrrelda alamkataloogide (kaustade) hierarhiaga arvuti kõvakettal --- põhimõtteliselt võiks ju kõiki faile ühes kataloogis koos hoida, aga siis oleks seal segamini kõikvõimalikke faile, millel omavahel mingit pistmist pole ja vajaliku info leidmine võib päris tülikas olla. Hoopis mõistlikum on failid teemade kaupa kataloogidesse jagada ja igale kataloogile asjakohane nimi panna. Liittüüpidel on programmi andmete korrastamisel täpselt samasugune funktsioon.

1.3.3  Avaldis

Valdava enamiku programmikeelte avaldised (ingl expression) on oma põhiomadustelt üsna sarnased matemaatikatunnist tuttavate aritmeetiliste avaldistega: avaldistes võib kasutada konstante ja muutujaid, tehtemärke ja funktsioonide tähiseid ning sulge tehete järjekorra märkimiseks.

Avaldise väärtustamiseks (ingl evaluation) --- selle avaldise väärtuse arvutamiseks --- asendatakse muutujate nimed selles avaldises nende muutujate väärtustega --- see tähendab, nende väärtustega, mis on parajasti salvestatud vastavatesse mälupesadesse --- sooritatakse vajalikud tehted ja lõpptulemust nimetatakse selle avaldise väärtuseks (ingl value).

Füüsikatunnist peaks olema hästi teada, et erinevat tüüpi suurusi (näiteks massi ja aega) ei saa omavahel kokku liita. Sarnased nõuded kehtivad ka programmeerimisel: selleks, et avaldises nõutud tehteid oleks võimalik sooritada, tuleb igat tehtemärki (operaatorit (ingl operator)) rakendada sobivatele väärtustele (operandidele (ingl operand)).

Translaator kontrollib programmis olevate avaldiste korrektsust andmetüüpide operatsioonivarude järgi --- iga väärtusega tohib sooritada ainult neid operatsioone, mis kuuluvad vastava tüübi operatsioonivarusse.

Ka iga operatsiooni tulemusel on oma tüüp, mida arvestatakse selle tulemuse kasutamisel järgmistes operatsioonides --- näiteks kahe täisarvu liitmisel on tulemuseks uus täisarv ja seda võib ka edaspidi kasutada ainult operatsioonides, mis kuuluvad täisarvutüübi operatsioonivarusse.

Erinevate keelte tüübisüsteemid on erinevad. Näiteks on mõnes keeles kahe täisarvu jagamisel tulemuseks uus täisarv (sellised keeled jagavad jäägiga), mõnes teises keeles aga reaalarv (sellised keeled jagavad täpselt5). Selleks, et kirjutada korrektseid programme, peab programmeerija tundma kasutatava keele tüübisüsteemi.

1.3.4  Omistamine

Imperatiivse keele kõige tähtsam primitiiv on omistamine (ingl assignment). Omistamiskäsk on tavaliselt kujul
muutuja¬avaldis
ning selle tähendus (semantika) on: arvutada antud avaldise väärtus ja salvestada tulemus antud muutuja väärtuse hoidmiseks kasutatavasse mälupessa. Selles mälupesas varem olnud andmed (muutuja esialgne väärtus) lähevad seejuures kaotsi.

Omistamiskäsu semantika juures on oluline, et avaldise väärtus arvutatakse välja enne muutuja esialgse väärtuse rikkumist. See võimaldab kasutada omistamiskäske kujul
muutuja¬muutuja+1.
Selline omistamiskäsk arvutab välja avaldise muutuja+1 väärtuse, kasutades selleks muutuja esialgset väärtust, ja alles pärast seda salvestab tulemuse muutuja mälupessa, suurendades sellega muutuja väärtust 1 võrra.

Omistamiskäsust (eriti selle viimatimainitud kujul) rääkides torkab silma, et muutuja osaleb omistamiskäsus kahes erinevas tähenduses --- avaldise väärtuse arvutamisel kasutatakse muutujat kui väärtust (oluline on tema mälupesa sisu, mitte selle asukoht), väärtuse salvestamisel aga kui kohta (oluline on tema mälupesa asukoht, mitte see, mida selles mälupesas parajasti hoitakse).

Muutuja esimeses tähenduses kasutamisel saadavat väärtust nimetatakse selle muutuja paremväärtuseks (ingl rvalue), sest selles tähenduses kasutatakse muutujat omistamismärgist paremal pool; tema teises tähenduses kasutamisel saadavat mälupesa aga vasakväärtuseks (ingl lvalue), sest selles tähenduses kasutatakse muutujat omistamismärgist vasakul pool.

Konstantidel ja avaldistel on üldiselt ainult paremväärtused --- avaldis 2+3 esitab väärtust 5, aga ei osuta mingit andmete salvestamiseks sobivat kohta arvuti mälus.

Muutujatel on tavaliselt olemas nii vasak- kui ka paremväärtus. Erandi moodustavad muutujad, millele pole veel midagi omistatud. Paljudes keeltes kasutatakse sellisel juhul muutuja paremväärtusena neid andmeid, mis muutuja hoidmiseks kasutatavas mälupesas parajasti on (enamasti on seal eelmiste programmide tööst mällu jäänud rämps, millega arvutamine mingit mõistlikku tulemust ei anna). Mõnes keeles loetakse, et sellisel muutujal paremväärtus puudub ja katse seda kasutada on viga. Mõnes keeles antakse igale muutujale kohe selle loomisel kindel algväärtus (arvulist tüüpi muutuja korral tavaliselt 0, muudel tüüpidel kindlat traditsiooni pole).

Neist kolmest variandist on levinuim esimene --- efektiivsuse tõttu. Paraku on see variant ka ohtlikem, sest väärtustamata muutujat kasutav programm hakkab küll tööle, aga võib igal käivitamisel erinevalt käituda --- vastavalt sellele, mis parasjagu mälus olema juhtub. Selliseid ebajärjekindlalt avalduvaid vigu on üldiselt üsna raske leida.

Üks võimalus algväärtustamata muutujatest tingitud vigade vältimiseks on igale muutujale kohe selle loomisel mingi väärtus omistada. Isegi kui see väärtus pole programmi järgneva loogika seisukohalt sobiv, on programmi käitumine vähemalt järjekindel ja vea leidmine seetõttu märksa lihtsam.

1.4  Pseudokeel

Edasises vaatleme algoritmide kirjeldusi poolformaalses pseudokeeles. Iga algoritmi kirjeldus koosneb pealkirjast, eel- ja järeltingimusest, kasutatavate abimuutujate kirjeldusest ning algoritmi sammude loendist.

Paljud algoritmid on lisaks sellele näha ka viies erinevas keeles programmidena õppematerjali lisades. Nende näiteprogrammide eesmärk on illustreerida tekstis kirjeldatud põhimõtete praktilist realiseerimist erinevates keeltes.

Algoritmi kirjelduses näitab eeltingimus tavaliselt seda, millistes muutujates ja millisel kujul peavad olema esitatud algandmed selle algoritmi tööks, ja järeltingimus seda, millistes muutujates ja millisel kujul on algoritmi töö lõppedes vastus.

Algoritmi sammudena kasutame järgmisi primitiive: Juhtkonstruktsioone (peale järjendi) meil esialgu ei ole. Nendega tutvume järgmistes peatükkides.

1.4.1  Näited

Lihtne tervitus

Esimene näide väljastab kasutajale tervituse.

Sellise programmiga on hea kontrollida programmeerimissüsteemi korrasolekut --- kui isegi nii lihtsa programmi täitmine ei õnnestu, on arvatavasti töövahendid rikkis; keerulisema programmi korral võib ebaõnnestumise põhjuseks olla viga programmis. Siiski võimaldab see programm teha läbi programmi koostamise tsükli: teksti sisestamine, transleerimine, käivitamine.

Algoritm 1   Lihtne tervitus
  1. väljasta `Tere, kasutaja'

Interaktiivne tervitus

Õige natuke keerulisem näide, mis kasutab ka üht abimuutujat.

Algoritm 2   Interaktiivne tervitus
Abimuutujad: nimi --- kasutaja nimi, tekst
  1. väljasta `Teie nimi: '
  2. sisesta nimi
  3. väljasta `Tere, ', nimi

Tasub tähele panna, et viimases väljastamiskäsus on esimene koma väljastatava teksti osa, teine aga kahe käsus esineva avaldise (tekstikonstandi ja muutuja) eraldaja. Samalaadsetele detailidele tuleb tähelepanu pöörata ka reaalsetes programmikeeltes.

Vahetus

Kahe antud muutuja (a ja b) väärtuste vahetamine.

Algoritm 3   Vahetab kahe muutuja väärtused
Sisend: a, b --- vahetatavad väärtused, mõlemad sama tüüpi
Väljund: a, b --- väärtused vahetatud
Abimuutujad: c, sama tüüpi kui a ja b
  1. c¬a
  2. a¬b
  3. b¬c

Selle algoritmi näitel saame illustreerida ka vahetingimuste kasutamist algoritmi õigsuses veendumiseks.

Vastavalt algoritmi kirjelduses olevale eeltingimusele peavad vahetatavad väärtused olema muutujates a ja b. Tähistame neid väärtusi vastavalt a0 ja b0. Kui lisaks tähistame puuduva väärtuse sümboliga ^, on algoritmi eeltingimus
a = a0, b = b0, c = ^.
Esimene samm omistab muutujale c muutuja a esialge väärtuse, seega pärast esimese sammu täitmist peab kehtima vahetingimus
a = a0, b = b0, c = a0.
Analoogiliselt peab pärast teist omistamist kehtima
a = b0, b = b0, c = a0
ja pärast kolmandat
a = b0, b = a0, c = a0,
mis, nagu näha, sisaldab endas ka programmi järeltingimust. Lisaks lubatud vahetusele on muutunud ka c väärtus, aga kuna c oli algusest peale kuulutatud abimuutujaks, on selle väärtuse rikkumine lubatud. Seega võime järeldada, et meie algoritm on korrektne.

Edaspidises lisame algoritmi olulisemad vahetingimused sageli kommentaaridena otse algoritmi sammude vahele.

Algoritm 3   Vahetab kahe muutuja väärtused
Sisend: a, b --- vahetatavad väärtused, mõlemad sama tüüpi
Väljund: a, b --- väärtused vahetatud
Abimuutujad: c, sama tüüpi kui a ja b
  1. --- vahetingimus: a = a0, b = b0, c = ^
  2. c¬a
  3. --- vahetingimus: a = a0, b = b0, c = a0
  4. a¬b
  5. --- vahetingimus: a = b0, b = b0, c = a0
  6. b¬c
  7. --- vahetingimus: a = b0, b = a0, c = a0

Õigete vahetingimuste leidmine on sageli lihtsam programmi või algoritmi tekstis tagantpoolt ettepoole liikudes.

Vaatleme näiteks ruutvõrrandi lahendamise algoritmi 4, mis kasutab üldtuntud valemit
x1, x2 =
-b ± sqrt(b2 - 4ac)
2a
.
Muidugi on sama üldtuntud ka ruutvõrrandi lahendivalemi rakendamise eeltingimused, aga oletame hetkeks, et me neid ei tea. Sellisel juhul saame algoritmi täitmiseks vajalikud eeltingimused kõige lihtsamalt leida just tagantpoolt ettepoole liikudes.

Algoritm 4   Lahendab ruutvõrrandi
Sisend: a, b, c --- võrrandi ax2 + bx + c = 0 kordajad
Väljund: x1, x2 --- võrrandi lahend
Abimuutujad: d --- abimuutuja
  1. d¬b2 - 4ac
  2. x1¬(-b - sqrt(d)) / (2a)
  3. x2¬(-b + sqrt(d)) / (2a)

Omistamiskäsu x2¬... täitmiseks peab olema võimalik arvutada selle paremal poolel oleva avaldise väärtus. Selleks omakorda on vaja, et murrujoone all ei oleks null (2a ¹ 0, ehk a ¹ 0) ja juuremärgi all ei oleks negatiivne arv (d ³ 0). Samad tingimused peavad kehtima ka omistamise x1¬... eel.

Selleks, et omistamise d¬... järel kehtiks järgmiste omistamiste jaoks vajalik tingimus (d ³ 0), ei tohi muutujale d omistatava avaldise väärtus olla negatiivne (b2 - 4ac ³ 0, ehk b2 ³ 4ac).

Lisades need tingimused algoritmi kirjeldusse, saamegi tulemuse, mille õigsust on võimalik rangelt tõestada.

Algoritm 4   Lahendab ruutvõrrandi
Sisend: a, b, c --- võrrandi ax2 + bx + c = 0 kordajad, a ¹ 0, b2 ³ 4ac
Väljund: x1, x2 --- võrrandi lahend
Abimuutujad: d --- abimuutuja
  1. --- vahetingimus: a ¹ 0, b2 ³ 4ac
  2. d¬b2 - 4ac
  3. --- vahetingimus: a ¹ 0, d ³ 0
  4. x1¬(-b - sqrt(d)) / (2a)
  5. x2¬(-b + sqrt(d)) / (2a)

Muidugi ei maksa eelnevast järeldada, et vahetingimuste hoolikas jälgimine on vajalik ainult matemaatiliste algoritmide õigsuses veendumiseks. Peaaegu kõigil primitiividel on mingid eeltingimused, mille rikkumise tagajärjeks on kas programmi töö katkemine veateatega või lihtsalt ebaõiged tulemused. Ja programmi autori mainele ei tule kasuks kumbki variant.

Ülesanded


Ülesanne 1   Leida igapäevasest elust vähemalt kaks erinevat algoritmi. Tuua välja nende sammud ning eel- ja järeltingimused. Sõnastada ka mõni vahetingimus.

Ülesanne 2   Uurida oma programmeerimissüsteemi andmetüüpe. Kontrolltööks loetleda kasutatava programmeerimissüsteemi täisarvutüübid ja nende väärtusvarud. Miks pole väärtusvarude otspunktid ``ümmargused'' arvud?

Ülesanne 3   Kirjutada algoritm ja (vabalt valitud keeles) programm, mille täitmise käigus omistatakse muutujale s kolme muutuja x, y ja z väärtuste summa ning muutujale k nende väärtuste aritmeetiline keskmine. Millised peaks olema s ja k tüübid, kui x, y ja z on täisarvud? Miks?

Ülesanne 4   Kirjutada programm, mis sisestab täisnurkse kolmnurga kaatetite pikkused ning väljastab selle kolmnurga hüpotenuusi pikkuse ja pindala. Millised on hüpotenuusi pikkuse ja pindala tüübid, kui kaatetite pikkused on reaalarvud? Aga kui kaatetite pikkused on täisarvud? Miks?

Ülesanne 5   Kirjutada programm, mis deklareerib kahe täisarvulise väljaga kirjetüübi ja neist kirjetest koosneva kolmeelemendilise massiivi, omistab selle massiivi kõigi kolme kirje mõlemale väljale mingid fikseeritud väärtused ning väljastab iga kirje sisu eraldi reale.


Kirjandus

Programmeerimise õppimiseks ei pea muidugi läbi lugema kõiki järgnevaid raamatuid, aga kindlasti soovitan tutvuda Pólya' ülesannete lahendamise metoodikaga ja lugeda vähemalt ühte ülejäänud raamatutest --- neis on arvutite ehituse ja tööpõhimõtete kohta palju huvitavat materjali, mille tundmine tuleb kasuks nii järgnevate peatükkide omandamisel kui ka üldisemalt.



György (George) Pólya. Kuidas seda lahendada. Valgus, 2001.
Maailmakuulsa matemaatiku raamat kirjeldab üldisi ülesannete lahendamise tehnikaid, mis sobivad suurepäraselt ka algoritmide ja programmide koostamiseks. 200 lk.


Rein Jürgenson. Programmeerimine. Valgus, 1989.
Programmeerimise algõpetus Basicu, Pascali ja Fortrani näitel. 376 lk.


Ülo Kaasik, Jüri Kiho, Mare Koit. Kuidas programmeerida. Valgus, 1990.
Programmeerimise algõpetus Basicu ja E-skeemide näitel. 264 lk.


Jüri Kiho. Elementaaralgoritmid. Tartu Ülikool, 1991.
Programmeerimise algõpetus E-skeemide näitel. 144 lk.


Rein Jürgenson. Programmeerimise algkursus. Tallinna Tehnikaülikool, 1999.
Programmeerimise algõpetus Pascali näitel. 88 lk.


J. Glenn Brookshear. Computer Science: An Overview. Addison-Wesley, 1999.
Varasemate trükkidega klassikaks saanud programmeerimise ja arvutiteaduse algõpetuse õpik. 609 lk.


Дж. Гленн Брукшир. Введение в компьютерные науки. Вильямс, 2001.
Eelmise tõlge. 688 lk.


1
Arthur Bloch. Murphy seaduste täielik kogu. Ersen, 1999.
2
http://www-cs-faculty.stanford.edu/~knuth/taocp.html
3
http://www-cs-faculty.stanford.edu/~knuth/mmix.html
4
Tegelikult on asi veidi keerulisem, aga täpsemaks selgituseks pole siinkohal ruumi.
5
Õigem oleks öelda, et jagavad täpsemalt, sest tegelikult on reaalarvud arvutis ligikaudsed suurused. Arvutustäpsusest tuleb veidi lähemalt juttu edaspidi.
Previous Up Next