Prova Analise de Algoritmos e Resolucao de Recorrencias - Ciencia da Computacao

1 A notação utilizada é a mesma dos slides da disciplina 2 Cada aluno tem apenas uma tentativa Finalize somente quando terminar de responder todas as questões 3 Cada aluno é responsável por checar se seus arquivos foram devidamente anexados 4 O questionário deve ser aberto pelo aluno com antecedência e as questões copiadas para acervo pessoal pois caso haja algum problema na Turing no dia da entrega e somente neste caso as questões devem ser entregues por email dentro do horário previsto para encerramento da atividade Considere a relação de recorrência Tn 3Tn 3 n lg n com T1 1 Ao aplicar o Teorema Mestre para a obtenção de um limite assintótico restrito para Tn é possível concluir que Escolha uma opção a Não é possível aplicar o Teorema Mestre para a solução de Tn b Tn θn c Tn θn lg n d Tn θn lg² n e Tn θn lg³ Questão 1 Ainda não respondida Vale 200 pontos Marcar questão Dê uma relação de recorrência Tn que expressa o tempo de execução número de operações elementares executadas pela função recursiva abaixo que recebe como entrada o valor de n um inteiro positivo Não precisa resolver a recorrência Justifique sua resposta int fint n int count 1 if n 1 for int i 1 i nn i for int j 1 j ii j count 1 count fn 1 2fn 1 return count Questão 2 Ainda não respondida Vale 250 pontos Marcar questão Considere o seguinte algoritmo recursivo para calcular o valor máximo de um vetor vpr Seja Cn o número de comparações executadas na linha 7 do algoritmo por uma chamada de Máximovpr onde n r p 1 Deduzca do algoritmo uma recorrência que defina Cn e resolvaa exibindo uma fórmula fechada para Cn Ou seja dê a solução exata da recorrência Considere a relação de recorrência T1 1 Tn 2Tn4 3 n 2 Utilizando o método iterativo resolva a recorrência Tn apresentando um limite superior mais restrito Notação O Considere que n é uma potência na base mais adequada Apresente a resolução completa da questão 1 Para aplicar o teorema mestre devemos primeiro expressar a relação de recorrência na forma Tn aTnb fn onde a e b são constantes e fn é uma função que satisfaz certas condições Nesse caso podemos expressar a relação de recorrência da seguinte forma Tn 3Tn3 nlg2n onde a 3 b 3 fn nlgn Em seguida devemos determinar a taxa de crescimento assintótica de fn Podemos fazer isso considerando os dois casos a seguir Se fn Onc para alguma constante c logba então a taxa de crescimento assintótica de Tn é dada por Onc Se fn Onclgkn para algumas constantes c e k onde c logba e k 0 então a taxa de crescimento assintótica de Tn é dada por O nclgk1n Em nosso caso podemos ver que fn Onlgn que se enquadra no segundo caso com c log33 1 e k 1 Portanto a taxa de crescimento assintótica de Tn é dada por Onlg2n Assim o limite assintótico restrito para Tn é Onlg2n 2 O tempo de execução da função f pode ser expresso como uma relação de recorrência da seguinte forma Tn cn2i2 2Tn1 Tn1 c onde c é uma constante que representa o tempo gasto para realizar as outras operações elementares da função como as operações de adição e comparação Nessa relação de recorrência Tn representa o tempo de execução da função f quando ela é chamada com uma entrada de tamanho n e o termo cn2i2 representa o tempo gasto para executar o loop interno O termo 2Tn1 representa o tempo necessário para realizar as chamadas recursivas para f com tamanho de entrada n1 e o termo Tn1 representa o tempo necessário para realizar as chamadas recursivas para f com tamanho de entrada n 1 O termo c representa o tempo gasto para realizar as outras operações elementares na função Simplificando a relação ficaria Tn cn2i2 3Tn1 c Essa relação de recorrência pode ser usada para expressar o tempo de execução da função f em termos do tamanho de sua entrada 3 Para encontrar a recorrência que define Cn precisamos considerar os diferentes casos que podem ocorrer quando o algoritmo é chamado com um dado valor de n Quando n 1 o algoritmo divide o vetor de entrada em duas metades na linha 6 e chama a si mesmo recursivamente em cada metade O número de comparações realizadas na linha 8 é igual ao número de comparações realizadas pelas duas chamadas recursivas mais 1 para a comparação na linha 8 Portanto Cn Cn2 Cn2 1 para n 1 Portanto podemos escrever Cn como Cn 0 se n 1 Cn Cn2 Cn2 1 se n 1 Para resolver essa recorrência podemos usar o método da substituição Vamos definir Sn Cn Cn2 Cn2 Então para n 1 temos Sn Cn Cn2 Cn2 Cn2 Cn4 Cn4 1 Cn2 Cn2 Sn2 Cn2 Cn2 Sn2 Sn2 Pelo princípio da indução matemática podemos mostrar que Sn 2k Sn2k para qualquer inteiro positivo k Em particular definindo k log2 n obtemos Sn 2log2 n Sn2log2 n n S1 0 Substituindo de volta obtemos Cn Sn Cn2 Cn2 Cn2 Cn2 A solução geral para esta recorrência é da forma Cn an b Substituindo as condições iniciais C1 0 e C2 1 obtemos C1 0 a b C2 1 2a b Resolvendo este sistema de equações obtemos a 1 e b 1 Portanto a fórmula fechada para Cn é Cn n 1 ou Cn n 1 Isso significa que o número de comparações realizadas pelo algoritmo é linear no tamanho do vetor de entrada 4 Para resolver a recorrência usando o método iterativo podemos começar substituindo o valor de Tn na expressão da recorrência pelo valor de Tn4 Isso nos dá a seguinte expressão Tn 2 Tn4 3 Agora podemos continuar substituindo o valor de Tn4 na expressão acima pelo valor de Tn42 e assim por diante Continuando esse processo chegamos à seguinte expressão Tn 2 2 Tn42 3 3 4 Tn42 6 Tn 2 4 Tn43 6 3 8 Tn43 9 Tn 2 8 Tn44 9 3 16 Tn44 12 Observando essa sequência de expressões podemos perceber que o limite superior mais restrito para a recorrência é On Isso significa que o tempo de execução do algoritmo aumenta de forma linear em relação ao tamanho da entrada n Resolvendo de outra forma utilizando o método iterativo Para resolver uma relação de recorrência usando um método iterativo vamos começar escrevendo a sequência de valores que a função assume para valores crescentes de n T1 1 T2 2T24 3 21 3 5 T4 2T44 3 21 3 5 T8 2T84 3 25 3 13 T16 2T164 3 213 3 29 Como podemos ver os valores de Tn parecem estar aumentando rapidamente à medida que n aumenta Isso sugere que a função Tn pode ter o limite superior mais restrito para a recorrência é On o que significa que o tempo necessário para calcular Tn cresce no máximo linearmente com o tamanho de n