Análise e Complexidade dAl itde Algoritmos - ?· 13/05/2010 1 Análise e Complexidade dAl itde Algoritmos…

Embed Size (px)

Text of Análise e Complexidade dAl itde Algoritmos - ?· 13/05/2010 1 Análise e Complexidade dAl itde...

  • 13/05/2010

    1

    Anlise e Complexidade d Al itde AlgoritmosPrincipais paradigmas do projeto de algoritmos

    - Recursividade- Tentativa e erroTentativa e erro- Diviso e Conquista- Programao dinmica- Algoritmos Gulosos e de Aproximao

    http://www.bolinhabolinha.comProf. Rodrigo Rochaprof.rodrigorocha@yahoo.com

    Onde Estamos Ementa

    Reviso:Estrutura de dados;Crescimento de funes; Induo matemtica e mtodos matemticos Induo matemtica e mtodos matemticos.

    Medidas de complexidade, anlise assinttica de limites de complexidades.

    Exemplos de anlise de algoritmo iterativos e recursivos. Anlise de desempenho de alguns algoritmos clssicos de

    busca e ordenao. Introduo aos principais paradigmas do projeto de

    algoritmos. Complexidade do Problema: Limites de Complexidade,

    Intratabilidade, Classes P, NP, problemas Np completos e NP-difceis.

  • 13/05/2010

    2

    Recursividade - Relembrando Definio

    Um mtodo/funo que invoca o prprio mtodo/funo

    Ateno Devemos ter um condio de parada da recurso Uma condio que se torne falsa ou um contador

    que atinja um determinado valorq j

    PROBLEMA Recurso que no termina

    Implementao Um compilador implementa a recursividade

    atravs de uma pilha Todos os dados no globais vo para pilhaTodos os dados no globais vo para pilha Grava o estado corrente para poder ser

    recuperado Exemplo:

    Algoritmo recursivo de pesquisa em rvores g p qbinrias

    O valor do ponteiro para o n e o endereo de retorno da chamada recursiva so armazenados na pilha

  • 13/05/2010

    3

    Recurso Vantagens

    Cdigo mais limpo e compacto Fceis de serem implementadosFceis de serem implementados

    Desvantagens Consumo elevado de recursosConsumo elevado de recursos Mais difceis de serem depurados

    Exemplo Somatria de nmeros

    Ex: soma(5) = 1+2+3+4+5 = 15

  • 13/05/2010

    4

    Exemplo Calculo do Mximo Divisor Comum (MDC)

    Fonte: somatematica.com.br

    Exemplo

  • 13/05/2010

    5

    Exerccio 1-) Crie um programa recursivo que

    calcule a potncia (potencia>=0) de um nmero inteironmero inteiro. Dica: 24 = 2 * 23

    23 = 2 * 22

    22 = 2 * 21

    21 = 2 * 20

    Exerccios Criar um funo recursiva para calcular o

    fatorial de um nmero Fonte: infoescola.comFonte: infoescola.com

    Applet: http://ccism.pc.athabascau.ca/html/lo/repos/comp272/applets/factorial/index.html

  • 13/05/2010

    6

    Quando no usar recursividade Mo da massa:

    Implementem o algoritmo para calcular a srie de Fibonacci (1 1 2 3 5 8 13 ....) pelos mtodos iterativos e recursivositerativos e recursivos.

    Calcule o tempo de execuo dos dois programas acima para as seguintes entradas: 10,20,30,50 e 100

    O que voc percebeu?q p

    Lendo o captulo 2.2 do livro texto (Zivian, Projeto de Algoritmos), responda quando no utilizar a recursividade?

    Exerccios Recurso Dada a sequinte funo recursiva:

    int f(int n, int m) {( , ) {if (n == 0) return m;else return f(n-1, 1-m);

    }

    Qual o resultado para f(3 7)?Qual o resultado para f(3,7)?(a) 0(b) 3(c) 7(d) -7(e) Nenhum dos anteriores

  • 13/05/2010

    7

    Resoluo

    (e)

    f(3,7)= f(2,-6)= f(1, 7)

    f(0 6)= f(0, -6)= -6

    Exerccios RecursoDada a seguinte funo recursiva:int g(int n) {

    if (n == 0) return 1if (n 0) return 1else return g(n-1) + g(n-2);

    }Qual alternativa correta?(a) No temos caso base(b) No recursivo(c) Essa funo sempre termina para qualquer n(d) Nenhuma das anteriores

  • 13/05/2010

    8

    Resoluo(d) g(n) onde n termina com 0

    g(0) = 1g(0) = 1Nenhum outro valor termina.g(-1) no termina, g(1) logo, tambm no termina

    Exerccios Recursoint method( int n) {

    if (n < = 1) return 1;return method(n/2) + method(1);return method(n/2) method(1);

    }A complexidade da funo method :(a) O(log n)(b) O(n)(c) O(n2)(d) O(2n)(e) O(n2n)

  • 13/05/2010

    9

    Resoluo(a) O domnio reduzido pela metade a cada

    chamada recursivachamada recursiva

    Complexidade - Recorrncias Trs mtodos para resolvrmos recorrncias

    Substituio Supomos um limite hipotticop pUsamos a induo matemtic para provar que a

    suposio est correta rvore de recursoConverte a recorrncia em uma rvoreCada n representa o custo envolvido

    MestreFornece limites para a recorrnciaRequer memorizao de 3 casos

  • 13/05/2010

    10

    Substituio Pressupes a forma da soluo Usa a induo matemtica para encontrar

    constantes e mostrar que a soluo funcionaconstantes e mostrar que a soluo funciona So pode ser usado quando fcil pressupor a

    forma da resposta

    Induo Matemtica

    O Mtodo de Induo Matemtica um mtodo de demonstrao elaborado com base no Princpio de Induo Finita, p ,frequentemente utilizado para provar que certas propriedades so verdadeiras para todos os nmeros naturais. (fonte: e-escola) Passos:

    b d i d base da induo hiptese da induo passo da induo

  • 13/05/2010

    11

    Exerccios Base da induo: Para qualquer inteiro positivo

    n < 2n Provando: para n=1 1

  • 13/05/2010

    12

    FacaAlgo Funo executada em T(n) Vetor [left-right] = nVetor [left right] n

    Demos a sanguinte relao: T(n) = 2 T(n/2) + O(n) [O(n) a combinao] T(1) = O(1)

    relao de recorrncia: T(1) = 1 T(n) = 2.T(n/2) + n , para n2T(n) 2.T(n/2) n , para n2

    Resolvendo... 1. Chute: T(n) = n + n.logn 2. Prova:1. Caso base: 1 + 1.log 1 = 12. H.I.: assumir que vlido para valores at n-13. Provar T(n):

    = 2.(n/2 + n/2.log n/2) + n = n + n.(logn -1) + n = n + n.logn Logo, T(n) O(n.logn)

  • 13/05/2010

    13

    Resolvendo a relao de recorrncia T(n) = 2 T(n/2) + n = 2 [2 T(n/4) + n/2] + n = 2 [2 T(n/4) + n/2] + n = 4 T(n/4) + 2n = 4 [2 T(n/8) + n/4] + 2n = 8 T(n/8) + 3n

    (Q l i t ?) = (Qual a prxima sentena?) = 16 T(n/16) + 4n = 2k T(n/2k) + k n

    Resolvendo a relao de recorrencia T(n) = 2 T(n/2) + n = 2 [2 T(n/4) + n/2] + n = 2 [2 T(n/4) + n/2] + n = 4 T(n/4) + 2n = 4 [2 T(n/8) + n/4] + 2n = 8 T(n/8) + 3n

    (Q l i t ?) = (Qual a prxima sentena?)

  • 13/05/2010

    14

    Generalizando n/2k = 1 OU n = 2k OU log2 n = k k = log2 nk log2 n

    = 2k T(n/2k) + k n = 2log2 n T(1) + (log2n) n = n + n log2 n [lembrando T(1) = 1] = O(n log n)

    rvore de Recorrncia Desenhar a rvore

    Cada n representa o tamanho do problema Levar em conta Levar em conta

    Altura da rvore Nmero de passos em cada nvel

    Soluo Soma dos passos de todos os nveisp

  • 13/05/2010

    15

    rvore de recurso T(n) = 2 T(n/2) + n

    rvore de recorrncia

  • 13/05/2010

    16

    rovore de Recorrncia

    Fonte: http://www.dsc.ufcg.edu.br/~abrantes

    Tentativa e Erro um caminho metdico de tentativa de

    decises para verificar se o objetivo alcanado

    Cenrio Devo tomar decises entre vrias escolhas

    possveisNo tenho informaes para escolher corretamenteCada deciso me leva a um novo conjunto de escolhasAlgumas seqncias de decises podem resolver o

    problema

    Fora - Bruta

  • 13/05/2010

    17

    Animao

    Fim sem soluo

    incio ?

    ?

    Fim sem soluo

    ??

    Fim sem soluo

    Fim sem soluo

    Fim sem

    33

    ?

    successo !!!

    Fim sem soluo

    http://www.hbmeyer.de/backtrack/backtren.htm

    Recursos

    Knights Tourhttp://www.kongregate.com/games/EvgenyKarataev/knights-tourhttp://www.troyis.com/troyis.phpp y y p phttp://www.funmin.com/online-games/knight/index.phphttp://games144.com/game/6326-the-knights-tour-game.php

    8 Queenhttp://www.coolbuddy.com/games/8queens/default.htmhttp://www.fetchfido.co.uk/games/8_queens/8_queens.htm

    (fcil) http://www.blackdog.net/games/board/8queens/index.html

    L bi i tLabirintohttp://www.flashrolls.com/puzzle-games/Labyrinth-Game.htmhttp://www.vectorgame.com/2008/03/labyrinth.htmlhttp://www.addictinggames.com/labyrinth.html

  • 13/05/2010

    18

    Estretgia Tabuleiro com n n posies:

    cavalo se movimenta segundo regras do xadrez.

    Problema: a partir de (x0; y0), encontrar, se existir, um passeio do cavalo que visita todos os pontos do tabuleiropasseio do cavalo que visita todos os pontos do tabuleiro uma nica vez.

    Tenta um prximo movimento:

    (fonte: Ziviani, Nivio http://www.dcc.ufmg.br/algoritmos/)

  • 13/05/2010

    19

    Exemplos Labirinto

    Estretgia Nome da Clula

    Clulas linha coluna Podem andar para cima,baixo,esquerda e direita Quando estou traando o caminho, no volto para a

    mesma direo Refazer o caminho de qualquer celula lin col at o fim

    Tento mover CIMA e tento resolver recursivamente a partir deste ponto

    Tento BAIXO, ESQUERDA e DIREITA

    Para evitar loops infinitos, guardar os caminhos

  • 13/05/2010

    20

    N Rainhas Dado um tabuleiro NxN, colocar N rainhas no

    tabuleiro de forma que nenhuma ameace(*) a outra Uma rainha esta ameaada quando ela est na

    mesma linha, coluna ou diagonal

    Fora Bruta Gera um rvore com todas as solues possveis Qual o problema?

    Paga-se muito caro

  • 13/05/2010

    21

    Tentativa e Erro (Backtracking) Cria outra sub-rvoreCria outra sub rvore

    somente se no achar a soluo

    Pode achar mais que uma soluouma soluo

    Exerccios Implemente uma soluo para o sudoku

    utilizando a tcnica de tentativa e erro.

  • 13/05/2010

    22

    Diviso e Conquista Divide o problema em partes menores, Encontrar a soluo para as partes Combin las na soluo geral Combin-las na soluo geral

    Exemplo Encontrar o maior e o menor elemento de