Ieškoti
:
:
Pamiršote slaptažodį?  Prisijungti>>
(Darbą įkėlė Svečias)

Aprašymas:



Darbas:

Algoritmai
Algoritmas - 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)L
t.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,


[1]  2  3  Toliau







Darnipora.lt