Questão de Algoritmos e Estrutura de Dados — Algoritmos — FUNDATEC 2023
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq890576
Banca
FUNDATEC
Órgão
CIGA-SC
Ano
2023
Nível
Médio
Cargo
Técnico em TI
Sobre projeto de algoritmos, é correto afirmar que:
AUm procedimento que chama a si mesmo, direta ou indiretamente, é denominado de algoritmo guloso. O uso de um algoritmo guloso permite uma descrição mais clara e concisa dos algoritmos, especialmente quando o problema a ser resolvido utiliza estruturas de repetição.
BOs algoritmos recursivos permitem definir o processo em um número finito de subtarefas parciais que devem ser exploradas recursivamente.
CAlgoritmos dinâmicos são tipicamente utilizados para resolver problemas de otimização. Um exemplo é o algoritmo para encontrar o caminho mais curto entre dois vértices de um grafo.
DO paradigma de divisão e conquista consiste em dividir o problema em partes menores, encontrar soluções para as partes, e então combinar as soluções obtidas em uma solução global.
EQuando um algoritmo recursivo tem complexidade exponencial, a técnica de balanceamento pode levar a um algoritmo mais eficiente.
Revelar gabarito e comentário▾
GabaritoD — O paradigma de divisão e conquista consiste em dividir o problema em partes menores, encontrar soluções para as partes, e então combinar as soluções obtidas em uma solução global.
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”.
Projeto de Algoritmos — Paradigmas
Gabarito: letra D. O paradigma de divisão e conquista corretamente descrito: decompor o problema em subproblemas menores, resolvê-los e combinar as soluções parciais. As demais alternativas contêm erros conceituais, trocando termos ou atribuindo propriedades inadequadas.
A banca testa o conhecimento sobre os principais paradigmas de projeto de algoritmos: recursão, algoritmo guloso, programação dinâmica e divisão e conquista. É essencial distinguir cada um com precisão.
NÃO CAIA NESSA!
A alternativa A confunde recursão (procedimento que chama a si mesmo) com algoritmo guloso (escolha local ótima). Já a alternativa B atribui à recursão a definição de divisão e conquista, que é um paradigma específico — recursão é apenas uma técnica que pode implementá-lo, mas não se restringe a ele. Fique atento a essas trocas frequentes em provas.
Paradigma
Definição Correta
Exemplo Típico
Erro Conceitual na Alternativa
Recursão
Procedimento que chama a si mesmo, direta ou indiretamente
Cálculo de fatorial, travessia de árvores
Alternativa A confunde com algoritmo guloso
Algoritmo Guloso
Escolha localmente ótima a cada passo, visando solução global ótima
Problema da mochila fracionária, árvore geradora mínima
Alternativa A atribui propriedade de recursão
Divisão e Conquista
Decompor problema em subproblemas menores, resolvê-los e combinar soluções
Merge sort, busca binária
Alternativa B atribui definição à recursão
Programação Dinâmica
Resolver problemas de otimização armazenando soluções de subproblemas
Caminho mais curto (Bellman-Ford), mochila 0/1
Alternativa C usa termo "algoritmos dinâmicos" (incorreto)
Paradigmas de projeto: Recursão (Procedimento chama a si mesmo, Descrição clara e concisa); Algoritmo guloso (Escolha localmente ótima, Busca solução global ótima); Programação dinâmica (Problemas de otimização, Caminho mais curto (Bellman-Ford)); Divisão e conquista (Divide em subproblemas menores, Resolve e combina soluções)
Alternativa A — ❌ Incorreta
O procedimento que chama a si mesmo é recursivo, não guloso. O algoritmo guloso (ou ganancioso) consiste em fazer a escolha localmente ótima a cada passo, visando uma solução global ótima. A frase ainda afirma que o algoritmo guloso "permite uma descrição mais clara e concisa [...] especialmente quando o problema utiliza estruturas de repetição" — isso é incorreto, pois a recursão é que frequentemente simplifica a descrição de problemas com repetição, não o guloso.
Alternativa B — ❌ Incorreta
A definição apresentada ("definir o processo em um número finito de subtarefas parciais que devem ser exploradas recursivamente") descreve o paradigma divisão e conquista, não simplesmente recursão. Um algoritmo recursivo pode, por exemplo, percorrer uma árvore sem necessariamente dividir o problema em subproblemas independentes. A recursão é uma técnica de implementação, enquanto divisão e conquista é uma estratégia de projeto.
Alternativa C — ❌ Incorreta
Embora a programação dinâmica seja de fato usada em problemas de otimização e o caminho mais curto em grafos seja um exemplo clássico (ex.: algoritmo de Bellman-Ford), a alternativa utiliza o termo "algoritmos dinâmicos", que não é a denominação consagrada. O correto é programação dinâmica ou algoritmos de programação dinâmica. Além disso, o exemplo pode causar confusão, pois o problema de caminho mais curto também pode ser resolvido por algoritmo guloso (Dijkstra) ou por divisão e conquista (em alguns contextos). A banca considera a imprecisão terminológica suficiente para tornar a alternativa falsa.
Alternativa D — ✅ Correta ⟵ GABARITO
A descrição corresponde exatamente ao paradigma divisão e conquista: dividir o problema em subproblemas menores (geralmente de forma recursiva), resolver cada subproblema (diretamente se pequeno) e combinar as soluções parciais em uma solução global. Exemplos clássicos são o merge sort e o quicksort. O material de apoio confirma: "Divisão e conquista - algoritmos de divisão e conquista reduzem repetidamente o problema em sub-problemas, geralmente de forma recursiva, até que o sub-problema é pequeno o suficiente para ser resolvido."
Alternativa E — ❌ Incorreta
A técnica de balanceamento (como em árvores balanceadas) não é uma abordagem geral para melhorar algoritmos recursivos exponenciais. O método mais comum é a memoização ou programação dinâmica, que armazena resultados de subproblemas para evitar recálculos. Balanceamento refere-se a estruturas de dados como árvores AVL ou Rubro-Negras, não a recursão exponencial. Portanto, a afirmação é falsa.