82 algoritmai

Informatikos testai
Testas
 5
Microsoft Word 102 KB
13 puslapiai

Algoritmavimo testas. Algoritmavimo testas.

82.Algoritmai

Algoritmai – efektyvios procedūros (EP), aprašančios veiksmų seką ir vienareikšmiškai duodančios tam tikrą rezultatą.
Mokykliniai daugybos “stulpeliu” ir dalybos “kampu” metodai, sudėtingos funkcijos diferencijavimo taisyklės ir t.t. – algoritmai.
Pagrindiniai reikalavimai
1.Algoritmas naudojamas su pradiniais duomenimis ir duoda rezultatus. Be to, algoritmo vykdymo metu pasirodo tarpiniai rezultatai.
Taigi, algoritmas operuoja su objektais -duomenimis – pradiniais, tarpiniais ir galutiniais
Algoritmų teorijoje nenaudojamas žodinis objektų apibrėžimas, vietoje to fiksuojami:

• konkretūs baigtiniai pradinių objektų rinkiniai ,

• baigtinis kitų objektų sudarymo būdų iš elementariųjų objektų rinkinys.
Elementariųjų objektų rinkinys sudaro
baigtinį pradinių simbolių alfabetą.
Tipinis kitų objektų sudarymo būdas – indukcija.
Paprasčiausias indukcinis apibrėžimas – klasikinis identifikatoriaus apibrėžimas, naudotas jau ALGOLe: identifikatorius yra raidė arba identifikatorius, kuriam iš dešinės pridėta raidė arba skaičius.

::=

::= ½

::= 0½1½2½3½4½5 ½6 ½7 ½8 ½9

2.Duomenys talpinami atmintyje.
3.Algoritmas susideda iš elementarių žingsnių arba veiksmų, skirtingų žingsnių aibė baigtinė.
4.Algoritmo žingsnių seka determinuota.
5.Natūralu iš algoritmo reikalauti rezultatyvumo.

Reikia skirti:

• algoritmo aprašą (instrukcijas/programą),

• algoritmo realizacijos mechanizmą (kompiuterį),

• algoritmo vykdymo procesą (veiksmų seką, gaunamą pritaikant algoritmą konkretiems duomenims).

3.Algoritmų modeliai
Algoritmų teorijoje:
• parenkamas baigtinis pradinių objektų rinkinys, tie objektai laikomi elementariais,
• parenkamas baigtinis naujų objektų sudarymo būdų rinkinys.
Algoritminiai modeliai, pretenduojantys į sąvokos “algoritmas” formalizavimą, turi būti universalūs.
Universalumas:
• įrodoma, kad vieną modelį galima pakeisti kitu,
• sukurta invariantiška modelių atžvilgiu sąvokų sistema, įgalinanti aptarti algoritmų savybes nepriklausomai nuo parinktos formalizacijos.
Yra trys pagrindiniai universalių algoritminių modelių tipai:
• rekursyviosios funkcijos – istoriškai pirmoji algoritmo sąvokos formalizacija,
• algoritmo vaizdavimas determinuotu įtaisu, gebančiu atlikti labai primityvias operacijas,
• bet kokių alfabetų žodžių perdirbimas; Posto sistemos, normaliniai Markovo algoritmai.
4.Tiuringo tezė
• Viskas, kas gali būti padaryta...