| § 2.1. Algoritmi și Executori

Lecția 14
§ 2.1. Algoritmi și Executori

Cuvinte cheie:

Algoritm
proprietățile algoritmului (discretitate; comprehensibilitate; certitudine; eficacitate; caracter de masă)
executor testamentar
caracteristicile executantului (gama de sarcini de rezolvat; mediu; mod de operare; sistem de comandă)
executarea formală a algoritmului

2.1.1. Conceptul de algoritm

Fiecare persoană în viața de zi cu zi, la școală sau la serviciu, rezolvă un număr imens de probleme de cea mai variată complexitate. Problemele complexe necesită multă gândire pentru a găsi o soluție; o persoană rezolvă sarcini simple și familiare fără ezitare, în mod automat. În cele mai multe cazuri, soluția la fiecare problemă poate fi împărțită în pași simpli (pași). Pentru multe astfel de sarcini (instalarea software-ului, asamblarea unui cabinet, crearea unui site web, operarea unui dispozitiv tehnic, cumpărarea unui bilet de avion prin Internet etc.), au fost deja dezvoltate și sunt oferite instrucțiuni pas cu pas, cu secvențiale execuție a căruia se poate ajunge la rezultatul dorit.

Exemplul 1. Sarcina „Găsiți media aritmetică a două numere” este rezolvată în trei pași:

1) gândiți-vă la două numere;
2) se adună cele două numere concepute;
3) împărțiți suma primită la 2.

Exemplul 2. Sarcina „Depuneți bani într-un cont de telefon” este împărțită în următorii pași:

1) mergeți la terminalul de plată;
2) alegeți un operator de telecomunicații;
3) introduceți numărul de telefon;
4) verificați corectitudinea numărului introdus;
5) introduceți o bancnotă în acceptorul de bancnote;
6) așteptați mesajul despre creditarea banilor în cont;
7) primiți un cec.

Exemplul 3. Etapele rezolvării problemei „Desenează un arici amuzant” sunt prezentate grafic:

Găsirea mediei aritmetice, depunerea banilor într-o factură de telefon și desenarea unui arici sunt, la prima vedere, procese complet diferite. Dar au un lucru în comun: fiecare dintre aceste procese este descris prin secvențe de instrucțiuni scurte, următoarele exacte care vă vor permite să obțineți rezultatul dorit. Secvențele de instrucțiuni date în exemplele 1-3 sunt algoritmi pentru rezolvarea problemelor corespunzătoare. Executorul acestor algoritmi este un om.

Algoritmul poate reprezenta o descriere a unei anumite secvențe de calcule (exemplul 1) sau pași de natură nematematică (exemplele 2-3). Dar în orice caz, înainte de dezvoltarea sa, trebuie clar definite condițiile inițiale (date inițiale) și ceea ce se dorește a se obține (rezultat). Putem spune că un algoritm este o descriere a unei secvențe de pași în rezolvarea unei probleme, care duce de la datele inițiale la rezultatul cerut.

În general, schema algoritmului poate fi reprezentată astfel (Fig. 2.1).

Orez. 2.1. Schema generală a algoritmului

Algoritmii sunt regulile de adunare, scădere, înmulțire și împărțire a numerelor studiate la școală, multe reguli gramaticale, reguli ale construcțiilor geometrice etc.

Animațiile „Lucrul cu algoritmul” (193576), „Cel mai mare divizor comun” (170363), „Mel mai mic multiplu comun” (170390) vă vor ajuta să vă amintiți unii dintre algoritmii învățați în lecțiile de limba rusă și matematică (http:/ /sc.edu.ru /).

Exemplul 4. Un anumit algoritm duce la faptul că dintr-un șir de caractere se obține un șir nou după cum urmează:

1. Se calculează lungimea (în caractere) a șirului de caractere original.
2. Dacă lungimea lanțului original este impară, atunci numărul 1 este atribuit lanțului original din dreapta, altfel lanțul nu se schimbă.
3. Simbolurile sunt schimbate în perechi (primul - cu al doilea, al treilea - cu al patrulea, al cincilea - cu al șaselea etc.).
4. În dreapta lanțului rezultat se atribuie numărul 2.

Lanțul rezultat este rezultatul algoritmului.

Deci, dacă lanțul inițial a fost А # В, atunci rezultatul algoritmului va fi lanțul # A1B2, iar dacă lanțul inițial a fost ABC @, atunci rezultatul algoritmului va fi lanțul BA @ B2.

2.1.2. Executor de algoritm

Fiecare algoritm este conceput pentru un anumit interpret.

Un executor este un obiect (om, animal, dispozitiv tehnic) capabil să execute un anumit set de comenzi.

Distinge interpreți formali și informali... Executorul formal execută întotdeauna aceeași comandă în același mod. Un interpret informal poate executa o comandă în moduri diferite.

Să luăm în considerare mai detaliat setul de interpreți formali. Interpreții formali sunt neobișnuit de diverși, dar pentru fiecare dintre ei pot fi specificate următoarele caracteristici: gama de sarcini de rezolvat (scop), mediul, sistemul de comandă și modul de operare.

Gama de sarcini de rezolvat... Fiecare interpret este creat pentru a rezolva o anumită gamă de sarcini - construirea de lanțuri de simboluri, efectuarea de calcule, desenarea desenelor pe un plan etc.

Mediul artistului... Zona, setarea, condițiile în care operează interpretul sunt de obicei numite mediul interpretului dat. Datele și rezultatele inițiale ale oricărui algoritm aparțin întotdeauna mediului executorului căruia îi este destinat algoritmul.

Sistemul de comandă al executorului... O instrucțiune către executant pentru a efectua o acțiune separată finalizată se numește comandă. Totalitatea tuturor comenzilor care pot fi executate de un anumit executant formează un sistem de comenzi pentru acest executant (SKI). Algoritmul este compilat ținând cont de capacitățile unui anumit interpret, cu alte cuvinte, în sistemul de comenzi al interpretului care îl va executa.

Moduri de operare ale interpretului... Pentru majoritatea interpreților, sunt furnizate modurile de control direct și de control al programului. În primul caz, executantul așteaptă comenzi de la o persoană și execută imediat fiecare comandă primită. În al doilea caz, executantului i se dă mai întâi o secvență completă de comenzi (program), apoi execută toate aceste comenzi în mod automat. O serie de interpreți lucrează numai în unul dintre aceste moduri.

Să luăm în considerare exemple de interpreți.

Exemplul 5. Artist O broasca testoasa se misca pe ecranul computerului, lasand o urma sub forma unei linii.

Sistemul de comandă al țestoasei constă din următoarele comenzi:

1. Înainte n (unde n este un număr întreg) - determină Țestoasa să se miște în n pași în direcția mișcării - în direcția în care sunt întoarse capul și corpul;
2. La dreapta m (unde m este un număr întreg) - provoacă o schimbare a direcției de mișcare a Țestoasei cu m grade în sensul acelor de ceasornic.
Înregistrare Repetați k [<Команда1> <Команда2> ... <Командаn>] înseamnă că succesiunea comenzilor din paranteze se va repeta de k ori.

Gândiți-vă la ce formă va apărea pe ecran după ce Țestoasa efectuează următorul algoritm.
Repetați 12 [Dreapta 45 Înainte 20 Dreapta 45]

Exemplul 6. Sistemul de comandă al executorului Calculatorul este format din două comenzi cărora li se atribuie numere:

1 - scade 1
2 - înmulțiți cu 3

Primul dintre ei scade numărul cu 1, al doilea îl mărește de 3 ori. La înregistrarea algoritmilor, pentru concizie, sunt indicate doar numerele de comandă. De exemplu, algoritmul 21212 înseamnă următoarea secvență de comenzi:

Înmulțiți cu 3
scade 1
inmultiti cu 3
scade 1
inmultiti cu 3

Acest algoritm convertește numărul 1 la 15:

((1 3 - 1) 3 - 1) 3 = 15.

Exemplul 7. Executor Robotul operează pe un câmp în carouri, între celulele adiacente ale căruia pot fi pereți. Robotul se deplasează în jurul celulelor câmpului și poate executa următoarele comenzi, cărora li se atribuie numere:

1 sus
2 - jos
3 - la dreapta
4 ramase

Când fiecare astfel de comandă este executată, Robotul se deplasează într-o celulă adiacentă în direcția specificată. Dacă în această direcție există un perete între celule, atunci Robotul este distrus.

Ce se întâmplă cu Robotul dacă execută secvența comenzilor 32323 (aici numerele indică numerele comenzii), începând de la celula A? Ce succesiune de comenzi ar trebui să execute robotul pentru a trece de la celula A la celula B fără să se prăbușească de la ciocnirea cu pereții?

Când dezvoltați un algoritm:

1) se evidențiază obiectele care apar în sarcină, se stabilesc proprietățile obiectelor, relațiile dintre obiecte și posibilele acțiuni cu obiectele;
2) se determină datele inițiale și rezultatul cerut;
3) se determină succesiunea acțiunilor executantului, ceea ce asigură trecerea de la datele inițiale la rezultat;
4) succesiunea acțiunilor este înregistrată cu ajutorul comenzilor incluse în sistemul de comenzi al executantului.

Putem spune că un algoritm este un model al activității executantului de algoritmi.

2.1.3. Proprietățile algoritmului

Nu orice instrucțiune, secvență de instrucțiuni sau plan de acțiune poate fi considerat un algoritm. Fiecare algoritm are în mod necesar următoarele proprietăți: discretitate, comprehensibilitate, certitudine, eficiență și caracter de masă.

Proprietatea discretitățiiînseamnă că modul de rezolvare a problemei este împărțit în etape (acțiuni) separate. Fiecărei acțiuni îi corespunde o prescripție (comandă). Numai după ce a finalizat o comandă, executantul poate trece la următoarea comandă.

Proprietatea de comprehensibilitateînseamnă că algoritmul constă numai din comenzi incluse în sistemul de comenzi al executantului, adică din astfel de comenzi pe care executantul le poate percepe și conform cărora poate efectua acțiunile cerute.

Proprietatea de certitudineînseamnă că nu există comenzi în algoritm, al căror sens poate fi interpretat ambiguu de către executant; sunt inacceptabile situațiile când, după executarea următoarei comenzi, executantului nu este clar ce comandă să execute următoarea. Datorită acestui fapt, rezultatul algoritmului este determinat în mod unic de setul de date inițiale: dacă algoritmul este aplicat de mai multe ori aceluiași set de date inițiale, atunci rezultatul este întotdeauna același rezultat.

Proprietatea de performanțăînseamnă că algoritmul ar trebui să ofere un rezultat după un număr finit, eventual foarte mare, de pași. În acest caz, rezultatul este considerat nu numai răspunsul datorat enunțului problemei, ci și concluzia că este imposibil să se continue din orice motiv soluționarea acestei probleme.

Proprietatea caracterului de masăînseamnă că algoritmul ar trebui să ofere posibilitatea aplicării sale pentru rezolvarea oricărei probleme dintr-o anumită clasă de probleme. De exemplu, algoritmul pentru găsirea rădăcinilor unei ecuații pătratice ar trebui să fie aplicabil oricărei ecuații pătratice, algoritmul pentru traversarea unei străzi ar trebui să fie aplicabil oriunde pe stradă, algoritmul pentru prepararea unui medicament ar trebui să fie aplicabil pentru prepararea oricărei cantități din acesta. , etc.

Exemplul 8. Luați în considerare una dintre metodele de găsire a tuturor numerelor prime care nu depășesc un număr natural n. Această metodă este numită „sita lui Eratosthenes” după numele savantului grec antic Eratosthenes (sec. III î.Hr.) care a propus-o.

Pentru a găsi toate numerele prime care nu sunt mai mari decât un număr dat n, urmând metoda lui Eratostene, trebuie să efectuați următorii pași:

1) scrieți pe rând toate numerele naturale de la 2 la n (2, 3, 4, ..., n);
2) încadrați într-un cadru 2 - primul număr prim;
3) ștergeți din listă toate numerele divizibile cu ultimul număr prim găsit;
4) găsiți primul număr nemarcat (numerele marcate sunt numere barate sau numere incluse într-un cadru) și închideți-l într-un cadru - acesta va fi următorul număr prim;
5) repetați pașii 3 și 4 până când nu există numere nemarcate.

Puteți obține o reprezentare mai vizuală a metodei de găsire a numerelor prime cu ajutorul animației „Sie of Eratosthenes” (180279) găzduită în colecția Unificată de resurse educaționale digitale.

Secvența de acțiuni considerată este un algoritm, deoarece satisface proprietățile:

discretie- procesul de găsire a numerelor prime se împarte în etape;
inteligibilitate- fiecare comandă este de înțeles unui elev de clasa a VIII-a care realizează acest algoritm;
certitudine- fiecare comandă este interpretată și executată de către executant fără ambiguitate; există instrucțiuni privind ordinea executării comenzilor;
eficacitate- dupa un anumit numar de pasi se obtine rezultatul;
caracter de masă- succesiunea acțiunilor este aplicabilă pentru orice n natural.

Proprietățile luate în considerare ale algoritmului fac posibilă o definiție mai precisă a algoritmului.

Un algoritm este o descriere a unei secvențe de acțiuni destinate unui anumit executant, care duc de la datele inițiale la rezultatul cerut, care are proprietățile discretității, inteligibilității, definiției, eficacității și caracterului de masă.

2.1.4. Capacitatea de a automatiza activitățile umane

Dezvoltarea algoritmului este de obicei o sarcină care necesită timp, care necesită cunoștințe profunde, ingeniozitate și consumatoare de timp din partea unei persoane.

Rezolvarea problemei conform algoritmului gata făcut necesită de la executant doar respectarea strictă a instrucțiunilor date.

Exemplul 9. Dintr-o grămadă care conține orice, mai mult de trei, număr de obiecte, doi jucători iau pe rând unul sau două obiecte. Câștigătorul este cel care, cu următoarea sa mișcare, poate ridica toate obiectele rămase.

Să luăm în considerare un algoritm, în urma căruia primul jucător își va asigura cu siguranță o victorie.

1. Dacă numărul de articole din teanc este multiplu de 3, atunci renunță la mișcare către adversar, altfel începe jocul luând 1 sau 2 articole astfel încât numărul de articole să fie un multiplu de 3.
2. De fiecare dată, la următoarea mutare, suplimentează numărul de obiecte luate de adversar la 3 (numărul de obiecte rămase trebuie să fie un multiplu de 3).

Este posibil ca interpretul să nu se aprofundeze în sensul a ceea ce face și să nu argumenteze de ce face asta și nu altfel, adică poate acționa formal. Capacitatea interpretului de a acționa în mod formal oferă capacitatea de a automatiza activitățile umane. Pentru asta:

1) procesul de rezolvare a problemei este prezentat sub forma unei secvenţe a celor mai simple operaţii;
2) este creată o mașină (dispozitiv automat) care este capabil să efectueze aceste operații în secvența specificată în algoritm;
3) o persoană este eliberată de activitățile de rutină, execuția algoritmului este încredințată unui dispozitiv automat.

CEL MAI IMPORTANT LUCRU

Executor testamentar- un obiect (om, animal, dispozitiv tehnic) capabil să execute un anumit set de comenzi.

Executorul formal execută întotdeauna aceeași comandă în același mod. Pentru fiecare contractant formal, puteți specifica: gamă de sarcini de rezolvat, mediu, sistem de comandă și mod de operare.

Algoritm- o descriere a secvenței de acțiuni destinate unui anumit interpret, care să conducă de la datele inițiale la rezultatul solicitat, care are proprietățile discretității, inteligibilității, certitudinii, eficacității și caracterului de masă.

Capacitatea interpretului de a acționa oficial oferă capacitatea de a automatiza activitățile umane.

Întrebări și sarcini

1. Citiți materialele prezentării pentru paragraful conținute în atașamentul electronic la manual. Prezentarea completează informațiile din textul paragrafului? Ce diapozitive ai putea adăuga la prezentarea ta?

2. Ce se numește algoritm?

3. Găsiți sinonime pentru cuvântul „prescripție”.

4. Dați exemple de algoritmi pe care îi învățați la școală.

5. Cine poate fi executantul algoritmului?

6. Dați un exemplu de antreprenor oficial. Dați un exemplu când o persoană acționează ca executor oficial.

7. Ce determină gama de sarcini ale executorului „calculator”?

8. Considerați procesorul de text de pe computerul dvs. drept executor. Descrieți gama de sarcini rezolvate de acest interpret și mediul său.

9. Ce este o comandă, un sistem de comenzi al unui executant?

10. Ce comenzi ar trebui să aibă un robot care îndeplinește funcțiile:

a) un casier într-un magazin;
b) un portar;
c) un agent de pază?

11. Enumerați principalele proprietăți ale algoritmului.

12. La ce poate duce lipsa oricărei proprietăți în algoritm? Dă exemple.

13. Care este importanța posibilității de execuție formală a algoritmului?

14. Sirul de numere se construieste dupa urmatorul algoritm: primele doua numere ale sirului se iau egale cu 1; fiecare număr următor din succesiune este luat egal cu suma celor două numere anterioare. Notează primii 10 termeni ai acestei secvențe. Aflați cum se numește această secvență.

15. Unele algoritmi primesc un șir nou dintr-un șir de simboluri, după cum urmează. În primul rând, se scrie lanțul original de caractere, după care se scrie în ordine inversă lanțul original de caractere, apoi se scrie litera care urmează în alfabetul rus după litera care se afla pe ultimul loc în lanțul original. Dacă în lanțul original litera „I” este pe ultimul loc, atunci litera „A” este scrisă ca următoarea literă. Lanțul rezultat este rezultatul algoritmului. De exemplu, dacă șirul de caractere original a fost „DOM”, atunci rezultatul algoritmului va fi șirul „DOMMODN”. Dat un șir de caractere „COM”. Câte litere „O” vor fi în lanțul de caractere, care se vor dovedi dacă aplicați algoritmul acestui lanț și apoi aplicați algoritmul din nou la rezultatul muncii sale?

16. Găsiți pe Internet animația pașilor algoritmului Eratosthenes. Găsiți toate numerele prime de până la 50 folosind algoritmul lui Eratosthenes.

17. Care va fi rezultatul executării de către Țestoasa (vezi exemplul 5) a algoritmului?

18. Notați algoritmul pentru calculatorul executor (vezi exemplul 6), care conține cel mult 5 comenzi:

a) obtinerea de la numarul 3 a numarului 16;
b) obtinerea de la numarul 1 a numarului 25.

19. Sistemul de comandă al executantului Constructor este format din două comenzi, cărora li se atribuie numere:

1 - atribuiți 2
2 - împărțiți la 2

Conform primei dintre ele, 2 este atribuit numărului din dreapta, iar conform celui de-al doilea, numărul este divizibil cu 2. Cum va fi convertit numărul 8 dacă executorul execută algoritmul 22212? Creați un algoritm în sistemul de comandă al acestui executant, conform căruia numărul 1 va fi convertit în numărul 16 (algoritmul nu trebuie să conțină mai mult de 5 comenzi).

20. În ce celulă ar trebui să se afle Robotul executant (exemplul 7) pentru a reveni la ea după executarea algoritmului 3241?

Software gratuit:

Sistemul Kumir - Un set de lumi educaționale (descărcați arhiva programului de pe site) sau vizitați pagina Kumir ((http://www.niisi.ru/kumir/)

Cuvântul „algoritm” provine de la numele matematicianului arab din secolul al IX-lea al-Khwarizmi, care a formulat regulile pentru efectuarea operațiilor aritmetice.

Algoritm- o instrucțiune precisă și ușor de înțeles pentru executant pentru a executa secvența finală de comenzi care conduc de la datele inițiale la rezultatul inițial.

Exemple: rutina zilnică, procedura de gătit, instrucțiuni etc.)

Executor de algoritm Este cel care execută algoritmul (om, animal, mașină, computer).

Sistemul de comandă al executorului- acesta este întregul set de comenzi pe care executantul știe să le execute (înțelege). Algoritmul poate fi construit numai din comenzile incluse în sistemul de comenzi al executantului.

de exemplu, performer Robotul poate executa comenzi înainte, înapoi, stânga, dreapta, pictează peste. Se mișcă în jurul unui câmp celular, delimitat de un perete și care conține pereți. Robotul nu poate trece prin perete.

Proprietățile algoritmului:

1.Eficiență (membru)- posibilitatea de a obţine rezultatul din datele iniţiale într-un număr finit de paşi. (De exemplu, când se efectuează algoritmul de adunare, 2 numere ar trebui să obțină suma).

2.Caracter de masă- capacitatea de a aplica algoritmul unui număr mare de date de intrare diferite. (De exemplu, puteți adăuga orice 2 numere, cunoscând algoritmul de adunare.)

3.Determinism(certitudine, acuratețe) - fiecare echipă trebuie să definească fără ambiguitate acțiunea interpretului.

4.inteligibilitate- comanda trebuie să fie scrisă într-un limbaj înțeles de computer.

5.Discretenie- împărțirea algoritmului în comenzi separate.

Metode de înregistrare a algoritmului:

1) În limbaj natural - înregistrare sub formă de comenzi separate într-o limbă pe care o persoană poate înțelege.

2) Grafic - în limbajul diagramelor bloc, folosind forme geometrice (oval, dreptunghi, paralelogram, romb).

3) Într-un limbaj algoritmic - un limbaj pentru scrierea algoritmilor pentru predarea programarii. Echipele sunt înregistrate în limba rusă.

4) Într-un limbaj de programare - un program. Limbaje de programare: Basic, Pascal, C, Visual Basic.

B7. Structuri algoritmice de bază: urmărire, ramificare, buclă; imaginea de pe diagramele bloc. Împărțirea sarcinilor în subsarcini. Algoritmi auxiliari.

Construcții algoritmice.În cadrul algoritmilor, se pot distinge grupuri de pași care diferă în structura lor internă - construcții algoritmice.

Construcții algoritmice de bază sunt secvențe liniare de pași (sau secvențiere), ramificare și buclă.

Este apelat un algoritm în care comenzile sunt executate secvenţial una după alta algoritm liniar.

Iată cum arată un algoritm liniar în limbajul diagramelor bloc:

Exemplu: algoritm pentru pornirea computerului:

1. Porniți computerul (apăsați butonul de pe protectorul de supratensiune).
2. Porniți monitorul, imprimanta.
3. Apăsați butonul de pornire de pe unitatea de sistem.
4. Așteptați până când sistemul de operare este încărcat și apare Desktop.
5. Treci la treabă.

În acest algoritm, toate acțiunile trebuie efectuate succesiv una după alta: nu puteți începe lucrul dacă alimentarea sau monitorul nu sunt pornite.

Structura algoritmică" ramificare"Este inclus condiție, în funcție de adevărul condiției, se execută una sau alta secvență de comenzi (serie).

O condiție este o afirmație care poate fi adevărată sau falsă. În condiție, două numere, două șiruri, două variabile sau expresii șir sunt comparate între ele folosind operații de comparare (>,<, =, >=, <=).

Scrierea în limbaj algoritmic: Dacă Condiție Atunci Seria 1 (Dacă Condiție este adevărat, atunci Seria 1, dacă Condiție este fals, atunci nu se execută nimic). Exemplu: Dacă astăzi este duminică, atunci nu trebuie să mergeți la școală. Formă de ramificare completă

În structuri algoritmice ciclu include o serie de comenzi care sunt executate de mai multe ori. Această secvență de comenzi este numită corpul ciclului.

Structurile algoritmice ciclice sunt de două tipuri:

• contra-cicluri, în care corpul buclei este executat de un anumit număr de ori;
• bucle condiționate, în care corpul buclei este executat atâta timp cât condiția este îndeplinită.

Ciclu cu contor- se foloseste cand se stie dinainte cate repetari ale corpului ciclului trebuie efectuate.

Vă rugăm să suspendați AdBlock pe acest site.

În această lecție, vom analiza câteva dintre conceptele teoretice care formalizează conceptul de programare. În același timp, vom formula mai precis sarcina principală a antrenamentului dumneavoastră.

Pentru început, vă sugerez să vă jucați puțin cu următoarea jucărie pentru copii. Completați primele cinci teme, întoarceți-vă și continuați să citiți lecția.

Fig. 1 Captură de ecran a terenului de joc la code.org

Sper să reușești. Acum, folosind acest exemplu, vom descrie câteva concepte de bază:

• executor testamentar;
• sistem de comenzi executorii;
• algoritm.

În jucărie controlăm o pasăre roșie. Sarcina fiecărei etape: să ducă pasărea la porc. Pasărea poate executa anumite comenzi, de exemplu: deplasare înainte, întoarcere la stânga, întoarcere la dreapta etc.

O persoană, mașină sau dispozitiv care poate executa anumite comenzi se numește executor. În această jucărie, evident, interpretul este o pasăre. Setul de comenzi pe care executantul le înțelege și știe să le execute este numit sistemul de comandă al executorului.

Secvența de comenzi pe care executorul trebuie să le execute pentru a rezolva problema se numește algoritm.

Este necesar să ne concentrăm pe mai multe puncte.

Executantul poate executa numai acele comenzi care sunt incluse în sistemul său de comandă.

Aceasta înseamnă, de exemplu, că nu poți să-i scrii interpretului de păsări: „Du-te la porc!” Mai precis, poți scrie, dar nu se va întâmpla nimic, tk. executantul unor astfel de comenzi nu stie.

Puteți scrie comenzile existente în orice ordine pe care o considerați corectă. Sarcina ta ca programator este de a împărți o sarcină complexă mare în pași mici separati, fiecare dintre care va fi clar pentru executant. Împărțiți și cuceriți din nou funcționează.

Executantul face exact ceea ce algoritmul îi cere să facă.

Artistul de păsări este foarte încrezător. Nu pune la îndoială ce scrii în program. Dacă, de exemplu, uitați să desfaceți pasărea, aceasta se va izbi de perete. Prin urmare, trebuie să ai grijă singur de totul.

Programele tale viitoare nu vor funcționa adesea așa cum ți-ai propus. Greșelile se întâmplă tuturor. Este important să înțelegeți că acesta nu este un prost al computerului, dar ați făcut o greșeală în algoritm. Nu fiți ca programatorii răi care au întotdeauna programul de vină.

Acum, dintr-un exemplu ilustrativ, să trecem la realitățile computerizate. Scriem programe pentru un computer, ceea ce înseamnă că computerul în cazul nostru este un executor. Sistem de comandă - funcții și constructe standard ale limbajului C.

Care este sarcina principală a predării noțiunilor de bază ale programării? Stăpânește abilitățile de gândire algoritmică. Adică, învață cum să notezi soluția la diferite probleme sub forma unui algoritm pentru un anumit interpret (în cazul nostru, un computer).

Deci, pentru a rezuma:

Program de calculator- un algoritm de rezolvare a unei probleme, scris într-un limbaj de programare.

Algoritm - o descriere exactă a ordinii acțiunilor care trebuie efectuate de către executant pentru a rezolva problema.

Executor - o persoană sau un dispozitiv care poate înțelege și executa un anumit set de comenzi.

Conceptul de algoritm. Executori de algoritm. Proprietățile algoritmului

Conceptul de algoritm este la fel de fundamental pentru informatică ca și conceptul de informație. Există multe definiții diferite ale unui algoritm, deoarece acest concept este destul de larg și este utilizat în diferite domenii ale științei, tehnologiei și vieții de zi cu zi.

Algoritmul este o secvență de acțiuni ușor de înțeles și precis care descrie procesul de transformare a unui obiect dintr-o stare inițială într-o stare finală.

Un algoritm este o descriere precisă a unei secvențe de acțiuni care vizează rezolvarea unei probleme date, destinate unui anumit executant.

Interpret algoritmul poate fi fie o persoană (rețete, diverse instrucțiuni, algoritmi pentru calcule matematice), fie un dispozitiv tehnic. Sunt diverse mașini (calculatoare, roboți industriali, aparate electrocasnice moderne). interpreți formali algoritmi. Executorul formal nu este obligat să înțeleagă esența problemei care se rezolvă, dar este necesară executarea exactă a secvenței de comenzi.

Algoritmul poate fi scris în diverse moduri (descriere verbală, descriere grafică - diagramă bloc, program într-unul din limbajele de programare etc.). Un program este un algoritm în care este scrislimbaj de programare .

Pentru a crea un algoritm (program), trebuie să știți:

un set complet de date inițiale ale problemei (starea inițială a obiectului);

scopul creării algoritmului (starea finală a obiectului);

sistemul de comandă al executantului (adică un set de comenzi pe care executantul le înțelege și le poate executa).

Algoritmul rezultat (programul) trebuie să aibă următorul set de proprietăți:

discretie (algoritmul este împărțit în pași separați - comenzi);

neambiguitate (fiecare comandă determină singura acțiune posibilă a executantului);

inteligibilitate (toate comenzile algoritmului sunt incluse în sistemul de comandă al executantului);

eficienţă (interpretul trebuie să rezolve problema într-un număr finit de pași).

Majoritatea algoritmilor au, de asemenea, proprietatea caracter de masă (folosind același algoritm, multe probleme similare pot fi rezolvate).

Metode de descriere a algoritmilor

S-a remarcat mai sus că același algoritm poate fi scris în moduri diferite. Algoritmul poate fi scris limbaj natural. Ca atare, folosim rețete, instrucțiuni etc. Pentru algoritmi de înregistrare destinati interpreților formali, special limbaje de programare... Orice algoritm poate fi descris grafic sub forma unei diagrame bloc... Pentru aceasta, a fost dezvoltat un sistem special de notație:

Desemnare	Descriere	Note (editare)
	Începutul și sfârșitul algoritmului
	Intrarea și ieșirea datelor.	Ieșirea datelor este uneori menționată diferit:
	Acțiune	În algoritmii de calcul, aceasta este sarcina
	Furculiţă	Furcă - o componentă necesară pentru implementarea ramurilor și buclelor
	Începe ciclul cu parametrul
	Proces tipic	În programare, proceduri sau subrutine
	Tranziții între blocuri

Să dăm un exemplu de descriere a unui algoritm pentru însumarea a două mărimi sub forma unei diagrame bloc:

Acest mod de a descrie algoritmul este cel mai grafic și mai ușor de înțeles pentru oameni. Prin urmare, algoritmii executorilor formali sunt de obicei dezvoltați mai întâi sub forma unei diagrame bloc și abia apoi creează un program pe una dintrelimbaje de programare .

Structuri algoritmice tipice

Programatorul are capacitatea de a proiecta și de a utiliza structuri algoritmice atipice, însă acest lucru nu este necesar. Orice algoritm arbitrar complex poate fi dezvoltat pe baza a trei structuri tipice: succesiune, ramificare și repetiție. În acest caz, structurile pot fi aranjate secvenţial una după alta sau imbricate unele în altele.

Structură liniară (urmează)

Cea mai simplă structură algoritmică este liniar. În ea, toate operațiunile sunt efectuate o dată în ordinea în care sunt scrise.

Ramificare

V ramificare completă există două opțiuni pentru acțiunile executantului, în funcție de valoarea expresiei logice (condiție). Dacă condiția este adevărată, atunci va fi executată doar prima ramură, în caz contrar va fi executată doar a doua ramură.

A doua ramură poate fi goală. Această structură se numește ramificare sau traversare incompletă.

Din mai multe ramuri este posibilă construirea structurii „ alegere„(Multiple branching), care va alege nu dintre două, ci dintr-un număr mai mare de opțiuni pentru acțiunile executantului, în funcție de mai multe condiții. Este esențial să se execute o singură ramură - într-o astfel de structură, ordinea condițiilor devine importantă: dacă sunt îndeplinite mai multe condiții, atunci doar una dintre ele va funcționa - prima de sus.

Ciclu (repetiție)

Cicluvă permite să organizați mai multe repetări ale aceleiași secvențe de comenzi- se numeste corpul ciclului. În diferite tipuri de algoritmi de buclă, numărul de repetări poate depinde de valoarea unei expresii logice (condiție) sau poate fi codificat în structura în sine. Există cicluri: " inainte de», « pa», cicluri cu un contor.În buclele „înainte” și „în timp ce” o expresie logică (condiție) poate precede corpul buclei ( bucla de precondiție) sau încheie bucla ( bucla după condiție).

Cicluri« inainte de„- repetarea corpului ciclului până când este îndeplinită condiția:

Cicluri « pa„- repetarea corpului ciclului în timp ce condiția este îndeplinită(Adevărat):

Contor bucle(cu parametru)- repetarea corpului buclei de un număr dat de ori:

Algoritm auxiliar (subrutină, procedură)

Algoritmul de ajutor este un modul care poate fi accesat de mai multe ori din algoritmul principal. Utilizarea algoritmilor de ajutor poate reduce semnificativ dimensiunea algoritmului și poate simplifica dezvoltarea acestuia.

Metode de dezvoltare a algoritmilor complecși

Există două metode de dezvoltare a algoritmilor complecși:

Metoda de detaliere secvenţială a sarcinilor("De sus în jos") este că problema complexă inițială este împărțită în subsarcini. Fiecare dintre subprobleme este luată în considerare și rezolvată separat. Dacă oricare dintre sarcinile secundare este dificilă, acestea sunt, de asemenea, împărțite în sarcini secundare. Procesul continuă până când subsarcinile sunt reduse la cele elementare. Soluțiile subproblemelor individuale sunt apoi colectate într-un singur algoritm pentru rezolvarea problemei inițiale. Metoda este utilizată pe scară largă deoarece permite mai multor programatori să dezvolte simultan un algoritm general care rezolvă subsarcini locale. Aceasta este o condiție prealabilă pentru dezvoltarea rapidă a produselor software.

Metoda de asamblare("De jos în sus") este de a crea un set de module software care implementează soluția sarcinilor tipice. La rezolvarea unei probleme complexe, programatorul poate folosi modulele dezvoltate ca algoritmi (proceduri) auxiliari. In multe sisteme de programare Există deja seturi similare de module, care simplifică și accelerează foarte mult crearea unui algoritm complex.

Algoritmi și procese de control

Control - interacțiunea intenționată a obiectelor, dintre care unele sunt controlate, altele sunt controlate.

În cel mai simplu caz, există două astfel de obiecte:

Din punct de vedere informatic acţiunile de control pot fi considerate informaţii de control. Informațiile pot fi transmise sub formă de comenzi. Se numește secvența de comenzi pentru controlul obiectului, care duce la un scop prestabilit algoritm de control... În consecință, obiectul de control poate fi numit executorul algoritmului de control. În exemplul de mai sus, obiectul de control funcționează „fără să se uite” la ceea ce se întâmplă cu obiectul de control ( control în buclă deschisă deschis... O altă schemă de control poate lua în considerare informații despre procesele care au loc în obiectul de control:

În acest caz, algoritmul de control trebuie să fie suficient de flexibil pentru a analiza aceste informații și a lua o decizie cu privire la acțiunile sale ulterioare în funcție de starea obiectului de control ( controlul feedback-ului). Această schemă de control se numește închis.

Mai detaliat sunt studiate procesele de control. cibernetică... Această știință susține că cele mai diverse procese de management din societate, natură și tehnologie au loc în mod similar, se supun acelorași principii.

Până la începutul subiectului

MBOU „Școala secundară Glinnovskaya”

districtul Novooskolsky

Regiunea Belgorod

Plan - schița lecției

(Clasa a 9-a)

„Algoritmi, concepte ale unui algoritm, proprietăți ale unui algoritm. Executori de algoritm "

Pregătite de:

Preda informatica

Tarasova N.G.

2011

Subiect: Conceptul de algoritmi, proprietățile algoritmului. Executori de algoritm, sistem de comandă a executorului. Metode de înregistrare a algoritmilor. Executarea formală a algoritmilor.

Tip de lecție: familiarizarea cu material nou.

Obiective:

1. Promovarea dezvoltării gândirii algoritmice;
2. Dați conceptul de algoritm, vorbiți despre proprietăți, oferiți o clasificare a algoritmilor;
3. Introduceți forma algoritmilor de scriere - diagramă bloc.

Echipament: proiector, prezentare.

În timpul orelor

1 org. Moment

Salutări, aterizare, apel nominal.

2 Actualizarea materialului de referință

Băieți, vă rog să-mi spuneți, cum înțelegeți cuvântul algoritm? Unde avem de a face cu acest concept?

3 Prezentarea materialului

Originea termenului „algoritm” este asociată cu matematica. Istoria originii sale este următoarea. În secolul al IX-lea, omul de știință al (al) -Khorezmi a trăit la Bagdad (nume complet - Muhammad bin Musa al-Khorezmi, adică Muhammad, fiul lui Musa din Khorezm), matematician, astronom, geograf. Într-una dintre lucrările sale, el a descris sistemul de numere zecimal și a formulat pentru prima dată regulile pentru efectuarea operațiilor aritmetice pe numere întregi și fracții ordinare. Originalul arab al acestei cărți s-a pierdut, dar a rămas traducerea latină din secolul al XII-lea, conform căreia Europa de Vest s-a familiarizat cu sistemul numeric zecimal și cu regulile de efectuare a operațiilor aritmetice.

Al-Khwarizmi s-a străduit să facă înțelese regulile formulate de el. A fost dificil de realizat acest lucru în secolul al IX-lea, când simbolismul matematic (semne de operație, paranteze, desemnări de litere etc.) nu fusese încă dezvoltat. Cu toate acestea, el reușește să dezvolte un stil clar de prescripție verbală strictă, care nu oferă cititorului posibilitatea de a se abate de la prescris sau de a sări peste orice acțiune.

Regulile din cărțile vezi-Khorezmi în traducerea latină au început cu cuvintele „a spus Algorizmi”. În alte traduceri latine, autorul a fost denumit Algorithmus. De-a lungul timpului, s-a uitat că Algorizmi (Algorithmus) este autorul regulilor, iar aceste reguli au început să fie numite algoritmi. Timp de multe secole, algoritmii au fost dezvoltați pentru a rezolva din ce în ce mai multe clase de probleme, dar însuși conceptul de algoritm nu avea o definiție matematică exactă.

În prezent, conceptul de algoritm a fost clarificat și realizat în secolul XX în cadrul unei științe numite teoria algoritmilor.

Algoritm - instrucțiuni precise și ușor de înțeles către executant pentru a efectua o succesiune de acțiuni care vizează rezolvarea sarcinii.

Algoritm - acţiune secvenţială clar organizată care duce la un anumit rezultat.

Un executor de algoritm este ceva abstract sau realun sistem capabil să efectueze o acțiune prescrisă de un algoritm (tehnic, biologic sau biotehnic).

Executant tehnic- bancomat;

Biologic - o persoană, un organism viu;

Biotehnica - Inteligență artificială.

Proprietățile algoritmului

Discretenie (separare, discontinuitate) - algoritmul trebuie scris ca o succesiune de pași sau etape.

inteligibilitate executantul algoritmului trebuie să știe cum să execute acest algoritm.

Certitudine (determinism) fiecare regulă a algoritmului ar trebui să fie clară, lipsită de ambiguitate și să nu lase loc arbitrarului.

Datorită acestei proprietăți, execuția algoritmului este de natură mecanică și nu necesită instrucțiuni suplimentare.

Eficacitatea(finititudine) algoritmul ar trebui să conducă la rezolvarea problemei într-un număr finit de pași.

Caracter de masă algoritmul este dezvoltat într-un mod general, astfel încât să poată fi aplicat pentru a rezolva probleme similare. În acest caz, datele sursă sunt selectate din unele zone, care sunt numite zona de aplicare a algoritmilor.

Metode de înregistrare a algoritmului

Dacă proprietățile certitudinii și discretității sunt păstrate cu un anumit grad de acuratețe, i.e. în program, o permutare a pașilor este posibilă sau conține pași dezirabili, dar nu obligatorii, atunci acesta nu este un algoritm, ciprescripție algoritmică.

Fiecare algoritm este proiectat pentru un anumit interpret. Poate fi o persoană, un robot, un computer etc. fiecare interpret are propriul său sistem de comandă. Când compuneți un algoritm, trebuie să luați în considerare pentru ce interpret este proiectat. Executantul poate efectua algoritmul fără să se aprofundeze în sensul a ceea ce face, pentru ceea ce face și, totuși, va obține rezultatul dorit. În astfel de cazuri, se spune că algoritmul este executat formal.

Formulare de înregistrare a algoritmului:

Verbal este o descriere a etapelor succesive ale procesării datelor. Algoritmul este o prezentare arbitrară în limbaj natural

Grafic - o succesiune de blocuri interconectate, fiecare dintre acestea corespunzând execuției uneia sau mai multor acțiuni.

O astfel de reprezentare grafică se numește diagramă bloc - un grafic direcționat care indică ordinea de execuție a instrucțiunilor algoritmului.

Forme grafice ale algoritmilor de înregistrare:

Structuri algoritmice de bază

Urmăriți (algoritm liniar) bucle

Ramificare

Urma - comenzile sunt executate una după alta în ordinea în care sunt scrise în algoritm.(Exemplu. Algoritm pentru deschiderea ușii apartamentului: obțineți cheia, introduceți-ogaura cheii, întoarceți numărul necesar de ori, luați cheia, deschideți ușa.închideți ușa)

Ramificare - datele afectează fluxul algoritmului, i.e. in functie de staresunt efectuate anumite acțiuni ale algoritmului.(Exemplu, algoritmul de „a intra” în apartamentul tău: sunați la apartament; dacă este cineva acasă, așteptați să se deschidă ușa șiintră în apartament, dacă nu este nimeni acasă, ia cheia; ...)

Ciclu (repetiție)- în procesul de executare a algoritmului, un anumitset de comenzi. (Exemplu.(Spălarea a 10 farfurii: luați o farfurie, spălați, puneți într-un uscător, luațifarfurie, spălați, puneți într-un uscător etc. până rămâneți fără farfurii.)

4 Aplicarea cunoștințelor acumulate

Sarcină executați comenzile algoritmului cu a = 1, b = 2, c = 3