Prova de Algoritmos - Pontifícia Universidade Católica de Minas Gerais

Pontifícia Universidade Católica de Minas Gerais Projeto e Análise de Algoritmos Prof Walisson Ferreira de Carvalho Questão 1 Encontre a fórmula fechada para a seguinte soma 1 1 2 1 2 3 1 3 4 1 𝑛 𝑛 1 Questão 2 Encontre a fórmula fechada do somatório abaixo e em seguida prove a usando indução matemática 4𝑖 52 4𝑖 52 𝑛 𝑖1 Questão 3 Usando a propriedade 𝑆𝑛 𝑎𝑛1 𝑎0 𝑎𝑖1 𝑛 𝑖0 encontre a fórmula fechada do somatório abaixo e em seguida prove a usando indução matemática Lembrese que 𝑎𝑥𝑖 𝑎𝑎𝑥𝑛1 1𝑥 𝑛 𝑖0 𝑆𝑛 4𝑖𝑋5𝑖 𝑛 𝑖0 Questão 4 Dada função abaixo responda a Explique o funcionamento da função b Faça a análise de complexidade da função c Essa função é On3 Prove d Essa função é On2 Prove e Essa função é On Prove f Essa função é Ω n3 Prove g Essa função é Ω n2 Prove h Essa função é Ω n Prove i Essa função é Θ n3 Prove j Essa função é Θ n2 Prove k Essa função é Θ n Prove Questão 5 Em um experimento uma determinada colônia de bactérias tem uma população inicial de 50000 A população é contada a cada 2 horas e ao final do intervalo de 2 horas a população triplica Seja an o número de bactérias presentes no início do nésimo período de tempo a Deduza a relação de recorrência Justifique b Determine a fórmula fechada da relação de recorrência encontrada em a Justifique Questão 6 Considere o algoritmo a seguir Suponha que a operação crucial é o fato de inspecionar um elemento O algoritmo inspeciona os n elementos de um conjunto e de alguma forma isso permite descartar 25 dos elementos e então fazer uma chamada recursiva sobre os 3n5 elementos restantes a Escreva uma equação de recorrência que descreva este comportamento b Converta esta equação para um somatório c Dê a fórmula fechada para este somatório Questão 7 Use árvore de recursão e teorema mestre para apresentar solução assintoticamente firme para a seguinte recorrência 𝑇𝑛 4𝑇 𝑛 5 𝑐𝑛2