Prova de Análise de Algoritmos e Complexidade - Questões e Respostas

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 A Questão 3 contém até duas opções corretas Se forem marcadas até duas não haverá penalidade da nota Respostas incorretas sofrem penalidades decréscimo na nota podendo a questão ser zerada 5 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 A função fn nlg n é polinomialmente limitada ou seja fn Onk para alguma constante positiva k Escolha uma opção Verdadeiro Falso A função fn lg 32n é polinomialmente limitada ou seja fn Onk para alguma constante positiva k Escolha uma opção Verdadeiro Falso Um algoritmo executa nn operações e na sequência outras n lg2n operações Seja fn a função que corresponde ao tempo total de execução deste algoritmo Marque a opção que corresponde ao que NÃO se pode afirmar sobre fn a fn Ωn2 lg n b fn ωn lg n c fn on3 d fn Θ4lg n Utilizando a definição de Θ apresente constantes c₁ c₂ e n₀ adequadas e prove que fn n5 n 6 Θn Dê um limite assintótico restrito notação Θ para a complexidade do trecho de código a seguir em função de n Considere que n é uma potência for int i n i 1 i2 for int j 0 j n j for int k 1 k nn k2 sum i j Selecione as opções que fornecem uma função monotonicamente crescente fn tal que fn Onlogn n3 e fn Ωn a Qualquer função do tipo fn a lg n b onde a e b são constantes e a 1 b Qualquer função do tipo fn a n b onde a e b são constantes e a 1 c Qualquer função do tipo fn an2 log n onde a é uma constante positiva d Qualquer função do tipo fn an3 bn2 cn d onde a b c e d são constantes e a 1 e fn n f Não existe tal função Considere a seguinte versão do algoritmo de ordenação da bolha 1 void bolha int n int v 2 int aux j i 3 for i 0 i n1 i 4 for j 0 j ni1 j 5 if vj vj1 6 aux vj 7 vj vj1 8 vj1 aux 9 10 11 Suponha que a execução de qualquer linha do código consome 1 unidade de tempo Dê o tempo de execução para o melhor e o pior casos do algoritmo Especifique quando esses casos ocorrem Lista de Exercícios Análise de Algoritmos Problema 1 Resposta Se a função é da ordem fn nlogn então temos que nlogn n12logn nlogn2 Mudando a base do algoritmo temos que logn logn n logn 10 Assim temos que n 1 2 logn10 Observe que se n 10 então logn10 1 Suponha que nk com k inteiro seja o polinômio de grau k que comparamos Se tomamos n 10r2 teremos 1 2 log102k10 k Assim teremos que n 1 2 log102k10 nr Exemplo se n 100 temos 10012 log10010 100 1000012 log1000010 100002 100000012 log10610 10000003 Então para n suficientemente grande n 1 2 logn10 supera nk para qualquer k fixo Resposta Falso Problema 2 Resposta A função é log32n como log3 1 temos que log3 0 477 e assim log32n 12n n0 1 Assim a função é polinominalmente limitada Resposta Verdadeiro Problema 3 Resposta Podemos dizer que os passos se somam fn a nn b n2 log2 Podemos associar b log2 b a uma nova constante O resultado é fn a n15 b n2 Assim a função é da ordem On2 Temos que é de classe Ωn15 de classe On2 Particular observamos a última relação 4logn que em resumo é fn n1log410 C n12 Não podemos dizer que existe K tal que fn a n15 b n2 K n05 Assim a falsa é fn Θ4logn Resposta fn Θ4logn Problema 4 Resposta Use aproximações para notar que 1 5n n12 6 1 5n 6 1 5n n 6 5n para n 6 Use c2 6 5 Analogamente observe que 0 n 1 5 n n12 6 Para um ajuste melhor lim n 1 5n n12 6 n 15 Por análise podemos garantir que existe um n suficientemente grande tal que 1 5 ε 1 5n n12 6 1 5 ε Basta tomar o n grande o suficiente 2 Problema 5 Resposta Observe que o comando i 2 satisfaz o seguinte i i2 O número de passos é log2n Isto descreve o primeiro for A seguir temos um for normal que resulta em n passos O último for que tem um número de passos proporcional a log2n2 pois n2 é o limite de parada A operação soma i j soma soma i j Podemos contabilizar 2 passos em cada execução pois se trata de duas somas i j e soma i j Assim a expressão é fn 2 log2n n logn2 4n log2n2 Podemos dizer que fn On log2n2 Problema 6 Resposta Observe que logn n3 3 que nos dá que Onlogn n3 On3 Também temos que n2 logn On3 Ambas são maiores que Ωn Assim já confirmamos que c e d estão na categoria desejada Já o item b é claramente do tipo Ωn e claramente menor que On3 Resta agora observar que n é muito maior que On3 e logn é menor que Ωn Resposta itens b c e d Problema 7 Resposta Esta função ordena o array ou vetor de forma crescente O processo é ir comparando os termos e quando ele encontra um maior ele adianta sua posição no array O melhor caso é quando o vetor já se encontra ordenado de forma crescente assim ele evita a etapa de atribuição Neste caso o if nunca funciona e ele apenas anda sobre os índices fn 2n 1 2n 2 2 1 2 n1n2 2 Cada parcela representa a variação dos números j para cada i fixo Note que o teste do if mesmo não sendo verdadeiro é executado sempre que passamos pelo for por isso contabilizamos duas vezes por serem dois comandos executados Agora o pior caso que se dá quando temos o vetor organizado em ordem decrescente fn 4n 1 4n 2 4 4 n1n2 2 A lógica aqui é que sempre entraremos no if quando entrarmos no for pois sempre o anterior será maior que o próximo ordem decrescente Após passar pelo primeiro ciclo o maior de todos estará na maior posição porém o resto do vetor estará decrescente e o raciocínio se repete