Post on 05-Oct-2018
FUNDAMENTELE
PROGRAMĂRII
Laura Dioşan
Recursivitate și complexități
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 prin divizare Backtracking Algoritmi de căutare Algoritmi de sortare Recapitulare
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 2
Sumar
Recursivitate
Concepte de bază
Mecanism
Exemple
Avantaje și dezavantaje
Complexități
De ce?
Exemple
Analiza eficienței unui algoritm
Complexitatea temporală
Complexitatea spațială
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 3
Recursivitate
Concepte de bază
Element recursiv
Element care se definește prin el însuși
Sub-algoritm recursiv
Sub-algoritm care se auto-apeleaza
Observație
Oprirea din recursivitate -- condiție pentru ieșirea din recursivitate
Recursivitate directă
SA1 apelează SA1
Recursivitate indirectă
SA1 apelează SA2, SA2 apelează SA1
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 4
Recursivitate
Exemplu
n! = n * (n-1)! = n * (n – 1) * (n – 2)! = ...
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 5
altfelnfactn
nnfact
),1(*
0,1)( def fact(n):
''' computes n! data: an integer n res: an integer 1 * 2 * 3 * ... * n ''' if (n == 0): return 1 else: return n * fact(n - 1) def testFact(): assert fact(5) == 120 assert fact(4) == 24 assert fact(1) == 1 assert fact(0) == 1 testFact()
Recursivitate Mecanism – dezvoltarea unui subalgoritm recursiv pentru rezolvarea unei probleme de
dimensiune n
Pas1 – oprirea din recursivitate
Stabilirea conditiei de oprire
identificarea celei mai simple solutii (pentru problema de dimensiune 1)
Pas2 – inductivitatea
Descompunerea problemei in probleme mai simple si rezolvarea lor
Ex. O problema mai mică (de dimensiune n-1) si un calcul banal
Ex 2 probleme mai mici (de dimeniuni n1, respectiv n2, a.î. n1 + n2 = n-1) si un calcul banal
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 6
def sum(l): ''' computes the sum of elements from a list data: a list of integers res: sum of elements ''' if (len(l) == 0): return 0 else: #len(l) > 0 return l[0] + sum(l[1:]) def testSum(): assert sum([1,2,3,4]) == 10 assert sum([]) == 0 assert sum([3]) == 3 testSum()
def product(l): ''' computes the product of elements from a list data: a list of integers res: product of elements ''' if (len(l) == 0): return 1 else: #len(l) > 0 middle = len(l) // 2 return product(l[0:middle]) * l[middle] * product(l[middle+1:]) def testProduct(): assert product([1,2,3,4]) == 24 assert product([]) == 1 assert product([1,2,3,4,5]) == 120 assert product([2]) == 2 testProduct()
Recursivitate Mecanism
La fiecare apel al unui subalgoritm recursiv se creează o tabelă de simboluri Cu parametrii subalgoritmului si variabilele locale
Tabelele de simboluri se stochează într-o stivă Când se termină execuția unui apel se elimină din stivă tabela de simboluri corespunzătoare acelui apel
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 7
def isPalindrom(str): ''' checks if a string is palindrom data: a string res: true, if str is palindrom and false, otherwise ''' dico = locals() print(id(dico), " ", dico) if (len(str) <= 1): return True else: return str[0]==str[-1] and isPalindrom(str[1:-1]) def testIsPalindrom(): assert isPalindrom("abcba") == True assert isPalindrom("abccba") == True assert isPalindrom("abcdba") == False testIsPalindrom()
def belongs(el, l): ''' checks if an element belongs to a list data: an integer and a list of integers res: true, if el is in list and false, otherwise ''' dico = locals() print(id(dico), " ", dico) if (l == []): return False else: if (el == l[0]): return True else: return belongs(el, l[1:]) def testBelongs(): assert belongs(5, []) == False assert belongs(5, [5,2,6,3]) == True assert belongs(5, [1,2,5,4,3]) == True assert belongs(5, [6,2,5]) == True assert belongs(5, [1,2,3]) == False testBelongs()
Recursivitate
Avantaje
Claritate
Cod simplificat
Dezavantaje
Consum de memorie pentru recursivități foarte adânci
La fiecare auto-apel se creează o nouă tabelă de simboluri
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 8
Complexități Necesitate
Problemă Căutarea unui număr într-o listă
Soluție Căutare iterativă
Căutare recursivă – o singură sub-problemă
Căutare recursivă – 2 sub-probleme
Care soluție este mai BUNĂ? Eficiența algoritmilor
Compararea algoritmilor pe baza
Timpului necesar efectuării calculelor
viteza de calcul (viteza de rulare) depinde de:
- datele de intrare (număr și calitate)
- mdificările efectuate de la o rulare la alta
- hardware-ul folosit
Memoriei necesare reținerii datelor temporare
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 9
Complexități Exemplu – numărul lui Fibonacci (regula de aur)
Fn = Fn-1 + Fn-2, F0=F1=1
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 10
def fibonacci_iterativ(n): ''' computes the Fibonacci number data: a positive integer res: fibonacci number of n ''' s1 = 1 s2 = 1 fibo = 0 for i in range(2, n + 1): fibo = s1 + s2 s1 = s2 s2 = fibo return fibo
def fibonacci_recursiv(n): ''' computes the Fibonacci number data: a positive integer res: fibonacci number of n ''' if (n <= 1): return 1 else: return fibonacci_recursiv(n-1)+fibonacci_recursiv(n-2)
def timeFibonacci(n): import time start_time = time.time() print("computing Fibbonacci_iterativ(", n, ") = ", fibonacci_iterativ(n)) end_time = time.time() print(" takes ", end_time - start_time, " seconds") start_time = time.time() print("computing Fibbonacci_recursiv(", n, ") = ", fibonacci_recursiv(n)) end_time = time.time() print(" takes ", end_time - start_time, " seconds“) timeFibonacci(23)
computing Fibbonacci_iterativ( 23 ) = 46368 takes 0.0 seconds computing Fibbonacci_recursiv( 23 ) = 46368 takes 0.015000104904174805 seconds
Complexități Analiza eficienței unui algoritm
Eficiența unui subalgoritm Necesarul de resurse (spațiale și temporale) folosite
Măsurarea eficienței:
Analiză asimptotica
Poate aborda aspecte ale eficienței pentru toate datele posibile
Nu poate oferi timpi exacți de rulare
Analiză empirică
Nu poate prezice performanța algoritmului pentru toatele datele de intrare
Poate determina timpii exacți de rulare pentru un set de date de intrare
Timpul de rulare se studiază în strânsă legătură cu dimeniunea și calitatea datelor de intrare
Pentru un set de date de intrare (specific) se poate estima timpul de rulare al unui algoritm
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 11
Complexități
Complexitatea temporală
Timpul de rulare
Nu este un număr exact
Este o funcție T(n) care depinde de mărimea și calitatea datelor de intrare n (n = size(I))
Se măsoară pașii de bază (numărul de instrucțiuni) efectuați de algoritm
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 12
Complexități Complexitatea temporală
Cel mai bun caz (caz favorabil sau best case) acele date de intrare pentru care timpul de calcul al algoritmului este cel mai mic
complexitatea algoritmului
oferă o limită inferioară pentru timpul de execuție
Cel mai rău caz (worst case)
acele date de intrare pentru care timpul de calcul al algoritmului este cel mai mare
complexitatea algoritmului
oferă o limită superioară pentru timpul de execuție
Cazul mediu (average case) timpul mediu de calcul al algoritmului (pentru orice date de intrare)
complexitatea algoritmului
oferă o predicție pentru timpul de execuție
Unde: A – algoritmul DA = domeniul datelor (mulțimea tuturr datelor de intrare ale algoritmului) I – o instanță a datelor de intrare ale algoritmului EA(I) – numărul de operații efectuate de algoritmul A având datele de intrare I PA(I) – probabilitatea ca algoritmul A să primească datele de intrare I
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 13
)(min)( IEABC ADI A
)(max)( IEAWC ADI A
ADI
AA IEIPAAC )()()(
Complexități
Case T(n)
Best
Worst
Average
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 14
def sumOfFirstNumbers(n): ''' computes the sum of first n natural numbers data: a natural number res: the sum of first n numbers ''' sum = 0 for i in range(1, n + 1): sum = sum + i return sum
nn
i
1
1
nn
i
1
1
nn
i
1
1
Complexitatea temporală
Exemple
Complexități
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 15
Case len(list)=n T(n)
Best el = list[0] 1
Worst el = list[n-1] el list
Average el = list[0] el = list[1] el = list[2] ... el = list[n-1] el list
1 2 3 ... n n+1 -------- (1+2+..+n+(n+1))/(n+1)=(n+2)/2
1111
0
nn
i
nn
i
1
0
1
Complexitatea temporală
Exemple
def search(el, list): ''' checks if an element belongs to a list data: an integer and a list of integers res: true, if elements belongs to list false, otherwise ''' for i in range(0, len(list)): if (list[i] == el): return True return False
Complexități Complexitatea temporală
Interpretare
Cum comparăm mai mulți timpi de rulare?
Stabilirea ordinului de mărime pentru fiecare timp de rulare
Exemplu
pp. 4 algoritmi cu următorii timpi de rulare
Cazul 1
T1(n) > T2(n), pentru orice n
=>algoritmul 2 este mai eficient ca algoritmul 1
Cazul 2
T1(n)>T3(n), pentru n<5
T1(n)<=T3(n), pentru n >= 5
=>algoritmul 3 este mai eficient ca algoritmul 1 pentru n suficient de mare analiza asimptotică
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 16
1)(
2)(
11)(
212
5
2
1)(
4
2
3
2
2
1
ordinnnT
ordinnnT
ordinnnT
ordinnnnT
Complexități
Complexitatea temporală
Elemente teoretice
Pentru o funcție f:N->R si un timp de rulare T:N->N, cum stabilim clasa de complexitate din care face parte T?
T(n)ϵO(f(n)) dacă există 2 constante, pozitive și independente
de n, c și n0 astfel încât 0≤T(n)≤c*f(n) pentru orice n ≥ n0
O(f(n)) - mulțimea funcțiilor cu ordin de mărime mai mic sau egal
cu ordinul de mărime al lui f(n)
Exemple
O(1): 4, 1, 100, 55
O(n): 3n+10, 100n, 2n-1, 3
O(n2): 2n2+3n+1, 5n2-1, 3n+10, 7
Dacă T(n) ϵO(f(n)) atunci (limita este constantă)
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 17
)(
)(lim
nf
nT
n
Complexități Complexitatea temporală
Complexități uzuale T(n) ϵ O(1)
timp de rulare constant
Complexitate foarte bună (indiferent de câte date trebuie procesate, algoritmul execută un număr constant de pași)
Ex. Accesarea unui element într-o listă, modificarea informațiilor într-un obiect
T(n) ϵ O(log(log(n)))
Timp de rulare log-logaritmic
Complexitate foarte bună (la fel ca cea constantă)
Ex. Heap-uri Fibonacci
T(n) ϵ O(log(n))
Timp de rulare logaritmic
Complexitatefoarte bună
Ex. Căutare binară, calcularea înălțimii unui arbore binar echilibrat
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 18
Complexități Complexitatea temporală
Complexități uzuale T(n) ϵ O(n)
Timp de rulare liniar
Complexitate bună
Ex. Căutare minimului/maximului într-o listă neordonată
T(n) ϵ O(nlog(n))
Timp de rulare linearitmic
Complexitate bună
Ex. Sortarea unei liste de elemente (MergeSort, QuickSort)
T(n) ϵ O(n2)
Timp de rulare quadratic
Complexitate bună dacă n e de ordinul miilor, dar complexitate slabă când n e de ordinul milioanelor
Ex. Sortarea unie liste (BubbleSort)
T(n) ϵ O(2n)
Timp de rulare exponențial
Complexitate slabă
Ex. Rezolvarea problemei comisului voiajor
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 19
Complexități
Complexitatea temporală
Exemple de analiză a complexității
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 20
Case T(n)
Best
Worst
Average
Overall O(n)
def sumOfFirstNumbers(n): ''' computes the sum of first n natural numbers data: a natural number res: the sum of first n numbers ''' sum = 0 for i in range(1, n + 1): sum = sum + i return sum def test_sum(): assert sumOfFirstNumbers(5) == 15 assert sumOfFirstNumbers(1) == 1
nn
i
1
1
nn
i
1
1
nn
i
1
1
Complexități
Complexitatea temporală
Exemple de analiză a complexității
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 21
Case T(n)
Best
Worst
Average
Overall O(n)
def sumOfFirstNumbers(n): ''' computes the sum of first n natural numbers data: a natural number res: the sum of first n numbers ''' sum = 0 i = 1 while (i<=n): sum = sum + i i = i + 1 return sum def test_sum(): assert sumOfFirstNumbers(5) == 15 assert sumOfFirstNumbers(1) == 1
nn
i
1
1
nn
i
1
1
nn
i
1
1
def searchEven(list): ''' checks if a list contains at least an even number data: a list of integers res: true, if list contains at least an even number false, otherwise ''' i = 0 while ((i < len(list)) and (list[i] % 2 != 0)): i = i + 1 return (i < len(list)) def test_searchEven(): assert searchEven([2,4,6]) == True assert searchEven([1,3,5]) == False assert searchEven([1,2,3]) == True
Complexități
Case T(n)
Best
Worst
Average
Overall O(n)
Complexitatea temporală
Exemple de analiză a complexității
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 22
21111
nn
i
2/)1(/)...321( nnn
211
Case T(n)
Best
Worst
Average
Overall O(n2)
Complexități
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 23
def sumOfElemFromMatrix(m): s = 0 for i in range(0, len(m)): for j in range(0, len(m[i])): s = s+ m[i][j] return s def test_sumOfElemFromMatrix(): assert sumOfElemFromMatrix([[1,2],[4,5],[7,9]]) == 28 assert sumOfElemFromMatrix([[1,2,3],[4,5,6],[7,8,9]]) == 45
mnn
i
m
j
*11 1
mnn
i
m
j
*11 1
mnn
i
m
j
*11 1
Complexitatea temporală
Exemple de analiză a complexității
Complexitatea temporală
Exemple de analiză a complexității
Complexități
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 24
Case T(n)
Best
Worst
Average
Overall O(n2)
mnn
i
m
j
*11 1
nn
i
1
1
mnmn
i
*1
n- numărul de cărți m – numărul mediu de autori ai unei cărți
class Book: def __init__(self, t, na, a): self.title = t self.noAuthors = na self.authors = a def getAuthors(self): return self.authors def searchBooksOfAnAuthor(books, author): res = [] for b in books: authors = b.getAuthors() i = 0 while (i < len(authors)): if (authors[i] == author): res.append(b) i = len(authors) else: i = i + 1 return res
def test_searchBooksOfAnAuthor(): b1 = Book("title1", 2, ["author1", "author2"]) b2 = Book("title2", 3, ["author2", "author3", "author4"]) b3 = Book("title3", 1, ["author4"]) books = [b1, b2, b3] assert searchBooksOfAnAuthor(books, “a") == [] assert searchBooksOfAnAuthor(books, "author5") == [] assert searchBooksOfAnAuthor(books, "author1") == [b1] assert searchBooksOfAnAuthor(books, "author2") == [b1, b2] assert searchBooksOfAnAuthor(books, "author4") == [b2, b3]
Complexitatea temporală
Exemple de analiză a complexității
Complexități
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 25
def sum(l): ''' computes the sum of elements from a list data: a list of integers res: sum of elements ''' if (len(l) == 0): return 0 else: #len(l) > 0 return l[0] + sum(l[1:]) def testSum(): assert sum([1,2,3,4]) == 10 assert sum([]) == 0 assert sum([3]) == 3
altfel1,1)-T(n
0 dacă,1)(
nnT
1 )(
1)0()1(
......
1)3()2(
1)2()1(
1)1()(
nnT
TT
nTnT
nTnT
nTnT
Complexități
Complexitate spațială
Estimează spațiul (cantitatea de memorie) necesar(ă) unui algoritm pentru a-și stoca datele de intrare, cele de ieșire, precum și cele intermediare
Folosește notațiile de la complexitatea temporală
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 26
Complexitatea spațială
Exemple
Complexități
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 27
def minArray_v1(): a = [] n = int(input("n = ")) for i in range(0, n): el = int(input("el = ")) a.append(el) minim = a[0] for i in range(1, n): if (a[i] < minim): minim = a[i] print("minim is " + str(minim)) def minArray_v2(): n = int(input("n = ")) minim = int(input("el = ")) for i in range(1, n): el = int(input("el = ")) if (el < minim): minim = el print("minim is " + str(minim))
S(n) = 1 + n + 1 = n + 2
S(n) = 1 + 1 + 1 = 3
Complexitatea spațială
Exemple
Complexități
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 28
def minArray_v1(): a = [] n = int(input("n = ")) for i in range(0, n): el = int(input("el = ")) a.append(el) minim = a[0] for i in range(1, n): if (a[i] < minim): minim = a[i] print("minim is " + str(minim)) def minArray_v2(): n = int(input("n = ")) minim = int(input("el = ")) for i in range(1, n): el = int(input("el = ")) if (el < minim): minim = el print("minim is " + str(minim))
S(n) = 1 + n + 1 = n + 2 ϵ O(n)
S(n) = 1 + 1 + 1 = 3 ϵ O(1)
Recapitulare
Recursivitate
Concepte de bază
Mecanism
Exemple
Avantaje și dezavantaje
Complexități
De ce?
Exemple
Analiza eficienței unui algoritm
Complexitatea temporală
Complexitatea spațială
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 29
Cursul următor
Recursivitate
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 30
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
Noiembrie, 2013 Fundamentele programării - recursivitate&complexitati 31
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
Noiembrie, 2013 32 Fundamentele programării - recursivitate&complexitati