Tema 5.1 Algoritmul și proprietățile acestuia. Metode de scriere a unui algoritm
Un algoritm este o descriere clară a succesiunii acțiunilor care trebuie efectuate pentru a rezolva o problemă. Orice problemă necesită obținerea unui rezultat din datele inițiale date, adică algoritmul descrie un proces secvențial de conversie a datelor originale într-un rezultat.
1) Discretență. Această proprietate constă în faptul că algoritmul ar trebui să reprezinte procesul de rezolvare a problemei ca execuție secvențială a pașilor simpli (sau predefiniți). În același timp, pentru fiecare etapă a algoritmului este necesar un interval de timp finit, adică transformarea datelor originale într-un rezultat se face discret în timp.
2) Certitudine (sau determinism). Această proprietate este că fiecare regulă de algoritm trebuie să fie clară, lipsită de ambiguitate și să nu lase loc pentru arbitrare. Datorită acestei proprietăți, execuția algoritmului este de natură mecanică și nu necesită instrucțiuni sau informații suplimentare despre rezolvarea problemei.
3) Eficacitatea (sau finitudinea). Această proprietate constă în faptul că algoritmul trebuie să conducă la rezolvarea problemei într-un număr finit de pași.
4) Masa. Această proprietate constă în faptul că algoritmul pentru rezolvarea problemei este considerat într-o formă generală, adică ar trebui să se aplice unei anumite categorii de probleme care diferă numai în datele originale. În acest caz, datele sursă pot fi selectate dintr-o anumită regiune, care se numește domeniul de aplicabilitate al algoritmului (în unele cazuri, datele originale pot fi absente).
Formele reprezentării algoritmului
În practică, se folosesc următoarele forme de reprezentare a algoritmilor:
· Verbal - o înregistrare într-o limbă naturală,
· Grafic - o înregistrare sub forma unei diagrame (diagramă);
· Scrieți într-o limbă specială (limbaj algoritmic sau pseudocod).
Metoda verbală este o descriere a etapelor succesive ale procesării datelor. Algoritmul este dat într-o declarație arbitrară în limba naturală.
De exemplu: scrie algoritmul pentru determinarea celui mai mare divizor comun (GCD) a două numere naturale (algoritmul lui Euclid). Algoritmul poate fi următorul:
· Specificați două numere;
· Dacă numerele sunt egale, luați oricare dintre acestea ca răspuns și opriți, în caz contrar continuați executarea algoritmului;
· Determinați numărul mai mare;
· Înlocuiți numerele mai mari cu diferența dintre numerele mai mari și mai mici;
· Repetați algoritmul de la pasul 2.
Această metodă este slab formalizată și este rar utilizată.
Modul grafic de reprezentare a algoritmilor este mai compact și mai clar comparativ cu cel verbal. În reprezentarea grafică, algoritmul este reprezentat ca o secvență de blocuri funcționale interdependente, fiecare dintre acestea corespund executării uneia sau mai multor acțiuni.
O astfel de reprezentare grafică este denumită schemă de algoritm sau diagramă grafică. In schema bloc a fiecărui tip de acțiune (de introducere a datelor brute, calculul valorilor de expresie, condițiile de verificare, controlează repetarea operațiilor, procesarea final și altele asemenea) corespunde formei geometrice, furnizate sub formă de bloc de simboluri. Simbolurile bloc sunt conectate prin liniile de tranziție care determină direcția fluxurilor de date.
Elementele principale ale diagramei algoritmului. Reguli pentru a face circuite și a denumirilor pentru operațiunile individuale de prelucrare a datelor reglementează standard de stat (GOST 19.701-90 „sistem unificat de algoritmi program de documentare. Schema, programe, date și sisteme. Datele de identificare și reguli de execuție“).
Limbile algoritmice se apropie de limbajul natural, deci se caracterizează prin: alfabet, operații - cuvinte, operatori - propoziții, sintaxă - reguli de scriere.
Regulile pentru construirea construcțiilor în limbajul algoritmic sunt mai "rigide". Acest lucru înseamnă că limbile algoritmice permit mai puțin diversitate pentru a descrie acțiunile algoritmului decât limbajul natural și simbolurile matematice uzuale, iar masina intelege cu siguranta orice limbaj de design. De exemplu, pentru a multiplica două variabile a și b, simbolurile matematice convenționale permit mai multe forme posibile de scriere:
ab a × b a'b a * b.
Un exemplu de limbaj algoritmic este pseudo-codul dat în tabel:
Vedere generală a algoritmului:
nume de algoritm (argumente și rezultate)
începutul descrierii valorilor intermediare
| | secvența de comenzi (corpul algoritmului)
O parte a algoritmului de la cuvântul alg la cuvântul nach se numește titlu, iar partea cuprinsă între cuvintele începe și partea de algoritm.
Propunerea ALG după numele algoritmului în paranteze indică caracteristici (args Res.) Și un tip de valoare (intacte. Vesch. Sim. Lit. sau log) de intrare (argument) și de ieșire (rezultate) variabile. Când se descriu matrice (tabele), se folosește fila cuvântului de serviciu. Suplimentat de perechi de granițe pentru fiecare index al elementelor matrice.
Exemplu de intrare a limbii algoritmice: