New definition of algorithm

Development of Science

"Development of Western science is based on two great achievements: the invention of the formal logical system (in Euclidean geometry) by the Greek philosophers, and the discovery of the possibility to find out causal relationships by systematic experiment (during Renaissance)." Albert Einstein (1953)

Complexitatea procesului de învăţare
De-a lungul vremii, în toate domeniile ştiinţifice se schimbă teoriile, metodele şi tehnicile de investigare, de aceea dinamica cunoaşterii umane influenţează dezvoltarea generală a societăţii umane. Pentru a obţine evoluţie şi eficienţă în viaţa sa, omul trebuie să se adapteze continuu la aceste schimbări ale cunoaşterii. În domeniul educaţiei, şi în special al învăţării şi perfecţionării, apariţia de noi tehnologii ale informaţiei şi comunicării (TIC), îmbunătăţirea teoriilor pedagogice şi psihologice, obligă pe elevi/studenţi, profesori, părinţi şi pe specialişti, să se adapteze la aceste schimbări.
Ce fac elevii şi studentii? Ce fac profesorii şi părinţii? Ce fac specialiştii? Ce fac guvernele ţărilor? read more: www.unibuc.ro/prof/vlada_m/  (The Power of Learning)

Abordarea  modernă a conceptului de algoritm

(Ref.: M. Vlada,  Concept_algoritmi-CNIV-2004)

Detalii: M. Vlada, Conceptul de ALGORITM - abordare MODERNĂ, Gazeta de Informatica, 2003 ( P-I , P-II, P-III, P-IV) , http://www.ginfo.ro/revista/anul2003.shtml

 

Practica dezvoltării aplicaţiilor/produselor software (ce necesită rezolvarea diverselor clase de probleme) scoate în evidenţă însuşirea de noi cunoştinţe şi cunoaşterea corespunzătoare a tuturor aspectelor privind modelul fizic, respectiv modelul virtual din interdependenţa Sistem de calcul-Algoritmică-Programare. Modelul virtual este determinat de gândirea obiectuală şi algoritmică, de modul de reprezentare a algoritmilor, precum şi de maşina virtuală pe care trebuie să se execute algoritmul elaborat. Conceptul de algoritm a avut o evoluţie dinamică determinată de interdependenţa menţionată şi de competenţa şi experienţa specialiştilor informaticieni în  activitatea de rezolvare a problemelor folosind calculatorul. Lucrarea prezintă o abordare modernă a conceptului de algoritm şi expune detaliat modul în care ar trebui privit (de către elevi, studenţi, profesori, specialişti) algoritmul luând în considerare diferite aspecte care sunt practic desconsiderate de abordarea clasică.

Definiţia conceptului de algoritm

 

Definiţie. Un algoritm este sistemul virtual A = (M, V, P, R, Di, De, Mi, Me) caracterizat de următoarele aspecte: elaborare, reprezentare, execuţie, corectitudine şi analiză.

     Sistemul virtual A este constituit din următoarele elemente:

 

• M – memorie virtuală (internă) utilizată pentru stocarea temporară a informaţiilor destinate variabilelor din mulţimea de variabile V; asupra variabilelor acţionează procesul de calcul P ce are acces la memorie prin rezervarea de memorie pentru variabilele din mulţimea V; iniţial memoria virtuală este folosită pentru rezervare de memorie pentru variabilele din mulţimea V, după care este utilizată pentru scrierea şi citirea de informaţii în locaţiile corespunzătoare variabilelor utilizate în procesul de calcul P;
• V – mulţime de variabile/structuri de date definite conform raţionamentului R corespunzător rezolvării unei probleme şi care utilizează memoria M prin locaţii de memorie pentru fiecare tip de variabilă din V; locaţiile de memorie rezervate variabilelor din V sunt utilizate de procesul de calcul P care prin execuţia instrucţiunilor ce constituie P, schimbă valorile(starea) locaţiilor de memorie corespunzătoare variabilelor în conformitate cu implementarea raţionamentului R;
• P – proces de calcul ce este reprezentat de o colecţie de instrucţiuni/comenzi exprimate într-un limbaj de reprezentare(cel mai utilizat fiind pseudocod-ul); folosind memoria virtuală M şi mulţimea de variabile V, colecţia de instrucţiuni implementează/codifică tehnicile şi metodele ce constituie raţionamentul R conceput special pentru rezolvarea unei clase de probleme; execuţia instrucţiunilor din P determină o dinamică a valorilor locaţiilor de memorie corespunzătoare din V; după execuţia tuturor instrucţiunilor din P, soluţia/soluţiile problemei se află în anumite locaţii de memorie ce constituie datele de iesire De;
• R – raţionament de rezolvare exprimat prin diverse tehnici şi metode specifice domeniului din care face parte clasa de probleme supuse rezolvării (matematică/fizică/chimie, etc.), care îmbinate cu tehnici de programare corespunzătoare realizează acţiuni/procese logice prin utilizarea memoriei virtuale M şi a mulţimii de variabile V;
• Di – date de intrare/input ce repezintă valori ale unor parametri ce caracterizează ipoteze de lucru/stări initiale; valorile datelor de intrare sunt stocate în memoria M prin intermediul instrucţiunilor de citire/intrare ce utilizează mediul de intrare Mi; acesta  este un dispozitiv virtual pentru citirea datelor de intrare;
• De – date de ieşire/output ce repezintă valori ale unor parametri ce caracterizează soluţia/soluţiile problemei invocate de cerinţele problemei/stările finale; valorile datelor de iesire sunt obţinute din valorile intermediare ale unor variabile generate de execuţia instrucţiunilor din procesul de calcul P şi care în final sunt stocate în memoria M în vederea transmiterii/scrierii lor către mediul de ieşire Me; acesta este un dispozitiv virtual pentru reprezentarea/scrierea datelor de ieşire sub forma grafică sau alfanumerică;
• Mi – mediu de intrare/input ce este un dispozitiv virtual de intrare/citire pentru citiri virtuale ale valorilor datelor de intrare pentru a fi stocate în memoria virtuală M;
• Me – mediu de ieşire/output ce este un dispozitiv de ieşire/scriere pentru preluarea datelor de ieşire din memoria virtuală M şi care au fost obţinute prin execuţia procesului de calcul P; datele de ieşire sunt transmise/scrise sub formă grafică sau alfanumerică pe un suport virtual(ecran virtual, hârtie virtuală, disk magnetic virtual, etc.).

    

      Elaborarea

 

              Elaborarea / conceperea algoritmului înseamnă  elaborarea unui proces demonstrativ/computaţional ce va constitui raţionamentul de rezolvare R şi care va îngloba metode şi tehnici eficiente pentru găsirea soluţiei/soluţiilor problemelor pentru care se elaborează algoritmul; elaborarea raţionamentului de rezolvare R constă din următoarele:

          -  definirea datelor de intrare/input (Di) şi a datelor de ieşire/output (De)

          -  aplicarea metodelor şi tehnicilor utilizate pentru rezolvare

          -  definirea mulţimii variabilelor V utilizate în rezolvare;

codificarea raţionamentului de rezolvare R într-un limbaj de reprezentare(de tip pseudocod) va constitui procesul de calcul P

    Reprezentare

   Prin reprezentarea algoritmului se întelege exprimarea formalizată într-un limbaj de reprezentare (în general, de tip pseudocod) a legăturii între  memoria M, mulţimea de variabile V şi  procesul de calcul P. Forma generală a unui algoritm:

algorithm nume_algoritm

    declarare_variabile    // secţiunea de declaraţii

begin

    procesul_de_calcul_P  //  corpul algoritmului

end

 

    Execuţia

   Algoritmii se consideră executaţi pe maşini abstracte / virtuale (ale căror caracteristici le "abstractizează" pe cele ale maşinilor de calcul / sistemelor de calcul existente la un moment dat).

   Astfel de modele de maşini de calcul sunt:

 

• Maşina Turing sau diverse automate cu stivă (1956-1972, a se vedea A. Aho, J. Hopcroft, J.D. Ullman, Data strutures and algorithms, Addison Wesley publishing Co.,1983)  ;
• Maşina MIX (Knuth's MIX Language, 1973, Knuth);
• Maşina RAM (The Random Access Machine, 1974, Aho-Hopcroft-Ullman);
• Maşina ASM (Abstract State Machines - A Formal Method for Specification and Verification);
• Maşina VDM (1980, Bjorner şi Jones, Vienna Development Method, programarea logică Prolog-Logic Programming);
• Maşina WAM (1983, Warren Abstract Machine, maşina abstractă Prolog- Logic Programming);
• Maşina pseudocod (Pseudo-Code Language, 1994, Cormen-Leiserson-Rivest)

          (a se vedea şi Michael T. Goodrich, Roberto Tomassia, Algotithm Design - Foundation, Analysis and Internet Examples, John Wiley & Sons, Inc., 2002).

 

      Prin intermediul unei maşini abstracte/virtuale (ce simulează o maşină  reală / sistem de calcul) execuţia algoritmului înseamnă interpretarea reprezentării algoritmului ca un mecanism virtual de tip dinamic care are o memorie virtuală M , un proces de calcul P, mediu de intrare Mi, mediu de ieşire Me şi toate aceste componente se vor confunda cu elementele corespunzătoare maşinii virtuale, excepţie procesul de calcul P ce este “lansat în execuţie” de unitatea centrală a maşinii virtuale; prin “lansarea în execuţie” a procesului de calcul P de către maşină virtuală se întelege exercitarea tuturor funcţiilor unităţii centrale (având memorie şi procesor) pentru a simula toate procesările invocate de instrucţiunile procesului de calcul P; execuţia algoritmului va însemna generarea de procese ce se vor desfăşura în timp şi care vor folosi memorie, dispozitive de calcul şi dispoziteve I/O la fel cum se întamplă cu lansarea în execuţie a formei executabile a unui program pe un sistem de calcul /calculator real. În felul acesta, algoritmul ce este sistemul virtual

                           A = (M, V, P, R, Di, De, Mi, Me)

poate fi considerat ca un “sistem de calcul” virtual având componentele de bază: M-memorie internă, P- procesor, Mi-mediu de intrare, Me-mediu de ieşire;

    Tinând seama că un program este codificarea algoritmului într-un limbaj de programare, definiţia unui program este asemănătoare cu definiţia unui algoritm cu deosebirea că nu mai este necesară prezenţa raţionamentului R, iar reprezentarea programului se va face conform sintaxei şi semanticii limbajului de programare ales; pentru ambele concepte “execuţia” evidentiază structura unui sistem cibernetic ce se află la baza arhitecturii unui sistem de calcul (ansamblu de componente hardware (dispozitive) şi software (programe)  ce oferă servicii utilizatorului  pentru  execuţia programelor ce implementează rezolvarea unor probleme.

În concluzie, învăţarea algoritmilor trebuie să fie precedată de învatarea elementelor de bază despre sistemele de calcul şi să preceadă învaţarea programării, şi anume: Sisteme de Calcul --> Algoritmi --> Programare. 

 

 Corectitudinea şi analiza

           Corectitudinea algoritmului este exprimată de corectitudinea parţială (procesul de calcul se termină-timpul de execuţie este finit- pentru orice dată de intrare dintr-un anumit domeniu de valori) şi corectitudinea totală (pentru orice dată de intrare dintr-un domeniu de valori, procesul de calcul realizează valori corecte conform scopului/funcţiei algoritmului). Există diverse metode pentru verificarea celor două componente ale corectitudinii (de exemplu,  pentru algoritmul lui Euclid reprezentat corect în pseudocod, corectitudinea parţială este verificată de faptul că şirul valorilor resturilor obţinute din împărţirile succesive este un sir convergent catre 0, iar corectitudinea totală este verificată de metoda lui Euclid printr-o simplă demonstraţie  matematică). Elaborarea aplicaţiilor informatice necesită testarea programelor care implementează diverşi algoritmi pentru ca programatorul să se convingă de corectitudinea algoritmilor concepuţi.

           Analiza algoritmului se referă la spaţiul de memorie utilizat şi la timpul necesar execuţiei algoritmului (timpul de execuţie); această analiză înseamnă măsurarea şi descrierea (cantitativă) a performanţelor algoritmului ce permite compararea diverselor soluţii algoritmice pentru aceeaşi problemă. De regulă, resursa timp este mai critică decât resursa spaţiu de memorie, dar sunt situaţii în activitatea de proiectare şi implementare a unor noi algoritmi, când se stabileşte un compromis între cerinţele de spaţiu de memorie şi cele referitoare la timpul de execuţie.

            Analiza unui algoritm cuprinde următoarele abordări:

• stabilirea unui model de calcul ;
• stabilirea timpului de calcul / de execuţie ;
• stabilirea ratei de creştere.

           Model de calcul

   Acest model va specifica operaţiile fundamentale elementare) pe care le utilizează algoritmul şi costul (în unitaţi de timp) asociat fiecărei operaţii elementare. În continuare vom prezenta câteva exemple :

• algoritmii numerici sunt analizaţi prin numărarea operaţiilor aritmetice mai costisitoare (costul unei înmulţiri sau al unei împărţiri este mult mai mare decat al unei adunări sau al unei scăderi) ;
• algoritmii de sortare/căutare sunt analizaţi prin numărarea operaţiilor de comparaţie;
•  algoritmii din geometria computaţională care realizează operaţii asupra poligoanelor, sunt analizaţi prin numărarea vârfurilor sau muchiilor prelucrate; 

        Timpul de execuţie

   Există aşa-numite măsuri de complexitate care descriu aspectul de performanţă care trebuie măsurat: timpul de execuţie în cazul cel mai defavorabil, în cazul mediu şi în cazul amortizat (marginea superioară în cazul cel mai defavorabil). Aceste masuri de complexitate depind  de volumul setului de date de intrare.

  Rata de creştere

     Prin analiza asimptotică se stabileşte rata de creştere a  timpului de execuţie în funcţie de volumul setului de date de intrare. Analiza asimptotică exprimă creşterea timpului de execuţie al unui algoritm în cazul creşterii (spre infinit) a volumului setului de date de intrare. Dacă timpul de execuţie este exprimat de funcţia f(n), n fiind numărul de elemente de intrare,  atunci rata de creştere a lui f(n) este dată de funcţia T(n). De exemplu, dacă f(n) = an² + bn + c, unde a, b, c sunt constante, atunci când n creşte spre infinit, termenii de ordin 1 şi 0 sunt nesemnificativi şi astfel în acest caz rata de creştere a lui f(n) este funcţia T(n) = n².

      În funcţie de variaţia funcţiei T(n) există următoarele categorii de algoritmi: lineari, pătratici, cubici, exponenţiali, logaritmici, liniar-logaritmici etc.

   Notaţiile utilizate în analiza asimptotică a algoritmilor sunt urmatoarele:

• O(f(n)) ce repezintă clasa funcţiilor care cresc mai puţin decât f(n) când n tinde către infinit;
• o(f(n)) ce exprimă clasa  funcţiilor care cresc strict mai lent decât f(n) când n tinde către infinit;
• W(f(n)) ce exprimă clasa funcţiilor care nu cresc mai încet decât f(n) când n tinde către infinit;
• Q(f(n)) ce exprimă  clasa funcţiilor care cresc cu aceeaşi rată ca şi f(n) când n tinde către infinit.