Paradigmas de Algoritmos - Fundamentos Flashcards
O que é um paradigma de algoritmo?
É uma abordagem ou técnica geral utilizada para projetar e implementar algoritmos para resolver problemas computacionais.
Quais são os principais paradigmas de algoritmos?
ivisão e conquista, programação dinâmica, ganancioso (greedy), força bruta e backtracking.
O que caracteriza o paradigma “divisão e conquista”?
Ele divide um problema em subproblemas menores, resolve esses subproblemas e combina as soluções para resolver o problema original.
Como o paradigma ganancioso resolve problemas?
Faz escolhas locais ótimas em cada etapa, com a esperança de que isso leve a uma solução global ótima.
Qual é a principal desvantagem do paradigma de força bruta?
Geralmente, é ineficiente porque explora todas as possibilidades, levando a tempos de execução elevados.
O que é programação dinâmica?
É um paradigma de algoritmos que resolve problemas ao decompor em subproblemas sobrepostos e armazenando suas soluções para evitar cálculos redundantes.
Quais são os dois componentes principais de um problema adequado para programação dinâmica?
Subproblemas sobrepostos e propriedade de subestrutura ótima.
O que significa subproblemas sobrepostos no paradigma dinâmico?
Quando um problema pode ser dividido em subproblemas menores, e esses subproblemas se repetem várias vezes no cálculo.
O que é a propriedade de subestrutura ótima?
Significa que a solução ótima de um problema pode ser construída a partir das soluções ótimas de seus subproblemas.
Qual é a diferença entre a abordagem “top-down” e “bottom-up” na programação dinâmica?
“Top-down” usa recursão com memorização, enquanto “bottom-up” constrói soluções iterativamente em uma tabela.
O que é a tabela em programação dinâmica?
É uma estrutura de dados, geralmente um array ou matriz, usada para armazenar soluções de subproblemas.
Como a programação dinâmica resolve o problema da sequência de Fibonacci?
Armazena os valores de Fibonacci previamente calculados em um array, evitando cálculos repetidos.
Qual é o benefício de usar memoização em programação dinâmica?
Reduz a redundância ao salvar os resultados de subproblemas já calculados, melhorando a eficiência.
Quando a programação dinâmica pode ser menos eficiente?
Quando o problema não possui subproblemas sobrepostos ou subestrutura ótima.
Qual é uma armadilha comum ao implementar programação dinâmica?
Definir incorretamente o estado ou a transição entre estados.
O que é um “estado” em programação dinâmica?
Uma representação compacta de um subproblema que inclui todas as informações necessárias para resolvê-lo.
Por que é importante definir corretamente a transição de estado?
Porque a transição determina como os subproblemas se relacionam e garante que as soluções parciais levem à solução final.
Qual das seguintes é uma característica necessária para aplicar programação dinâmica?
(a) Subproblemas independentes
(b) Soluções aproximadas
(c) Subestrutura ótima
(d) Algoritmos de força bruta
(c) Subestrutura ótima
O que a tabela em programação dinâmica armazena?
(a) Todas as entradas do problema
(b) Resultados de subproblemas já resolvidos
(c) Solução final apenas
(d) Dados de entrada ordenados
(b) Resultados de subproblemas já resolvidos
Qual é a complexidade temporal típica de um algoritmo de programação dinâmica?
(a) Exponencial
(b) Polinomial
(c) Logarítmica
(d) Depende do problema
(d) Depende do problema
Qual das seguintes técnicas é mais usada em programação dinâmica?
(a) Divisão e conquista
(b) Ordenação e busca
(c) Top-down com memoização
(d) Pesquisa aleatória
(c) Top-down com memoização
