Cópia de IAA - Comentários sobre respostas da prova on line 1, questão 1, versão curta 2023

Prévia do material em texto

IAA - Dificuldades na 
resolução e na 
correção da prova on 
line 1 - 2023
Fábio Nakano
Q1 - respostas “mínimas” dentro do que eu espero
“ O tamanho do problema, nesse caso, é determinado pelo valor da variável de entrada 
N. Isso ocorre pois o valor de N determina quantas vezes a função será chamada 
recursivamente. Ou seja, quanto maior o valor de N, mais vezes a função será chamada.”
“A característica do problema que corresponde ao tamanho do problema é a variável n, 
porque quanto maior essa variável, ou seja, quanto mais longe do início da sequência o 
número que deseja-se calcular está, mais vezes a função fibonaccir(int n) será executada, 
em outras palavras, a recursão do código será maior.”
Q1 - Fugiu à pergunta? Não há problema se o 
tamanho do problema corresponde ao valor 
armazenado em uma variável…
“A característica do problema que corresponde diretamente ao tamanho do problema no 
preâmbulo de análise de algoritmos é a QUANTIDADE DE DADOS DE ENTRADA que o 
algoritmo precisa processar para que se encontre a solução do problema. Assim, 
entende-se que o tamanho do problema é diretamente proporcional à dimensão dos 
dados de entrada, sendo tal tamanho comumente representado por uma variável "N" que 
pode indicar diferentes aspectos: tamanho de uma lista, tamanho de um vetor, 
quantidade de elementos em uma matriz, etc.”
Q1 - Tem idéia do que é a resposta da próxima 
questão mas parece não saber a resposta desta 
questão…
“Como esse problema se trata de uma FUNÇÃO RECURSIVA, a característica de seu 
tamanho seria do tipo \( T(n) = T(n-1) + T(n-2) \)”
Q1 - não respondeu ao que foi pedido na 
pergunta, cometeu um erro e foi excessivo…
“A recursividade da função aumenta o tamanho do problema, a recursividade pode 
aumentar o tempo de execução de uma função, mas o impacto depende da 
implementação específica da recursão e do problema sendo resolvido. É importante 
analisar cuidadosamente o algoritmo recursivo e, quando necessário, considerar 
abordagens iterativas ou outras técnicas de otimização para melhorar o desempenho.”
Q1 - não respondeu explicitamente ao que foi 
pedido na pergunta … talvez já tenha cursado a 
disciplina…
“Essa recorrência é semelhante à recorrência da sequência de Fibonacci em si, pois 
cada chamada da função divide o problema em duas subproblemas menores (n-1 e 
n-2) até chegar aos casos base. A complexidade de tempo dessa implementação é 
exponencial, pois a função realiza uma quantidade exponencial de chamadas 
recursivas, o que leva a um tempo de execução exponencial em relação a n. Para 
melhorar a eficiência, você pode implementar uma versão iterativa ou usar 
memoização para armazenar os resultados intermediários e evitar chamadas 
redundantes. Isso reduziria a complexidade de tempo para linear em relação a n.”
Q2 - resposta 
“mínima” que 
espero 
Q2 - Esta resposta desvia da esperada
“A função fibonaccir chama a sim mesma duas vezes nas seguintes linhas de código: linha 19: "int 
aux1=fibonaccir(n-1, nivel+1);" linha 22: "int aux2=fibonaccir(n-2, nivel+1);" Assim, 
considerando uma chamada para o valor n, o tempo de execução dependerá das chamadas 
sucessivas para n-1 e n-2, pois elas são feitas até que o caso base seja atingido. Portanto, a 
função em forma de recorrência que é proporcional ao tempo de execução da função fibonaccir 
é T(n) = T(n-1) + T(n-2).”
Q3- Resposta “minima” 
esperada
Q3 - demonstrou por 
indução mas tem um 
erro… e agora?...