INTRODUÇÃO AED

8/18/2019 INTRODUÇÃO AED

1/35

Algoritmos e Estruturas de Dados I

Luciano Nascimento Moreira Adaptado dos slides da

Profª. Renata Oliveira


2/35

Ementa

● Medidas de complexidade.● Anlise assint!tica de limites de complexidade.● Anlise de algoritmos.● Algoritmos para pes"uisa e ordena#$o.● %ipos A&stratos de Dados● 'omputa&ilidade.


3/35

(i&liografia

● )I*IANI+ N. Pro,etos de Algoritmos comImplementa#$o em Pascal e '. Editora Pioneira.● %O-'ANI+ L.+ *.+ *elos+ P.+ A.+ -.+ 'omplexidade

de Algoritmos+ ª Ed.+ -agra/ Lu00atto+ Rio 1randedo -ul+ 233.

● 'ORMEN+ %. 4.+ Rivest+ R. L.+ Leiserson. '. E.+ Algoritmos / %eoria e Prtica Ed. 'ampus+ 2332.


4/35

'rit5rios de Avalia#$o

● *er cronograma de atividades+ entregue em salade aula.


5/35

O&,etivos

● (uscar a efici6ncia dos algoritmos – Espa#o de mem!ria7 no de variveis+ no e taman8o

das estruturas de dados utili0adas

– %empo7 no de a#9es elementares reali0adas peloprocessador

● Mostrar princ:pios &sicos e t5cnicas de anlisede algoritmos


6/35

O&,etivos

● Despertar para "uest9es como7 – ;u$o &om 5 um algoritmo<

– Existe uma forma mel8or de pro,et/lo<

– ;ual 5 o custo de se usar um dado algoritmo pararesolver um pro&lema espec:fico<

– ;ual 5 o algoritmo de menor custo poss:vel "ue possaresolver um pro&lema particular<

– Existem algoritmos similares para resolver o pro&lema< – ;ue estrutura de dados 5 mais ade"uada ao

pro&lema<


7/35

O&,etivos

● Identificar classes de pro&lemas da 'i6ncia da'omputa#$o7 – P

– NP

– NP/'ompleto

– NP/Dif:cil


8/35

Introdu#$o

=>m con8ecimento de t5cnicas depro,eto poder a,udar a criar novos

algoritmos+ mas sem as ferramentas daanlise de algoritmos n$o 8 como

determinar a "ualidade dos resultados?


9/35

Motiva#$o

● Os &enef:cios de carter prtico podem+ s! eles+serem suficientes para ,ustificar o estudo dessadisciplina.

=Algoritmos diferentes para resolver o mesmopro&lema podem diferir dramaticamente em

efici6ncia. Essa diferen#a pode ser mais

significante "ue a diferen#a entre umsupercomputador e um des@top?


10/35

Motiva#$o

● Exemplo7 -e,a a seguinte situa#$o7 ordenar umcon,unto de um mil8$o de elementos● 'aso 7

– -upercomputador capa0 de processar de 33 mil89esde instru#9essegundoB

– Executando Ordena#$o por Inser#$o DiretaB

– Mel8or programador do mundo programou o algoritmo

de inser#$o usando linguagem de m"uinaB – Programa resultante re"uer 2Cn2 instru#9es para

ordenar n elementos.


11/35

Motiva#$o

● 'aso 27 – Des@top capa0 de processar de mil8$o de instru#9es

por segundo

– Executando Ordena#$o por 4eapsort

– Programador med:ocre programou o algoritmo de8eapsort usando linguagem de alto n:vel+ com umcompilador n$o muito eficiente

–

'!digo resultante usa 3CnClg n instru#9es docomputador para ordenar n elementos


12/35

● 'alcule o tempo de execu#$o para cada caso7

– 'aso 7 -upercomputador

– 'aso 27 P' dom5stico

Motiva#$o

T 1= 2∗(106

)

2

inst 100∗106inst /seg=

5,6 horas

T 2=50∗106∗log (106)inst

106inst / seg

=16,67min


13/35

Motiva#$o

● =A tecnologia n$o evoluiu s! em 8ardare+mas em softare tam&5m?

● 'aso 2 aprox. 23 ve0es mais rpido "ue'aso .


14/35

'omplexidade de %empo

● O custo de aplicar um algoritmo pode ser medido7.Executando o programa em um computador e medir o

tempo de execu#$o.● Ex7 no de miliseg. Em um I(M Poer com 2F1& de

mem!ria usando AIG+ Linux+ ...● 'onclu:mos "ue ele 5 rpido+ lento+ muito rpido+ muito

lento...


15/35


2.>sar um modelo matemtico &aseado em umalinguagem de programa#$o ou em umcomputador ideali0ado● O con,unto de opera#9es e o custo de cada uma tem de

ser fornecido● Podemos ignorar o custo de algumas das opera#9es

envolvidas. Por exemplo para algoritmos de ordena#$oconsideramos o no de compara#9es e trocas entre os

elementos do con,unto a ser ordenado.


16/35


● Podemos concluir "ue7 – O tempo de execu#$o em um computador particular

n$o 5 interessante.

– Muito mais interessante 5 uma compara#$o relativa

entre algoritmos.


17/35


-upondo "ue7● As opera#9es s$o todas executadas

se"uencialmente. A execu#$o de toda e "ual"ueropera#$o toma uma unidade de tempo. A mem!riado computador 5 infinita.

● Assim nos so&ram duas grande0as7 – %empo H nmero de opera#9es executadas

– ;uantidade de dados de entrada.


18/35


● Podemos expressar de forma a&strata a efici6nciade um algoritmo+ descrevendo o seu tempo deexecu#$o como uma fun#$o do taman8o dopro&lema J"uantidade de dadosK. Isto 5 c8amadode complexidade de tempo

Exemplo7 Dois algoritmos de


19/35

Exemplo7 Dois algoritmos deordena#$o1-begin

2- for i := 2 to n do

3- for j := n downto i do

4- if ( a[j-1] > a[j] )

5- begin

6- x = a[j-1];

7- a[j-1] = a[j];

- a[j] = x;

!- end;

1"-end#

1$ begin

2- for i = 1 to n-1

3- begin

4- % = i;

5- x = a[i];

6- for j = i&1 to n

7- begin

- if (a[j] ' x)

!- begin

1"- % = j;

11- x = a[%];

12- end

13- end

14- a[%] = a[i];

15- a[i] = x; 16- end

17-end


20/35

Exemplo7 Ordena#$o A

●

Racioc:nio7 – J"uadroK● Algoritmo7

1-begin

2- for i := 2 to n do

3- for j := n downto i do

4- if ( a[j-1] > a[j] )

5- begin

6- x = a[j-1];

7- a[j-1] = a[j];

- a[j] = x;

!- end;

1"- for-end

11- for-end

1"-end#


21/35


●

Anlise por nmero de compara#9es7 'JnK H

+3 'JnK H n i Q

2+ C (n)=∑i=2

n

n−i+1

C (n)=(n – 1)+1

2∗(n – 1)

C (n)=n2−n2

=O(n2)

C (n)=(n−1)+(n−2)+ ...+1


22/35


●

Anlise por nmero de trocas7 – Mel8or caso7 *etor , ordenado+ n$o reali0a troca H

OJK

– Pior 'aso7 Ordem decrescente

– 'aso M5dio7● OJn2K

C (n)=∑i=2

n

n−i+1=O (n2)


23/35

1rfico A


24/35

Exemplo7 Ordena#$o (● Racioc:nioAlgor:tmo7

1$ begin

2- for i = 1 to n-1

3- begin

4- % = i;

5- x = a[i];

6- for j = i&1 to n

7- begin

- if (a[j] ' x)

!- begin

1"- % = j;

11- x = a[%];

12- end

13- end

14- a[%] = a[i];

15- a[i] = x;

16- end

17-end


25/35

Exemplo7 Ordena#$o (

●

Neste algoritmo o nmero de ve0es "ue acompara#$o Ja, xK 5 executada 5 expresso porJn/KQJn/2KQ...Q2Q H Jn2K x Jn/K.

● O nmero de trocas a@ H aiB ai H x 5 reali0adono pior caso+ onde o vetor est ordenado emordem inversa+ somente n/ ve0es+ num total de 2

x Jn/K. OJnK


26/35

Interpreta#$o

●

Interesse7 'omportamento assint!tico da fun#$o+ou se,a+ como a fun#$o varia com a varia#$o de n.● Ra0$o7 Para mim 5 interessante sa&er como o

algoritmo se comporta com uma "uantidade de

dados real:stica para o meu pro&lema e o "ueacontece "uando eu vario esses dados.

1 fi d A (


27/35

1rfico de A x (

Comportamento Assintótico

I t t $


28/35

Interpreta#$o

●

Exemplo7 -e a complexidade de A um 5 expressapor faJnK H n2 e a de ( por f&JnK H 33Cn. – Isto significa "ue A cresce "uadraticamente Juma

par&olaK e "ue & cresce linearmente Jem&ora se,a

uma reta &em inclinadaK.

I t t $


29/35

Interpreta#$o

●

-e eu uso esses algoritmos para um con,unto de3 elementos+ o segundo com %&H333 5 pior do"ue o primeiro com %aHS33.

● -e eu os uso para um con,unto de 3.333

elementos+ por5m+ terei %aHS33.333.333 e%&H.333.333.

● Isto por"ue o comportamento assint!tico dos dois

5 &em diferente.

Al it


30/35

Algoritmos

● Algoritmo 5 um m5todo para resolver um determinado tipo depro&lema JDicionrioK.

● T um m5todo preciso e usvel por um computador para asolu#$o de um pro&lema.

● T composto por um con,unto finito de passos+ cada umre"uerendo uma ou mais instru#9es.

● 'ada opera#$o deve ser perfeitamente definida e clara.● >m programa 5 uma express$o de um algoritmo em uma

linguagem de programa#$o.● =>m algoritmo corresponde a uma descri#$o de um padr$o de

comportamento+ expresso em termos de um con,unto finito dea#9es?. JDi,@straK

U d A& 6 i


31/35

Ureas de A&rang6ncia

●

'inco reas importantes e distintas da pes"uisa7 – 'omo pro,etar um algoritmo7 o ato de criar um algoritmo 5uma arte "ue nunca poder ser totalmente automati0ada.

– 'omo expressar algoritmos7 a programa#$o estruturada+

por exemplo+ tem como finalidade a express$o clara econcisa de um algoritmo em linguagem de programa#$o.

– 'omo verificar a corretude de um algoritmo7 5 o processono "ual se verifica se o algoritmo fornece sa:da corretapara toda entrada de dados poss:vel. Esta verifica#$odeve ser feita independentemente do c!digo deprograma#$o usado na implementa#$o.

U d A& 6 i


32/35

Ureas de A&rang6ncia

● 'omo analisar algoritmos7 refere/se ao processo dedeterminar o tempo e a mem!ria de um computador "ue oalgoritmo ir re"uerer. Permite fa0er um ,ulgamento"ualitativo de um algoritmo so&re outro.

● 'omo testar um programa7 consiste em duas fases depura#$o e desempen8o. – Depura#$o7 consiste em executar o programa so&re um con,unto

de dados+ para verificar se ele funciona corretamente. T &omlem&rar "ue =uma prova de corretude vale mais "ue mil testes?.

– Desempen8o7 5 o processo de executar um programa corretoso&re um con,unto de dados para medir o tempo e o espa#ogastos. A medida de desempen8o comumente 5 c8amada de(A%ERIA DE %E-%E-.

Exemplos de contri&ui#9es da Anlise


33/35

Exemplos de contri&ui#9es da Anlisede Algoritmos.●

Pro&lema – 'riptografia

– Pes"uisa em textos

– Acesso a &anco dedados

– Otimi0a#$o

●

Pro&lema A&strato – Vatora#$o de inteiros

– 'asamento de padr$o

– Pes"uisa e Ordena#$o

– NP/'ompleto

O desenvolvimento de algoritmos


34/35


●

-e algum dia algu5m escrever um sistema "uegera automaticamente algoritmos corretos eeficientes+ n$o precisaremos mais dessa disciplinae de muitas outras da 'omputa#$o. Mas+

en"uanto isso n$o acontece+ o desenvolvimentode algoritmos continua sendo AR%E e 'IWN'IA.



35/35

. Esta&elecimento do pro&lema.2. Desenvolvimento de um modelo.. Pro,eto de um algoritmo.. 'orretude do algoritmo.

. Anlise de complexidade do algoritmo.X. Implementa#$oY. %este do programa7 DEP>RAZ[O e DE-EMPEN4OF. Documenta#$o.


Documents

INTRODUÇÃO AED