Elabore um algoritmo em pseudocódigo que, dado um conjunto finito de pares (x_i,y_i) com x_i equidistantes…

Questão

Elabore um algoritmo em pseudocódigo que, dado um conjunto finito de pares (x_i,y_i) com x_i equidistantes, verifique se os pontos são exatamente de uma função y = a x^2, determine o coeficiente a e indique se a parábola tem máximo ou mínimo. Analise a complexidade do algoritmo.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Resposta modelo (pseudocódigo e justificativa): 1) Ordenar pares por x (se necessário). Assuma passo h = x_2 - x_1 ? 0 e que todos os passos são iguais. Complexidade O(n log n) se ordenar, O(n) se já ordenado. 2) Calcular primeiras diferenças d[i] = y[i+1] - y[i] para i=1..n-1 (O(n)). 3) Calcular segundas diferenças dd[i] = d[i+1] - d[i] para i=1..n-2 (O(n)). 4) Verificar se todas dd[i] são iguais dentro de tolerância numérica e (para dados reais). Se não, concluir que não é y=ax^2. 5) Se constantes, para passo h, a = dd / (2·h^2) (porque ?²y ˜ 2a·h^2). Use média das dd para reduzir ruído. 6) Verificar que para cada x_i, |y_i - a·x_i^2| = e; se sim, aceitar e retornar a. 7) Determinar máximo ou mínimo: se a>0 há mínimo em (0,0) com valor 0; se a<0 há máximo em (0,0) com valor 0. (No caso geral de forma ax^2+bx+c isso muda; aqui b=0 implicando vértice na origem). Complexidade total: O(n) após ordenação; espaço adicional O(n). Observações: escolher e conforme precisão dos dados, usar média das segundas diferenças para robustez e tratar casos com x não centrados (se x não contém 0, ajuste transformando x?x-x0 para verificar formato ax^2).

Explicação

O algoritmo proposto utiliza diferenças finitas para identificar se os pontos seguem a forma de uma parábola, permitindo calcular o coeficiente a de forma precisa. A verificação da constância das segundas diferenças garante que os dados se ajustam a uma função quadrática, enquanto a análise do sinal de a determina a natureza do vértice. A complexidade do algoritmo é eficiente, especialmente considerando a ordenação e a análise linear subsequente.

Raio-X da questão

Questões parecidas com resolução

• Descreva um procedimento algorítmico para, dado um conjunto finito de pares (x,y) com x inteiros, decidir se existe uma…
• Descreva um algoritmo (pseudocódigo) que detecte se uma tabela finita de pares (x,y) representa uma função do tipo y = a…
• Dado um conjunto finito de pares (xi, yi) com xi distintos, descreva um procedimento computacional para verificar se…
• Descreva um algoritmo em palavras ou pseudocódigo que, dada uma tabela de pares (x,y), verifique se os pontos podem ser…
• Considere dados de um processo computacional: x = 0,1,2,3 e y = 0, k, 4k, 9k com k>0 desconhecido. Descreva como…
• A partir de uma tabela de pares (x,y) gerada por um sistema, proponha um procedimento algorítmico para: 1) verificar se…

Todas as questões de Leitura e interpretação de tabelas e gráficos (de colunas ou barras simples ou múltiplas) referentes a variáveis categóricas e variáveis numéricas