Backtracking

Batracking

Metoda de rezolvare a problemelor care indeplinesc urmatoarele conditii :
1.Solutia problemei este sub forma de vector de forma s=x1x2x3...xn, unde x1 apartine multimii A1, x2 ap. A2, xn apartine An.
2.Multimile A1, A2... An sunt multimi finite(adica nu pot fi N, Z, Q, R)
3.Nu exista o alta metoda de rezolvare mai eficienta.

Ex. Sa se genereze toate permutarile de 3 elemente.
A={1,2,3}
AxAxA={(1,1,1)(1,1,2)(1,1,3)...(3,3,3)}

Principiul metodei :
Daca in procesul de generare a unui vector solutie pentru componenta k atunci cand s-a generat o secventa din vector formata din elementele x1, x2,..., xk constatam ca valoarea xk nu este bine aleasa ( pastrand-o, nu se poate ajunge la o solutie) nu se trece la componenta k+1, ci se trece la cautarea unei valori pentru valoarea xk. Daca aceasta valoare nu exista, se reia procedeul pentru valoarea xk-1. Deoarece procedeul presupune cautare cu revenire, numele este backtracking.
Subprogramul care implementeaza metoda backtracking este urmatorul :

procedure back(k:integer);
begin
if solution (k) then tipar
else
begin
init (k);
while succesor (k) do
if valid (k) then back (k+1)
end.


Aceasta procedura este valabila pentru toate problemele rezolvate cu backtracking. Procedura este recursiva deoarece back(k) apeleaza back(k+1). Procedura foloseste in cadrul ei 5 subprograme.Acestea sunt:
-solutie,
-tipar,
-init,
-succesor,
-valid.
Cele 5 subprograme difera de la problema la problema.

1.
procedure init (k:integer);
begin
sol [k]:=0
end.

Initializarea fiecarui element de pe fiecare nivel se face cu o valoare mai mica decat cea mai mica valoare din multimea A.


2.
function (k:integer) : boolean
begin
if sol[k]begin
sol[k]:=sol[k+1];
succesor:= true
end;
else
succesor:=false
end.


Functia succesor cauta in multimea A daca elementul de pe nivelul k care este curent are succesor sau nu.


3. function valid:(k:integer): boolean
var i: integer
begin
valid:=true
for i:=1 to *k-1* do
if sol[i]= sol[k] then
valid:=false;
end.


4.function solution(k:integer): boolean
begin
solutie:=*k=n+1*
end.


5.procedure tipar(k:integer)
var i:integer;
begin
for i:=1 to n do
write (sol[i]);
writeln;
end.


Declararea:
sol: array [1, ..., 10] of integer
var n: integer;
procedura INIT
procedura SUCCESOR
procedura VALID
procedure SOLUTIE
procedure BACK

begin
write(*n=n*)
read (n)
back (1)
end.

Microsoft Power Point.

Prima lectie din semestrul doi.
Oh well, cred ca am sarit peste prima parte. Eh.
Here u go.




In acelasi diapozitiv se pot conditiona texte cu imagini, cu grafice, cu diagrame. Ordinea de prezentare a diapozitivelor poate fi schimbata cu ajutorul butoanelor de actiuni sau a hiperlegaturilor. Fiecare diapozitiv este tratat ca un document : poate avea antet, subsol.
Scopul unei prezentari multimedia este
-Evidentierea elementelor mai importante din prezentare
-Controlarea fluxului de informatie
-Captarea interesului auditorului pentru prezentare
-Publicarea prezentarii pe net.

Tehnicile care pot fi folosite sunt
1. Animatia
2.Tranzitia
3. Comentariile verbale.
4. Butoanele pt actiuni
5. Inserarea clipurilor audio si video
6. Hiperlegaturile

Animatia reprezinta adaugarea de efecte speciale ( vizuale sau sonore) la nivelul unui text, obiect sau diagrama dintr-un diapozitiv. Animatia poate fi realizata prin
1.adaugarea unor efecte textelor, obiectelor, diagramelor.
2.prezentarea progresiva a elementelor unui diapozitiv
3.stabilirea ordinii in care apar elementele unui diapozitiv
4.controlarea modului in care apar elementele unui diapozitiv ( automat, dupa un interval de timp sau la actiunea click a mausului)
5.stabilirea intervalului de timp dupa care apar elementele
6. adaugarea de efecte speciale dupa afisarea unui element ( schimbarea culorii, estomparea obiectului sau ascunderea obiectului)
La nivelul textului, se pot folosi
-prezentarea progresiva : - litera cu litera -cuvant cu cuvant -paragraf cu paragraf
-crearea textului de text zburator
-adaugarea de sunete

La nivelul obiectului se pot folosi cam aceleasi tehnici ca si la text cu exceptia prezentarii progresive a unor elemente ale obiectului. La nivelul diagramei se pot folosi a)prezentarea progresiva a elementelor (serie cu serie, element cu element, categorie cu categorie sau intreaga diagrama.
Afisarea diagramelor : stanga-dreapta, sus jos, centru margine, adaugarea de sunete.

Fisa de lucru : Realizati 3 diapozitive cu text, imagine, in care sa prezentati 3 animale din muntii Carpati. Diapozitivele sa fie formatate astfel : In antet, numele nostru, iar subsolul sa fie paginat.

Primul post. Introducere.

Okay.

Am facut blogul asta ca sa postez cam toate lectiile la info. Ca doar n-o sa stau eu sa scriu pe caiet, cand am un comp in fata :)) .
Si cam atat.