Subprograme

7x puncte

categorie: Informatica

nota: 10.00

nivel: Liceu

Se aplica problemelor in care solutia poate fi reprezentata sub forma unui vector - x=(x1, x2, x3, ...xk,... xn) a,Z S, unde S este multimea solutiilor problemei si S=S1 x S2 x... x Sn, si Si sunt multimi finite avand s elemente si xi a,Z si , (A")i = 1..n.Pentru fiecare problema se dau relatii intre componentele vectorului x, care sunt numite conditii interne ; solutiile posibile care satisfac co[...]
DOWNLOAD REFERAT

Preview referat: Subprograme

Se aplica problemelor in care solutia poate fi reprezentata sub forma unui vector - x=(x1, x2, x3, ...xk,... xn) a,Z S, unde S este multimea solutiilor problemei si S=S1 x S2 x... x Sn, si Si sunt multimi finite avand s elemente si xi a,Z si , (A")i = 1..n.Pentru fiecare problema se dau relatii intre componentele vectorului x, care sunt numite conditii interne ; solutiile posibile care satisfac conditiile interne se numesc solutii rezultat. Metoda de generare a tuturor solutiilor posibile si apoi de determinare a solutiilor rezultat prin verificarea indeplinirii conditiilor interne necesita foarte mult timp.

Metoda backtracking evita aceasta generare si este mai eficienta. Elementele vectorului x, primesc pe rand valori in oridinea crescatoare a indicilor, x[k] va primi o valoare numai daca au fost atribuite valori elementelor x1.. x[k-1]. La atribuirea valorii lui x[k] se verifica indeplinirea unor conditii de continuare referitoare la x1...x[k-1]. Daca aceste conditii nu sunt indeplinite, la pasul k, acest lucru inseamna ca orice valori i-am atribui lui x[k+1], x[k+1], .. x[n] nu se va ajunge la o solutie rezultat.

Metoda backtracking construieste un vector solutie in mod progresiv incepand cu prima componenta a vectorului si mergand spre ultima cu eventuale reveniri asupra atribuirilor anterioare.Problemele rezolvate prin aceata metoda necesita timp mare de executie, de aceea este indicat sa se foloseasca metoda numai daca nu avem alt algoritm de rezolvare.

Daca multimile S1,S2,...Sn au acelasi numar k de elemente, timpul necesar de executie al algoritmului este k la n. Daca multimile S1, S2.. Sn nu au acelasi numar de elemente, atunci se noteaza cu 'm' minimul cardinalelor multimilor S1..Sn si cu 'M', maximul. Timpul de executie este situat in intervalul [m la n .. M la n]. metoda backtracking are complexitatea exponetiala, in cele mai multe cazuri fiind ineficienta. Ea insa nu poate fi inlocuita cu alte variante de rzolvare mai rapide in situatia in care se cere determinarea tuturor solutiilor unei probleme.
DOWNLOAD REFERAT
« mai multe referate din Informatica

CAUTA REFERAT

TRIMITE REFERAT CERE REFERAT
Referatele si lucrarile oferite de E-referate.ro au scop educativ si orientativ pentru cercetare academica.
Confidentialitatea ta este importanta pentru noi

E-referate.ro utilizeaza fisiere de tip cookie pentru a personaliza si imbunatati experienta ta pe Website-ul nostru. Te informam ca ne-am actualizat termenii si conditiile de utilizare pentru a integra cele mai recente modificari privind protectia persoanelor fizice in ceea ce priveste prelucrarea datelor cu caracter personal. Inainte de a continua navigarea pe Website-ul nostru te rugam sa aloci timpul necesar pentru a citi si intelege continutul Politicii de Cookie. Prin continuarea navigarii pe Website-ul nostru confirmi acceptarea utilizarii fisierelor de tip cookie conform Politicii de Cookie. Nu uita totusi ca poti modifica in orice moment setarile acestor fisiere cookie urmarind instructiunile din Politica de Cookie.


Politica de Cookie
Am inteles