Algoritmai

AlgoritmaiAlgoritmas – tai baigtinė seka pažingsninių tikslių instrukcijų, skirtų atlikti tam tikrą darbą.Formaliai algoritmas turi patenkinti 3 sąlygas:1) jis turi atlikti darbą;2) jis turi būti aiškus ir nedviprasmiškas;3) jis turi apibrėžti žingsnių seką, reikalingą darbui atlikti, t.y. jis turi nurodyti žingsnių atlikimo tvarką.Informatikoje dažnai dar reikalaujama, kad algoritmas būtų baigtinis dviem prasmėm:4) atliekamų žingsnių skaičius turi būti baigtinis, t.y. algoritmas turi tikrai baigti darbą;5) kiekvienam žingsniui atlikti turi pakakti baigtinio laiko ir baigtinių resursų, t.y. kiekvienas žingsnis turi būti toks, kad jį būtų galima atlikti.Reikalavimai 4-5 garantuoja, kad algoritmas bus baigtas baigtiniu laiku ir su baigtiniais resursais. Algoritmai, tenkinantys tik sąlygas 1-3, vadinami daliniais (angl. partial) algoritmais, o tenkinantys visas penkias sąlygas – pilnais (angl. total) algoritmais.

Nuo algoritmo yra neatsiejama jo vykdytojo sąvoka. Vienam vykdytojui algoritmas gali būti aiškus ir nedviprasmiškas, o kitam – visai nesuprantamas. Nuo vykdytojo tiesiogiai priklauso, kokius primityvus galima naudoti, apibrėžiant veiksmus. Pavyzdžiui, vienam vykdytojui veiksmas – paskaičiuoti Furje transformaciją – yra elementarus (t.y. jo nereikia skaidyti), kitam jį reikia išreikšti paprastesniais veiksmais.

Algoritmų pavyzdžiai.Euklido algoritmas sveikų teigiamų skaičių A ir B bendram didžiausiam dalikliui (BDD) rasti:1. Rasti A dalybos iš B liekaną.2. Pakeisti A – B.3. Pakeisti B liekana, rasta 1 žingsnyje.4. Kartoti žingsnius 1-3, kol B bus 0.5. BDD bus A reikšmė.Patikrinkime, ar pateiktas pavyzdys tenkina anksčiau suformuluotus reikalavimus, t.y. ar tai iš tikrųjų algoritmas.Pirmojo reikalavimo – algoritmas turi atlikti darbą – patikrinimui reikia įrodyti, kad atliekant nurodytus veiksmus bet kokiai sveikų teigiamų skaičių A ir B porai tikrai bus rastas jų bendras didžiausias daliklis. Būtina pastebėti, kad norint parodyti, jog šis reikalavimas netenkinamas, pakanka surasti vieną skaičių porą, kuriai BDD bus nerastas.

Įrodymas, kad pagal Euklido algoritmą randamas BDD:Jei A dalijasi iš L, tai galima užrašyti A=nL, kur n – kažkoks sveikas skaičius. Analogiškai jei B dalijasi iš L, tai B=mL, kur m – kažkoks sveikas skaičius. Taigi jei A ir B dalijasi iš L, tai A mod B = A – kB = nL – kmL = (n – km)Lt.y. A dalybos iš B liekana irgi dalijasi iš L.Tai reiškia Euklido algoritmo 1-ame žingsnyje atliekamas veiksmas nekeičia BDD reikšmės: BDD(A, B) = BDD(A’, B’) = … = BDD(L, 0) = L.Kitų reikalavimų tenkinimas yra pakankamai akivaizdus:– žingsniai aiškūs ir nedviprasmiški: matyt, visiems aišku kaip paskaičiuoti dalybos liekaną, pakeisti reikšmes ir patikrinti, ar ji lygi nuliui;– nurodyta žingsnių tvarka: atliekami žingsniai 1, 2, 3, tikrinama sąlyga (4) ir pagal ją grįžtama prie 1-o žingsnio arba pereinama prie 5-o;– žingsnių skaičius baigtinis: A dalybos iš B liekana L yra sveikas neneigiamas skaičius, mažesnis už A, todėl turime sveikų neneigiamų skaičių Li seką A> L1 > L2 >…, kadangi A baigtinis skaičius, tai po baigtinio žingsnių skaičiaus L taps 0;– žingsniai elementarūs, todėl aišku, kad kiekvienam iš jų pakaks baigtinio laiko ir resursų.

Teigiamo skaičiaus N kvadratinės šaknies radimo algoritmas:1. Paimti bet kokią pradinę kvadratinės šaknies reikšmę r>0.2. Pakeisti r reikšme [r+(N / r)] / 2.3. Kartoti žingsnį 2 tol, kol r daug nebesikeis.Tam, kad tai būtų algoritmas, reikėtų tiksliau apibrėžti, ką reiškia “r daug nebesikeis”, pavyzdžiui, senos ir naujos r reikšmių skirtumo modulis bus mažesnis už 0.0001.

Algoritmai gali būti ir nesusiję su kažkokiais skaičiavimais, pavyzdžiui, kiaušinio virimo ar skambinimo telefonu algoritmai.

Norint išspręsti kažkokį uždavinį, pirmiausia reikia sugalvoti jo sprendimo būdą, t.y. algoritmą. Po to jį reikia išreikšti operacijomis, kurias gali atlikti vykdytojas, ir užrašyti vykdytojui priimtina forma. Jei vykdytojas žmogus, algoritmą galima pateikti labai įvairiai:

– natūralia kalba, kaip buvo pateiktuose pavyzdžiuose;– diagramomis

Pav. 1 Euklido algoritmas– bet kokia kita žmogui priimtina forma.

Jei vykdytojas ne žmogus, algoritmą reikia pateikti specifine, tam vykdytojui priimtina forma, pavyzdžiui, specialia algoritmine kalba. Jei mes turime algoritmą, išreikštą vykdytojo operacijomis, tai jį užrašyti ar perrašyti vienokia ar kitokia kalba nėra sudėtinga.

Informatikoje kaip vykdytojas dažniausiai suprantamas kompiuteris. Pagrindinės idėjos:• kompiuteriai apdoroja duomenis, išreikštus simboliais;• jie kontroliuojami instrukcijomis, kurios ir sudaro algoritmą;• instrukcijos irgi pateikiamos mašinai kaip simbolių seka.Taigi viskas, ko reikia algoritmų pateikimui kompiuteriui, tai kalba patogiam instrukcijų užrašymui.

Programa – tai algoritmo išraiška tikslia kalba, suprantama kompiuteriui, t.y. programavimo kalba.Pats kompiuteris moka atlikti tik labai elementarias operacijas, pavyzdžiui, sudėti du skaičius. Bet kadangi tiek programa, tiek duomenys jai kompiuteriui pateikiami kažkokiais simboliais, tai natūralu, kad viena programa gali būti duomenimis kitai programai. Todėl nebūtina algoritmus išreikšti elementariausiomis operacijomis, kurias tiesiog gali įvykdyti kompiuteris. Galima kurti aukštesnio lygio (tolimesnes kompiuteriams ir artimesnes žmonėms) programavimo kalbas ir programas transliatorius, kurios tą kalbą išverstų į kompiuteriui suprantamas instrukcijas. Yra sukurta daug ir įvairių programavimo kalbų. Pažiūrėkime, kaip Euklido algoritmas gali būti užrašytas programavimo kalbomis Pascal ir C.Euklido algoritmas (Pascal): repeat liekana := A mod B; { 1. } A := B; { 2. } B := liekana; { 3. } until B = 0; { 4. } writeln(A) { 5. }Euklido algoritmas (C): do { liekana = A % B; /* 1. */ A = B; /* 2. */ B = liekana; /* 3. */ } while (B != 0); /* 4. */ printf(“%d n”, A); /* 5. */

Tai programų fragmentai, realizuojantys patį Euklido algoritmą, bet tam, kad juos būtų galima pateikti kompiuteriui vykdyti, reikia dar:– nurodyti, kaip gaunami pradiniai duomenys (skaičiai A ir B);– apipavidalinti programą pagal konkrečios programavimo kalbos reikalavimus.

Programa realizuojanti Euklido algoritmą (Pascal):program Euklido;

var A, B, liekana : integer;begin writeln(‘Iveskite 2 sveikus teigiamus skaicius:’); readln(A, B); if (A <= 0) or (B <= 0) then writeln(‘Pirmas skaicius nera teigiamas!’) else begin write(‘BDD(‘, A, ‘,’, B, ‘)=’); repeat liekana := A mod B; { 1. } A := B; { 2. } B := liekana; { 3. } until B = 0; { 4. } writeln(A) { 5. } endend.

Programa realizuojanti Euklido algoritmą (C):#include int main(){ int A, B, liekana; printf(“Iveskite 2 sveikus teigiamus skaicius: n” ); scanf(“%d %d”, &A, &B); if ((A <= 0) || (B <= 0)) printf(“Pirmas skaicius nera teigiamas! n” ); else { printf(“BDD(%d,%d)=”, A, B ); do { liekana = A % B; // 1. A = B; // 2. B = liekana; // 3. } while (B != 0); // 4. printf(“%d n”, A); }}

Programa realizuojanti Euklido algoritmą (C++):#include int main(){ int A, B, liekana; cout << “Iveskite 2 sveikus teigiamus skaicius: ” << endl; cin >> A >> B; if ((A <= 0) || (B <= 0)) cout << “Pirmas skaicius nera teigiamas! ” << endl; else { cout << “BDD(” << A << “,” << B << “)=”; do { liekana = A % B; // 1. A = B; // 2. B = liekana; // 3. } while (B != 0); // 4. cout << A << endl; }}