-bolyai facultatea de matematică şi informatică...

32
FUNDAMENTELE PROGRAMĂRII Laura Dioşan Recursivitate și complexități UNIVERSITATEA BABEŞ-BOLYAI Facultatea de Matematică şi Informatică

Upload: hanguyet

Post on 05-Oct-2018

221 views

Category:

Documents


0 download

TRANSCRIPT

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