Questão de Algoritmos e Estrutura de Dados — Algoritmos — INAZ do Pará 2024
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg260380
Banca
INAZ do Pará
Órgão
Prefeitura de São Sebastião do Tocantins - TO
Ano
2024
Nível
Superior
Cargo
Professor de Informática - Licenciatura em Computação
Sobre classificações de algoritmos, analise as alternativas abaixo e identifique qual delas descreve CORRETAMENTE um tipo específico de algoritmo de acordo com suas características e propósito.
AUm algoritmo ganancioso precisa conhecer a solução de todos os subproblemas em cada passo para tomar a decisão mais adequada.
BAlgoritmos de divisão e conquista lidam com problemas complexos, reduzindo-os iterativamente em subproblemas menores, geralmente utilizando técnicas de programação linear para solucionar cada subproblema.
CAlgoritmos não-determinísticos sempre retornam o mesmo resultado ao resolver o problema, pois tomam decisões exatas e previsíveis a cada passo.
DA programação dinâmica evita o recálculo de soluções de subproblemas já resolvidos anteriormente, armazenando essas soluções para otimizar o tempo de execução.
EUm algoritmo serial divide o problema em subproblemas para resolver simultaneamente em diferentes processadores e, em seguida, agrupa os resultados.
Revelar gabarito e comentário▾
GabaritoD — A programação dinâmica evita o recálculo de soluções de subproblemas já resolvidos anteriormente, armazenando essas soluções para otimizar o tempo de execução.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Classificações de Algoritmos
Gabarito: letra D. A programação dinâmica é a técnica que armazena soluções de subproblemas já resolvidos para evitar recálculos, otimizando o tempo de execução. Essa é a descrição correta dentre as alternativas.
A banca testa o conhecimento sobre as características fundamentais de diferentes paradigmas algorítmicos. Vamos analisar cada alternativa:
Alternativa
Tipo de Algoritmo
Característica Descrita
Correção da Descrição
A
Ganancioso (Guloso)
Precisa conhecer a solução de todos os subproblemas em cada passo
❌ Incorreta (faz escolha local, sem visão global)
B
Divisão e Conquista
Reduz iterativamente usando programação linear
❌ Incorreta (essência recursiva; não usa programação linear)
C
Não-determinístico
Sempre retorna o mesmo resultado
❌ Incorreta (permite resultados diferentes; é determinístico que é previsível)
D
Programação Dinâmica
Evita recálculo armazenando soluções de subproblemas
✅ Correta (definição clássica: memoização/tabela)
E
Serial
Divide em subproblemas para resolver simultaneamente
❌ Incorreta (descrição de algoritmo paralelo, não serial)
Alternativa A — ❌ Incorreta
Afirma que um algoritmo ganancioso (guloso) precisa conhecer a solução de todos os subproblemas em cada passo. Isso é falso. O algoritmo guloso toma a melhor decisão local no momento, sem considerar o panorama completo dos subproblemas. Ele não requer conhecimento global; a escolha é feita com base em critérios imediatos. Essa descrição se aproxima mais da programação dinâmica, que analisa subproblemas sobrepostos.
Alternativa B — ❌ Incorreta
Diz que algoritmos de divisão e conquista reduzem problemas iterativamente usando programação linear. Erro duplo: (1) divisão e conquista é recursiva, não iterativa (embora possa ser implementada iterativamente, a essência é recursiva); (2) a resolução dos subproblemas não depende de programação linear — cada subproblema é resolvido pela mesma técnica ou de forma independente. Programação linear é uma área de otimização, não um componente típico desse paradigma.
Alternativa C — ❌ Incorreta
Afirma que algoritmos não-determinísticos sempre retornam o mesmo resultado. Isso contradiz a própria definição: não-determinismo permite múltiplas execuções com resultados possivelmente diferentes (a menos que o problema seja determinístico). Na prática, algoritmos não-determinísticos são modelos teóricos onde a escolha não é predeterminada. Algoritmos determinísticos é que produzem sempre a mesma saída para a mesma entrada.
Alternativa D — ✅ Correta ⟵ GABARITO
A programação dinâmica evita o recálculo de subproblemas já resolvidos armazenando suas soluções (memoização ou tabela). Isso é exato: ela explora subproblemas sobrepostos e otimiza o tempo de execução ao reutilizar resultados. É a definição clássica da técnica.
Alternativa E — ❌ Incorreta
Descreve um algoritmo paralelo, não serial. Algoritmo serial executa instruções sequencialmente em um único processador. A divisão em subproblemas executados simultaneamente em múltiplos processadores é característica de algoritmos paralelos. A alternativa inverte os conceitos.
NÃO CAIA NESSA!
Para fixar, lembre-se: guloso → decisão local sem visão global; divisão e conquista → recursão + combinação; programação dinâmica → memoização; não-determinístico → escolha não previsível; serial → sequencial. A banca adora trocar os atributos entre paradigmas. Resolva muitas questões para identificar esses padrões.