Análise e Projeto de Algoritmos Prof. Eduardo Barrére [email protected]

Análise e Projeto de Algoritmos

Prof. Eduardo Barrére

[email protected]

www.ufjf.br/pgccwww.dcc.ufjf.br

Programa de Pós-Graduação em Ciência da Computação – DCC – UFJF APA / Barrére

A Disciplina ....

Lecionada por dois professores:

Eduardo Barrére Foco principal: Análise de Algoritmos ( 30 pontos)

Prova de 30 pontos, provavelmente 07/11

Raul Fonseca Foco principal: Projeto de Algoritmos (70 pontos)


Primeira parte ....

Ementa abordada: Conceitos básicos. Dominação assintótica. Problemas P, NP, NP-

Completo e NP-Difícil. Classes de problemas.

“Culpado” pela Análise de Algoritmos: Donald. E. Knuth


BibliografiaThe Design And Analysis Of Computer AlgorithmsAHO, ALFRED V.ADDISON WESLEYISBN: 02010002961ª Edição - 1974

Algoritmos - Teoria e PraticaSTEIN, CLIFFORD, LEISERSON, CHARLES E., RIVEST, RONALD L., CORMEN, THOMAS H.CAMPUSISBN: 85352092631ª Edição - 2002

Introduction To AlgorithmsLEISERSON, CHARLES E., RIVEST, RONALD L., CORMEN, THOMAS H.MIT PRESS. ISBN: 0262033844. 3ª Edição - 2009

Complexity theory: exploring the limits of efficient algorithmsWegener, IngoSpringer2005


http://en.wikibooks.org/wiki/Haskell/Performance_Introduction

http://www.eng.unt.edu/ian/books/free/lnoa.pdf

Complexidade De Algoritmos (Coleção: LIVROS DIDATICOS UFRGS, V.13)TOSCANI, LAIRA VIEIRA, VELOSO, PAULO A.S.BOOKMAN. ISBN: 8577803503. 2ª Edição - 2008

Art Of Computer Programming 3 VolsKNUTH, DONALD ERVINADDISON WESLEY. ISBN: 0201485419. 2ª Edição - 1998

Algoritmos e heuristicas: desenvolvimento e avaliacao de performanceCampello, Ruy Eduardo, Maculan, NelsonEDUFF. 1994

Bibliografia


Bibliografia

Analysis Of Algorithms: An Active Learning ApproachMCCONNELL, JEFFREYJONES AND BARTLETT. ISBN: 0763707821. 2007

Algorithm DesignGOODRICH, MICHAEL T., TAMASSIA, R.IE-WILEY. ISBN: 0471383651. 1ª Edição - 2001

Algorithms and ComplexityHerbert S. WilfA K Peters. 2 ª Edição – 2002. ISBN: 9781568811789

Mathematics For The Analysis Of AlgorithmsGREENE, DANIEL H., KNUTH, DONALD E.SPRINGER VERLAG NY. ISBN: 0817647287. 3ª Edição - 2008


Conceitos....

O que é um algortimo? Entrada -> processamento (sequencia finita) -> saída Formado por regras não ambiguas!

Tudo pode ser “resolvido” por um algoritmo? (computabilidade)

Tudo que é resolvido por um algoritmo é aceitável? Complexidade: simplificadamente, a quantidade de

trabalho requerido para solucionar o problema


Aquecendo....

Compare e critique as duas proposições a seguir:

Proposição 1: "O candidato estará eleito se obtiver metade mais um dos votos válidos".

Proposição 2: "O candidato estará eleito se obtiver mais da metade dos votos válidos".


Aquecendo....Cada um dos algoritmos abaixo recebe um inteiro positivo e devolve outro inteiro

positivo. Os dois algoritmos são equivalentes: devolvem o mesmo número se receberem um mesmo n.

Digamos que uma operação aritmética é uma adição, subtração, multiplicação ou divisão. Quantas operações aritméticas o primeiro algoritmo faz? Quantas operações aritméticas o segundo algoritmo faz? Qual dos dois algoritmos é mais eficiente?

Soma-Quadrados-A (n)

1 . x ← 0

2 . para j crescendo de 1 até n faça

3 . x ← x + j · j

4 . devolva x

Soma-Quadrados-B (n)

1 . x ← n · (n+1) · (2n+1)2 . x ← x/6

3 . devolva x


Então...

“Uma base sólida de conhecimento e técnica de algoritmos é uma das características que separa o programador experiente do aprendiz. Com a moderna tecnologia de computação, você pode realizar algumas tarefas sem saber muito sobre algoritmos, mas com um boa base em algoritmos você pode fazer muito, muito mais.”

Cormen, Leiserson, Rivest, Stein


Aquecendo....

Mostre que, para qualquer número inteiro positivo n tem-se (n−1)/2 ≤ piso(n/2) ≤ n/2

piso(x) O único inteiro i tal que i ≤ x < i+1. A notação correta

para piso(x) é:

└ x ┘


Prova Matemática

Uma prova matemática é uma argumentação precisa que procura convencer o leitor de que uma certa proposição, previamente enunciada, está correta.

É uma sequência de afirmações organizada da seguinte maneira: cada afirmação é consequência simples das afirmações anteriores e das hipóteses da proposição em discussão; a última afirmação é a proposição que se deseja provar.


Prova Matemática Considere a configuração do jogo Campo

Minado. Cada posição do tabuleiro é especificada por suas coordenadas. Assim, por exemplo, o extremo superior esquerdo do tabuleiro tem coordenadas (1,1) e o cruzamento da primeira linha com a segunda coluna tem coordenadas (1,2).

PROPOSIÇÃO: A posição (1,2) da configuração acima não contém bomba.


Prova Matemática PROPOSIÇÃO: A posição (1,2) da configuração acima não contém

bomba. PROVA, por contradição:

■ Suponha, por um momento, que há uma bomba em (1,2).

■ A posição (2,3) é vizinha de duas bombas e há uma bomba em (3,4); logo, as posições (2,2) e (3,2) não têm bomba alguma.

■ Portanto, o "3" na posição (3,3) garante que há uma bomba em (4,2).

■ Agora, o "2" na posição (5,3) garante que não há bomba em (5,2) nem em (6,2). Mas isso é inconsistente com o "3" na posição (6,3).

■ Esta contradição mostra que (1,2) não pode conter bomba.


Algoritmo

Estratégia: especificar (definir propriedades) arquitetura (algoritmo e estruturas de dados) Analise de complexidade (tempo de execução e

memória) implementar (numa linguagem de programação) testar (submeter entradas e verificar

observância das propriedades especificadas)


Complexidade (aperitivo...)

Tipos de Complexidade Espacial

Este tipo de complexidade representa, por exemplo, o espaço de memória usado para executar o algoritmo.

Temporal Este tipo de complexidade é o mais usado podendo

dividir-se em dois grupos: Tempo (real) necessário à execução do algoritmo.

(como podemos medir?) Número de instruções necessárias à execução.


Análise de AlgoritmosPara avaliar e comparar o desempenho de dois algoritmos: executar ambos (muitas vezes) para ver qual é mais rápido fornece

indicações sobre o desempenho e informação sobre como efetuar uma análise mais profunda.

Que dados usar? dados reais: verdadeira medida do custo de execução dados aleatórios: assegura-nos que as experiências testam o

algoritmo e não apenas os dados específicos Caso médio

dados perversos: mostram que o algoritmo funciona com qualquer tipo de dados Pior caso!

dados benéficos: Melhor caso


Análise de Algoritmos A análise precisa é uma tarefa complicada:

algoritmo é implementado numa dada linguagem linguagem é compilada e programa é executado num dado

computador difícil prever tempos de execução de cada instruções e antever

otimizações muitos algoritmos são "sensíveis" aos dados de entrada muitos algoritmos não são bem compreendidos

Para prever o tempo de execução de um programa: apenas é necessário um pequeno conjunto de ferramentas

matemáticas


Medidas de Análise Devem ser independentes da tecnologia

(hardware/software) Modelos Matemáticos simplificados baseados nos

fatores relevantes: Tempo de Execução

Uma função que relaciona o tempo de execução com o tamanho de entrada:

t = F(n) Conjunto de operações a serem executadas. Custo associado à execução de cada operação.

Ocupação de Espaço em Memória

Analise de Algoritmos


Complexidade

Exemplo Sejam 5 algoritmos A1 a A5 para resolver um mesmo problema, de

complexidades diferentes. (Supomos que uma operação leva 1 ms para ser efetuada.)

Tk(n) é a complexidade ou seja o número de operações que o algoritmo efetua para n entradas

n A1 T1(n)= n

A2 T2(n)=nlog n

A3 T3(n)=n2

A4 T4(n)=n3

A5 T5(n)=2n

16 0.016s 0.064s 0.256s 4s 1m4s32 0.032s 0.16s 1s 33s 46 Dias

512 0.512s 9s 4m22s 1 Dia 13h 10137 Séculos

tempo necessário para o algoritmo em função de n entradas


Operações primitivas

Atribuição de valores a variáveis Chamadas de métodos Operações aritméticas Comparação de dois números Acesso a elemento de um array Seguir uma referência de objeto (acesso a objeto) Retorno de um método


Exemplo de Análise de Algoritmo 1

arrayMax(A, n):

Entrada: array A com n>=1 elementos inteiros

Saida: o maior elemento em A

tmpMax <- A[0]

for i<-1 to n-1 do

if tmpMax < A[i] then

tmpMax <- A[i]

return tmpMax



T∗(n) = c1*1+ c2*n + c3*(n-1) + c5 * 1 (melhor caso)T∗(n) = c1+ n*c2 + n*c3 – c3 + c5

se considerarmos os custos iguais, teremos:

T∗(n) = c+ n*c + n*c – c + c = 2n*c + c ( = 2n + 1 para c=1)

código custo vezes

tmpMax <- A[0] c1 1

for i <- 1 to n-1 do c2 n

if tmpMax < A[i] then c3 n-1

tmpMax <- A[i] c4 n-1

return tmpMax c5 1



T∗(n) = c1*1+ c2*n + c3*(n-1) + c4*(n-1) + c5 * 1 (pior caso)T∗(n) = c1+ n*c2 + n*c3 – c3 + n*c4 – c4 + c5

se considerarmos os custos iguais, teremos:T∗(n) = c+ n*c + n*c – c + n*c – c + c = 3n*c ( = 3n para c=1)

T∗(n) ≤ t(I) ≤ T*(n)

código custo vezes

tmpMax <- A[0] c1 1

for i <- 1 to n-1 do c2 n

if tmpMax < A[i] then c3 n-1

tmpMax <- A[i] c4 n-1

return tmpMax c5 1


Observações sobre consumo de tempo:

estimar consumo do algoritmo, independente do computador

despreze constantes multiplicativas: 10 n é o mesmo que n

consumo de tempo é diferente para cada instância do problema

agrupe instâncias por “tamanho” o conceito de tamanho de uma instância muitas instâncias têm o mesmo tamanho consumo de tempo no pior caso consumo de tempo no melhor caso



Rearranjar um vetor em ordem crescente

A[1 . . n] é crescente se A[1] ≤ · · · ≤ A[n]


Exemplo de Análise de Algoritmo 2ORDENA-POR-INSERÇÃO (A, n)1 para j ← 2 até n faça2 chave ← A[j]3 i ← j − 14 enquanto i ≥ 1 e A[i] > chave faça5 A[i+1] ← A[i]6 i ← i − 17 A[i+1] ← chave



O algoritmo faz o que prometeu? Invariante: no início de cada iteração, A[1 . . j−1] é crescente Se vale na última iteração, o algoritmo está correto!

vale na primeira iteração se vale em uma iteração, vale na seguinte

ORDENA-POR-INSERÇÃO (A, n)1 para j ← 2 até (*) faça2 chave ← A[j]3 i ← j − 14 enquanto i ≥ 1 e A[i] > chave faça5 A[i+1] ← A[i]6 i ← i − 17 A[i+1] ← chave



Quanto tempo consome? Suponha 1 unidade de tempo por linha

Linha total de unidades de tempo1 = n2 = n − 13 = n − 14 ≤ 2+3+· · ·+n = (n − 1)(n+2)/25 ≤ 1+2+· · ·+(n−1) = n(n − 1)/26 ≤ 1+2+· · ·+(n−1) = n(n − 1)/27 = n − 1

total ≤ 3/2n2 + 7/2n − 4 unidades de tempo

ORDENA-POR-INSERÇÃO (A, n)1 para j ← 2 até n faça2 chave ← A[j]3 i ← j − 14 enquanto i ≥ 1 e A[i] > chave faça5 A[i+1] ← A[i]6 i ← i − 17 A[i+1] ← chave



Encontrar a soma dos elementos positivos de um vetor A[1 . . n]

Uma instância do problema: Encontrar a soma dos elementos positivosdo vetor (20; -30; 15; -10; 30; -20; -30; 30)



O algoritmo está correto! Invariante: no começo de cada iteração s é a soma dos positivos de A[1 .. i-1]No fim,s é a soma dos positivos de A[1 .. n].

SOMAPOSITIVOS (A; n)1 s = 02 para i = 1 até n faça3 se A[i] > 04 então s = s + A[i]5 devolva s

O algoritmo está correto? testes só podem mostrar que

o algoritmo está errado (????) análise pode provar que o

algoritmo está correto.



SOMAPOS (A;n)1 se n = 02 então devolva 03 senão s = SOMAPOS (A; n - 1)4 se A[n] > 05 então devolva s + A[n]6 senão devolva s

T(n) : consumo de tempo no pior caso recorrência: T(n) = T(n - 1) + const T(n) = ?

Algoritmo recursivo



Observações sobre algoritmos recursivos Problemas com estrutura recursiva:

cada instância do problema contém uma instância menor do mesmo problema

Algoritmo recursivo: se a instância em questão é pequena resolva-a

diretamente Senão: reduza-a a uma instância menor do mesmo

problema encontre solução S da instância menor use S para construir solução da instância original


Análise: Crescimento de Funções O tempo de execução geralmente dependente de um

único parâmetro N ordem de um polinômio tamanho de um arquivo a ser processado, ordenado, etc ou medida abstrata do tamanho do problema a considerar

(usualmente relacionado com o número de dados a processar)

Quando há mais de um parâmetro procura-se exprimir todos os parâmetros em função de um só faz-se uma análise em separado para cada parâmetro


Análise: Crescimento de Funções

Os Algoritmos têm tempo de execução proporcional a 1 - muitas instruções são executadas uma só vez ou poucas

vezes (se isto for verdade para todo o programa diz-se que o seu tempo de execução é constante)

Log N - tempo de execução é logarítmico (cresce ligeiramente à medida que N cresce) (quando N duplica log N aumenta mas muito pouco; apenas duplica quando N aumenta para N2)

N - tempo de execução é linear (típico quando algum processamento é feito para cada dado de entrada) (situação ótima quando é necessário processar N dados de entrada) (ou produzir N dados na saída)


Análise: Crescimento de Funções N log N - típico quando se reduz um problema em

subproblemas, se resolve estes separadamente e se combinam as soluções (se N é 1 milhão N log N é perto de 20 milhões)

N2 - tempo de execução quadrático (típico quando é preciso processar todos os pares de dados de entrada) (prático apenas em pequenos problemas, ex: produto matriz - vetor)

N3 - tempo de execução cúbico (para N = 100, N3 = 1 milhão, ex: produto de matrizes)

2N - tempo de execução exponencial (provavelmente de pouca aplicação prática; típico em soluções de força bruta) (para N = 20, 2N = 1 milhão; N duplica, tempo passa a ser o quadrado)

Documents

Análise e Projeto de Algoritmos Prof. Eduardo Barrére [email protected]