ALGORITMUL - reguli de sistem formulate într-un limbaj simplu la executor, care definește trecerea de la acceptabil la unele date inițiale, iar rezultatul are numere de proprietăți, determinarea definiteness membrelor.
Cuvântul "algoritm" a devenit din nou comun cu apariția computerelor electronice pentru a desemna totalitatea acțiunilor care formează un anumit proces. Aici ne referim nu numai la procesul de rezolvare a unei anumite probleme matematice, ci și la o rețetă culinară și instrucțiuni pentru utilizarea unei mașini de spălat și multe alte reguli secvențiale care nu sunt relevante pentru matematică - toate aceste reguli sunt algoritmi. Cuvântul "algoritm" este cunoscut tuturor în zilele noastre, a intrat cu încredere în conversația care acum este adesea în paginile ziarelor, în discursurile politicienilor există expresii "algoritm de comportament", "algoritm de succes" etc.
Problema definirii conceptului de "algoritm".
Timp de mai multe secole, conceptul algoritmului a fost asociat cu numere și acțiuni relativ simple asupra lor, iar matematica în sine a fost, în cea mai mare parte, o știință de calcul, o știință aplicată. Cel mai adesea, algoritmii au fost prezentați sub formă de formule matematice. Ordinea etapelor elementare ale algoritmului a fost stabilită prin aranjarea parantezelor, iar etapele în sine au constat în efectuarea operațiilor aritmetice și a operațiilor de relaționare (verificarea egalității, inegalității etc.). Adesea, calculele erau greoaie, iar calculele efectuate manual au consumat mult timp, dar esența procesului de calcul a rămas evidentă. Matematicienii nu aveau nevoie de conștientizarea și definirea strictă a conceptului de algoritm, în generalizarea lui. Dar odată cu dezvoltarea matematicii, au apărut noi obiecte care aveau nevoie să funcționeze: vectori, grafice, matrici, seturi etc. Cum se definește unicitatea pentru ei sau cum se stabilește finitudinea algoritmului, care pași sunt considerați elementari? În anii 1920, sarcina de a defini cu exactitate conceptul de algoritm a devenit una dintre problemele centrale ale matematicii. La acea vreme, au existat două puncte de vedere asupra problemelor matematice:
Toate problemele sunt solvabile algoritmic, dar pentru unii, algoritmul nu este încă găsit, deoarece secțiunile corespunzătoare ale matematicii nu au fost încă dezvoltate.
Există probleme pentru care algoritmul nu poate exista deloc.
Ideea existenței unor probleme care nu pot fi rezolvate din punct de vedere al algoritmului sa dovedit a fi corectă, dar pentru ao justifica, a fost necesară o definiție precisă a algoritmului. Încercările de a dezvolta o astfel de definiție au dus la apariția unei teorii a algoritmilor, care a inclus lucrările multor matematicieni renumiți - K. Gedel. K. Cherch, S. Clini, A. Turing. E.Post, A.Markov, A.Kolmogorov și mulți alții.
Definirea exactă a conceptului algoritmului a făcut posibilă demonstrarea indecidabilității algoritmice a multor probleme matematice.
Apariția primelor proiecte de calculatoare a stimulat studiul posibilităților de aplicare practică a algoritmilor, a căror utilizare, datorită muncii lor, nu a fost disponibilă anterior. Dezvoltarea în continuare a tehnologiei informatice a determinat dezvoltarea aspectelor teoretice și aplicate ale studiului algoritmilor.
Noțiunea de "algoritm".
În viața de zi cu zi, fiecare persoană se confruntă cu nevoia de a rezolva probleme de complexitate foarte diferite. Unele dintre ele sunt dificile și necesită o reflecție lungă pentru a găsi soluții (și uneori nu pot fi găsite), în timp ce altele, dimpotrivă, sunt atât de simple și familiare încât sunt rezolvate automat. În acest caz, chiar și sarcina cea mai simplă este efectuată în mai mulți pași succesivi (pași). Într-o secvență de etape poate fi descrisă ca procesul de rezolvare a multor probleme, cunoscute din matematică școlare: reducerea fracțiilor la un numitor comun, soluția sistemului de ecuații liniare prin eliminarea succesivă a necunoscutelor, construirea unui triunghi pe trei laturi cu rigla și compasul, etc. O astfel de secvență de pași în rezolvarea unei probleme se numește algoritm. Fiecare acțiune individuală reprezintă etapa algoritmului. Secvența de pași ai algoritmului este strict fixată, adică pașii trebuie să fie ordonați. Este adevărat că există algoritmi paralele pentru care această cerință nu este respectată.
Conceptul de algoritm se apropie de alte concepte, cum ar fi metoda (metoda Gauss de rezolvare a sistemelor de ecuații liniare), metoda (metoda de construire a unui triunghi pe trei laturi cu ajutorul unei busole și a unui conducător). Este posibil să se formuleze principalele caracteristici ale algoritmilor.
Prezența datelor inițiale și a unui anumit rezultat.
Un algoritm este o instrucțiune precis definită, aplicându-i în mod consecvent datele originale, puteți obține o soluție la problemă. Pentru fiecare algoritm există un set de obiecte care sunt acceptabile ca date de intrare. De exemplu, în algoritmul de împărțire a numerelor reale, dividendul poate fi orice, iar divizorul nu poate fi zero.
Masa, adică capacitatea de a aplica de mai multe ori același algoritm. Algoritmul servește, de regulă, pentru a rezolva nu o problemă specifică, ci o anumită clasă de probleme. Deci, algoritmul de adăugare este aplicabil oricărei perechi de numere naturale.
Determinism.
Atunci când se aplică algoritmul la aceleași date inițiale, același rezultat ar trebui să fie întotdeauna obținut, de exemplu, procesul de conversie a informațiilor în care este implicată tossing-ul monedei nu este determinist și nu poate fi numit algoritm.
Eficacitate.
Execuția algoritmului trebuie să conducă în mod necesar la finalizarea acestuia. În același timp, este posibil să se dea exemple de algoritmi formali infinit utilizați pe scară largă în practică. De exemplu, algoritmul sistemului de colectare a datelor meteorologice constă în repetarea continuă a succesiunii acțiunilor ( „temperatura aerului măsură“, „determină presiunea atmosferică“) realizată cu o anumită frecvență (un minut, o oră) în timpul duratei de viață a sistemului.
Certitudine.
La fiecare pas al algoritmului, interpretul trebuie să aibă suficiente informații pentru a-l executa. În plus, interpretul trebuie să știe în mod clar cum se efectuează. trepte manual ar trebui să fie relativ simplu, elementar, și contractantul ar trebui să înțeleagă în mod clar semnificația fiecărei etape a secvenței de acțiuni care alcătuiesc algoritmul (calculul suprafeței dreptunghiului pentru orice artist ar trebui să poată să se înmulțească și să interpreteze semnul «x» este multiplicarea). Prin urmare, alegerea formei de reprezentare a algoritmului este foarte importantă. De fapt, vorbim despre limba în care este scris algoritmul.
Forme de reprezentare a algoritmilor.
Pentru a scrie algoritmi, aveți nevoie de o anumită limbă și este foarte important, care limbă este aleasă. Înregistrarea algoritmilor în limba rusă (sau orice altă limbă naturală) este greoaie și incomodă.
De exemplu, descrierea algoritmului Euclid de a găsi GCD (cel mai mare divizor comun) a două numere întregi pozitive poate fi reprezentat în trei etape. Pasul 1: Împărțiți m cu n. Fie p restul diviziei.
Pasul 2: Dacă p este zero, atunci n este originalul GCD.
Pasul 3: Dacă p nu este zero, atunci m este egal cu n. și n este egal cu p. Reveniți la pasul 1.
Articole similare
Trimiteți-le prietenilor: