User Tools

Site Tools


wiki:sinteza_teorie.4.1

Noțiunea de algoritm - Sinteza Teoriei


Etimologie

Cuvântul algoritm provine de la numele unui matematician arab (Mohammed ibn-Musa al-Khowarizmi cunoscut ca “părintele algebrei”) ale cărui lucrări au fost traduse în latină sub numele de Algoritmus.

Definiție

Un algoritm este o metoda de rezolvare a unei probleme oarecare. Acesta trebuie exprimat în pași mărunți cunoscuți (exemplu: Pasul 1, Pasul 2 …) care să nu fie foarte numeroși. El poate primi anumite informații sau date, iar la final poate oferi un alt set de informați sau de date. De asemenea acesta trebuie să dureze un timp cât mai mic.

Un exemplu în acest sens poate fi văzută problema încălzirii apei. Un algoritm pentru rezolvarea ei ar fi:

  • Pasul 1: Luăm o oală.
  • Pasul 2: Punem apă în oală.
  • Pasul 3: Punem oala pe aragaz.
  • Pasul 4: Dăm drumul la aragaz.
  • Pasul 5: Așteptăm 5 minute.
  • Pasul 6: Închidem argazul.
  • Pasul 7: Avem apă încălzită.

Se poate observa că putem considera ca date de intrare: Oala, apa, aragazul.Date de ieșire sunt: apa încălzită.

Un scop al algorimilor este acela de a putea fi utilizat pe probleme asemănătoare. De exemplu problema încălzirii apei este asemănătoare cu cea a facerii unui ceai. Putem folosi primul algoritm și doar să îl modificăm un pic adăugând încă un pas, Pasul 3.5: punem ingredientele pentru ceai în oală.
În ciuda faptului că un algoritm seamănă a o înșiruire de pași care se întamplă o singură dată, putem aveam pași care se repetă. De exemplu Pasul 5 ar puteam fi înlocuit cu “Cât timp apa nu se evaporă așteptăm”. Asta înseamnă că atât timp cât condiția “apa nu se evaporă” este adevărată va trebui să așteptăm.
Un algoritm dă mereu același răspuns pentru aceleași date de intrare.

Utilizare
  • Metoda de calcul al unei operații de înmulțire
    • Pasul 1: Citim înumulțirea: 4*5
    • Pasul 2: Împărțin înumușirea în adunări: 4*5=4+4+4+4+4
    • Pasul 3: Facem adunările: 4+4+4+4+4 = 20
    • Pasul 4: Spunem rezultatul 4*5=20
  • Metoda de calcul al unei împărțiri cu rest
    • Pasul 1: Citim împărțirea.
    • Pasul 2: Câtul este numărul de câte ori scădem împărțitorul din deîmpărțitorul pana valoarea rămasă este mai mare sau egala cu zero, dar mai mică decât împărțitorul. Câtul va fi zero pentru început și îl creștem de fiecare dată când scădem.
    • Pasul 3: Cât timp deîmpărțitorul este mai mare sau egal decât împărțitorul:
      • Pasul 3.1: Scădem din deîmpațitor împărțitorul.
      • Pasul 3.2: Mărim cîtul cu 1.
    • Pasul 4: Restul este ce a rămas din deîmpărțitor.
    • Pasul 5: Afișăm rezultatul.
      • Exemplu: 10/3
        • Pasul 1 D = 10, Î = 3
        • Pasul 2 C = 0
        • Pasul 3 D > Î → 10 > 3 Adevărat
          • Pasul 3.1 D = D - Î → D = 10 - 3 = 7
          • Pasul 3.2 C = C + 1 → C = 0 + 1 = 1
        • Pasul 3 D > Î → 7 > 3 Adevărat
          • Pasul 3.1 D = D - Î → D = 7 - 3 = 4
          • Pasul 3.2 C = C + 1 → C = 1 + 1 = 2
        • Pasul 3 D > Î → 4 > 3 Adevărat
          • Pasul 3.1 D = D - Î → D = 4 - 3 = 1
          • Pasul 3.2 C = C + 1 → C = 2 + 1 = 3
        • Pasul 3 D > Î → 1 > 3 Fals
        • Pasul 4 R = D → R = 1
        • Pasul 5 C = 3, R = 1
  • Afișarea pe ecran a unei imagini.
  • Sugestile pentru căutările pe diferite motoare de căutare.
  • etc…..

Noțiunea de algoritm

O metodă de rezolvare a unor clase de probleme descrisă pas cu pas.

Algoritmii se află în tot ceea ce facem zi de zi. Ei sunt rețete pentru a crea „un produs”. Cum vă deplasați la școală? Care este metoda prin care vă pregătiți sandwish-ul dimineața? Cum vă cumpărați o haină sau cum vă întoarceți de la școală acasă? Cum găsește GoogleMaps traseul cel mai scurt pentru a merge de la Cluj la București?

Reprezintă pașii dintr un proces, numiți instrucțiuni, care se execută într-o ordine bine stabilită.

Gândiți-vă la cum realizați un avion din hârtie, sau la cum vă pregătiți ghiozdanul de școală pentru ziua de mâine. Cum procedați? Este importantă ordinea în care pliați foaia de hârtie? Puteți realiza avionul dacă nu aveți resursele necesare construirii acestuia, în cazul de față foaia de hârtie?

O funcție care pleacă de la date de intrare, le prelucrează și returnează date de ieșire.

Metaforic vorbind, algoritmul este o „mașinărie” care schimbă datele de intrare în date de ieșire. Imaginați-vă că doriți să trimiteți unui coleg modul în care se pliază foaia de hârtie pentru a obține un avion asemenea cu al vostru. Cum scrieți instrucțiunile care trebuie urmate? Poate că deja cunoașteți mai multe variante diferite de pliere care duc la același rezultat? Poate că ați reușit să găsiți o variantă de rezolvare care implică mai puține plieri astfel că timpul în care faceți avionașul scade. Sunt multe posibilități de scriere a unui algoritm. Limbajul utilizat de un copil în redactarea instrucțiunior diferă de cel al unui adult care are o perspectivă mult mai largă și cunoștințe vaste dobândite din experiența proprie. Dar, pe măsură ce exersăm, scriem mai multe variante de rezolvare care duc la același produs final, căpătăm experiență și reușim să proiectăm variante tot mai eficiente, mai intuitive în folosire și cu un aspect atractiv.

=)Exemplu: Programul unei zile de școală

  • Pasul 1: mă trezesc
  • Pasul 2: mă spăl
  • Pasul 3: mănânc
  • Pasul 4: merg la școală
  • Pasul 5: vin acasă
  • Pasul 6: mănânc
  • Pasul 7: fac temele
  • Pasul 8: mă joc
  • Pasul 9: mănânc
  • Pasul 10: mă culc

=)Exemplu: Jocul piatră – hârtie – foarfecă (doi jucători)

  • Pasul 1: Ambii jucători aleg una din cele trei variante: piatră, hârtie, foarfecă
  • Pasul 2: Dacă ambii jucători aleg aceeași variantă se reia de la pasul 1
  • Pasul 3: Dacă alegerile jucătorilor sunt diferite:
    • Pasul 3.1: Dacă primul jucător alege piatră și al doilea jucător hârtie, atunci al doilea jucător câștigă un punct
    • Pasul 3.2: Dacă primul jucător alege piatră și al doilea jucător foarfecă, atunci primul jucător câștigă un punct
    • Pasul 3.3: Dacă primul jucător alege hârtie și al doilea jucător piatră, atunci primul jucător câștigă un punct
    • Pasul 3.4: Dacă primul jucător alege hârtie și al doilea jucător foarfecă, atunci al doilea jucător câștigă un punct
    • Pasul 3.5: Dacă primul jucător alege foarfecă și al doilea jucător piatră, atunci al doilea jucător câștigă un punct
    • Pasul 3.6: Dacă primul jucător alege foarfecă și al doilea jucător hârtie, atunci primul jucător câștigă un punct
  • Pasul 4: Se repetă de la pasul 1 până când unul dintre jucători ajunge la 2 puncte
wiki/sinteza_teorie.4.1.txt · Last modified: 2017/08/08 08:42 by cheres.adriana