30
Técnicas de Desenho de Algoritmos Mudança de ênfase: da implementação de algoritmos para o desenho de algoritmos A ver: 5 tipos de algoritmos abordagem ao problema exemplos complexidade em tempo e espaço Referências: Mark Allen Weiss. Data Structures & Algorithm Analysis in Java. Addison- Wesley, 1999. Robert Sedgewick. Algorithms in C++. Addison-Wesley, 1992. Steven S. Skiena. The Algorithm Design Manual. Springer 1998.

Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Embed Size (px)

Citation preview

Page 1: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Técnicas de Desenho de Algoritmos• Mudança de ênfase:

– da implementação de algoritmos

– para o desenho de algoritmos

• A ver: 5 tipos de algoritmos

– abordagem ao problema

– exemplos

– complexidade em tempo e espaço

Referências:• Mark Allen Weiss. Data Structures & Algorithm Analysis in Java. Addison-

Wesley, 1999. •Robert Sedgewick. Algorithms in C++. Addison-Wesley, 1992. •Steven S. Skiena. The Algorithm Design Manual. Springer 1998.

Page 2: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Algoritmos Gananciosos

• Exemplos Anteriores: Dijkstra, Prim, Kruskal

• Cada fase do algoritmo: – decisão baseada no ganho imediato

– consequências futuras não consideradas

• Algoritmo atinge óptimos locais– se é óptimo global, é solução

– se não, pode servir para obter aproximação

• Exemplo de problema que resolve bem: fazer trocos, minimizando número de notas e moedas

– estratégia: dar repetidamente a maior unidade possível

• Exemplo de problema que não resolve bem: caminho mais rápido usando estratégia da melhor aresta adjacente

Page 3: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Problema de escalonamento

• Dados: tarefas e tempos

• Objectivo: minimizar tempo médio de terminação

TempoTarefa

j 1 15

j 2 8

j 3 3

j 4 10 j3 j2 j4 j1

3 11 21 36

j1 j2 j3 j4

15 23 26 36

Tempo médio: 25

Tempo médio: 17.75

Page 4: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Escalonamento

• 2ª solução é óptima

• Porquê: tarefas mais curtas primeiro

• Tarefas:

• Terminações: ti1, ti1+ti2, ...

• Custo total da solução:

(n ­ k +1) tikk = 1

n∑ (n+1)  tikk =1

n∑ − k tikk = 1

n∑=

Se existe x>y tal que tix < tiy: troca de jix e jiy diminui custo

ji1

, ji2

,..., jin

Page 5: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Escalonamento multiprocessador

• Exemplo com 3 processadores

j1j2j3j4j5j6j7j8j9

356101114151820

Tarefa Tempo

j1

j2

j3

j4

j5

j6

j7

j8

j9

3 5 6 13 16 28 34 4020

Total de tempos: 165Tempo médio: 18.33

Page 6: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Solução óptima não é única

• Para cada i, o≤ i < n/P– as tarefas j iP+1 a j (i+1)P são alocadas a processadores diferentes

j1

j2

j3

j4

j5

j6

j7

j8

j9

3 5 6 14 15 20 30 34 38

Page 7: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Minimizar tempo de completação

• Tempo a minimizar é o da última tarefa a terminar

j1

j2

j3 j4

j5

j6

j7

j8

j9

3 95 14 16 19 34

Este problema é variante do empacotamento, logo NP-completo!

Page 8: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Divisão e conquista

• Divisão: resolver recursivamente problemas mais pequenos (até caso base)

• Conquista: solução do problema original é formada com as soluções dos

subproblemas

– Há divisão quando o algoritmo tem pelo menos 2 chamadas recursivas no corpo

– Subproblemas devem ser disjuntos

• Algoritmos já vistos:

– Travessia de árvores em tempo linear: processar árvore esquerda, visitar nó,

processar árvore direita

– Ordenações:

• mergesort: ordenar 2 subsequências e juntá-las

• quicksort: ordenar elementos menores e maiores que pivot, concatenar

Page 9: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Quicksort

function quicksort(array) var list less, greater if length(array) ≤ 1 return array select and remove a pivot value pivot from array for each x in array if x ≤ pivot then append x to less else append x to greater return concatenate(quicksort(less), pivot, quicksort(greater))

Page 10: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Programação Dinâmica

• Divisão e conquista: problema é partido em subproblemas que se resolvem separadamente; solução obtida por combinação das soluções

• Programação dinâmica: resolvem-se os problemas de pequena dimensão e guardam-se as soluções; solução de um problema é obtida combinando as de problemas de menor dimensão

• Divisão e conquista é top-down

• Programação dinâmica é bottom-up

• Abordagem é usual na Investigação Operacional– “Programação” é aqui usada com o sentido de “formular restrições ao

problema que tornam um método aplicável”

• Quando é aplicável a programação dinâmica: estratégia óptima para resolver um problema continua a ser óptima quando este é subproblema de um problema de maior dimensão

Page 11: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Aplicação directa - Fibonacci

• Problemas expressos recursivamente que podem ser reescritos em formulação iterativa

• Exemplo: números de Fibonacci

/** Números de Fibonacci * versão recursiva */ n >= 0

int fib( const unsigned int n ){

if( n <= 1 )return 1;

else return fib( n-1 ) + fib( n-2 );

}

/** Números de Fibonacci * versão iterativa */int fibonacci(int n ){

int last=1, nextToLast=1, answer=1;if( n <= 1 )

return 1;for( int i = 2; i<=n; i++ ){

answer = last + nextToLast;nextToLast = last;last = answer;

}return answer;

}

Page 12: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Fibonacci

• Expressão recursiva: algoritmo exponencial

• Expressão iterativa: algoritmo linear

Problema na formulação recursiva: repetição de chamadas iguais

F0F1

F2

F3

F4

F5

F6

F1

F2

F0F1

F2

F0

F3

F1

F1 F2

F0

F3

F4

F1

F1

F2

F0F1

Page 13: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Exemplo: Equação de recorrência

C(n) = 2n

C(i)i =0

n−1

∑ + n Para resolver numericamente, expressão recursiva é directa

double eval( int n ){double sum = 0.0;if( n == 0 )return 1.0;

for( int i = 0; i < n; i++ )Sum += eval( i );

return 2.0 * sum / n + n;}

Algoritmo recursivo é exponencial!

Problema: repetição de chamadas

Page 14: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Chamadas Repetidas

C0

C1

C2

C3

C4

C5

C0 C0

C1 C0

C0

C1

C2

C0 C0

C1 C0

C0

C1

C2

C3

C0 C0

C1 C0

C0

C1

C2

C0 C0

C1 C0

Page 15: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Solução iterativa 1

double eval(int n )

{

double [ ] c = new double [n+1];

c[0] = 1.0;

for( int i = 1; i <= n; i++ )

{

double sum = 0.0;

for( int j = 0; j < i; j++ )

sum += c[j];

c[i] = 2.0 * sum / i + i;

}

return c[n];

}

Algoritmo iterativo O(n2)

Evita chamadas recursivas guardando tabela de C(n)

Page 16: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Solução iterativa 2

double eval(int n ){

double sum = 0.0;

double [ ] a = new double [n+1];

a[0] = 1.0;

for( int i = 1; i <= n; i++ )a[i] = a[i-1] + 2.0 * a[i-1] / i + i;

double answer = 2.0 * a[n] / n + n;return answer;

}

Algoritmo iterativo O(n)

Tabela de A(n) guarda valor dos somatórios; para cada entrada basta acrescentar 1 termo

Page 17: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Algoritmos de retrocesso

• Algoritmos em que se geram escolhas que vão sendo testadas e eventualmente refeitas

• Problemas para os quais não existem algoritmos eficientes: retrocesso é melhor que pesquisa exaustiva

– solução é gerada e avaliada parcialmente

– quando uma solução parcial não satisfaz objectivos, retrocesso apenas desfaz última escolha

– evita-se a pesquisa em ramos que garantidamente não levam a solução - poda da árvore de pesquisa

• Exemplo: arranjo da mobília numa casa– grande número de possibilidades

– cada peça de mobília é colocada, solução é arranjo satisfatório

– chegando a ponto onde qualquer arranjo é inconveniente, desfaz-se o último passo e tenta-se alternativa

– muitos arranjos nunca são testados

Page 18: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Problema da portagem

• Dados: n pontos p1, p2, ..., pn situados no eixo dos xx– xi é a coordenada x de pi

– x1= 0

– determinam n (n-1)/2 distâncias d1, d2, ..., dm da forma |xi - xj|

• Distâncias podem ser geradas em tempo O(n2)

Algoritmo que se segue: O(n2 log n) - é conjectura

• Problema inverso: coordenadas dos pontos a partir das distâncias: mais difícil– Não há algoritmo garantido como polinomial para o problema

• D - conjunto das distâncias |D| = m = n (n-1) / 2

Page 19: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Exemplo

D= {1, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 10}

|D| = 15 -> n = 6

x1 = 0, x6 = 10

x1 = 0 x6 = 10

D= {1, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8}

maior distância: 8 então x2 = 2 ou x5 = 8 (escolha é indiferente)

x1 = 0 x6 = 10

D= {1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7}

x5 = 8

Page 20: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Exemplo

7 - maior valor em D -> x4 = 7 ou x2 = 3

x4 = 7 distâncias x6 - 7 = 3 e x5 - 7 = 1 estão em D

x2 = 3 distâncias 3-x1 = 3 e x5 - 3 = 5 estão em D

x1 = 0 x6 = 10x5 = 8x4 = 7

D= {2, 2, 3, 3, 4, 5, 5, 5, 6}

6 - maior valor em D -> x3 = 6 ou x2 = 4

x3 = 6 distância x4 - x3 = 1 impossível, já não existe 1 em D

x2 = 4 distâncias x2-x1 = 4 e x5 - x2 = 4 impossível, só 1 vez 4 em D

É preciso retroceder!

Page 21: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Exemplo

x4 = 7 não conduziu a solução

tenta-se agora x2 = 3

x1 = 0 x6 = 10x5 = 8x2 = 3D= {1, 2, 2, 3, 3, 4, 5, 5, 6}

6 - maior valor em D -> x4 = 6 ou x3 = 4

x3 = 4 impossível, só 1 vez 4 em D

x1 = 0 x6 = 10x5 = 8x2 = 3 x4 = 6

D= {1, 2, 3, 5, 5}

Page 22: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Exemplo

x1 = 0 x6 = 10x5 = 8x2 = 3 x4 = 6x3 = 5

D = { }

x1=0, x5=10

x5=8

x2=3

x3=6 x2=4 x3=4 x4=6

x3=5

x4=7**

* *

Árvore de decisão

Page 23: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Análise

• Na ausência de retrocesso

– D pode ser mantido como árvore de pequisa equilibrada

• O(n2) operações em D

• remoção: D tem O(n2) elementos, não há reinserções, total é O(n2)

• pesquisa: 1 tentativa de colocação faz no máximo 2n, total é O(n2)

– Tempo total é O(n2 log n)

• Com retrocesso: perde-se eficiência

– não existe limite polinomial para o retrocesso requerido

– não estão identificados “exemplos patológicos”

– com pontos de coordenadas inteiras e distribuídas uniformemente, conjectura é que

retrocesso não ocorre mais que O(1)

Page 24: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Jogos

• Como jogar automaticamente um jogo estratégico?

• Exemplo: jogo do galo

– pode construir-se algoritmo que nunca perde e aproveita oportunidades para ganhar

– posições críticas armazenadas em tabela

– escolha de jogada baseada na posição corrente usando uma tabela

– ... todo a análise do jogo feita pelo programador

• Em geral, em jogos não triviais

– não é possível dispor de decisões para todos os caminhos a partir de uma posição

– é preciso recomputar a cada jogada

– é impraticável explorar todas as hipóteses

Page 25: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Minimax

• Estratégia minimax– função de avaliação da “qualidade” de uma posição

• 1 se posição de vitória

• 0 se é empate

• -1 se é para perder

– se se pode fazer avaliação por inspecção do tabuleiro: posição terminal

– posição não terminal: valor é determinado assumindo recursivamente jogadas óptimas de ambos os lados

Um jogador tenta minimizar e o outro maximizar o valor da posição

Para posição P:

• Se é a minha vez de jogar– avalio recursivamente as posições sucessoras Ps, escolhendo o valor maior;

– ao avaliar Ps as suas sucessoras são avaliadas e o menor valor é escolhido (caso mais favorável para o oponente)

Page 26: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Pesquisa com limite de profundidade• Em jogos complexos: inviável pesquisar todos os nós terminais para avaliar a

posição– parar a determinada profundidade

– nós onde pára a recursão tratados como nós terminais

– função de estimativa para avaliar nós terminais

• Ex: xadrez - avaliar peças e suas posições

• Para aumentar o factor de previsão - métodos que avaliam menos nós e não perdem informação sobre posições já avaliadas

X O X X O X...

X OX X O X...

tabela de transposição

Page 27: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Árvore do jogo• Estrutura da pesquisa de posições (nós) e valores das avaliações

42 25 27 7 72 86 9 44 50 68 73 A

42 27 86 44 68 73

27 44 68 C

44 68

44

44

Max

Min

Max

Min

Max

Page 28: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Cortes α −β• Estrutura da pesquisa de posições (nós) e valores das avaliações

73 23 30 40 19 27

73 40 27 B

40 27

40 D

40

44

Max

Min

Max

Min

Max

Page 29: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Corte α

≥ 44

44 ≤ 40

40 D ?

Max

Min

Valor em D não pode aumentar resultado na raiz: o seu nó pai é min e tem valor

garantidamente inferior ao conseguido na raiz até ao momento

Page 30: Técnicas de Desenho de Algoritmos - paginas.fe.up.ptprog2/docs/algoritmos.pdf · Técnicas de Desenho de Algoritmos • Mudança de ênfase: – da implementação de algoritmos

Corte β

Valor em C não pode aumentar resultado na raiz: nó pai é max e tem valor

garantidamente superior ao conseguido na raiz até ao momento

≤ 44

44 ≥ 68

68 D ?

Min

Max