Algoritmai1
5 (100%) 1 vote

Algoritmai1

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, 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.

Šiuo metu Jūs matote 52% šio straipsnio.
Matomi 586 žodžiai iš 1135 žodžių.
Peržiūrėkite iki 100 straipsnių per 24 val. Pasirinkite apmokėjimo būdą:
El. bankininkyste - 1,45 Eur.
Įveskite savo el. paštą (juo išsiųsime atrakinimo kodą) ir spauskite Tęsti.
SMS žinute - 2,90 Eur.
Siųskite sms numeriu 1337 su tekstu INFO MEDIA ir įveskite gautą atrakinimo kodą.
Turite atrakinimo kodą?
Po mokėjimo iškart gausite atrakinimo kodą, kurį įveskite į laukelį žemiau:
Kodas suteikia galimybę atrakinti iki 100 straispnių svetainėje ir galioja 24 val.