Prova Projeto Analise de Algoritmo

Projeto e Análise de Algoritmos P1 Engenharia da Computação 4º Período 20242 Prof Philippe Leal Alunoa Data 14032025 ATENÇÃO A complexidade assintótica somente será aceita se a local estiver correta 1 Valor 15 Resolva a seguinte relação de recorrência sujeito à condição básica T11 Tn2Tn21n² Obs 1 Não é necessário provar somente encontrar a SFF Obs 2 Reduza a SFF ao máximo que conseguir 2 Valor 20 Determine a complexidade local e assintótica de pior caso do algoritmo em pseudocódigo a seguir n2 1 R 1 2 para i n 1 i 1 i faça 3 para j 1 j i 1 j faça 4 se Vj 0 então 5 R R 3 6 senão 7 para k 2 k n 1 k faça 8 R R i 9 fim 10 fim 11 fim 12 fim 13 retorna R Obs 1 A complexidade de cada linha onde há operação do algoritmo tem que ser apresentada Obs 2 A complexidade assintótica somente será aceita se a local de cada linha onde há operação estiver correta Obs 3 As tabelas para o cálculo da complexidade também têm que ser apresentadas 3 Valor 20 Considere duas matrizes A aᵢⱼₙₓₙ e B bᵢⱼₙₓₙ de números inteiros Faça uma função iterativa na Linguagem C para verificar se a propriedade 1 abaixo é respeitada Sua função deve retornar 1 se a propriedade for respeitada ou retornar 0 caso contrário Determine a complexidade local e assintótica de pior caso da sua função Considere que a função receberá por parâmetro as duas matrizes já preenchidas bⱼⱼ aᵢⱼ j 1 n Obs 1 Lembrese que na Linguagem C os índices de uma matriz variam de 0 até n 1 e não de 1 até n como consta na expressão acima Obs 2 Não é permitido utilizar qualquer outra estrutura de dados vetor matriz lista etc além das duas matrizes Obs 3 As complexidades local e assintótica só serão corrigidas se o algoritmo estiver totalmente correto 4 Valor 15 Considere a sequencia S 5 10 15 20 25 Considere também um número natural n n 1 o qual indica que devem ser somados os n primeiros termos de S Por exemplo para n 4 o resultado seria S 5 10 15 20 50 Crie uma função recursiva na Linguagem C que receba por parâmetro o valor de n e calcule a soma dos n primeiros termos de S Encontre a relação de recorrência do seu algoritmo e a resolva encontre a SFF Obs 1 Não é permitido utilizar outra variável na função Somente a variável n recebida por parâmetro Obs 2 Não é permitido utilizar qualquer estrutura de repetição e nem de dados vetor matriz lista etc na função Na dúvida do que é permitido pergunte ao Professor Obs 3 Não é necessário fazer a verificação somente encontrar a SFF Obs 4 Reduza a SFF o máximo que conseguir O que confia no Senhor esse é feliz Provérbios 1620b Questão 1 Valor 15 Resolva a seguinte relação de recorrência sujeito à condição básica T11 Tn2Tn21n² Obs 1 Não é necessário provar somente encontrar a SFF Obs 2 Reduza a SFF ao máximo que conseguir 1 m log₂ n Começamos expandindo a recorrência para os primeiros valores de i Para i 1 Tn 2Tn2 1n² Para i 2 Tn 2 2Tn2² n2² 1n² 4Tn2² 2 1n2² 1n² 4Tn2² 2 4n² 1n² Para i 3 Tn 4 2Tn2³ n2² 8n² 1n² 8Tn2³ 4 1n4² 8n² 1n² 8Tn2³ 4 16n² 8n² 1n² 2 Em geral após i iterações Tn 2ⁱ Tn2ⁱ j0 to i1 2ʲ n2ʲ² 3 Tomando i m log₂ n temos 2ᵐ n e Tn 2ᵐT1 j0 to m1 2ʲ n2ʲ² 2ᵐT1 n 1 n j0 to m1 2ʲ n2ʲ² j0 to m1 2ʲ 2²ʲn² 1n² j0 to m1 2³ʲ 1n² 2³ᵐ 12³ 1 1n² n³ 17 n³7n² 17n² n7 17n² 4 Somando as partes Tn n n7 17n² 8n7 17n² Tn 8n7 17n² Questão 2 Valor 20 Determine a complexidade local custo de cada linha e a complexidade assintótica de pior caso do seguinte algoritmo para n2 1 R 1 2 para i n1 i 1 i faça 3 para j 1 j i1 j faça 4 se Vj 0 então 5 R R 3 6 senão 7 para k 2 k n1 k faça 8 R R i 9 fim 10 fim 11 fim 12 fim 13 retorna R Linha Operação Custo cₗ vezes Total cₗ 1 atribuição R 1 Θ1 1 Θ1 2 comparação e decrementar Θ1 n1 Θn 3 comparação e incrementar Θ1 i1 i2 n11 Θn² 4 comparação Vj 0 Θ1 i1 i2 n11 Θn² 5 multiplicação e atribuição Θ1 i1 i2 n11 Θn² 6 7 inicialização do k Θ1 ij Vj0 1 see note 8 soma e atribuição Θ1 i1 i2 n2 j1 Θn³ 9 comparação e incremento Θ1 mesmo caso de 8 Θn³ 13 retorno Θ1 1 Θ1 Descrição Coluna Linha número do passo no pseudocódigo Coluna Operação ação principal realizada atribuição comparação etc Coluna Custo cₗ tempo unitário de execução dessa operação constante Θ1 Coluna de execuções número de vezes que a linha é executada no pior caso Ex i1 i2 vem do laço duplo sobre i e j Coluna Total produto do custo unitário pelo número de execuções oferecendo o termo que cada linha contribui para o custo assintótico total Nota No pior caso todas as entradas caem no senão logo a soma interna linhas 79 ocorre i1 i2 vezes para j e para cada uma Θn iterações em k Tn Θ1ₗᵢₙₕₐ ₁ Θnₗᵢₙₕₐ ₂ Θn²ₗᵢₙₕₐₛ ₃₄₅ Θn² nₗᵢₙₕₐₛ ₇₉ Θ1 Θn Θn² Θn³ Θn³ Tn Θn³ Questão 3 Valor 20 Considere duas matrizes A aijnn e B bijnn de inteiros Faça uma função iterativa em C que verifica se para todo j 0 n 1 bjj i0 ijn1 aij A função deve retornar 1 se a propriedade é satisfeita e 0 caso contrário Em seguida determine a complexidade local custo de cada linha e a complexidade assintótica de pior caso retorna 1 se Bjj ij Aij para todo j senão 0 int verificaint n int Ann int Bnn long long prod linha 1 forint j 0 j n j linha 2 prod 1 linha 3 forint i 0 i n i linha 4 ifi j linha 5 continue linha 6 prod Aij linha 7 if Bjj prod linha 8 return 0 linha 9 return 1 linha 10 Linha Operação Custo cℓ execuções cℓ 1 declaração prod Θ1 1 Θ1 2 forj comparação e incremento Θ1 n 1n Θn 3 atribuição prod1 Θ1 n Θn 4 fori comparação e incremento Θ1 nn 1n² Θn² 5 comparação ij Θ1 n² Θn² 6 continue Θ1 n Θn 7 multiplicação prodAij Θ1 nn 1 Θn² 8 comparação Bjjprod Θ1 n Θn 9 return 0 Θ1 0 pior caso Θ1 10 return 1 Θ1 1 Θ1 Descrição das colunas Linha número da instrução no código C Operação ação executada declaração comparação atribuição etc Custo cℓ custo unitário de cada operação Θ1 execuções quantas vezes a linha roda no pior caso detalhando comparações e incrementos cℓ contribuição assintótica de cada linha para o custo total Somando apenas os termos dominantes Θn² linhas 457 n² Θn linhas 2368 n Θ1 outras Θn² Tn Θn² Questão 4 Valor 15 Considere a sequência S 5 10 15 20 25 e um natural n 1 Definimos recursivamente a função que retorna a soma dos n primeiros termos de S Retorna Sn 5 10 5n int somaSint n if n 1 custo 1 return 5 S1 5 else return somaSn1 5n custo 1 além da chamada Seja Tn o número de operações desta função Então T1 Θ1 Tn Tn 1 Θ1 n 2 Seja c a constante que representa o custo Θ1 de cada chamada extra Temos T1 c Tn Tn 1 c n 2 Agora calculamos explicitamente para alguns valores T1 c T2 T1 c c c 2c T3 T2 c 2c c 3c T4 T3 c 3c c 4c Tk Tk 1 c k 1c c k c Tn Tn 1 c n 1c c n c Portanto Tn n c Θn Para a soma dos valores definimos Sn 5 n 1 Sn 1 5n n 2 Em fecho Sn k1n 5k 5 k1n k 5 nn 12 5nn 12 Sn 5nn 12