este limita unui sir 
( sirul converge la ) daca orice vecinatate a lui contine toti termenii sirului, exceptand (eventual) un numar finit de termeni, sau, echivalent: in afara oricarei vecinatati a lui se afla (cel mult) un numar finit de termeni ai sirului.Divide
et impera este o tehnica de elaborare a
algoritmilor care consta in:
Descompunerea cazului ce trebuie
rezolvat intr-un numar de subcazuri mai mici ale aceleiasi probleme.
Rezolvarea succesiva si independenta
a fiecaruia din aceste subcazuri.
Recompunerea subsolutiilor astfel
obtinute pentru a gasi solutia cazului initial.
Sa presupunem ca avem un algoritm A cu timp patratic. Fie c o
constanta, astfel incat timpul pentru a rezolva un caz de marime n este
tA(n) cn2.
Sa presupunem ca este posibil sa rezolvam un astfel de caz prin descompunerea
in trei subcazuri, fiecare de marime n/2.
Fie d o constanta, astfel incat timpul necesar pentru descompunere si
recompunere este t(n) dn.
Folosind vechiul algoritm si ideea de descompunere-recompunere a subcazurilor,
obtinem un nou algoritm B, pentru care:
Problema clasică de programare care necesită back-tracking (revenirea pe urma lăsată) este problema ieşirii din labirint:
- iată o soluţie simplă care iniţializează labirintul în mod static, ca o matrice de caractere
Metoda backtracking foloseşte la rezolvarea multor probleme. Pentru ca o problemă să poată să fie rezolvată cu metoda backtracking, ea trebuie să îndeplinească simultan următoarele condiţii:
- poate avea mai multe soluţii, acestea fiind puse sub formă de vector ca de exemplu S(x1,x2,x3,…xn), unde x1ЄA1, x2ЄA2,…, xnЄAn
- mulţimile A1, A2, A3, …, An sunt mulţimi finite, având elementele aflate într-o ordine bine stabilită, ele putând să fie chiar identice.
