TP1

Tehnici de programare20122012

[email protected]

Cuprins

Prezentare general

Cum se scrie un program?

Curs Introductiv


Complexitatea algoritmilor

Scurt prezentare curs

Curs - 14 sptmni

Lurcri practice - 14 sptmni

Test n primele sptmni pentru recunoaterea cursului

Evaluare:

Prezentare general

Evaluare:

Curs (tem pe parcurs + examen final) Laborator

Metode de programare Complexitatea algoritmilor

Pointeri. Lucru pe biti

Stiva

Backtracking

Prezentare general

Recursivitate

Divide at Impera

Greedy

Programare dinamic

Bibliografie

Tudor Sorin, Tehnici de programare, Teora, 1995

Cormen T.H., Leiserson C.E., Rivest R.R., Introducere n algoritmi, Agora, 2000

Ivac C., Prun M., Bazele informaticii, Petrion, 1995

Atanasiu. A, Pintea R., Culegere de probleme pascal, Petrion, 1996

Manz. D, et. al., Informatica. Culegere de probleme rezolvate i propuse, Mirton, 2005

Prezentare general

Manz. D, et. al., Informatica. Culegere de probleme rezolvate i propuse, Mirton, 2005

Ionescu C., et. al., Informatica pentru grupele de performan, Dacia Educaional, 2004

Ciocrlie H., Ciocrlie R., Tehnici de programare i structuri de date, Eurostampa, 2010

Pai implementare Analiz

nelegerea corect a cerinei problemei

Verificarea constrngerilor (timp de execuie, memorie, ...)

Proiectare

n funcie de timpul alocat rezolvrii problemei (contratimp -> fr proiectare n


n funcie de timpul alocat rezolvrii problemei (contratimp -> fr proiectare n detaliu, lucru cu compilatorul)

Implementare

Scriere cod

Depanare

Testare

Exemplu implementareProblem:

Se d un numr natural cu numr impar de cifre. Afiai numrul format dup eliminarea cifrei din mijloc multiplicat cu 37. Numrul trebuie s conin minim 3 cifre.

Pas 1. Problema impune validarea datelor de intrare?

- dac da, atunci se fac toate validrile imaginate n limita timpului disponibil


Pas 2. Problema impune constrngeri de date i timp?

- dac nu exist informaii ntrebm sau presupunem (alegem cazul cel mai defavorabil posibil a fi implementat n timpul alocat)- presupunem long/unsigned long suficient ca tip de dat

Exemplu implementare (cont.)Pas 3. O implementare rapid

Se d un numr natural cu numr impar de cifre. Afiai numrul format dup eliminarea cifrei din mijloc multiplicat cu 37. Numrul trebuie s conin minim 3 cifre.

unsigned long n,m,x, cifre=0;

coutn;

m=n;


while (m){ //numarul de cifre

cifre++; m/=10;

}

x=pow(10,cifre/2);

m=n%x; //ultimele cifre

n/=10*x; //primele cifre

n=n*x+m; //n fara cifra din mijloc

cout

Exemplu implementare (cont.)Pas 4. Testare/Depanare/Refactorizare

- Programul compileaz ?

- Testarea rezultatelor pentru cteva numere. Testarea valorilor la limit. Reimplementare dac e nevoie.

- Se pot aduce mbuntiri? (mai e timp?)- Se poate crete domeniul de valori (unsigned long)? Crete complexitatea ?


- Codul arat bine? E comentat?

Identare/Notaii cod/Comentare

Identare (K&R, KNF, GNU)+ exemple

Notaii cod

+ exemple Camel Case


+ exemple Hungarian

Comentare

+ exemple

Stil de programare

+ aspect general

+ claritate/lizibilitate

+ modularitate


+ robustee

Analiza algoritmilor

Problem: Se d o list de n elemente, A[1..n] i un element auxiliar x. S se gseasc indexul i, cu proprietatea c A[i]=x, 1 i n.

+ exemple


+ 2 metode

Cutare liniarAlgoritm: LINEARSEARCH

Input: vector A[1..n] de n elemente i un element x.

Output: i dac x = A[i], 1 i n, i 0 n caz contrar.

1. i 1

2. while (i < n) and (x A[i])


+ cte comparaii minim?

+ cte comparaii maxim?

2. while (i < n) and (x A[i])

3. i i+1

4. end while

5. if (x = A[i]) then return i else return 0

Cutare binarAlgoritm: BINARYSEARCH

Input: vector A[1..n] de n elemente sortate cresctor i un element x.

Output: j if x = A[j], 1 j n, i 0 n caz contrar.

Observaie: fie li i lf doi indexi ai vectorului A[1..n], reprezentnd limita iniial i respectiv limita superioar a unui subvector A[li..lf]. Se observ c


A[li] A[(li+lf)/2] A[lf]

Rezolvare: la fiecare pas se va mpri intervalul n jumtate i elementul x se va cuta n doar unul din cele dou intervale de indexi A[li..(li+lf)/2] i A[(li+lf)/2+1..lf], n funcie de valoarea A[(li+lf)/2] .

+ cte comparaii minim? cte comparaii maxim?

Cutare binar (cont.)Algoritm: BINARYSEARCH exemplificare (element cutat x=37)

+ li=1, lf=10

Index (i) 1 2 3 4 5 6 7 8 9 10

A[1..10] 3 7 12 21 25 26 27 29 37 39


+ li=1, lf=10

+ pas 1: k=[(li+lf)/2] = 5+ pas 2: se obin 2 intervale [1..5] i [6..10]

+ pas 3: pt. c A[k]=25 < 37

se alege intervalul A[6..10]

+ pas 4: li=6, lf=10, repeta pasul 1 pn (li==lf) sau A[k]=x

Cutare binar (cont.)Algoritm: BINARYSEARCH exemplificare (element cutat x=37)

Index (i) 6 7 8 9 10

A[6..10] 26 27 29 37 39k=8, (A[k]=29)

Cutare binar (cont.)Algoritm: BINARYSEARCH pseudocod

1. li 1; lf n;

2. while (li lf)

3. k [(li + lf) / 2]

4. if (x = A[k]) then return 1

5. else if (x < A[k]) then lf k-1


+ dup fiecare pas i, numrul de elemente se njumtete: pas i elemente

+ la ultimul pas,

5. else if (x < A[k]) then lf k-1

6. else li k+1

7. end while

8. return 0

12 in

1log12 21+=

=

nini

Ordinul/rata de cretere a unui algoritm+ timpul de execuie a unui algoritm este o funcie de dimensiunea datelor de intrare

405060708090

100

t

i

m

p

(

m

s

)

Rata de cretere

log ncn

nlog n


+

+

+ cu ct n crete cu att scade importana termenilor de grad inferior

23)( nnnf +=3log)( ++= nnnnf

0102030

0 5 10 15 20 25 30

date de intrare (n)

cn^2cn^3

Ordinul/rata de cretere a unui algoritmO( ) O( ) O( ) O( ) O( ) O ( )3nnlog n nn log 2n n2n

12827 =

25628 =

1024210 =

s007.0

s008.0

s01.0

s128.0

s256.0

s1

s89.0

s2

s10

s16

s65

ms1

ms2

ms16

sec1

ani3110

ani6910

ani30010


4096212 =

202

s012.0

s02.0

s4

ms1

s49

sec20

ms16

min3.18

sec68

ani37

ani122110

ani31456510

Operaii elementare: (i) adunare, scadere, nmulire i mprire(ii) comparaii i operatori logici(iii) atribuiri

Notaii asimptotice

Notaii

- limita superioar


- lim. inf. = lim. sup.

- limita inferioar

Notaii asimptotice ODefiniie:

).()(, a... i dac

))(()( c spunem

:)(),(

0

0

)(

ncgnfnnconstc n

ngOnfRngnf

not

=

=


).()(, a.. 0 ncgnfnn

).()(, a..12 i 1 c pt.),()(12)(

1,2102)( Fie

00

33

23

ncgnfnncnnOnfnnf

nnnnf

===

++=

Notaii asimptotice O


Notaii asimptotice O

patratic )(rsupralinia )log(

liniar )(logaritmic )(logconstant 1

2=

=

=

=

=

nOnnO

nOnO

)(


factorial )!(expontial )(polinomial )(patratic )( 2

=

=

=

=

nOcOnOnO

n

c

constanta - c

Notaii asimptotice Definiie: Rngnf :)(),( Fie

,

).()(, a.. .const i dac ))(()( c spunem

00

)(

ncgnfnnc nngnf

not

==


).()(, a.. .const i dac 00 ncgnfnnc n =

).()()(, a.. .const, i dac

))(()( c spunem

210

210

)(

ngcnfngcnncc n

ngnfnot

=

=

Complexitate P/NP/NP-complet

Algoritmi deterministici

Algoritmi nondeterministici

P = Polinomial

NP

P


P = Polinomial

NP = Nondeterministic Polinomial

NP-complet

NPcomplet

NPP

Date post:	25-Nov-2015
Category:	Documents
Upload:	andreea-elena
View:	16 times
Download:	2 times

TP1

Documents