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

• Uma livraria registra, em uma tabela, a quantidade de livros vendidos em duas filiais durante uma campanha. As linhas…
• Em um inventário de sementes, a equipe registrou a quantidade de um lote usando agrupamentos: 3 grupos de 10.000…
• Por que alguns horários de biblioteca ficam lotados enquanto outros permanecem vazios? Para decidir a ampliação do…
• Uma cooperativa de reciclagem contratou fretes e registrou o custo total conforme a distância percorrida. O grafico…
• O gráfico mostra o consumo mensal de energia dos equipamentos de uma padaria: forno, 520 kWh; refrigeração, 280 kWh…
• Uma comunidade rural avalia caixas d'água de base quadrada e altura fixa de 5 m. O gráfico mostra o volume V, em m³, em…

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