Prova Analise de Algoritmos - Questoes e Resolucao

Noções de Análise de Algoritmos 1 35 points Para cada uma das afirmações abaixo prove se é verdadeiro ou falso justificando formalmente usando definições manipulações algébricas e implicações se for preciso Atenção Para resolver essa questão você deve obrigatoriamente empregar a definição de notação BigO vista em sala a n² 200n 300 On b 10n² 200n 500n On² c 2n² 20n 50 On d Seja Cnk o número de combinações de n objetos tomados k a k É verdade que Cn2 On² É verdade que Cn3 On³ 2 15 points Sejam as funções de complexidade an n² n 549 e bn 49n 49 referentes a certos algoritmos A e B respectivamente Para que valores de n é melhor aplicar o Algoritmo A 3 25 points Faça um algoritmo que ordene os elementos de um vetor de inteiros em ordem crescente Qual a complexidade de pior caso e melhor caso do seu algoritmo Prove que suas respostas estão corretas 4 25 points A sequência de Fibonacci é uma sequência de elementos F0 F1 Fn definida do seguinte modo Fj j se 0 j 1 Fj 1 Fj 2 se j 1 Elaborar um algoritmo iterativo não recursivo para determinar o elemento Fn da sequência cuja complexidade seja linear em n Apresente um argumento informal de por quê seu algoritmo é linear Resolva as questões usando papel e caneta em ordem Logo após tire fotos das respostas com atenção aos seguintes detalhes 1 LEGIBILIDADE Suas respostas devem ser legíveis no papel e também nas fotos tiradas ao final Verifique se suas fotos não ficaram borradas Para facilitar tire uma foto para cada questão submetida Certifiquese de que você tenha escrito um cabeçalho com seu nome e matrícula na resposta da primeira questão 2 Formato PDF Utilize a ferramenta de sua escolha para gerar um arquivo PDF com as fotos de suas respostas na ordem em que os itens foram pedidos 3 SUBMISSÃO Via Moodle faça upload do arquivo PDF com suas respostas na seção da respectiva atividade no Moodle 4 REQUISITOS Você é responsável por verificar os requisitos de submissão e que o upload funcionou corretamente Após submeter suas respostas no Moodle verifique se consegue efetuar o download do arquivo e abrilo corretamente Se você não verificar e ao final o arquivo não tiver sido enviado corretamente sua nota na atividade não será contabilizada Não envie a solução da tarefa por email pois ela não será considerada 1 a Falso pois não existem tal que para todo 𝑛0 𝑐 ℕ 𝑛 2 200𝑛 300 𝑐𝑛 Podemos observar também que evidenciando que 𝑛 𝑛0 𝑛 lim 𝑛 𝑛 2200𝑛300 0 quando cresce temos que 𝑛 𝑛 2 200𝑛 300 𝑛 b Verdadeiro pois para todo 10𝑛 2 200𝑛 500 𝑛 10𝑛 2 200𝑛 2 500𝑛 2 710𝑛 2 𝑛 1 Portanto existem tal que para 𝑛0 1 𝑐 710 ℕ 10𝑛 2 200𝑛 500 𝑛 𝑐𝑛 2 todo 𝑛 𝑛0 Logo pela definição temos que 10𝑛 2 200𝑛 500 𝑛 𝑂𝑛 2 c Falso pois não existem tal que para todo 𝑛0 𝑐 ℕ 2𝑛 2 20𝑛 50 𝑐𝑛 Podemos observar também que evidenciando que 𝑛 𝑛0 𝑛 lim 𝑛 2𝑛 220𝑛50 0 quando cresce temos que 𝑛 2𝑛 2 20𝑛 50 𝑛 d Verdadeiro pois Portanto existem 𝐶𝑛 2 𝑛𝑛1 2 𝑛𝑛 1 𝑛 2 𝑛 𝑛 2 tal que para todo Logo pela definição 𝑛0 1 𝑐 1 ℕ 𝐶𝑛 2 𝑐𝑛 2 𝑛 𝑛0 temos que 𝐶𝑛 2 𝑂𝑛 2 Verdadeiro pois 𝐶𝑛 3 𝑛𝑛1𝑛2 6 𝑛𝑛 1𝑛 2 𝑛 3 3𝑛 2 2𝑛 𝑛 3 2𝑛 3 3𝑛 3 Portanto existem tal que para todo 𝑛0 1 𝑐 3 ℕ 𝐶𝑛 3 𝑐𝑛 3 𝑛 𝑛0 Logo pela definição temos que 𝐶𝑛 3 𝑂𝑛 3 2 Queremos determinar tal que 𝑛 𝑎𝑛 𝑏𝑛 𝑎𝑛 𝑏𝑛 𝑛 2 𝑛 549 49𝑛 49 𝑛 2 50𝑛 500 0 Vamos determinar as raízes de 𝑛 2 50𝑛 500 𝑏 2 4𝑎𝑐 50 2 4 1 500 𝑛 𝑏 2𝑎 50 500 2 𝑛1 50 500 2 36 18 𝑛2 50 500 2 13 82 Como temos que quando Como 𝑎 1 𝑛 2 50𝑛 500 0 13 82 𝑛 36 18 temos que será melhor optar pelo algoritmo A quando 𝑛 ℤ 14 𝑛 36 3 include iostream include vector include limitsh using namespace std int main int n cin n vectorint vn for int i 0 i n i cin vi forint i 0 i n1 i int menor INTMAX int pos 1 forint j i 1 j n j ifvj menor menor vj pos j int aux vpos vpos vi vi aux for int i 0 i n i cout vi cout endl return 0 O algoritmo proposto é conhecido como Selection Sort onde a cada iteração 𝑖 temos que está ordenado e todo e temos que 𝑣0 𝑖 1 𝑎 𝑣0 𝑖 1 𝑏 𝑣𝑖 𝑛 Queremos ordenar Iremos selecionar o menor elemento de e 𝑎 𝑏 𝑣𝑖 𝑛 𝑣𝑖 𝑛 colocálo na posição fazendo com que esteja ordenado e todo 𝑣𝑖 𝑣0 𝑖 𝑎 𝑣0 𝑖 e temos que Tendo assim uma invariante de laço que vale 𝑏 𝑣𝑖 1 𝑛 𝑎 𝑏 para todo 𝑖 1 𝑛 1 O algoritmo possui complexidade de pior e melhor caso iguais a Isso 𝑂𝑛 2 acontece porque o algoritmo sempre executa instruções 𝑖0 𝑛1 𝑗𝑖1 𝑛 𝐶 𝑖0 𝑛1 𝑗𝑖1 𝑛 𝐶 𝐶 𝑖0 𝑛1 𝑗𝑖1 𝑛 1 𝐶 𝑖0 𝑛1 𝑛 𝑖 𝐶 𝑖0 𝑛1 𝑛 𝑖0 𝑛1 𝑖 𝐶 𝑛𝑛 1 𝑛𝑛1 2 𝑖0 𝑛1 𝑗𝑖1 𝑛 𝐶 𝐶 𝑛𝑛1 2 𝐶𝑛 2 𝑛 𝐶𝑛 2 𝑂𝑛 2 4 include iostream include vector using namespace std int main int n cin n vectorint Fn1 F0 0 F1 1 forint i 2 i n i Fi Fi1 Fi2 cout Fn endl return 0 O algoritmo apresentado é linear pois ele irá executar vezes o laço 𝑛 1 Resultando assim em uma complexidade linear 1 a Falso pois não existem n0c ℕ tal que n 2200n300cn para todo nn0 Podemos observar também que lim n n n 2200n300 0 evidenciando que quando n cresce temos que n 2200n300n b Verdadeiro pois 10n 2200n 500 n 10n 2200n 2500n 2710n 2 para todo n1 Portanto existem n01c710ℕ tal que 10n 2200n 500 n c n 2para todo nn0 Logo pela definição temos que 10n 2200n 500 n On 2 c Falso pois não existem n0c ℕ tal que 2n 220n50cn para todo nn0 Podemos observar também que lim n n 2n 220n50 0 evidenciando que quando n cresce temos que 2n 220n50n d Verdadeiro pois Cn2nn1 2 nn1n 2nn 2 Portanto existem n01c1ℕ tal que Cn2cn 2para todo nn0 Logo pela definição temos que Cn2On 2 Verdadeiro pois Cn3nn1n2 6 nn1n2n 33n 22nn 32n 33n 3 Portanto existem n01c3ℕ tal que Cn3c n 3para todo nn0 Logo pela definição temos que Cn3On 3 2 Queremos determinar n tal que anbn anbn n 2n54949n49 n 250n5000 Vamos determinar as raízes de n 250n500 Δb 24 ac nb n150 n250 Como a1 temos que n 250n5000 quando 1382n3618 Como nℤ temos que será melhor optar pelo algoritmo A quando 14n36 3 include iostream include vector include limitsh using namespace std int main int n cin n vectorint vn for int i 0 i n i cin vi forint i 0 i n1 i int menor INTMAX int pos 1 forint j i 1 j n j ifvj menor menor vj pos j int aux vpos vpos vi vi aux for int i 0 i n i cout vi cout endl return 0 O algoritmo proposto é conhecido como Selection Sort onde a cada iteração i temos que v0i1 está ordenado e todo av0i1 e bvin temos que ab Queremos ordenar vi n Iremos selecionar o menor elemento de vi n e colocálo na posição vi fazendo com que v0i esteja ordenado e todo av0i e bvi1n temos que ab Tendo assim uma invariante de laço que vale para todo i1n1 O algoritmo possui complexidade de pior e melhor caso iguais a On 2 Isso acontece porque o algoritmo sempre executa i0 n1 ji1 n C instruções i0 n1 ji1 n CC i0 n1 ji1 n 1C i0 n1 niC i0 n1 ji1 n CC nn1 2 Cn 2nC n 2On 2 4 include iostream include vector using namespace std int main int n cin n vectorint Fn1 F0 0 F1 1 forint i 2 i n i Fi Fi1 Fi2 cout Fn endl return 0 O algoritmo apresentado é linear pois ele irá executar n1 vezes o laço Resultando assim em uma complexidade linear