Metoda Backtracking
Prezentarea tehnicii Backtracking Aceasta tehnica se foloseste în rezolvarea problemelor care...
Aceasta fituica rezuma Algoritmica Grafurilor. Mai jos poate fi vizualizat un extras din document (aprox. 2 pagini).
Arhiva contine 13 fisiere doc de 13 pagini (in total).
Iti recomandam sa te uiti bine pe extras si pe imaginile oferite iar daca este ceea ce-ti trebuie pentru documentarea ta, o poti descarca. Ai nevoie de doar 3 puncte.
Domeniu: Calculatoare
Curs 1
1.Notatii.Definitii
Multiset – S multime finita, S!=VID
R=(S,r) r:S->N³0, r=functie multiplicitate
r:S->{0,1} => def partilor lui S (R)
xÎR <=>r(x)³1
|R|=S(x Î S) r(x)
|R|=p => R este o p-multiparte peste S
2.Puteri ale unei multimi
S!=VID, p ap N³0
p!=0
Sp={( x1,…,xp)/ x1,…,xp ap S} – multimea p-vectorilor peste S. Pt notatia x1…xp =m0, Sp= multimea p-cuvintelor peste S;
S(p)={X/X Í S, |X|=p} – multimea p-partilor lui S
S<p>={X/X este p-multiset peste S} – multimea p-multipartilor peste S
S0=m. cuvintelor fara litere=cuv. vid; S(0)= {Æ}; S<0>= {Æ}
S*= S0U S1U S2U… = toate cuv. peste S (vocabularul peste S)
S(*)=S(0)US(1)…US(n), n=|S|
S<*>= S<0>U S<1>U…
3.Graf
V-mult finita si nevida
V sn mult varfurilor
G=(V,E) sn graf orientat dc arcele au sens
E=multiset peste V2 (sn mult arcelor)
G=(V,E) sn graf neorientat dc arcele nu au sens
E=multiset peste V<2> (sn mult muchiilor)
G=(V,E) sn graf simplu dc E ÍV(2)
E sn mult muchiilor
Exemple
V={a,b,c}
V2={aa,ab,ac,ba,bb,bc,ca,cb,cc}
{exemplu de graf orientat}
V<2> {exemplu de graf neorientat}
V(2) (ex de graf simplu)
Grad
G=(V,E) graf orientat
Fie e ÎE
x e not cu e- (sn origine, vf initial)
y e not cu e+ (sn terminus, vf final)
x Î V. dG-(x)=gradul int al vf x in rap cu graful G
=|{e/e Î E, e+=x}|
dG+(x)=gradul ext al vf x in rap cu graful G
=|{e/e ap E, e-=x}|
dG(x)= dG-(x)+ dG+(x)=gradul vf x(buclele cresc si gradul int si gradul ext)
An 1 Sem 2 - FMI