Prova-Analise-de-Algoritmos-e-Teoria-da-Computacao-Questoes-e-Resolucao

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 Questão 1 Ainda não respondida Vale 200 pontos Marcar questão Considere a relação de recorrência Tn 3Tn3 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 2 Ainda não respondida Vale 250 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 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 Deduza 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