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.

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 de codificare a 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.

Comandă 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.

1. Efimova O., Morozov V., Ugrinovich N. Curs de tehnologie informatică cu bazele informaticii. Manual pentru liceu. - M.: SRL „Editura AST”; ABF, 2000
2. Cartea-atelier de probleme în informatică. În 2 volume/Ed. I. Semakina, E. Henner. - M.: Laboratorul de Cunoștințe de bază, 2001.
3. Ugrinovich N. Informatică și tehnologii informaționale. 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 despre programare; poate ar trebui să utilizați recomandările metodologice pentru 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.

7.1. Ce este un algoritm?

Numele „algoritm” provine din forma latină a numelui matematicianului din Asia Centrală al-Khwarizmi - Algorithmi. Algoritmul este unul dintre conceptele de bază ale informaticii și matematicii.

7.2. Ce este un "Algorithm Executor"?

Interpretul se caracterizează prin:

• • Miercuri;
  • acțiuni elementare;
  • sistem de comandă;
  • refuzuri.

miercuri(sau decorul) este „habitatul” interpretului. De exemplu, pentru interpretul Robot din manualul școlar, mediul este un câmp celular infinit. Pereții și celulele pictate fac, de asemenea, parte din mediu. Iar locația lor și poziția robotului însuși au stabilit un specific starea mediului.

Sistem de comandă. Fiecare executant poate executa comenzi doar dintr-o anumită listă strict specificată - sistemul de comenzi executor. Pentru fiecare comandă trebuie specificată conditii de aplicabilitate(în care stări de mediu poate fi executată comanda) și descris rezultatele executării comenzii. De exemplu, comanda Lucrare „sus” poate fi executată dacă nu există niciun zid deasupra Lucrării. Rezultatul său este deplasarea Robotului cu o celulă în sus.

După apelarea comenzii, executantul execută corespunzătoare acţiune elementară .

Eșecuri erori de executor apar dacă o comandă este apelată într-o stare de mediu care este inacceptabilă pentru aceasta.

În informatică, executorul universal al algoritmilor este calculator.

7.3. Ce proprietăți au algoritmii?
Principalele proprietăți ale algoritmilor sunt următoarele:

Intelegere pentru interpret - i.e. Executorul algoritmului trebuie să știe cum să-l execute.

Discretenie(discontinuitate, separare) - i.e. Algoritmul trebuie să reprezinte procesul de rezolvare a unei probleme ca o execuție secvențială a unor pași (etape) simple (sau definiți anterior).

Certitudine- adica Fiecare regulă a algoritmului trebuie 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 sau informații suplimentare despre problema rezolvată.

Eficacitatea (sau membru). Această proprietate este că algoritmul trebuie să conducă la rezolvarea problemei într-un număr finit de pași.

Caracter de masă. Aceasta înseamnă că algoritmul de rezolvare a problemei este dezvoltat într-o formă generală, adică. ar trebui să fie aplicabilă pentru o anumită clasă de probleme care diferă doar în datele inițiale. În acest caz, datele inițiale pot fi selectate dintr-o anumită zonă, care se numește zona de aplicabilitate a algoritmului.

Conceptul de algoritm

Limbaje algoritmice

Algoritmi. Algoritmizare.

Conceptul de algoritm este la fel de fundamental pentru informatică ca și conceptul de informație. De aceea este important să o înțelegem.

Nume "algoritm" provine din forma latină a numelui celui mai mare matematician din Asia Centrală Muhammad ibn Musa al-Khwarizmi(Alhorithmi), care a trăit în 783-850. În cartea sa „On Indian Counting”, el a subliniat regulile de scriere a numerelor naturale folosind cifre arabe și regulile de lucru cu ele într-o „coloană”, care sunt acum familiare oricărui școlar. În secolul al XII-lea, această carte a fost tradusă în latină și a devenit larg răspândită în Europa.

În fiecare zi, o persoană întâmpină nevoia de a respecta anumite reguli, de a efectua diverse instrucțiuni și instrucțiuni. De exemplu, când traversezi drumul la o intersecție fără semafor, trebuie mai întâi să te uiți la stânga. Dacă nu sunt mașini, atunci traversați pe jumătate, iar dacă sunt mașini, așteptați până trec, apoi traversați pe jumătate. După aceea, priviți în dreapta și, dacă nu sunt mașini, apoi traversați drumul până la capăt, iar dacă sunt mașini, așteptați până trec, apoi traversați drumul până la capăt.

În matematică, pentru a rezolva probleme tipice, folosim anumite reguli care descriu secvențe de acțiuni. De exemplu, reguli pentru adunarea fracțiilor, rezolvarea ecuațiilor pătratice etc. De obicei, orice instrucțiuni și reguli sunt o succesiune de acțiuni care trebuie efectuate într-o anumită ordine. Pentru a rezolva o problemă, trebuie să știți ce este dat, ce ar trebui să fie primit și ce acțiuni și în ce ordine ar trebui efectuate pentru a face acest lucru. O prescripție care determină ordinea în care sunt efectuate acțiunile asupra datelor pentru a obține rezultatele dorite este un algoritm.

Algoritm- o instrucțiune predeterminată, clară și precisă pentru un posibil executant să efectueze o anumită secvență de acțiuni pentru a obține o soluție la o problemă într-un număr finit de pași.

Aceasta nu este o definiție în sensul matematic al cuvântului, ci mai degrabă Descriere concept intuitiv al unui algoritm, dezvăluind esența acestuia.

Conceptul de algoritm nu este doar unul dintre conceptele principale ale matematicii, ci și unul dintre conceptele principale ale științei moderne. Mai mult, odată cu apariția erei informaticii, algoritmii devin unul dintre cei mai importanți factori ai civilizației.

Executor de algoritm- acesta este un sistem abstract sau real (tehnic, biologic sau biotehnic) capabil să efectueze acțiuni prescrise de algoritm.

Interpretul se caracterizează prin:

• Miercuri;
• acțiuni elementare;
• sistem de comandă;
• refuzuri.

miercuri(sau decorul) este „habitatul” interpretului. De exemplu, pentru interpretul Robot din manualul școlar, mediul este un câmp celular infinit. Pereții și celulele pictate fac, de asemenea, parte din mediu. Iar locația lor și poziția robotului însuși au stabilit un specific starea mediului.

Sistem de comandă. Fiecare executant poate executa comenzi doar dintr-o anumită listă strict specificată - sistemul de comenzi executor. Pentru fiecare comandă trebuie specificată conditii de aplicabilitate(în care stări de mediu poate fi executată comanda) și descris rezultatele executării comenzii. De exemplu, comanda Lucrare „sus” poate fi executată dacă nu există niciun zid deasupra Lucrării. Rezultatul său este deplasarea Robotului cu o celulă în sus.

După apelarea comenzii, executantul execută corespunzătoare acţiune elementară.

Eșecuri erori de executor apar dacă o comandă este apelată într-o stare de mediu care este inacceptabilă pentru aceasta.

În informatică, executorul universal al algoritmilor este calculator.

| § 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 de bani în contul dvs.;
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-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 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.

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, 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

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:

Î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

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:

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

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ă.

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.

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ă.

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).

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:

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ținute în anexa electronică la manual. Prezentarea completează informațiile conținute în textul paragrafului? Ce diapozitive ai putea folosi pentru a-ți completa prezentarea?

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/)

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

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.

Un algoritm este o secvență clară și precisă de acțiuni care descrie procesul de transformare a unui obiect din starea inițială în starea finală.

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

Interpret Algoritmul poate fi fie o persoană (rețete de gătit, diverse instrucțiuni, algoritmi pentru calcule matematice), fie un dispozitiv tehnic. Sunt diverse mașini (calculatoare, roboți industriali, aparate electrocasnice moderne). executorii formali algoritmi. Un interpret formal nu este obligat să înțeleagă esența problemei rezolvate, ci trebuie să execute cu precizie o secvență de comenzi.

Algoritmul poate fi scris în diverse moduri (descriere verbală, descriere grafică - diagramă bloc, program într-unul dintre 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 sarcinii (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);

claritate (toate comenzile algoritmului sunt incluse în sistemul de comenzi executor);

eficacitate (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 puteți rezolva multe probleme similare).

Modalități de a descrie algoritmi

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

Să dăm un exemplu de descriere a algoritmului de însumare a două mărimi sub forma unei diagrame bloc:

Acest mod de a descrie algoritmul este cel mai vizual ș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 organigrame și abia apoi creează un program pe una dintrelimbaje de programare .

Structuri algoritmice tipice

Programatorul are posibilitatea de a construi și utiliza structuri algoritmice atipice, cu toate acestea, acest lucru nu este necesar. Orice algoritm, oricât de complex, poate fi dezvoltat pe baza a trei structuri tipice: urmărire, ramificare și repetiție. În acest caz, structurile pot fi amplasate secvenţial una după alta sau imbricate unele în altele.

Structura liniară (urmează)

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

Ramificare

ÎN 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 doar a doua ramură.

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

Din mai multe ramuri puteți construi o structură „ alegere”(ramificarea multiplă), care va alege nu dintre două, ci dintr-un număr mai mare de opțiuni pentru acțiunile interpretului, în funcție de mai multe condiții. Este important ca o singură ramură să fie executată - î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 diverse tipuri de algoritmi ciclici, 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», bucle cu un contor.În buclele „until” și „while”, o expresie logică (condiție) poate precede corpul buclei ( buclă cu precondiție) sau încheie bucla ( buclă cu postcondiție).

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

Cicluri « Pa» - repetarea corpului ciclului atâta timp cât condiția este îndeplinită(Adevărat):

Bucle cu contor(cu parametru)– repetarea corpului buclei de un număr specificat de ori:

Algoritm auxiliar (subrutină, procedură)

Algoritm auxiliar este un modul care poate fi accesat în mod repetat din algoritmul principal. Utilizarea algoritmilor auxiliari poate reduce semnificativ dimensiunea algoritmului și poate simplifica dezvoltarea acestuia.

Metode de dezvoltare a algoritmilor complexi

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

Metoda de detaliere secvenţială a sarcinilor(„de sus în jos”) este că sarcina complexă inițială este împărțită în subsarcini. Fiecare dintre sarcinile secundare este luată în considerare și rezolvată separat. Dacă oricare dintre sarcinile secundare este complexă, acestea sunt, de asemenea, împărțite în subsarcini. Procesul continuă până când subsarcinile sunt reduse la cele elementare. Soluțiile la subprobleme individuale sunt apoi combinate î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 și să rezolve subprobleme locale. Aceasta este o condiție necesară pentru dezvoltarea rapidă a software-ului.

Metoda de asamblare(“de jos în sus”) constă în crearea unei varietăți de module software care implementează soluția problemelor tipice. Atunci când rezolvă o problemă complexă, un programator poate folosi modulele dezvoltate ca algoritmi (proceduri) auxiliari. In multe sisteme de programare Există deja seturi similare de module, ceea ce simplifică și accelerează semnificativ crearea unui algoritm complex.

Algoritmi și procese de control

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

Î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. Este numită o secvență de comenzi pentru a controla un obiect care duce la un scop predeterminat algoritm de control. În consecință, obiectul de control poate fi numit executorul algoritmului de control. În exemplul luat în considerare, 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 decizii 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.

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

Până la începutul subiectului