Experiența bogată în dezvoltarea și aplicarea algoritmilor sugerează o serie de proprietăți comune care sunt inerente în orice algoritm, inclusiv algoritmii enumerați mai sus.
Discretența algoritmului: orice algoritm poate fi considerat un proces de construire secvențială a cantităților, care se desfășoară în timp discret, în conformitate cu o anumită rețetă, numită program.
Masivitatea algoritmului: algoritmul serveste pentru a rezolva nu o singura sarcina, ci o intreaga clasa de sarcini similare. În acest aspect, tabela de multiplicare nu este un algoritm, dar multiplicarea printr-o coloană de numere multivate este un algoritm. De exemplu, în algoritmul lui Euclid, numerele a și b sunt selectate dintr-un set infinit (numărător) de întregi.
Determinismul algoritmului: după finalizarea etapei următoare, este determinată în mod unic ce să facem în continuare.
Pașii elementari ai algoritmului: soluția problemei este împărțită în etape, fiecare dintre acestea trebuie să fie simplă și locală. Aceasta înseamnă că operația corespunzătoare ar trebui să fie elementară pentru executorul algoritmului (om sau mașină). De exemplu, operațiile de comparare, scădere și permutare a numerelor care apar în algoritmul lui Euclid sunt destul de standard și familiare. În același timp, algoritmul euclidian poate să apară ca o operație elementară a unui algoritm mai complex.
Eficacitatea algoritmului: algoritmul într-un număr finit de pași trebuie să ducă la o oprire, ceea ce indică atingerea rezultatului dorit. Deci, atunci când căutați o cale într-un labirint, o oprire apare fie pe un site accesibil, fie când vă întoarceți la site-ul original, dacă obiectivul specificat nu este posibil. În special, oricine prezintă un algoritm pentru rezolvarea unei probleme trebuie să demonstreze că algoritmul se oprește după un număr finit de pași (așa cum se spune, converge) pentru orice x al domeniului de activitate. Cu toate acestea, pentru a verifica eficacitatea (convergența algoritmului) este mult mai dificilă decât alte proprietăți.
Metode de specificare a algoritmilor
Algoritmul poate fi specificat în următoarea formă:
în formă verbală (verbală);
sub formă de LHSA (schema logică grafică a algoritmului) - în formă grafică sub forma unei diagrame bloc;
sub forma structurogramei lui Nassi-Schneiderman;
sub forma unui program de calculator.
O diagramă grafică reprezintă o reprezentare grafică a unui algoritm. Când este construit, conținutul fiecărei etape a algoritmului este scris într-o formă arbitrară în interiorul blocului reprezentat de figura geometrică. Ordinea treptelor este indicată de săgețile care leagă blocurile. Utilizarea diferitelor forme geometrice reflectă natura diferită a acțiunilor efectuate. Dimensiunile formelor și aspectul acestora sunt reglementate de GOST 19.003-80 sau ISO1028-73.
În dreptunghiul (blocul de calcule) se înregistrează acțiunile, în urma cărora datele își schimbă valorile.
În romb (blocul de comparație), condițiile care trebuie verificate sunt scrise pentru a selecta opțiunea de a continua calculul.
O paralelogramă (bloc I / O) conține informații despre datele de intrare și ieșire.
Oval înseamnă începutul sau sfârșitul procesului de calcul.
Cele mai utilizate simboluri ale LHSA
Blocul de modificări (ciclu)
În schema bloc a algoritmului, pașii corespund etapelor algoritmului, iar marginile corespund tranzițiilor dintre pași. Vârfurile din diagrama bloc pot fi de două tipuri: vârfurile de la care se lasă o margine (se numesc operatori) și nodurile de la care ies cele două margini (se numesc condiții logice și predicate). În plus, există un singur operator de capăt de la care nu există muchii și un singur operator de pornire.
O caracteristică importantă a diagramei este că linkurile pe care le descrie nu depind de faptul dacă pașii sunt elementari sau sunt algoritmi independenți - cum spun programatorii, blocuri. Cu ajutorul diagramelor bloc, mai mulți algoritmi, considerați ca blocuri, pot fi legați într-un algoritm agregat. O astfel de combinație de algoritmi se numește o compoziție de algoritmi. În schimb, un algoritm mare poate fi împărțit în blocuri, care vor fi dezvoltate în paralel de diferiți programatori, care este utilizat pe scară largă în programare.
În diagrama bloc, diferența dintre descrierea algoritmului și procesul de implementare este clar vizibilă. Descrierea este un grafic, procesul de implementare este calea din grafic. Căi diferite în același grafic apar cu date diferite care creează condiții logice diferite la punctele de decizie (la punctele de ramură). Lipsa de convergență înseamnă că, în procesul de calcul, condițiile care conduc la sfârșitul algoritmului nu apar și procesul devine looped.
Pentru toată vizibilitatea limbajului diagramelor bloc, trebuie avut în vedere că reflectă legăturile dintre unitățile de control individuale și nu informațiile. Diagrama indică doar ce trebuie să facă în continuare, care bloc este trecut de control. Diagramele nu conțin informații despre date, memorie sau seturile de pași elementari folosiți. În esență, diagrama nu este o limbă, ci un mijloc de descriere a determinismului algoritmului. Ca toate modelele grafice, este un instrument destul de convenabil și vizual. Trebuie să ne amintim că punctele de ramificație nu pot fi doar binare (alegerea a două opțiuni posibile, în funcție de adevăr sau de falsitatea stării logice), ci și multivaluate (alegerea unei ramificații din mai multe posibile). Este important să alegeți o singură cale în prezența mai multor posibile.
Articole similare
Trimiteți-le prietenilor: