FUNDAMENTELE
PROGRAMĂRII
Laura Dioşan
Metode de rezolvare a problemelor
Backtracking
Divide et impera
UNIVERSITATEA BABEŞ-BOLYAI
Facultatea de Matematică şi Informatică
Conținut curs Introducere în procesul de dezvoltare software Programare procedurală Programare modulară Tipuri definite de utilizator Principii de dezvoltare a aplicațiilor soft Testarea și inspectarea programelor Recursivitate Complexitatea algoritmilor Metode de rezolvare a problemelor
Backtracking Divide et impera Programare dinamică Greedy
Algoritmi de căutare Algoritmi de sortare Recapitulare
Decembrie, 2013 Fundamentele programării - tehnici de rezolvare a problemelor 2
Sumar
Rezolvarea problemelor
Tipologie
Tehnici
Divide et impera
Backtracking
Decembrie, 2013 Fundamentele programării - tehnici de rezolvare a problemelor 3
Probleme
Tipologie
În funcție de structură
Care pot fi descompuse în sub-probleme
Căutarea unui element într-un vector
Care nu pot fi descompuse
Amplasarea reginelor pe o tablă de șah
În funcție de numărul de soluții
Cu o singură soluție
Sortarea unui vector
Cu mai multe soluții
Generarea permutărilor
Decembrie, 2013 Fundamentele programării - tehnici de rezolvare a problemelor 4
Probleme
Tipologie
În funcție de posibilitățile de rezolvare
Rezolvabile în mod determinist
Calculul sinusului unui unghi sau a rădăcinii pătrate dintr-un număr
Rezolvabile în mod stocastic (euristic)
Probleme din lumea reală proiectarea unui ABS
Presupun căutarea unei soluţii
Decembrie, 2013 5 Fundamentele programării - tehnici de rezolvare a problemelor
Probleme
Tipologie
În funcție de complexitatea temporală a rezolvării
Probleme din clasa P – rezolvabile în timp polinomial (n2, n3, ...)
sortări
Probleme din clasa NP – rezolvabile în timp non polinomial (2n, n!,, ..)
Cel mai scurt drum într-un graf de orașe
Decembrie, 2013 6 Fundamentele programării - tehnici de rezolvare a problemelor
Probleme
Tipologie În funcție de scop
Probleme de căutare/optimizare
Planificare, proiectarea sateliţilor
Probleme de modelare
Predicţii, clasificări
Probleme de simulare
Teoria jocurilor economice
model intrări ieşiri
model intrări ieşiri
model intrări ieşiri
Decembrie, 2013 7 Fundamentele programării - tehnici de rezolvare a problemelor
Rezolvarea problemelor
Constă în identificarea unei soluţii
În informatică proces de căutare
În inginerie şi matematică proces de optimizare
Cum?
Reprezentarea soluţiilor (parţiale) puncte în spaţiul de căutare
Proiectarea unor operatori de căutare transformă o posibilă soluţie în altă soluţie
Decembrie, 2013 8 Fundamentele programării - tehnici de rezolvare a problemelor
Paşi în rezolvarea problemelor
Definirea problemei
Analiza problemei
Alegerea unei tehnici de rezolvare
căutare
reprezentarea cunoştinţelor
abstractizare
Decembrie, 2013 9 Fundamentele programării - tehnici de rezolvare a problemelor
Paşi în rezolvarea problemelor prin căutare –
Alegerea unei tehnici de rezolvare
Rezolvarea prin utilizarea regulilor (în combinaţie cu o strategie de control) de deplasare în spaţiul problemei până la găsirea unui drum între starea iniţială şi cea finală
Rezolvare prin căutare
Examinarea sistematică a stărilor posibile în vederea identificării
unui drum de la o stare iniţială la o stare finală
unei stări optime
Spaţiul stărilor = toate stările posibile + operatorii care definesc legăturile între stări
Decembrie, 2013 10 Fundamentele programării - tehnici de rezolvare a problemelor
Paşi în rezolvarea problemelor prin căutare –
Alegerea unei tehnici de rezolvare
Rezolvare prin căutare
Strategii de căutare multiple cum alegem o
strategie?
Complexitatea computaţională (temporală şi spaţială)
Completitudine algoritmul se sfârşeşte întotdeauna şi găseşte o
soluţie (dacă ea există)
Optimalitate algoritmul găseşte soluţia optimă (costul optim al
drumului de la starea iniţială la starea finală)
Decembrie, 2013 11 Fundamentele programării - tehnici de rezolvare a problemelor
Paşi în rezolvarea problemelor prin căutare –
Alegerea unei tehnici de rezolvare
Rezolvare prin căutare Strategii de căutare multiple cum alegem
o strategie? Complexitatea computaţională (temporală şi spaţială)
Performanţa strategiei depinde de:
Timpul necesar rulării
Spaţiul (memoria) necesară rulării
Mărimea intrărilor algoritmului
Viteza calculatorului
Calitatea compilatorului
Se măsoară cu ajutorul complexităţii Eficienţă computaţională
Spaţială memoria necesară identificării soluţiei
S(n) – cantitatea de memorie utilizată de cel mai bun algoritm A care rezolvp o problemă de decizie f cu n date de intrare
Temporală timpul necesar identificării soluţiei
T(n) – timpul de rulare (numărul de paşi) al celui mai bun algoritm A care rezolvă o problemă de decizie f cu n date de intrare
Factori interni
Factori externi
Decembrie, 2013 12 Fundamentele programării - tehnici de rezolvare a problemelor
Paşi în rezolvarea problemelor prin căutare –
Alegerea unei tehnici de rezolvare
Rezolvarea problemelor prin căutare poate consta în:
Construirea progresivă a soluţiei
Identificarea soluţiei potenţiale optime
Decembrie, 2013 13 Fundamentele programării - tehnici de rezolvare a problemelor
Paşi în rezolvarea problemelor prin căutare –
Alegerea unei tehnici de rezolvare
Rezolvarea problemelor prin metode clasice
Metode exacte
Metoda generării și testării
backtracking
Metoda divizării -> Divide et Impera
Metoda programării dinamice
Metode euristice
Metoda greedy
Decembrie, 2013 14 Fundamentele programării - tehnici de rezolvare a problemelor
Gnerează și testează Ideea de bază
Generarea unei posibile soluții și verificarea corectitudinii ei
Trial and error Căutare exhaustivă
Mecanism
Generare: determianrea tuturor soluțiilor posibile Testare: căutarea acelor soluții care sunt corecte
(respectă anumite condiții)
Când se poate folosi
Probleme care pot avea mai multe soluții Probleme cu constrângeri (ale căror soluții trebuie să
respecte anumite condiții)
Decembrie, 2013 Fundamentele programării - tehnici de rezolvare a problemelor 15
Generează și testează
Algoritm
Decembrie, 2013 Fundamentele programării - tehnici de rezolvare a problemelor 16
#D = D(D1) = D(D1(D2))... def generate_test(D): while (True): sol = generate_solution() if (test(sol) == True): return sol
Generează și testează
Exemple
Generarea permutărilor cu n=3 elemente
Analiza complexității
Numărul de soluții posibile: 33, adică nn
Decembrie, 2013 Fundamentele programării - tehnici de rezolvare a problemelor 17
start
1
1
1 2 3
2
1 2 3
3
1 2 3
2
1
1 2 3
2
1 2 3
3
1 2 3
3
1
1 2 3
2
1 2 3
3
1 2 3
def permut3(): for i in range(1,4): for j in range(1,4): for k in range(1, 4): #generate possibleSolution = [i,j,k] #test if ((i != j) and (j != k) and (k != i)): print(possibleSolution)
[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]
Generează și testează Algoritm
Adăugarea de condiții la generarea unei soluții nu se mai explorează toate soluțiile posibile se construiesc soluții (parțial) corecte
care respectă anumite condiții
Backtracking Spațiul de căutare al unei soluții s este S (domeniul de definiție) O soluție este formată din mai multe elemente (s[0], s[1], s[2],...) Funcția init generează o valoare nulă pentru domeniul de definiție al
soluției Funcția getNext returnează succesorul (din domeniul de definiție) al
unui element al soluției Funcția isConsistent verifică dacă o soluție (parțială) este corectă Funcția isSolution verifică dacă o soluție (parțială) este soluție finală
(completă) a problemei Decembrie, 2013 Fundamentele programării - tehnici de rezolvare a problemelor 18
#D = D(D1) = D(D1(D2))... def generate_test(D): while (True): sol = generate_solution_cond() if (test(sol) == True): return sol
Generează și testează
Exemple
Generarea permutărilor cu n=3 elemente
Backtracking - variantă iterativă
Decembrie, 2013 Fundamentele programării - tehnici de rezolvare a problemelor 19
def init(): return 0 def getNext(sol, pos): return sol[pos] + 1 def isConsistent(sol): isCons = True i = 0 while ((i<len(sol)-1) and (isCons==True)): if (sol[i] == sol[len(sol) - 1]): isCons = False else: i = i + 1 return isCons def isSolution(solution, n): return len(solution) == n
def permut_back(n): k = 0 solution = [] initValue = init() solution.append(initValue) while (k>= 0): isSelected = False while ((isSelected==False) and (solution[k]<getLast(n))): solution[k] = getNext(solution, k) isSelected = isConsistent(solution) if (isSelected == True): if (isSolution(solution,n) == True): print(solution) else: k = k + 1 solution.append(init()) else: del(solution[k]) k = k - 1 permut_back(3)
Generează și testează
Exemple
Generarea permutărilor cu n=3 elemente
Backtracking - variantă recursivă
Decembrie, 2013 Fundamentele programării - tehnici de rezolvare a problemelor 20
def init(): return 0 def getNext(sol, pos): return sol[pos] + 1 def isConsistent(sol): isCons = True i = 0 while ((i<len(sol)-1) and (isCons==True)): if (sol[i] == sol[len(sol) - 1]): isCons = False else: i = i + 1 return isCons def isSolution(solution, n): return len(solution) == n
def permut_back_rec(n, solution): initValue = init() solution.append(initValue) elem = getNext(solution, len(solution) - 1) while (elem <= n): solution[len(solution) - 1] = elem if (isConsistent(solution) == True): if (isSolution(solution, n) == True): print(solution) else: permut_back_rec(n, solution[:]) elem = getNext(solution, len(solution) - 1) sol = [] permut_back_rec(3, sol)
start
1
1
1 2 3
2
1 2 3
3
1 2 3
2
1
1 2 3
2
1 2 3
3
1 2 3
3
1
1 2 3
2
1 2 3
3
1 2 3
Generează și testează
Exemple
Backtracking
Analiza complexității
Decembrie, 2013 Fundamentele programării - tehnici de rezolvare a problemelor 21
Generează și testează
Exemple
Generarea turnurilor de m cuburi care nu se răstoarnă având la dispoziție n cuburi
Backtracking - variantă iterativă
Decembrie, 2013 Fundamentele programării - tehnici de rezolvare a problemelor 22
cubes = [10, 2, 5, 6, 7] def init(): return 0 def getNext(sol, pos): return sol[pos] + 1 def getLast(n): return n def isConsistent(sol): isCons = True; i = 0 while ((i<len(sol)-1) and (isCons==True)): if (sol[i] == sol[len(sol) - 1]): isCons = False else: i = i + 1 if (len(sol) > 1): if (cubes[sol[len(sol) - 1] - 1] > cubes[sol[len(sol) - 2] - 1]): return False return isCons def isSolution(solution, n): return len(solution) == n def print_sol(solution): tower = [] for s in solution: tower.append(cubes[s - 1]) print(tower)
def towers(n, m): k = 0 solution = [] initValue = init() solution.append(initValue) while (k>= 0): isSelected = False while ((isSelected == False) and (solution[k] < getLast(n))): solution[k] = getNext(solution, k) isSelected = isConsistent(solution) if (isSelected == True): if (isSolution(solution,m) == True): print_sol(solution) else: k = k + 1 solution.append(init()) else: del(solution[k]) k = k - 1 towers(len(cubes), 4)
Divide et impera Ideea de bază
Descompunerea problemei în sub-probleme independente și similare problemei inițiale, dar de dimensiuni mai mici, rezolvarea sub-problemelor și stabilirea soluției finale prin combinarea sub-soluțiilor
Mecanism
Divide: împărțirea problemei în sub-probleme Conquer: rezolvarea sub-problemelor Combine: combinarea sub-soluțiilor pentru obținerea
soluției finale
Când se poate folosi
Problema P având datele de intrare D poate fi rezolvată prin rezolvarea aceleiași probleme P, dar cu datele de intrare d, unde d < D
Decembrie, 2013 Fundamentele programării - tehnici de rezolvare a problemelor 23
Divide et impera
Algoritm
Decembrie, 2013 Fundamentele programării - tehnici de rezolvare a problemelor 24
#D = d1 U d2 U d3...U dn def div_imp(D): if (size(D) < lim): return rez rez1 = div_imp(d1) rez2 = div_imp(d2) ... rezn = div_imp(dn) return combine(rez1, rez2, ..., rezn)
Divide et impera Exemple
Să se găsească elementul maxim dintr-o listă
Size(problema) = n
Versiunea 1
Size(sub-problema1) = n -1
Size(sub-problema2) = n-2
...
adică:
D = l = [l1,l2,..,ln],
d1 = [l2,..,ln],
d2 = [l3,..,ln],
...
Decembrie, 2013 Fundamentele programării - tehnici de rezolvare a problemelor 25
def findMax(l): ''' descr: finds the maximul elem of a list data: a list res: the maximal elem of list ''' if (len(l) == 1): return l[0] max = findMax(l[1:]) if (max > l[0]): return max else: return l[0] def test_findMax(): assert findMax([2,5,3,6,1]) == 6 assert findMax([12,5,3,2,1]) == 12 assert findMax([2,5,3,6,11]) == 11 test_findMax()
)(1..11)(
1 )1( )2(
...
1)2()1(
1)1( )(
,1)1(
1,1)(
nOnnT
TT
nTnT
nTnT
altfelnT
nnT
Divide et impera Exemple
Să se găsească elementul maxim dintr-o listă
Size(problema) = n
Versiunea 2
Size(sub-problema1) = n/2
Size(sub-problema2) = n/2
adică:
D = l = [l1,l2,..,ln],
d1 = [l1,..,ln/2],
d2 = [ln/2+1,..,ln]
Decembrie, 2013 Fundamentele programării - tehnici de rezolvare a problemelor 26
def findMax_v2(l): ''' descr: finds the maximul elem of a list data: a list res: the maximal elem of list ''' if (len(l) == 1): return l[0] middle = len(l) // 2 max_left = findMax_v2(l[0:middle]) max_right = findMax_v2(l[middle:len(l)]) if (max_left < max_right): return max_right else: return max_left def test_findMax_v2(): assert findMax_v2([2,5,3,6,1]) == 6 assert findMax_v2([12,5,3,2,1]) == 12 assert findMax_v2([2,5,3,6,11]) == 11 test_findMax_v2() )(1212*2)(
)12/()12(2..221)(
2)2(*2)2(*2
...
2)2(*2)2(*2
2)2(*2)2(*2
1)2(*2)2(
log2n
,1)2/(*2
1,1)(
121
101
22-k32-k2
2-k21-k
1-kk
2
k
nOnnT
nT
TT
TT
TT
TT
nk
altfelnT
nnT
k
kk
kkk
Recapitulare
Divide et impera
Generează și testează
exhaustiv
backtracking
Decembrie, 2013 Fundamentele programării - tehnici de rezolvare a problemelor 27
Cursul următor
Rezolvarea problemelor prin metode clasice
Metode exacte
Metoda generării și testării
Metoda divizării -> Divide et Impera
Metoda programării dinamice
Metode euristice
Metoda greedy
Decembrie, 2013 Fundamentele programării - tehnici de rezolvare a problemelor 28
Materiale de citit şi legături utile
1. Limbajul Python http://docs.python.org/3/reference/index.html
2. Biblioteca standard Python http://docs.python.org/3/library/index.html
3. Tutorial Python http://docs.python.org/3/tutorial/index.html
4. Frentiu, M., H.F. Pop, Fundamentals of Programming, Cluj University Press, 2006, 220 pagini
5. Kent Beck.Test Driven Development: By Example. Addison-Wesley Longman, 2002 http://en.wikipedia.org/wiki/Test-driven_development
6. Martin Fowler. Refactoring. Improving the Design of Existing Code. Addison-Wesley, 1999 http://refactoring.com/catalog/index.html
Decembrie, 2013 Fundamentele programării - tehnici de rezolvare a problemelor 29
Informaţiile prezentate au fost colectate din diferite surse de pe internet, precum şi din cursurile de Fundamentele Programării ţinute în anii anteriori de către:
Lect. Dr. Adriana Guran – www.cs.ubbcluj.ro/~adriana
Lect. Dr. Istvan Czibula - www.cs.ubbcluj.ro/~istvanc
Lect. Dr. Andreea Vescan -www.cs.ubbcluj.ro/~avescan
Lect. Dr. Ioan Lazăr -www.cs.ubbcluj.ro/~ilazar
Decembrie, 2013 30 Fundamentele programării - tehnici de rezolvare a problemelor