Prova Analise de Algoritmos Complexidade Assintotica e Notacao - Ciencias da Computacao

Informação Marcar questão 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 1 contém até duas opções corretas Se forem marcadas até duas não haverá penalidade da nota Caso sejam marcadas mais do que duas opções será aplicada uma penalidade 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 Questão 1 Ainda não respondida Vale 20 pontos Marcar questão Seja n um inteiro maior do que 1 Assinale cada opção que corresponde a uma função fn tal que fn O5lg n e fn Ωn2 Escolha uma ou mais a fn n2 lg n 100n b fn nn c fn 5n n3 d fn n2 n lg n e fn n lg10 n Questão 2 Ainda não respondida Vale 10 pontos Marcar questão A função fn lg1000 n é polinomialmente limitada ou seja fn Onk para alguma constante positiva k Escolha uma opção Verdadeiro Falso A função fn nn31n é polinomialmente limitada ou seja fn Onk para alguma constante positiva k Escolha uma opção Verdadeiro Falso Utilizando a definição de Θ apresente constantes c1 c2 e n0 adequadas e prove que fn n27 n lg n 4 Θn2 Para o trecho de algoritmo abaixo dê as complexidades assintóticas de tempo de melhor e pior casos usando a notação Θ em função de n um valor inteiro positivo recebido como entrada Considere que x e y são valores reais quaisquer Justifique sua resposta sum 0 if x y for int i 1 i nn i2 for int k 1 k n2 k sum i else for int j 0 j 100 j for int k j k n2 k sum j Questão 6 Ainda não respondida Vale 20 pontos Marcar questão Um certo algoritmo executa dⁿ operações e cada uma dessas operações é executada em tempo Od logd dⁿ onde d e n são números inteiros maiores do que 1 O limite assintótico superior mais justo sobre o tempo total de execução do algoritmo é Escolha uma opção a Odⁿ¹ lg n b Odⁿ¹ n c Odⁿ n d Nenhuma das outras alternativas e Odⁿ d lg n Objetivas 1 nenhuma resposta correta tal função não existe pois 5log m Ont logo não há função limitada inferiormente por n² e superiormente por 5log m 2 Verdadeiro dada que log m Om¹ log m Om¹⁰⁰⁰ 3 Verdadeiro m131n m13 1xn m13n m13 Om⁴ k 13 6 custa Od log d² Od m operações dⁿ total Odⁿ d n Odⁿ¹ n b Discursivas 4 devemos provar que m₀ c₁ c₂ tais que 0 c₁ n² n²7 n log n 4 c₂ n² para n m₀ Vamos analisar os dois sistemas de inequações 1º c₁ n² n²7 n log n 4 I tomando n 0 podemos dividir ambos os lados por n² c₁ 17 log nn 4n² fx gx lim n fx c₁ lim n gn 17 logo para c₁ 17 a 1ª proposição é verdadeira I to máximo c1 114 I n214 n27 n log n 4 0 n214 n log n 4 essa função é sempre positiva n 0 logo para a 1 inequação podemos selecionar qualquer n0 0 2a n27 n log n 4 c2n2II 17 log nn 4n2 c2 fn gn lim n fn 17 lim n gn c2 logo para 17 c2 a 2a proposição é verdadeira para m m0 para algum m0 tomando c2 12 II n27 n log n 4 n22 5n214 n log n 4 0 5n214 4 n log n n log n 4 5n214 monótona crescente monótona decrescente para n 1 para n 1 f1n f2n f11 f21 f13 f23 logo podemos tomar n0 3 Por fim temos c1 114 c2 12 e n0 3 são constantes adequadas que tornam fn Θn2