Metoda Trierii

Get Started. It's Free
or sign up with your email address
Rocket clouds
Metoda Trierii by Mind Map: Metoda Trierii

1. Schema:

2. Necesitatea studierii

2.1. Definiție

2.1.1. Se numește metoda trierii metoda ce identifică toate soluțiile unei probleme in dependență de mulțimea soluțiilor posibile. Toate soluțiile se indentifică prin valori, ce aparțin tipurilor de date studiate: integer, boolean, enumerare sau subdomeniu. În probleme mai complicate este nevoie de a reprezenta aceste elemente prin tablouri, articole sau mulțimi

2.2. Necesitatea

2.2.1. 1. MetodaTrierii cercetează toate cazurile posibile introduse astfel selectînd soluţiile care ar îndeplini condiţia problemei.

2.2.2. 2. Datorită acestei structuri de soluţionare, probleme relativ de simple sînt efectuate rapid, încadrîndu-se în timpul minim de execuţie.

2.3. Metoda Trierii este aplicată pe larg în soluţionarea problemelor avînd scopuri didactice. Aceasta însa nu poate fi aplicată problemelor complexe ce necesită date de intrare a căror valori sunt foarte mari. Astfel de date ce sînt supuse prelucrării conduc spre algoritmi exponenţiali. Pentru verificarea tuturor cazurilor va fi necesar de un timp mare de execuţie care depinde de nr. de k elemente ce trebuie găsite in mulţimea soluţiilor posibile S. Însa timpul pentru majoritatea execuţiilor în ziua de azi este limitat de diferite circumstanţe de aceea metoda trierii se foloseste numai în cazul cînd timpul de execuţie nu este critic.

3. Schema generală a algoritmului

3.1. Schema de aplicare a metodei trierii este reprezentată mai jos:

4. Probleme din viață rezolvabile prin metoda trierii

4.1. Metoda trierii poate fi folosită pentru rezolvarea următoarelor probleme din viață:

4.1.1. Aflarea numărului minim de monede care pot fi date drept plată sau rest;

4.1.2. Medicii deseori se confruntă cu necesitatea aplicării metodei trierii cazurilor, când numărul răniților sau bolnavilor este foarte mare, medicul fiind suprasolicitat, în cazul unui război, sau când își periclitează propria viață în cazul unei epidemii periculoase;

4.1.3. Aflarea ariei maxime a unui lot de teren, avînd la dispoziție o anumită lungime de sîrmă ghimpată, spre exemplu (ca perimetru dat);

4.1.4. Generarea submulțimilor unei mulțimi (aflarea tuturor combinațiilor posibile), ceea ce ne poate fi foarte util în viața de zi cu zi;

4.1.5. Afișarea coordonatelor a două puncte date ce au distanță minimă sau maximă, ceea ce va fi foarte folositor dacă plănuim o călătorie;

4.1.6. Calcularea șanselor de a lua premiul mare la loterie etc.

5. Abordarea metodei în alte țări

5.1. Pentru a aplica metoda trierii, în alte țări se folosește cel mai des tipul de algoritm Greedy, care are rolul de a construi soluția optimă pas cu pas, la fiecare pas fiind selectat în soluție elementul care pare optim la momentul respectiv.

5.1.1. Metode de Studiere

5.1.1.1. Toate soluţiile se identifică prin valori, ce aparţin tipurilor de date studiate: integer, boolean, enumerare, char, subdomeniu, tablouri unidimensionale.

5.1.1.1.1. Fie P o problemă, soluţia căreia se află printre elementele mulţimii S cu un număr finit de elemente. S={s1, s2 , s3 , ... , sn} . Soluţia se determină prin analiza fiecărui element si din mulţimea S.

5.1.1.1.2. SCHEMA GENERALĂ for i:=1 to k do if SolutiePosibila si then PrelucrareaSolutiei

5.1.2. Etape de studiere

5.1.2.1. Generarea soluţiilor posibile necesită elaborarea unor algoritmi speciali. În general,aceşti algoritmi realizează operaţiile legate de prelucrarea unor mulţimi:

5.1.2.1.1. Reuniunea;

5.1.2.1.2. Intersecţia;

5.1.2.1.3. Diferenţa;

5.1.2.1.4. Generarea tuturor submulţimilor;

5.1.2.1.5. Generarea elementelor unui produs cartezian;

5.1.2.1.6. Generarea permutărilor, aranjamentelor sau combinărilor de obiecte

5.1.3. Tehnici de studiere

5.1.4. Instrumente TIC

6. Tehnici de elaborare a algoritmilor

6.1. Tehnica Greedy

7. Concluzii

7.1. Prin metoda trierii programele elaborate afişează pe ecran soluţiile găsite dupa ce este analizat fiecare element;

7.2. Deşi soluţiile problemei sunt de tip ordinal, ele mai pot fi prezentate sub formă de tablou sau mulţime.

7.3. Nu toate problemele pot fi rezolvate prin această metodă, dar anume cele care implică enumerarea după calcul, alegerea între elemente.

7.4. Avantaje

7.4.1. Avantajul principal al algoritmilor bazați pe metoda trierii constă în faptul că programele respective sunt relativ simple, iar depanarea lor nu necesită teste sofisticate. În majoritatea problemelor de o reală importanță practică metoda trierii conduce la algoritmii exponențiali. Întrucît algoritmii exponențiali sunt inacceptabili în cazul datelor de intrare foarte mari, metoda trierii este aplicată numai în scopuri didactice sau pentru elaborarea unor programe al căror timp de execuție este critic.

8. Metoda Gredy

9. Tehnici de elbaborare a algoritmilor

9.1. Tehnica Greedy

9.1.1. hjjjjjjj