Acasă › Navigatori › Executarea algoritmului pentru o anumită decizie a executorului. Informatica si tehnologia informatiei. Modalități de a descrie algoritmi

Executarea algoritmului pentru o anumită decizie a executorului. Informatica si tehnologia informatiei. Modalități de a descrie algoritmi

Cuvinte cheie:

algoritm
proprietățile algoritmului
- discretie
- claritate
- certitudine
- eficacitate
- caracter de masă
executor testamentar

caracteristicile interpretului
- gama de sarcini de rezolvat
- miercuri
- mod de operare
- sistem de comandă
executarea formală a algoritmului

3.1.1. Conceptul de algoritm

Fiecare persoană din Viata de zi cu zi, la studiu sau la locul de muncă, rezolvă un număr imens de probleme de complexitate diferită. Problemele complexe necesită multă gândire pentru a găsi o soluție; O persoană rezolvă sarcini simple și familiare fără să se gândească, în mod automat. În cele mai multe cazuri, soluția la fiecare problemă poate fi împărțită în etape (pași) simple. Pentru multe astfel de sarcini (instalare software, asamblarea unui cabinet, crearea unui site web, operarea unui dispozitiv tehnic, achiziționarea unui bilet de avion prin internet etc.) au fost deja dezvoltate și oferite instrucțiuni pas cu pas, care, atunci când este executat consecvent, poate duce la rezultatul dorit.

Exemplul 1. Problema „Găsiți media aritmetică a două numere” se rezolvă în trei pași:

gândește-te la două numere;
adunați două numere în minte;
Împărțiți suma rezultată la 2.

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

mergeți la terminalul de plată;
selectați un operator de telecomunicații;
Introduceti un numar de telefon;
verificați că numărul introdus este corect;
introduceți o bancnotă în acceptorul de bancnote;
așteptați un mesaj despre creditarea banilor în contul dvs.;
primi un cec.

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

Găsirea mediei aritmetice, depunerea banilor într-un cont de telefon și desenarea unui arici sunt, la prima vedere, procese complet diferite. Dar au o caracteristică comună: fiecare dintre aceste procese este descrisă printr-o succesiune de instrucțiuni scurte, a căror respectare strictă vă 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 o persoană.

Algoritmul poate fi o descriere a unei anumite secvențe de calcule (exemplul 1) sau a pașilor de natură non-matematică (exemplele 2-3). Dar, în orice caz, înainte de dezvoltarea sa, condiții inițiale(date de intrare) și ce urmează a fi obținut (rezultat). Putem spune că un algoritm este o descriere a succesiunii de pași în rezolvarea unei probleme, care duce de la datele inițiale la rezultatul cerut.

În general, diagrama de funcționare a algoritmului poate fi reprezentată după cum urmează (Fig. 3.1):

Orez. 3.1.
Schema generală a algoritmului

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

Animațiile „Lucrul cu un algoritm”, „Cel mai mare divizor comun”, „Mel mai mic multiplu comun” (http://school-collection.edu.ru/) vă vor ajuta să vă amintiți câțiva algoritmi studiați în lecțiile de limba rusă și de matematică.

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

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

Lanțul rezultat este rezultatul algoritmului.

Deci, dacă lanțul inițial a fost A#B, 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.

3.1.2. Executor de algoritm

Fiecare algoritm este proiectat pentru un anumit interpret.

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

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

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

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

Sistem de comandă a executorului. O instrucțiune către un executant pentru a efectua o acțiune separată finalizată se numește comandă. Setul tuturor comenzilor care pot fi executate de un executor formează sistemul 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 executantului care îl va executa.

Moduri de operare performer. Pentru majoritatea interpreților, modurile de control direct și controlul 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 oferă mai întâi o secvență completă de comenzi (program), apoi execută toate aceste comenzi în mod automat. Un număr de interpreți lucrează numai într-unul dintre modurile denumite.

Să ne uităm la exemple de interpreți.

Exemplul 5. Performer Țestoasa se mișcă pe ecranul computerului, lăsând o urmă sub forma unei linii. Sistemul de comandă al țestoasei este format din două comenzi:

Dreapta m (unde m este un număr întreg) - face ca direcția de mișcare a țestoasei să se schimbe cu m grade în sensul acelor de ceasornic.

Repetare înregistrare k [<Команда1> <Команда2> ... <Командаn>] înseamnă că secvența comenzilor din paranteze va fi repetată de k ori.

Gândiți-vă ce cifră va apărea pe ecran după ce Țestoasa finalizează următorul algoritm.

Repetați 12 [Dreapta 4 5 Înainte 20 Dreapta 45]

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

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

Folosind acest algoritm, numărul 1 va fi convertit în 15: ((1-3-1)-3-1)-3 = 15.

Exemplul 7. Robotul Performer operează pe un câmp în carouri, între celulele adiacente pot exista pereți. Robotul se deplasează de-a lungul celulelor câmpului și poate executa următoarele comenzi, cărora li se atribuie numere:

Când execută fiecare astfel de comandă, Robotul se deplasează într-o celulă adiacentă în direcția indicată. Dacă există un zid în această direcție între celule, atunci Robotul este distrus. Ce se va întâmpla cu Robotul dacă execută secvența de comenzi 32323 (aici numerele indică numerele de comandă), începând să se miște din 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ă atunci când lovește pereții?

Când dezvoltați un algoritm:

sunt identificate obiectele care apar în problemă, proprietăţile obiectelor, relaţiile dintre obiecte şi acțiuni posibile cu obiecte;
se determină datele inițiale și rezultatul necesar;
se determină succesiunea acțiunilor executantului, asigurând trecerea de la datele inițiale la rezultat;
succesiunea acțiunilor este înregistrată cu ajutorul comenzilor incluse în sistemul de comandă al executantului.

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

3.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, înțelegere, certitudine, eficacitate și caracter de masă.

Proprietatea discretității înseamnă că calea către rezolvarea unei probleme este împărțită în etape (acțiuni) separate. Fiecare acțiune are o instrucțiune (comandă) corespunzătoare. Numai după ce a executat o comandă, executantul poate începe să execute următoarea comandă.

Proprietatea de înțelegere î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 în funcție de care poate efectua acțiunile cerute.

Proprietatea certitudinii înseamnă că algoritmul nu conține comenzi al căror sens poate fi interpretat ambiguu de către executant; Situațiile sunt inacceptabile când, după executarea comenzii următoare, executantului nu este clar ce comandă să execute la pasul următor.

Proprietatea de eficiență înseamnă că algoritmul trebuie să poată obține un rezultat după un număr finit, eventual foarte mare, de pași. În acest caz, rezultatul este considerat nu numai răspunsul determinat de enunțul problemei, ci și concluzia despre imposibilitatea de a continua rezolvarea acestei probleme din orice motiv.

Proprietatea producției de masă înseamnă că algoritmul trebuie să ofere posibilitatea aplicării sale pentru a rezolva orice problemă 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 străzii ar trebui să fie aplicabil oriunde pe stradă, algoritmul pentru prepararea medicamentului ar trebui să fie aplicabil pentru prepararea oricărei cantități din acesta, etc.

Exemplul 8. Să luăm în considerare una dintre metodele de găsire a tuturor numerelor prime care nu depășesc n. Această metodă este numită „sita lui Eratosthenes”, numită după omul de știință grec antic Eratosthenes care a propus-o.

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

notează toate numerele întregi de la 2 la n la rând (2, 3, 4, ..., n);
cadrul 2 - primul număr prim;
tăiați din listă toate numerele divizibile cu ultimul număr prim găsit;
găsiți primul număr nemarcat (numerele marcate sunt numere tăiate sau numere incluse într-un cadru) și închideți-l într-un cadru - acesta va fi un alt număr prim;
repetați pașii 3 și 4 până când nu au mai rămas numere nemarcate.

Vă puteți face o idee mai vizuală a metodei de găsire a numerelor prime folosind animația „Sita lui Eratosthenes” (http://school-collection.edu.ru/).

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

discretitate - procesul de găsire a numerelor prime este împărțit în pași;
înțelegere - fiecare comandă este de înțeles unui elev de clasa a IX-a care execută 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 - după un anumit număr de pași se obține rezultatul;
caracter de masă - succesiunea de acțiuni este aplicabilă pentru orice n natural.

Proprietățile luate în considerare ale algoritmului ne permit să oferim o definiție mai precisă a algoritmului.

3.1.4. Posibilitatea de automatizare a activităților umane

Dezvoltarea unui algoritm este de obicei o sarcină intensivă în muncă, care necesită ca o persoană să aibă cunoștințe profunde, ingeniozitate și mult timp.

Rezolvarea unei probleme folosind un algoritm gata făcut necesită doar executantului să urmeze cu strictețe instrucțiunile date.

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

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

Dacă numărul de obiecte din grămadă este multiplu de 3, atunci dați loc adversarului, altfel începeți jocul.
La următoarea mutare, adaugă de fiecare dată numărul de obiecte luate de adversarul tău la 3 (numărul de obiecte rămase trebuie să fie un multiplu de 3).

Interpretul poate să nu se adâncească în sensul a ceea ce face și să nu motiveze pentru care acționează astfel și nu altfel, adică poate acționa formal. Capacitatea interpretului de a acționa formal oferă posibilitatea automatizării activității umane. Pentru aceasta:

procesul de rezolvare a unei probleme este prezentat ca o succesiune de operatii simple;
este creată o mașină ( dispozitiv automat), capabil să efectueze aceste operații în secvența specificată în algoritm;
o persoană este eliberată de activitățile de rutină, execuția algoritmului este încredințată unui dispozitiv automat.

Cel mai important

Performer - un obiect (persoană, animal, dispozitiv tehnic), capabil să execute un set specific de comenzi. Un interpret formal execută întotdeauna aceeași comandă în același mod. Pentru fiecare executant formal, puteți specifica: gama de sarcini de rezolvat, mediul, sistemul de comandă și modul de operare.

Un algoritm este o descriere a unei secvențe de acțiuni destinate unui anumit executant, care duce de la datele inițiale la rezultatul cerut, care are proprietățile de discretie, înțelegere, certitudine, eficacitate și caracter de masă.

Capacitatea interpretului de a acționa formal oferă posibilitatea automatizării activității umane.

Întrebări și sarcini

Cum se numește un algoritm?
Găsiți sinonime pentru cuvântul „prescripție”.
Dați exemple de algoritmi pe care i-ați studiat la școală.
Cine poate fi executantul algoritmului?
Dați un exemplu de interpret formal. Dați un exemplu când o persoană acționează ca un interpret formal.
Ce comenzi ar trebui să îndeplinească un robot funcțiile de: a) casier într-un magazin; b) un portar; c) un agent de pază?
Ce determină gama de sarcini îndeplinite de executantul „calculator”?
Considerați ca un interpret procesor de cuvinte, disponibil pe computerul dvs. Descrieți gama de sarcini rezolvate de acest interpret și mediul său.
Ce este o echipă, un sistem de comenzi de executant?
Enumerați principalele proprietăți ale algoritmului.
La ce poate duce absența oricărei proprietăți într-un algoritm? Dă exemple.
De ce este important să poți executa formal un algoritm?
Secvența de numere este construită după următorul algoritm: primele două numere ale șirului sunt luate egale cu 1; Fiecare număr următor din succesiune este considerat egal cu suma celor două numere anterioare. Notează primii 10 termeni ai acestei secvențe.
Unele algoritmi obțin un lanț nou dintr-un șir de caractere, după cum urmează. În primul rând, se scrie lanțul original de caractere, după care se scrie lanțul original de caractere în ordine inversă, apoi se scrie litera care urmează în alfabetul rus după litera care a fost pe ultimul loc în lanțul original. Dacă ultimul loc în lanțul inițial este litera Z, atunci litera A este scrisă ca următoarea literă. Lanțul rezultat este rezultatul algoritmului. De exemplu, dacă lanțul original de caractere a fost DOM, atunci rezultatul algoritmului va fi lanțul DOMMODN. Este dat șirul de caractere COM. Câte litere O vor fi în lanțul de simboluri care vor fi obținute dacă aplicați algoritmul acestui lanț și apoi aplicați algoritmul din nou la rezultatul muncii sale?
Găsiți o animație a pașilor algoritmului lui Eratosthenes pe Internet. Utilizați algoritmul lui Eratosthenes pentru a găsi toate numerele prime care nu depășesc 50.
Care va fi rezultatul executării algoritmului de către Turtle (vezi Exemplul 5)?
Notați un algoritm pentru executorul Calculator (exemplul 6), care să nu conțină mai mult de 5 comenzi:
Sistemul de comenzi executor Constructorul este format din două comenzi cărora li se atribuie numere:
Conform primului dintre ele, la numărul din dreapta se adaugă 2, conform celui de-al doilea, numărul se împarte la 2. Cum va fi convertit numărul 8 dacă executantul 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).
În ce celulă ar trebui să fie localizat performerul Robot (exemplul 7) pentru a reveni la ea după executarea algoritmului 3241?

| § 2.1. Algoritmi si executori

Lecția 14
§ 2.1. Algoritmi si executori

Cuvinte cheie:

Algoritm
proprietățile algoritmului (discretitate; înțelegere; 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 studiu sau la locul de muncă rezolvă un număr mare de probleme de complexitate diferită. Problemele complexe necesită multă gândire pentru a găsi o soluție; O persoană rezolvă sarcini simple și familiare fără să se gândească, în mod automat. În cele mai multe cazuri, soluția la fiecare problemă poate fi împărțită în etape (pași) simple. Pentru multe dintre aceste 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, secvențiale a căror implementare poate duce la rezultatul dorit.

Exemplul 1. Problema „Găsiți media aritmetică a două numere” se rezolvă în trei pași:

1) gândiți-vă la două numere;
2) adăugați două numere planificate;
3) Împărțiți suma rezultată la 2.

Exemplul 2. Sarcina „Depuneți bani în contul dvs. 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 un număr de telefon;
4) verificați că numărul introdus este corect;
5) introduceți o bancnotă în acceptorul de bancnote;
6) așteptați un mesaj despre creditarea banilor în contul dvs.;
7) primiți un cec.

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

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

În general, diagrama de funcționare a algoritmului poate fi reprezentată după cum urmează (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 în școală, multe reguli gramaticale, reguli ale construcțiilor geometrice etc.

Animațiile „Lucrul cu un algoritm” (193576), „Cel mai mare divizor comun” (170363), „Mel mai mic multiplu comun” (170390) vă vor ajuta să vă amintiți câțiva algoritmi studiați în lecțiile de limba rusă și de matematică (http://sc.edu. ru /).

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

1. Se calculează lungimea (în caractere) a șirului original de caractere.
2. Dacă lungimea lanțului original este impară, atunci numărul 1 este adăugat la lanțul 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. Numărul 2 se adaugă în dreapta lanțului rezultat.

Lanțul rezultat este rezultatul algoritmului.

Deci, dacă lanțul inițial a fost A#B, 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 proiectat pentru un anumit interpret.

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

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

Moduri de operare performer. 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 oferă mai întâi o secvență completă de comenzi (program), apoi execută toate aceste comenzi automat. Un număr de interpreți lucrează numai într-unul dintre modurile denumite.

Să ne uităm la exemple de interpreți.

Exemplul 5. Performer Țestoasa se mișcă pe ecranul computerului, lăsând o urmă sub forma unei linii.

Sistemul de comandă Turtle 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 de mișcare - în direcția în care se înfruntă capul și corpul său;
2. Dreapta m (unde m este un număr întreg) - provoacă o schimbare a direcției de mișcare a Țestoasei cu t grade în sensul acelor de ceasornic.
Record Repetați k [<Команда1> <Команда2> ... <Командаn>] înseamnă că succesiunea comenzilor din paranteze se va repeta de k ori.

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

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

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

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

Folosind acest algoritm, numărul 1 va fi convertit în 15:

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

Exemplul 7. Robotul Performer operează pe un câmp în carouri, între celulele adiacente pot exista pereți. Robotul se deplasează de-a lungul celulelor câmpului și poate executa următoarele comenzi, cărora li se atribuie numere:

1 sus
2 - jos
3 - corect
4 ramase

Ce se va întâmpla cu Robotul dacă execută secvența de comenzi 32323 (aici numerele indică numerele de comandă), începând să se miște din 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ă atunci când lovește pereții?

Când dezvoltați un algoritm:

1) se identifică obiectele care apar în problemă, 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, asigurând trecerea de la datele inițiale la rezultat;
4) succesiunea acțiunilor este înregistrată folosind comenzi incluse în sistemul de comandă al executantului.

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

2.1.3. Proprietățile algoritmului

Proprietate discretăînseamnă că calea către rezolvarea unei probleme este împărțită în pași (acțiuni) separate. Fiecare acțiune are o instrucțiune (comandă) corespunzătoare. Numai după ce a executat o comandă, executantul poate începe să execute următoarea comandă.

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

Proprietatea certitudiniiînseamnă că algoritmul nu conține comenzi al căror sens poate fi interpretat ambiguu de către executant; Situațiile sunt inacceptabile 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 produce întotdeauna același rezultat.

Proprietatea de performanțăînseamnă că algoritmul trebuie 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 determinat de enunțul problemei, ci și concluzia despre imposibilitatea de a continua rezolvarea acestei probleme din orice motiv.

Proprietatea caracterului de masăînseamnă că algoritmul trebuie să ofere posibilitatea aplicării sale pentru a rezolva orice problemă 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 străzii ar trebui să fie aplicabil oriunde pe stradă, algoritmul pentru prepararea medicamentului ar trebui să fie aplicabil pentru prepararea oricărei cantități din acesta, etc.

Exemplul 8. Să luăm î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ă omul de știință grec antic Eratosthenes (secolul al III-lea î.Hr.) care a propus-o.

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

1) notează pe rând toate numerele naturale de la 2 la n (2, 3, 4, ..., n);
2) cadrul 2 - primul număr prim;
3) tăiaț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 tăiate sau numere incluse într-un cadru) și închideți-l într-un cadru - acesta va fi un alt număr prim;
5) repetați pașii 3 și 4 până când nu au mai rămas numere nemarcate.

Puteți obține o idee mai vizuală a metodei de găsire a numerelor prime folosind animația „Sie of Eratosthenes” (180279) postată în Colecția Unificată de Resurse Educaționale Digitale.

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

discretie- procesul de găsire a numerelor prime se împarte în etape;
intelegere- fiecare comandă este de înțeles unui elev de clasa a VIII-a care execută 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 număr natural n.

Proprietățile luate în considerare ale algoritmului ne permit să oferim o definiție mai precisă a algoritmului.

2.1.4. Posibilitatea de automatizare a activităților umane

Dezvoltarea unui algoritm este de obicei o sarcină intensivă în muncă, care necesită ca o persoană să aibă cunoștințe profunde, ingeniozitate și mult timp.

Rezolvarea unei probleme folosind un algoritm gata făcut necesită doar executantului să urmeze cu strictețe instrucțiunile date.

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

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

1. Dacă numărul de obiecte din grămadă este multiplu de 3, atunci dați loc adversarului, altfel începeți jocul luând 1 sau 2 obiecte astfel încât numărul de obiecte rămase să fie un multiplu de 3.
2. La următoarea mutare, adaugă de fiecare dată numărul de obiecte luate de adversarul tău la 3 (numărul de obiecte rămase trebuie să fie un multiplu de 3).

1) procesul de rezolvare a unei probleme este prezentat ca o succesiune de operatii simple;
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

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

Un interpret formal execută întotdeauna aceeași comandă în același mod. Pentru fiecare executor 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 executant care duce de la datele inițiale la rezultatul solicitat, care are proprietățile de discretie, înțelegere, certitudine, eficacitate și caracter 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 de prezentare pentru paragraful conținut în aplicație electronică la manual. Prezentarea completează informațiile conținute în textul paragrafului? Ce diapozitive ai putea adăuga la prezentarea ta?

2. Ce se numește algoritm?

3. Alegeți sinonime pentru cuvântul „prescripție”.

4. Dați exemple de algoritmi pe care i-ați studiat la școală.

5. Cine poate fi executantul algoritmului?

6. Dați un exemplu de interpret formal. Dați un exemplu când o persoană acționează ca un interpret formal.

7. Ce determină gama de sarcini îndeplinite de executantul „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 echipă, un sistem de comenzi de executant?

10. Ce comenzi ar trebui să îndeplinească un robot următoarele funcții:

a) 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 absența oricărei proprietăți într-un algoritm? Dă exemple.

13. Care este importanța de a putea executa formal un algoritm?

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 considerat egal cu suma celor două numere anterioare. Notează primii 10 termeni ai acestei secvențe. Aflați cum se numește această secvență.

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

16. Găsiți o animație a pașilor algoritmului lui Eratostene pe Internet. Utilizați algoritmul lui Eratosthenes pentru a găsi toate numerele prime care nu depășesc 50.

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

18. Notați un algoritm pentru executorul Calculator (vezi exemplul 6), care să nu conțină mai mult de 5 comenzi:

a) primirea de la numărul 3 a numărului 16;
b) primirea de la numărul 1 a numărului 25.

19. Sistemul comenzilor executantului Constructorul este format din două comenzi cărora li se atribuie numere:

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

Conform primului dintre ele, la numărul din dreapta se adaugă 2, conform celui de-al doilea, numărul se împarte la 2. Cum va fi convertit numărul 8 dacă executantul 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ă fie localizat performerul Robot (exemplul 7) pentru a reveni la ea după executarea algoritmului 3241?

Software gratuit:

Sistem KuMir - Set de lumi educaționale (descărcați arhiva programului de pe site) sau vizitați pagina KuMir ((http://www.niisi.ru/kumir/)

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

În această lecție ne vom uita la câteva concepte teoretice care formalizează conceptul de programare. În același timp, vom formula mai precis sarcina principală a pregătirii dumneavoastră.

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

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

Sper că totul a funcționat pentru tine. Acum, folosind acest exemplu, vom descrie câteva concepte de bază:

executor testamentar;
sistem de comenzi executant;
algoritm.

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

O persoană, mașină sau dispozitiv care poate executa unele 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 le poate executa este numit sistem de comenzi executorii.

Secvența de comenzi pe care un executant trebuie să le execute pentru a rezolva o problemă se numește algoritm.

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

Executorul 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!” O poți nota mai precis, dar nu se va întâmpla nimic, pentru că... executantul unor astfel de comenzi nu știe.

Puteți nota comenzile disponibile î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 individuali mici, fiecare dintre care va fi înțeles de executant. Principiul „împărțiți și cuceriți” este din nou la lucru.

Artistul face exact ceea ce algoritmul îi spune să facă.

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

Programele tale viitoare nu vor funcționa adesea așa cum ai vrut. Greșelile se întâmplă tuturor. Aici este important să înțelegeți că nu computerul este prost, dar ați făcut o greșeală la algoritm. Nu fiți ca programatorii răi, pentru care programul este întotdeauna de vină pentru tot.

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

Care este scopul principal al predării noțiunilor de bază ale programării? Stăpânește abilitățile de gândire algoritmică. Adică, învățați să scrieți 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.

Un algoritm este o descriere precisă a ordinii acțiunilor pe care trebuie să le efectueze un executant pentru a rezolva o problemă.

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

Cuvântul „algoritm” provine de la numele matematicianului arab al-Khwarizmi din secolul al IX-lea, 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ă, ordinea de gătit, instrucțiuni etc.)

Executor de algoritm– acesta este cel care execută algoritmul (persoană, animal, mașină, computer).

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

De exemplu, performer Robotul poate executa comenzi înainte, înapoi, stânga, dreapta, pictură. Se mișcă printr-un câmp celular delimitat de un perete și care conține pereți. Robotul nu poate trece prin perete.

Proprietățile algoritmului:

1.Performanță (membru)– capacitatea de a obține un rezultat din datele inițiale într-un număr finit de pași. (De exemplu, atunci când se execută algoritmul de adunare a 2 numere, ar trebui să se obțină suma).

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

3.Determinism(certitudine, acuratețe) – fiecare comandă trebuie să determine în mod unic acțiunea executantului.

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

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

Modalități de a scrie algoritmul:

1) În limbaj natural – înregistrarea sub formă de comenzi separate într-un limbaj înțeles de oameni.

2) Grafic – în limbajul organigramelor, folosind forme geometrice (oval, dreptunghi, paralelogram, romb).

3) Într-un limbaj algoritmic - un limbaj pentru scrierea algoritmilor pentru predarea programarii. Comenzile sunt scrise î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ă; imagine pe diagrame bloc. Împărțirea sarcinilor în subsarcini. Algoritmi auxiliari.

Proiecte algoritmice.În cadrul algoritmilor se pot distinge grupuri de pași care diferă ca structură internă - construcții algoritmice.

Construcții algoritmice de bază sunt o secvență liniară de pași (sau următoarele), ramificații și bucle.

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

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

Exemplu: algoritm pentru pornirea computerului:

Porniți computerul (apăsați butonul pornit val protector).
Porniți monitorul și imprimanta.
Clic Butonul de pornire pe unitate de sistem.
Așteptați încărcarea sistem de operareși aspectul desktopului.
Treci la treabă.

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

În structura algoritmică " ramificare" 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 operatori de comparare (>,<, =, >=, <=).

Înregistrare în limbaj algoritmic: IfCondition Then Series 1 (Dacă Condiție adevărat, apoi adevărat Episodul 1, Dacă Condiție false, atunci nu se execută nimic). Exemplu: Dacă astăzi este duminică, atunci nu este nevoie să mergi la școală. Forma completă de ramificare

În structuri algoritmice ciclu include o serie de comenzi care sunt executate în mod repetat. Această secvență de comenzi este numită corpul buclei.

Există două tipuri de structuri algoritmice ciclice:

bucle contracate, î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ă.

Bucla cu contor– folosit când se știe dinainte câte repetări ale corpului buclei trebuie efectuate.

Algoritmul și proprietățile acestuia.

Algoritm- o instrucțiune clară și precisă către executant pentru a executa secvența finală de comenzi care conduc de la datele inițiale la rezultatul dorit.

Executor de algoritm- acesta este obiectul sau subiectul pentru care algoritmul este proiectat să îl controleze.

Sistemul de comandă al executantului (SCS) este întregul set de comenzi pe care executantul le poate executa.

Proprietăți ale algoritmului: înțelegere, acuratețe, caracter finit.

Claritate: algoritmul este compus doar din comenzi incluse în SKI-ul executantului.

Precizie: Fiecare comandă a algoritmului de control determină acțiunea fără ambiguitate a executantului.

Finisaj (sau performanță): execuția algoritmului trebuie să conducă la un rezultat într-un număr finit de pași.

Mediul interpretului: mediul în care operează interpretul.

O anumită secvență de acțiuni ale interpretului se aplică întotdeauna unora date sursă. De exemplu, pentru a pregăti un fel de mâncare după o rețetă culinară, aveți nevoie de produsele (date) corespunzătoare. Pentru a rezolva o problemă matematică (rezolvarea unei ecuații pătratice), aveți nevoie de date numerice inițiale (coeficienți de ecuație).

Setul complet de date: un set de date necesar și suficient pentru a rezolva sarcina (obține rezultatul dorit).

Metode de scriere a algoritmilor.

Cele mai comune metode sunt: grafic, verbal si in forma programe de calculator.

Metoda grafică presupune utilizarea anumitor simboluri grafice – blocuri.

Nume bloc	Desemnarea blocului	Conţinut
Proces		Procesarea datelor
Luarea deciziilor		Un bloc logic pentru verificarea adevărului sau falsității unei anumite condiții
Transfer de date		Intrarea sau ieșirea de informații
Start Stop		Începutul sau sfârșitul programului
Modificare		Organizarea unui proces ciclic - antet ciclu

Colecția de blocuri formează așa-numita organigrama algoritmului.

Înregistrare verbală algoritmii sunt concentrați în primul rând pe interpretul uman și permit înregistrarea diferită a instrucțiunilor, dar înregistrarea trebuie să fie destul de precisă.

La scrierea algoritmilor sub forma programe calculatoarele folosesc limbaje de programare - sisteme pentru codificarea instrucțiunilor și regulile de utilizare a acestora. Scrierea algoritmilor sub formă de programe se caracterizează printr-un grad ridicat de formalizare.

Algoritmi pentru lucrul cu marimi. Structuri algoritmice de bază.

O cantitate este un singur obiect de informare care are un nume, o valoare și un tip.

Realizatorul algoritmilor de lucru cu cantități poate fi o persoană sau un dispozitiv tehnic special, cum ar fi un computer. Un astfel de interpret trebuie să aibă memorie pentru depozitarea cantităților.

Cantitatile pot fi constante sau variabile.

Valoare constantă (constant) nu își modifică valoarea în timpul execuției algoritmului. O constantă poate fi notată prin propria sa valoare (numerele 10, 3.5) sau printr-un nume simbolic (numărul ).

Valoare variabilă poate modifica valoarea în timpul executării algoritmului. O variabilă este întotdeauna desemnată printr-un nume simbolic (X, A, R5 etc.).

Tip de cantitate definește setul de valori pe care o valoare le poate lua și setul de acțiuni care pot fi efectuate cu acea valoare. Tipuri de bază de mărimi: întregi, reale, simbolice, logice.

Expresie- o înregistrare care definește succesiunea acțiunilor asupra cantităților. O expresie poate conține constante, variabile, semne de operare și funcții. Exemplu:

A + B; 2*X-Y; K + L - sin(X)

O comandă de atribuire este o comandă a executorului care are ca rezultat o variabilă care primește o nouă valoare. Format de comandă:

nume variabilă>:=expresie>

Comanda de atribuire este executată în următoarea ordine: mai întâi se calculează, apoi valoarea rezultată este atribuită unei variabile.

Exemplu. Fie ca variabila A să aibă valoarea 6. Ce valoare va primi variabila A după executarea comenzii: A:= 2 * A - 1?
Soluţie. Calcularea expresiei 2*A - 1 cu A=6 va da numărul 11. Aceasta înseamnă că noua valoare a variabilei A va fi egală cu 11.

În cele ce urmează se va presupune că executantul algoritmilor de lucru cu marimi este un calculator. Orice algoritm poate fi construit din comenzi sarcinile, intrare, ieșire, ramificareȘi ciclu.

Comanda de intrare- o comandă prin care valorile variabilelor sunt setate prin dispozitive de intrare (de exemplu, o tastatură).

Exemplu: intrare A - introducerea valorii variabilei A de la tastatura computerului.

Comanda de ieșire: o comandă care afișează valoarea unei cantități pe un dispozitiv de ieșire a computerului (cum ar fi un monitor).

Exemplu: concluzie X - valoarea variabilei X este afișată pe ecran.

Comanda de filială- împarte algoritmul în două căi în funcție de o anumită condiție; apoi execuția algoritmului trece la continuarea generală. Ramificarea poate fi completă sau incompletă. Descrierea ramificării în diagrame bloc și în limbaj algoritmic:

Aici, o serie înseamnă una sau mai multe comenzi secvențiale; kv - capăt de ramificare.

Comanda buclă asigură executarea repetată a unei secvențe de comenzi (corpul buclei) pe baza unei anumite condiții.

Buclă cu precondiție- o buclă a cărei execuție se repetă până când condiția buclei este adevărată:

Buclă cu parametru- execuția repetată a corpului buclei în timp ce parametrul întreg parcurge setul tuturor valorilor de la inițial (In) la final (Ik):

Exemplu. Sunt date două fracții simple. Creați un algoritm pentru obținerea unei fracții care este rezultatul împărțirii lor.
Soluţie.În formă algebrică, soluția problemei arată astfel:
a/b: c/d = a*d/b*c = m/n
Datele inițiale sunt patru mărimi întregi: a, b, c, d. Rezultatul este două numere întregi m și n.

algîmpărțirea fracțiilor
intact a, b, c, d, m, n
începe intrarea a, b, c, d
m:=a*d
n:=b*c
ieșire „Numerator=", m
ieșire „Numitor=", n
koi

Vă rugăm să rețineți că pentru a afișa text (orice secvență de caractere), acesta trebuie să fie scris între ghilimele în comandă concluzie.

Efimova O., Morozov V., Ugrinovich N. Curs de tehnologie informatică cu bazele informaticii. Tutorial pentru liceu. - M.: SRL „Editura AST”; ABF, 2000
Cartea-atelier de probleme în informatică. În 2 volume/Ed. I. Semakina, E. Henner. - M.: Laboratorul de Cunoștințe de bază, 2001.
Ugrinovich N. Informatica si tehnologia de informație. Clasele 10-11 - M.: Laboratorul de Cunoștințe de bază, SA „Manuale de la Moscova”, 2001

Sarcini și teste pe tema „Algoritmi și executori”

Desenitor pentru managementul artistului - Algoritmi clasa a VI-a
Lecții: 4 Teme: 9 Teste: 1
2 Sarcini: 9 Teste: 1

Draga student!

Cunoașterea subiectului „Algoritmi și executanți” este necesară în primul rând pentru studierea ulterioară a programării. Limbajul de programare QBasic a fost ales ca bază pentru studiul programării. Am abandonat ideea de a include Visual Basic sau orice alt limbaj de programare orientat pe obiecte în cursul nostru, deoarece această abordare nu a fost încă utilizată pe scară largă în majoritatea școlilor secundare din Federația Rusă. În plus, programarea orientată pe obiecte se bazează pe principiile programării clasice Dos.

Cursul nostru este conceput pentru programul de educație generală. Când vă pregătiți pentru examenele de admitere în tehnologia informației la universități, trebuie să vă familiarizați cu specificul studiului de programare la o anumită universitate. În unele cazuri, este necesar un studiu aprofundat al unui număr de subiecte, de exemplu, „Matrice”. Ar trebui să acordați atenție acestui lucru atunci când studiați literatura de programare; poate ar trebui să utilizați recomandări metodologice privind pregătirea pentru examene, care sunt publicate în prezent în majoritatea instituțiilor de învățământ superior.

În concluzie, remarcăm că realizarea „acrobației” în programare este posibilă doar cu practică constantă și rezolvarea unor probleme specifice aplicate.

Popular în categoria: