Análise e Projeto de Algoritmos: Recorrências e Métodos de Resolução

Análise e Projeto de Algoritmos Márcia Cappelle Erika Coelho e Hebert Coelho com slides dos Profs Humberto Longo e Hugo Nascimento Instituto de Informática Universidade Federal de Goiás 2021 INFUFG APA 20211 M Cappelle E Coelho H Coelho 1 1 de 796 Introducdo Quando um algoritmo faz uma chamada recursiva seu tempo de execucdo frequentemente é descrito por uma recorréncia Ex MergeSort e1 sen1 Tn 1 2Tn2 On sen1 Como resolver a recorréncia Ex Tn Onlgn eS 9 INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorréncias 285 315 de 796 Introdução Métodos Métodos apresentados aqui para resolver recorrências obter limites Θ e O Método iterativo Método de substituição Método da árvore de recursão e Método mestre INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 286 315 de 796 Introducdo Detalhes técnicos geralmente negligenciados Pisos e tetos Supomos que os argumentos das funcées sao inteiros Condicées limites que representam termos constantes Ex e1 sen1 Tn 1 2Tn2 On sen1 geralmente é referenciado apenas como Tn 2Tn2 On o8 9 INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorréncias 287 315 de 796 Método de substituição Etapas 1 Pressupor a forma da solução 2 Usar indução matemática para encontrar as constantes e mostrar que a solução funciona INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 288 315 de 796 Método de substituicdo Exemplo 1 senl1 Tin 2Tn2 n sen1 Supor Tn Onlgn 28 3 INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorréncias 289 315 de 796 Método de substituição Exemplo Base n 1 T1 1 Tn On lg n implica em Tn cn lg n para constantes c n0 e n n0 Mas T1 cn lg n 1 c 1 lg 1 1 0 INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 290 315 de 796 Método de substituição Exemplo Base n 2 T2 2T1 2 4 T2 c 2 lg 2 4 2c c 2 INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 291 315 de 796 Método de substituição Exemplo Hipótese de Indução Tm Om lg m para m n 2 Ou seja Tn2 cn2 lgn2 para alguma constante positiva c INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 292 315 de 796 Método de substituição Exemplo Prova para Tn On lg n Tn 2T n 2 n 2c n 2 lg n 2 n 2c n 2 lg n 2 n cn lg n cn lg 2 n cn lg n cn n cn lg n para c 1 INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 293 315 de 796 Método de substituição Como fazer um bom palpite Usar a mesma solução para uma recorrência similar Ex Tn 2Tn2 17 n é Tn On lg n Encontrar limites superiores e inferiores altos para a recorrência Em seguida abaixar gradualmente o limite superior e elevar o limite inferior Ex Tn Ωn e Tn On2 Sutilezas em alguns casos é necessário reforçar a hipótese de indução INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 294 315 de 796 Método de substituição Como evitar armadilhas Ex provar que Tn On ou seja Tn c n para alguma constante c Tn 2T n 2 n 2c n 2 n 2c n 2 n cn n On Errado pois não provamos a forma exata INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 295 315 de 796 Método de substituição Mudança de variáveis Manipulação algébrica visando tornar uma recorrência semelhante a outra Ex Considere Tn 2Tn lg n Faça m lg n ou seja 2m n Substituindo em Tn temos T2m 2T2m2 m Faça Sm T2m Substituindo na recorrência acima chegamos a Sm 2Sm2 m Recorrência do MergeSort Cuja solução é Sm Om lg m Portanto Tn T2m Sm Om lg m Olg n lg lg n INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 296 315 de 796 Método iterativo Descrição e exemplo Abrir repetidas vezes a recorrência até conseguir identicar um padrão na mesma Considere Tn 3T n 4 n Tn n 3T n 4 n 3 n 4 3T n 16 n 3 n 4 3 n 16 3T n 64 n 3 n 4 9 n 16 27T n 64 n 3 n 4 9 n 16 27 n 64 3iT n 4i Iteração até n 4i 1 ou seja i log4 n n 4i n 4i INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 297 315 de 796 Método iterativo Descricdo e exemplo Representar a recorréncia como um somatorioprodutorio e resolver 0 mesmo P Tnn39 916 271Gl43TE Segue que Tn n3490 427 4 384 1 co n 2 a Onlo843 I 4non On o8 9 INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorréncias 298 315 de 796 Método da árvore de recursão Características Semelhante ao método iterativo só que gerando uma árvore de recursão Útil quando a recorrência descreve o tempo de um algoritmo do tipo dividireconquistar 1 Devese abrir a recorrência criando uma árvore das chamadas recursivas 2 Cada nó da árvore representa o custo de um único subproblema 3 Somase todos os custos em cada nível da árvore 4 Computase então a altura da árvore e somase os custos dos níveis a m de obter o custo total da recorrência Esta técnica é muito utilizada para gerar uma boa suposição de tempo a qual é então validada através do método da substituição INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 299 315 de 796 Método da árvore de recursão Exemplo 1 Considere Tn 3T n 4 Θn2 Simplicação Tn 3T n 4 cn2 para c 0 e n 4k com k 0 INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 300 315 de 796 Método da arvore de recursao Exemplo 1 en cn an 3 3 aha a 2 Z 2 vo Q n n n n n n n n n 2 x ct eis zs cGs clas clas cGze ze 3 on T1 T1 T1 Onle8s 3 Formula do custo do nivel 2 i 3c a apeet cn Niveis i 012 logy 1 com esse custo 2 6 INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorréncias 301 315 de 796 Método da árvore de recursão Exemplo 1 Custo do último nível quando n 1 i log4 n Quantidade de nós 3i 3log4 n nlog4 3 T1 Θ1 Conclusão nlog4 3T1 Θnlog4 3 INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 302 315 de 796 Método da arvore de recursao Exemplo 1 Somando todos os custos temos logy n1 Tn 3 Jen Onlo84 3 j0 316841 9 log 3 oer cn On 084 O que é uma formula confusa 8 9 INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorréncias 303 315 de 796 Método da arvore de recursao Exemplo 1 Somando todos os custos temos log n1 Tn 5 Jen Onlo84 3 j0 CO en 0 z Onees8 G0 1 2 log 3 T316 On 84 iSen On43 On Note também que Tn Qn pela raiz da arvore de recorréncia o que nos leva a concluir que Tn On 28 9 INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorréncias 304 315 de 796 Método da arvore de recursdo Exemplo 1 Agora podemos usar 0 método da substituicdo para verificar se a suposicdo Tn On é correta Desejamos mostrar que Tn dn para alguma constante positiva d Tn 37 n4 en 3d I cn 3d4 cn dn cn dn sed 1613c o8 9 INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorréncias 305 315 de 796 Método da arvore de recursdo Exemplo 2 Tn Tn3 T2n3 On Simplificacdo Tn Tn3 T2n3 en cn cn ae 8 o2 on oO oN cg e9 cn LN AN AN OS J LN c 3 6 38 7 te at 9 INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorréncias 306 315 de 796 Método da arvore de recursdo Exemplo 2 Ramo mais profundo 2 3 5 n1 n5 2 logsgn 28 9 INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorréncias 307 315 de 796 Método da árvore de recursão Exemplo 2 Obs Se a árvore fosse completa teríamos 2log32 n folhas nlog32 2 nk com k 1 ωn log n Mas esse não é o caso já que há menos do que nlog32 2 folhas e a árvore reduz a quantidade de nós internos na medida em que desce abaixo dos níveis com n 3 1 e 2n 3 1 Logo consideramos por simplicação que Tn ainda é On log n INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 308 315 de 796 Método da árvore de recursão Exemplo 2 Prova por substituição Tn On lg n Tn dn lg n para algum d 0 e n n0 Tn Tn3 T2n3 cn d n 3 lg n 3 d 2n 3 lg 2n 3 cn passo de indução d n 3 lg n lg 3 d 2n 3 lg 2 lg n lg 3 cn d n 3 lg n lg 3 2 lg 2 2 lg n 2 lg 3 cn d n 3 3 lg n 3 lg 3 2 cn dnlg n lg 3 23 cn dnlg n lg 2 23 cn dnlg n 1 23 cn dnlg n 13 cn dn lg n dn 3 cn dn lg n para d 3c INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 309 315 de 796 Método Mestre Características Resolve recorrências da forma Tn aTnb fn onde a 1 e b 1 são constantes e fn é uma função assintoticamente positiva a é a quantidade de subproblemas cada um de tamanho nb fn é a soma dos tempos para dividir e conquistar o problema nb será interpretado com signicado nb ou nb INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 310 315 de 796 Método Mestre Regras 1 Se fn Onlogb a ϵ para alguma constante ϵ 0 então Tn Θnlogb a 2 Se fn Θnlogb a então Tn Θnlogb a lg n 3 Se fn Ωnlogb a ϵ para alguma constante ϵ 0 e se afnb cfn para alguma constante c 1 e para todo n sucientemente grande então Tn Θfn INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 311 315 de 796 Método Mestre Exemplo 1 Tn 9Tn3 n Temos que a 9 e b 3 e fn n Como fn n Onlogb a ϵ On2ϵ para ϵ 1 então Tn Θnlogb a Θn2 INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 312 315 de 796 Método Mestre Exemplo 2 Tn T2n3 1 Temos que a 1 e b 32 e fn 1 Como fn 1 Θnlog32 1 Θ1 então Tn Θnlogb a lg n Θlg n INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 313 315 de 796 Método Mestre Exemplo 3 Tn 3Tn4 n lg n Temos que a 3 e b 4 e fn n lg n Como fn n lg n Ωnlogb a ϵ Ωn0793ϵ para ϵ 0 2 e como afnb cfn para algum c 1 e n n0 3fn4 cfn 3n 4 lg n 4 cn lg n 3 4 lg n 4 c lg n 3 4 lg n 3 4 lg 4 c lg n 3 4 lg n 3 2 c lg n c 3 4 e n 1 então Tn Θfn Θn lg n INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 314 315 de 796 Método Mestre Exemplo 4 Tn 2Tn2 n lg n Dado que a 2 e b 2 logb a log2 2 1 Como fn n lg n fn Onlogb a ϵ On1ϵ para qualquer ϵ 0 fn Θnlogb a Θn e fn Ωnlogb a ϵ Ωn1ϵ para qualquer ϵ 0 fn n lg n é assintoticamente maior que nlogb a n fn n lg n não é polinomialmente maior que nlogb a n fn nlogb a n lg n n lg n é assintoticamente menor que nϵ ϵ 0 Consequentemente Tn não está em nenhum caso previsto pelo Teorema Mestre INFUFG APA 20211 M Cappelle E Coelho H Coelho Recorrências 315 315 de 796 Livros Texto T H Cormen C E Leiserson e R L Rivest Introduction to Algorithms McGrawHill New York 1990 C H Papadimitriou U V Vazirani e S Dasgupta Algoritmos McgrawHill Brasil 2009 U Manber Algorithms A Creative Approach AddisonWesley 1989 D E Knuth The Art of Computer Programming Volume 1 Fundamental Algorithms Addison Wesley 1998 D E Knuth The Art of Computer Programming Volume 2 Sorting and Searching Addison Wesley 1998 N Ziviani Projeto de Algoritmos com Implementações em Pascal e C Editora Thomson 2a Edição 2004 INFUFG APA 20211 M Cappelle E Coelho H Coelho Bibliograa 796 796 de 796