Algoritm

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Notă despre dezambiguizare.svg Dezambiguizare - Dacă sunteți în căutarea altor semnificații, consultați Algoritmul (dezambiguizarea) .

Un algoritm este o strategie care este utilizată pentru a rezolva o problemă și constă dintr-o secvență finită de operații (numită și instrucțiuni), care vă permite să rezolvați toate întrebările din aceeași clasă. Trebuie să fie:

  • finit, adică atunci când constă dintr-un număr finit de instrucțiuni și are un final;
  • determinist, adică la pornirea de la aceleași date de intrare , se obțin aceleași rezultate de ieșire;
  • fără ambiguități, operațiunile trebuie să poată fi interpretate în același mod de toată lumea, chiar dacă executorul este diferit;
  • general, adică atunci când soluția este aceeași pentru toate problemele din aceeași clasă.

Termenul derivă din transcrierea latină a numelui matematicianului persan al-Khwarizmi , [1] care a trăit în secolul al 9-lea d.Hr. , care este considerat unul dintre primii autori care s-au referit la acest concept atunci când a scris cartea Restaurare și reducere reguli .

Cele mai vechi noțiuni de algoritm se găsesc în documente care datează din secolul al XVII-lea î.Hr. , cunoscute sub numele de papirusurile Ahmes , care conțin o colecție de probleme cu soluția lor, inclusiv o problemă de multiplicare pe care scriitorul susține că a copiat-o din alte papirusuri înainte de 12 secole. .

Algoritmul este un concept fundamental al informaticii , în primul rând pentru că este baza noțiunii teoretice de calculabilitate : o problemă poate fi calculată atunci când poate fi rezolvată folosind un algoritm. Mai mult, algoritmul este un concept cheie chiar și în faza de programare a dezvoltării software-ului : luând automat o problemă, programarea constituie în esență traducerea sau codarea unui algoritm pentru această problemă într-un program , scris într-un anumit limbaj , pe care îl poate prin urmare, să fie efectiv executat de un computer prin reprezentarea logicii sale de procesare .

Definiție

În secolul al XX-lea , conceptul de algoritm a fost formalizat pentru a rezolva problema matematică a „deciziei” ( Entscheidungsproblem ), pusă de David Hilbert în 1928, iar alte formalizări ulterioare au venit odată cu dezvoltarea conceptelor de „ calculabilitate efectivă[2]. și a „metodei eficiente” [3] . Cele mai cunoscute formalizări matematice sunt funcțiile recursive ale lui Gödel - Herbrand - Kleene din 1930, 1934 și 1935; Calculul lambda al bisericii Alonzo și formularea 1 a lui Emil Post din 1936; și, în cele din urmă, mașina Turing din 1936–37 și 1939. În ciuda acestui fapt, o definiție a conceptului de algoritm care este formală și non-tehnică lipsește încă [4] și, prin urmare, este forțat să se mulțumească cu ideea intuitivă a Algoritm ca „o secvență ordonată și finită de pași elementari (operații sau instrucțiuni) care duce la un rezultat bine determinat într-un timp finit”.

Modele formale

Reprezentarea grafică a algoritmului Quicksort
Pictogramă lupă mgx2.svg Același subiect în detaliu: Teoria calculabilității § Ce este un algoritm .

Definiția algoritmului recent raportat este destul de informală, în timp ce era necesar să existe o definiție mai riguroasă pentru a face față conceptului de algoritm cu instrumente matematice. În acest scop, au fost definite câteva modele de algoritmi matematici , printre care unul dintre cele mai faimoase este mașina Turing . Reprezintă un fel de computer ideal echipat cu un program de rulat, dar, în comparație cu un computer real, mașina Turing are o funcționare extrem de simplă, care poate fi descrisă cu ușurință cu termeni matematici, folosind concepte precum set , relație și funcție .

Mașina lui Von Neumann , care este modelul arhitectural primitiv al tuturor computerelor actuale, este echivalentă, în termeni de putere de calcul, cu mașina Turing. Cu alte cuvinte, s-a demonstrat că o anumită problemă poate fi rezolvată de un computer (programat corespunzător) dacă și numai dacă poate fi rezolvată și de o mașină Turing. Pe lângă mașina Turing, propusă de Alan Turing în 1936 , în aceeași perioadă alți matematicieni au dezvoltat diverse reprezentări formale ale conceptului de algoritm, printre care amintim, de exemplu, calculul lambda . După câțiva ani, a rezultat că toate aceste modele erau echivalente: problemele pe care le putea rezolva o mașină Turing erau aceleași pe care le putea rezolva o mașină von Neumann și, de asemenea, aceleași care puteau rezolva o funcție construită cu calcul lambda [ fără sursă ] .

Printre altele, din aceste rezultate a apărut teza Church-Turing , care afirmă că orice algoritm poate fi modelat cu o mașină Turing. Cu alte cuvinte, această teză susține că este în esență imposibil să încercăm să ne imaginăm un model de algoritm mai puternic și, în consecință, că nici o mașină nu va putea rezolva vreodată probleme pe care o mașină Turing nu le poate rezolva în principiu. Aceasta nu este o teoremă dovedită matematic, deoarece teza stabilește egalitatea a două concepte, algoritmul și mașina Turing, dar prima nu are o definiție formală. Teza este acum în general împărtășită, deși progresul în cercetarea în domeniul hipercomputației pare uneori să o pună în discuție.

Proprietățile fundamentale ale algoritmilor

Din definiția anterioară a algoritmului putem deduce câteva proprietăți necesare, fără de care un algoritm nu poate fi definit ca atare:

  • etapele constitutive trebuie să fie „elementare”, adică nu pot fi descompuse în continuare ( atomicitate );
  • etapele constitutive trebuie să fie interpretabile într-un mod direct și univoc de către executant , fie el uman sau artificial ( univocitate );
  • algoritmul trebuie să fie compus dintr - un număr finit de pași și necesită o cantitate finită de date de intrare (finitudine)
  • execuția trebuie să se încheie după un timp finit ( încetare );
  • executarea trebuie să conducă la un rezultat unic ( eficacitate ).
Exemplu de diagramă a unui algoritm de metodă Zis, gata!

Astfel, de exemplu, „spargerea ouălor” poate fi considerat în mod legitim un pas elementar al unui „algoritm de gătit” (rețetă), dar „adăugarea suficientă sare” nu ar putea fi prea, deoarece expresia „suficient” este ambiguă și nu indicați cu precizie care sunt pașii necesari pentru a determina cantitatea necesară. Un pas ca „pregătirea unei cratițe” nu poate fi considerat legitim deoarece poate fi descompus în continuare în sub-operațiuni (aprinderea focului, reglarea flăcării, punerea cratiței pe aragaz etc.) și, de asemenea, pentru că conține ambiguitate (nu specifică cât de mare trebuie să fie cratița, cât trebuie umplută cu smântână și așa mai departe). Dimpotrivă, „continuați să amestecați la foc mare până când compusul capătă o culoare maro” este o instrucțiune iterativă acceptabilă, care implică un număr finit de operații (agitate), deși acest număr nu este cunoscut a priori, deoarece depinde de ceea ce este numită intrare (gradul de umiditate al făinii din amestec, puterea flăcării etc.).

Cu toate acestea, instrucțiunile neelementare pentru prepararea cremei ar putea fi asociate cu o referință adecvată la o altă secțiune a cărții de rețete, care oferă un subalgoritm specific pentru această operațiune specifică. Acest lucru sugerează că, pentru ușurința implementării, algoritmii pot fi modulari , adică orientați pentru a rezolva subprobleme specifice și organizați ierarhic . În plus, o rețetă care include gătitul cu microunde nu poate fi pregătită de un interpret fără aparatul adecvat; aceasta se referă la problema fezabilității algoritmilor sau a compatibilității acestora cu resursele materiale și temporale disponibile. În cele din urmă, pot exista mai mulți algoritmi valabili pentru a rezolva aceeași problemă, dar fiecare cu un grad diferit de eficiență .

Algoritmul este în general descris ca un „proces de rezolvare a problemelor”. În acest context, „problemele” luate în considerare sunt aproape întotdeauna caracterizate de date de intrare variabile, pe care algoritmul în sine va opera pentru a ajunge la soluție. De exemplu, calculul celui mai mare divizor comun al a două numere este un exemplu de „problemă”, iar datele sale de intrare , care variază din când în când, sunt cele două numere în cauză. Pentru un nematematic acest lucru ar putea apărea ca o „familie de probleme” (problema calculării celui mai mare divizor comun între 10 și 15, problema calculării acestuia între 40 și 60, între 35 și 95 și așa mai departe). Matematicianul și informaticianul identifică cu cuvântul „problemă” întreaga familie și cu „instanță” sau „x” fiecare dintre întrebările specifice obținute prin fixarea a două valori particulare. Având în vedere această premisă, un algoritm rezolvă o problemă dacă pentru orice situație a problemei într-un timp finit produce soluția dorită sau un anumit rezultat sau date de ieșire ( ieșire ) din datele de intrare ( intrare ).

Dacă această idee a avut deja o anumită importanță pentru calculul matematic, apariția informaticii a îmbogățit-o cu o nouă importanță și, de fapt, cu informatica a început să se răspândească termenul „algoritm”. De fapt, dacă pentru a obține un anumit rezultat (a rezolva o anumită problemă) există o procedură infailibilă, care poate fi descrisă fără echivoc până la detalii și care duce întotdeauna la scopul dorit într-un timp finit, atunci există condițiile pentru încredințarea acestui lucru sarcină pe un computer , pur și simplu prin introducerea algoritmului în cauză într-un program scris într-un limbaj adecvat pe care mașina îl poate înțelege.

Un algoritm poate fi descris inițial prin utilizarea unei diagrame sau prin utilizarea unui pseudocod . Ulterior, în faza de programare , algoritmul astfel scris va fi tradus în limbaj de programare de către un programator sub formă de cod sursă, dând viață programului care va fi executat de computer, posibil după o traducere ulterioară în limbajul mașinii . Teorema Böhm-Jacopini își asumă o relevanță teoretică deosebită în acest context, care afirmă că orice algoritm poate fi implementat folosind doar trei structuri, secvența , selecția și bucla ( iterație ), pentru a fi aplicate recursiv la compoziția instrucțiunilor elementare. În practica curentă, programatorul profesionist în munca sa efectuează automat acest proces de traducere scriind direct codul sursă necesar în modalitățile menționate anterior, găsind deja soluția la problema dată.

Abordare matematică

Există numeroase modele matematice de algoritm. În general, un algoritm primește un set de valori (date) în intrare și generează una în ieșire (numită soluție). Prin urmare, având în vedere un algoritm A, funcția care asociază ieșirea corespunzătoare fiecărei intrări x a lui A este notată cu f A.

Această corespondență între intrare și ieșire nu este problema rezolvată de algoritm. În mod formal, o problemă este o funcție definite pe un set D i de elemente pe care le vom numi resturi, la valori pe un set D s de rezoluții.

Studiul unui algoritm este împărțit în două faze:

  1. sinteză (numită și proiectare sau proiect): dată fiind o problemă A, construiți un algoritm f pentru a rezolva A, adică astfel încât f = f a .
  2. analiză: dat un algoritm f și o problemă A, demonstrați că f rezolvă A, adică f = f a ( corectitudine ) și evaluați cantitatea de resurse utilizate de f ( complexitate concretă ).

Formalizarea unei probleme

Pentru fiecare problemă avem asta: unde este sunt cazurile problemei e sunt soluțiile și este o soluție la problema de exemplu x.

Studiul complexității de calcul a unui algoritm

Pictogramă lupă mgx2.svg Același subiect în detaliu: Teoria complexității computaționale .

O mare parte din teoria algoritmilor este studiul complexității, al calculului și al spațiului. Cu alte cuvinte, vrem să știm, pe măsură ce complexitatea problemei crește, cum crește timpul necesar pentru a executa algoritmul și spațiul de memorie ocupat într-un computer.

Complexitatea unui algoritm este măsurată asimptotic. Există patru metode pentru calcularea complexității unui algoritm:

Este definit asimptotic din două motive

  • deoarece fiecare computer poate implementa algoritmi diferit, timpul precis nu poate fi estimat
  • vrem să oferim o idee cantitativă despre modul în care algoritmul poate crește în timp, pe măsură ce intrarea crește, pentru valori tot mai mari.

Luând o funcție asociată cu un algoritm de tipul:

puteți defini funcția de greutate ca

care exprimă dimensiunea datelor de intrare, adică numărul de biți care sunt utilizați pentru a codifica datele de intrare în algoritm. De exemplu, pe un vector lungimea aceluiași va determina numărul de biți necesari pentru a-l codifica, iar pe matrici numărul ordinii, adică luată de exemplu o matrice pătrată, ordinea aceluiași este determinată de unul dintre cei doi dimensiuni (orizontale sau verticale).

Complexitatea unui algoritm este definită ca:

care indică pentru fiecare valoare întreagă n (adică mărimea problemei) cantitatea de timp și / sau spațiu utilizate de algoritm pentru procesarea datelor de mărimea n. Un algoritm se poate comporta semnificativ diferit chiar și pentru instanțele care au aceeași dimensiune (adică aceeași greutate).

Se arată că complexitatea unui algoritm este o funcție strict în creștere, pentru care acesta deține

De fapt, este banal să dovedim asta tinde spre infinit pe măsură ce crește (adică numărul de date care trebuie prelucrate), deoarece este redus cu (e o ), deoarece numărul minim de spații de memorie pentru a stoca un set de date este cardinalitatea sa. Rețineți că pentru tablourile rare, elementele care nu sunt nule trebuie considerate ca fiind numărul de date .

Două măsuri pentru sistemele de calcul secvențiale sunt valori Și care reprezintă respectiv timpul și spațiul de memorie cerute de un algoritm la intrare . Pentru proprietatea menționată mai sus, domeniul trebuie deci să coincidă cu întregul . Prin urmare, putem lua în considerare Și ca funcții întregi pozitive reprezentând numărul de operații elementare (nu timpul de execuție efectiv) efectuat și numărul de celule de memorie utilizate în timpul executării imediat .

Descrieți funcțiile Și poate fi foarte complicat din moment ce variabila presupune valori pe setul tuturor intrărilor. O soluție care oferă informații bune despre Și constă în introducerea conceptului de dimensiune a unei instanțe, grupând astfel intrările care au aceeași dimensiune: funcția de dimensiune asociază fiecărei intrări un număr natural care reprezintă intuitiv cantitatea de informații conținută în datele luate în considerare. De exemplu, dimensiunea naturală a unui număr întreg pozitiv Și , adică numărul de cifre necesare pentru a reprezenta în notație binară. În mod similar, dimensiunea unui vector de elemente este constituită de obicei din numărul componentelor sale, în timp ce dimensiunea unui grafic este dată în comun de numărul de noduri și de arce. Mărimea la denotă cu .

Având în vedere un algoritm pe un set de intrări , se poate întâmpla ca două instanțe , de dimensiuni egale adică . = . duce la timpi de execuție diferiți pentru același algoritm. Prin urmare, vorbim de complexitatea intrării și se disting trei cazuri:

  1. complexitate în cel mai rău caz
  2. complexitate în cazul mediu
  3. complexitate în cel mai bun caz

Cazul mediu ne permite să studiem algoritmul pe baza frecvenței cu care apar intrările și complexitatea algoritmului pentru fiecare dintre ele:

Când cazurile sunt la fel de probabile, cazul mediu este calculat ca media aritmetică a complexității calculată pe toate intrările posibile:

De exemplu, într-un algoritm de căutare liniară , dacă elementul căutat este primul din listă, suntem în cel mai bun caz, . Complexitatea în cazul mediu este . În cel mai rău caz, elementul căutat este ultimul din listă: în acest caz , adică toate pași pentru a găsi soluția.

Cel mai rău caz este ceea ce se consideră de obicei pentru a descrie complexitatea unui algoritm. În unele cazuri (de exemplu, rapid ) se ia în considerare cazul mediu, deoarece cel mai rău caz apare foarte rar sau chiar cu probabilitate zero.

Complexitate și stabilitate

Omologul complexității unui algoritm este stabilitatea sa numerică : stabilește cât de mult un algoritm este „rezistent” la anumite seturi de date. Evident, discursul este în general legat de analiza numerică și de implementarea algoritmilor pe mașini specifice, totuși ar putea exista algoritmi pur matematici care pentru unele date oferă rezultate nedeterminate, precum , în timp ce alți algoritmi echivalenți cu aceleași date reușesc încă să ofere răspunsuri: primii sunt mai puțin stabili decât cei din urmă. Un exemplu sunt limitele calculate cu metoda canonică sau cu metoda De l'Hôpital .

Exemplu: studiul complexității rezolvării sistemelor liniare

Pictogramă lupă mgx2.svg Același subiect în detaliu: Set de ecuații liniare .

Vrem să găsim un algoritm eficient pentru a rezolva un sistem liniar de ecuații în necunoscute (chiar 100, 1000 ...). Cu alte cuvinte, trebuie să evaluăm, printre toți algoritmii de soluție disponibili, cel care necesită mai puțin timp și consumă mai puțin spațiu decât ceilalți. Algebra ne oferă două metode importante de soluție de interes enorm în scopul studierii complexității algoritmilor.

NOTĂ
în exemple se ia în considerare faptul că sistemul este determinat în mod unic. În timpul analizei este posibil să știm care sunt condițiile pentru ca algoritmii pe care urmează să îi expunem să fie aplicabili
Pictogramă lupă mgx2.svg Același subiect în detaliu: Regula lui Cramer .

Regula lui Cramer permite soluția unui sistem liniar în cel mai simplu mod datorită unei singure definiții:

unde este este matricea formată prin înlocuirea coloanei i a lui cu vectorul termenilor cunoscuți. Determinantul matricei poate fi calculat a priori, deci numai calculul lui decisiv pentru rezolvarea sistemului. Determinantul este de obicei definit de dezvoltarea Laplace , care oferă în mod direct un algoritm recursiv :

unde este este elementul coordonatelor Și este minorul obținut prin ștergerea fișierului -alea linie și -a coloana. Complexitatea acestui algoritm pentru calcularea determinantului este , deoarece pentru fiecare determinant al ordinii trebuie calculat determinanți ai ordinii .

Prin urmare, se utilizează alți algoritmi cu o complexitate mai bună. (De altfel, astfel de algoritmi sunt, de asemenea, baza unor metode mai eficiente pentru calcularea determinantului). Una dintre acestea este metoda Gauss de eliminare , care se bazează pe două principii importante.

Primul este că două sisteme liniare

Și

sunt la fel dacă se obține prin înlocuirea rândurilor și coloanelor din cu combinațiile lor liniare și elementele de sunt combinații liniare ale elementelor din pe baza coeficienților de .

Al doilea este că pentru a rezolva un sistem triunghiular (de exemplu, în cazul în care matricea coeficienților are proprietatea triunghiularității) este suficient să se utilizeze algoritmul de substituție înainte sau înapoi (complexitatea de calcul este ).

Se arată că pentru a transforma sistemul într-unul triunghiular este nevoie de un algoritm a cărui complexitate este . Prin aplicarea algoritmului de substituție directă la acest sistem, se găsesc soluțiile exacte ale sistemului și se arată că complexitatea totală a algoritmului Gauss este întotdeauna .

În ceea ce privește complexitatea spațială:

  • algoritmul bazat pe regula lui Cramer necesită doar o variabilă suplimentară, în care să se stocheze determinantul matricei coeficienților, prin urmare complexitatea sa este minimă: (acesta este pentru a stoca matricea coeficientului, pentru a stoca vectorul termenilor cunoscuți și a soluțiilor, plus un spațiu egal cu pentru calculul determinanților)
  • Algoritmul lui Gauss nu necesită alt spațiu decât cel necesar pentru a stoca matricea coeficienților și vectorul termenilor cunoscuți. La sfârșitul algoritmului, vectorul termenilor cunoscuți va conține soluția. Prin urmare, complexitatea sa spațială este, de asemenea, minimă: .

Structuri de date

Pictogramă lupă mgx2.svg Același subiect în detaliu: Structura datelor .

Majoritatea algoritmilor folosesc tehnici pentru a reprezenta și organiza datele utilizate în calcul și aceste reprezentări, numite structuri de date, nu sunt neapărat la fel de sofisticate ca algoritmul care le folosește: algoritmii simpli pot necesita structuri de date complexe și invers.

Pentru a facilita și abstractiza gestionarea și interacțiunea structurilor complexe de date, sunt dezvoltați algoritmi speciali care implementează cele mai comune operații care trebuie efectuate asupra acestora. Exemple de structuri comune de date sunt vectori , liste , cozi , stive , copaci și grafice .

Catalogarea algoritmilor

Algoritmii sunt grupați și catalogați în funcție de funcția lor sau de tehnicile utilizate pentru a le crea, totuși o catalogare riguroasă și completă a devenit acum imposibilă.

În informatică este posibilă catalogarea algoritmilor în:

Multe categorii de algoritmi sunt strâns legate de organizarea datelor în memorie ( structuri de date ).

Alți algoritmi

Notă

  1. ^ Luca Serianni , Italian Grammar , ed. UTET-De Agostini, Torino, 2010, ISBN 978-88-6008-057-8 , p. 104.
  2. ^ Kleene 1943 in Davis 1965:274
  3. ^ Rosser 1939 in Davis 1965:225
  4. ^ Yiannis N. Moschovakis, What is an algorithm? , in B. Engquist e W. Schmid (a cura di), Mathematics Unlimited — 2001 and beyond , Springer, 2001, pp. 919–936 (Part II).

Bibliografia

Voci correlate

Altri progetti

Collegamenti esterni

Controllo di autorità Thesaurus BNCF 21026 · LCCN ( EN ) sh85003487 · GND ( DE ) 4001183-5 · BNF ( FR ) cb119358199 (data) · BNE ( ES ) XX527980 (data) · NDL ( EN , JA ) 00560337