Algoritmi

Algoritma jēdziens. Algoritmu pieraksta veidi.
Algoritmu izpildītajs

Parasta dzīvē par algoritmu uzskata instrukciju, sekojot kurai var sasniegt mērķi. Algoritms norada, kas un ka jadara, lai atrisinatu doto uzdevumu. Šadu nestingru 'sadzīves' algoritmu piemēri - kulinarijas receptes, sadzīves tehnikas lietošanas instrukcijas, spēļu noteikumi utt. Sadzīves algoritmi paredzēti cilvēkiem, kuriem ir gan pieredze, gan intuīcija, tapēc autori nedoma par formulējumu īpašu stingrību un precizitati. Būtu interesanti redzēt, ka robots saprastu tadas instrukcijas ka 'pievienot sals pēc garšas' vai 'varīt līdz gatavībai'.

Informatika nepieciešamas stingrakas algoritma definīcijas (un dažadiem nolūkiem - dažadas).

Skolas kursa parasti lieto šadu definīciju kopa ar paskaidrojumiem - algoritma īpašībam, kuras precizē algoritma jēdzienu.

Algoritms - ir darbību secības precīzs apraksts, kas nodrošina mērķa sasniegšanu.

Algoritmam japiemīt šadam īpašībam:

- viennozīmīgums (formulējums nepieļauj dažadas interpretacijas un parpratumus);

- formalitate (dažadi izpildītaji saprot un izpilda algoritmu vienadi; rezultats ir neatkarīgs no izpildītaja);

- noteiktība (katra momenta ir skaidrs, kada darbība jaizpilda un kas jadara nakošaja solī);

- diskrētība (algoritms sastav no atsevišķam elementaram pabeigtam darbībam);

- visparīgums (algoritms ir paredzēts nevis vienam atsevišķam uzdevumam, bet gan veselai radniecīgu uzdevumu klasei, piemēram, kvadratvienadojuma risinašanas algoritmam ir jabūt tadam, lai ar to palīdzību varētu atrisinat jebkuru kvadratvienadojumu).

- galīgums un efektivitate (algoritms nodrošina mērķa sasniegšanu galīga soļu skaita).

Skolas kursa sniegta algoritma definīcija nav pietiekami strikta un formala zinatniskiem mērķiem. Par algoritma jēdziena precizēšanu matematiķi saka domat jau 17.gadsimta (kad Leibnics mēģinaja izdomat visparīgu algoritmu jebkura matematikas uzdevuma risinašanai). 19.gadsimta beigas vairaki matematiķi nodarbojas ar visparīga algoritma meklēšanu, kas nodrošinatu jebkuras teorēmas parbaudi dotaja aksiomu sistēma. Šadi algoritmi netika atrasti. Tad matematiski saka meklēt pieradījumus, ka šada veida visparīgi uzdevumi ir algoritmiski neatrisinami (tas izdevas), un līdzi ar to precizēt algoritma jēdzienu. Skaidrs, ka algoritmam ir jabūt tadam, lai to izpildīt varētu ne tikai cilvēks (kuram ir noteiktas zinašanas, pieredze un intuīcija), bet pat automats. Atlika tikai sameklēt piemērotu automatu.

1930. gados paradījas vairaki darbi, veltīti šai problēmai. Matematiķi izdomaja vienkaršus automatus (shēmas) ar ļoti pieticīgu komandu sistēmu, kura ir pietiekama algoritmisko uzdevumu risinašanai (piemēram, Posta mašīna, Tjuringa mašīna, Markova algoritmiskas shēmas). Matematisko pētījumu rezultata paradījas vēl viena algoritma definīcija: algoritms ir darbību secība, kas nodrošina mērķa sasniegšanu galīga soļu skaita, un kuru var izpildīt Posta mašīna (vai cits analogs automats).

Jebkurš algoritms ir paredzēts konkrētam izpildītajam: cilvēkam, robotam, dzīvniekam, automatam, datoram utt. - un ir attēlots izpildītajam saprotama forma. Katram izpildītajam ir sava komandu sistēma – komandu komplekts, kuras viņš saprot un prot izpildīt. Lai iepazītu izpildītaju, janoskaidro:

• kados apstakļos viņš var stradat un ko var darīt;
• kada ir izpildītaja komandu sistēma, un kada forma viņš uztver komandas;
• ka izpildītajs izpilda komandas; kados gadījumos var rasties situacija, kad viņš nevar izpildīt komandu. 

Aplūkosim piemēru. Uz lauciņa 10x10 (apstakli) atrodas bruņurupucis (izpildītajs), kas var parvietoties pa lauciņa rūtiņam un zīmēt vai nezīmēt līniju - savas pēdas. Bruņurupuča komandu sistēma:

Situacija 'nevaru' rodas, ja:

• janolaiž jau nolaisto zīmuli vai japaceļ jau pacelto;
• jaiet aiz lauciņa robežam.

Pieņemsim, ka sakuma bruņurupucis atrodas lauciņa 11x11 centra, zīmulis ir pacelts. Sastadīsim viņam algoritmu kvadrata 3x3 zīmēšanai.

1. nolaist zīmuli; 2. paiet 3 soļus uz priekšu;

3. paiet 3 soļus pa kreisi;  4. paiet 3 soļus atpakaļ;

5. paiet 3 soļus pa labi;  6. pacelt zīmuli;

7. beigas.

Lūk, te ir tada algoritma piemērs, kuru bruņurupucis nevar izpildīt:

1. paiet 33 soļus uz priekšu; 2. beigas.

Algoritma pieraksta veidi:

- notacija (instrukcija, kura tiek izmantoti parasti vardi),

- blokshēma (uzskatams grafiskais attēlojums),

- programma (ta var būt uzrakstīta visparīga algoritmiska valoda vai konkrēta programmēšanas valoda).

Piemērs: algoritms kvadratvienadojuma ax²+bx+c=0 risinašanai.

Jēdziens par struktūrprogrammēšanu. Algoritmu tipi
(linearas darbību secības, sazarošanas, cikli)

Blakus skaitļošanas tehnikas pilnveidošanai noris arī programmēšanas valodu attīstība; programmēšana paradas jaunas koncepcijas, kuras atvieglo lielu projektu izstradašanu un modificēšanu. Viena no šadam koncepcijam - struktūrprogrammēšana - ir daudzu trešas paaudzes programmēšanas valodu (tai skaita Pascal) pamata.

Lielu programmu veidošanas procesa programmētajus gaida šadas problēmas:

• to, ko viegli izdarīt 1-2 reizes, gandrīz nav iespējams atkartot 1000 reizes bez kļūdam;
• garu programmas tekstu ļoti grūti lasīt (un vēl grūtak atcerēties);
• lielu programmu grūti modificēt;
• pilna programmas testēšana nav iespējama (ja vairakam sakumvērtībam programma izvadīja pareizu rezultatu, tas vēl nenozīmē, ka ta pareizi apstradas arī visus citus datus. Programmas testēšana var pieradīt, ka taja ir kļūdas, bet nekada gadījuma nevar pieradiet to, ka kļūdu nav).

Lai lielu programmu veidošana un modificēšana nebūtu parak mokošs process, jaievēro noteikti noteikumi (piemēram, mainīgajiem japiešķir tadi nosaukumi, kas atspoguļo to jēgu).

Struktūrprogrammēšanas koncepcija izvirza šadas prasības programmas tekstam:

• Skaidra strukturēšana, kas palīdz uztvert programmas loģiku. Programma tiek būvēta no fragmentiem, katrs fragments atbilst vienai no trim algoritmu pamat­konstrukcijam: (linearas darbību secība, sazarošanas vai cikls). Nedrīkst izmantot parejas, kuras traucē programmas saprašanu (piemēram, nedrīkst pariet no viena cikla vidus otra cikla vidū);
• Vairak vai mazak neatkarīgi programmas fragmenti tiek noformēti ka atsevišķas apakšprogrammas (funkcijas vai procedūras); lielas programmas teksts var būt sadalīts vairakos failos (moduļos);
• Pēc iespējas, programma jaraksta visparīga veida (izmantojot konstantes, apakšprogrammas ar parametriem utt.) - tas atvieglos programmas modificēšanu (piemēram, mainīt konstantes vērtību viena vieta ir vieglak, neka meklēt šo vērtību visur, kur ta sastopama).
• Planojot lielas programmas izstradašanu, nedrīkst steigties: pirmkart japardoma programmas struktūra, jaizvēlas piemērots algoritms. Darba gaita pastavīgi japrecizē uzdevuma nostadne. Bieži gadas, ka tehniska uzdevuma izstradašana prasa vairak laika, neka pati programmēšana.

Nedrīkst arī aizmirst, ka tehnika un programmatūra ļoti atri mainas, tapēc bieži nav vērts tērēt veselus gadus ideala algoritma meklēšanai un pilnīgas programmas veidošanai, kura pēc dažiem gadiem bezcerīgi novecos (ja tikai algoritmam nav zinatniskas vērtības). Programmētaja uzdevums - izvēlēties tadu vienkaršu atrisinajumu, kuru vēlak nenaksies apžēlot.

Algoritmu pamatkonstrukcijas

Lineara darbību secība Sazarošanas:

darbības (operatori) vienkarši tiek izpildīta viena vai otra darbība

seko cita citai atkarīgi no kada nosacījuma

						varianti

Cikli: programmas fragments tiek atkartots vairakas reizes

а) iteraciju cikls: b) cikls ar priekšnosacījumu: с) cikls ar pēcnosacījumu:

Uzdevumu piemēri, kurus var atrisinat, izmantojot dažadas algoritmu konstrukcijas:

Lineara darbību secība: zinot taisnstūra malas, aprēķinat ta laukumu.

Sazarošanas: zinot х, aprēķinat y pēc formulas:

Cikls: izvadīt argumenta un funkcijas y=x³ vērtību tabulu intervala [1;20] ar soli 1.