Algoritmai1

Konspektas
 5
Microsoft Word 39 KB
2 puslapiai

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