Paradigmas de Algoritmos - Desafios Flashcards
Qual o paradigma usado pelo algoritmo de Strassen?
Dividir para Conquistar
Qual paradigma e algoritmo produz a solução ótima para o problema de agendar tarefas em um dia de modo a maximizar o valor obtido por elas? Qual a complexidade base desse algoritmo? Como melhorá-la?
Paradigma dinâmico.
- Comece ordenando as atividades em ordem crescente de término.
- Para cada atividade, guarde o valor p(j) = maior i < j tal que as atividades i e j são compatíveis
- Para cada elemento i, calcule o maior valor entre o maior valor obtido escolhendo o elemento i e o maior valor não escolhendo esse elemento. Para isso, use o valor p(j) para acessar o próximo elemento compatível com j.
A complexidade básica desse algoritmo é exponencial, visto que ele realiza a mesma operação várias vezes. É possível reduzi-la para n log n armazenando os valores calculados em um cache, de modo que cada cálculo seja realizado apenas uma vez.
Qual paradigma e algoritmo produz a solução ótima para o problema do subarray contíguo com soma máxima? Qual o nome e a complexidade desse algoritmo?
Paradigma dinâmico.
- Itere por todos os elementos do array. Para cada elemento, armazene nele o maior entre o próprio elemento e o elemento somado ao valor salvo no elemento anterior
- A maior soma em um subarray contíguo é o maior valor armazenado nesse processo. Se for necessário identificar os elementos do subarray, basta começar no elemento com soma máxima e iterar pelos elementos à esquerda.
O algoritmo é conhecido como algoritmo de Kadane e possui complexidade O(n).
Qual paradigma e algoritmo produz a solução ótima para o problema de armazenar itens em uma sacola de modo a maximizar o valor total? Qual a complexidade base desse algoritmo? Como melhorá-la?
Paradigma dinâmico.
- Para cada item, calcule o maior valor entre o maior valor obtido ao colocá-lo na sacola e tentar colocar o próximo (com o peso disponível reduzido) ou não colocar o elemento e tentar colocar o próximo na sacola. Retorne o maior valor obtido pelo processo.
A complexidade básica desse algoritmo é exponencial, visto que ele realiza a mesma operação várias vezes. É possível reduzi-la para n log n armazenando os valores calculados em uma tabela (N x (W + 1)) em que N são os itens 0, 1, 2, …, n e W é o peso máximo, com o valor T[i][j] representando o máximo valor obtível com o elemento i em uma mochila com capacidade j.
Qual o pressuposto principal do algoritmo dinâmico do valor máximo armazenável em uma mochila? Por que esse pressuposto é necessário? De que forma é possível fazer adaptações nessa solução para ser aplicável a esse tipo de situação?
O pressuposto usado é o de que os pesos na mochila são valores inteiros. Isso é necessário porque a tabela armazena todas as combinações possíveis de pesos e itens menor que o peso limite. Para aplicar o problema a pesos não inteiros, é necessário convertê-los para inteiro, potencialmente multiplicando-os por uma potência de 10 grande o suficiente para torná-los inteiros.
Construa um algoritmo capaz de contar as inversões em um array (uma inversão ocorre quando existem dois elementos ai e aj tais que i < j mas ai > aj). Qual a sua complexidade? Qual algoritmo famoso possui funcionamento similar a este?
O princípo do algoritmo é o mesmo do merge sort e:
- Recursivamente, divida a lista em n/2 listas até cada lista ter tamanho 1.
- Ao combinar as listas, conte as inversões nesse nível e então ordene-as. Visto que as listas de tamanho n/2 estão ordenadas, não é necessário comparar todos os elementos; se o i-ésimo elemento da lista da esquerda é menor que o j-ésimo elemento da lista da direita, ele também é menor que os elementos posteriores a j.
A complexidade é a mesma do Merge Sort; ele realiza o merge sort e faz a contagem de inversões durante a etapa do merge, sem custo assintótico adicional.
Construa um algoritmo que encontre o k-ésimo menor elemento em um array desordenado com complexidade de tempo O(n) no caso médio.
- Escolha um elemento aleatório p em um array.
- Crie três arrays auxiliares: menor, maior e igual. Itere pelo array e coloque cada item no array correspondente.
- Identifique o sub-array onde o k-ésimo elemento está e repita o processo.
Construa um algoritmo que encontre, de maneira eficiente, os dois pontos mais próximos em um plano cartesiano.
- Divida recursivamente a lista de n pontos em listas de n/2 pontos até cada lista ter um elemento.
- Ao combinar as listas, salve em uma variável o valor da menor distância entre dois elementos no array à esquerda e a menor distância entre dois elementos no array à direita.
- Para identificar a menor distância entre elementos de lados opostos, começamos identificando a menor das distâncias salvas na etapa anterior.
- Remova do processo todos os elementos com distância maior até a divisória. Entre os elementos restantes, ordene-os pelo eixo y.
- Compare cada elemento com os elementos do lado oposto com até 7 posições de diferença. Registre a menor distância encontrada.
- Retorne a menor das três distâncias encontradas e repita o processo de forma recursiva.
Qual paradigma e abordagem produz a solução ótima para o problema de agendar tarefas em um dia de modo que o máximo de tempo possível seja ocupado?
Paradigma ganancioso, agendando tarefas (compatíveis) em ordem crescente de hora de término.
Todo problema que pode ser resolvido com recursão pode ser resolvido com programação dinâmica. Verdadeiro ou Falso? Justifique.
Falso. Apenas problemas com subestrutura ótima e sobreposição de subproblemas podem ser resolvidos eficientemente com programação dinâmica.
Em programação dinâmica, o método bottom-up é sempre mais eficiente que o método top-down com memoização. Verdadeiro ou Falso? Justifique.
Falso. A eficiência depende da implementação e da estrutura dos subproblemas.
A programação dinâmica é tipicamente mais eficiente do que a força bruta em problemas de otimização. Verdadeiro ou falso? Justifique.
Verdadeiro. Ela evita o cálculo redundante de subproblemas, típico da força bruta.
Em programação dinâmica, a ordem de resolução dos subproblemas não importa. Verdadeiro ou falso? Justifique.
Falso. Na abordagem bottom-up, a ordem importa porque cada subproblema depende de resultados anteriores.
A programação dinâmica é aplicável a problemas em grafos, como o menor caminho. Verdadeiro ou falso? Justifique.
Verdadeiro. Algoritmos como Bellman-Ford e Floyd-Warshall usam programação dinâmica.
Problemas com subproblemas independentes não podem ser resolvidos eficientemente por programação dinâmica. Verdadeiro ou falso? Justifique.
Verdadeiro. A programação dinâmica depende da sobreposição de subproblemas. Se não há sobreposição, a melhor técnica é a dividir para conquistar.
A programação dinâmica sempre requer mais espaço do que a recursão. Verdadeiro ou falso? Justifique.
Falso. Ela pode ser otimizada para usar menos espaço em alguns casos (ex., otimização de espaço na Mochila).
Qual problema é mais adequado para a abordagem de programação dinâmica?
(a) Soma de uma sequência ordenada
(b) Verificação de primalidade
(c) Subsequência comum máxima
(d) Algoritmo de busca em profundidade
(c) Subsequência comum máxima
Em programação dinâmica, qual é a diferença entre memoização e tabela?
(a) A tabela usa recursão; memoização não.
(b) Memoização armazena resultados na memória; a tabela, no disco.
(c) Memoização usa uma abordagem top-down; a tabela, bottom-up.
(d) Não há diferença.
(c) Memoização usa uma abordagem top-down; a tabela, bottom-up.
Como a complexidade espacial pode ser reduzida em programação dinâmica?
(a) Usando menos subproblemas
(b) Mantendo apenas os estados necessários
(c) Evitando a memoização
(d) Reduzindo o tamanho da entrada
(b) Mantendo apenas os estados necessários
Qual problema abaixo é um exemplo clássico de programação dinâmica?
(a) Ordenação por fusão
(b) Caminho mínimo em um grafo
(c) Pesquisa binária
(d) Algoritmo de Kruskal
(b) Caminho mínimo em um grafo
Qual abordagem é melhor para resolver problemas de programação dinâmica com alta dependência sequencial?
(a) Força bruta
(b) Top-down com memoização
(c) Bottom-up com tabela
(d) Algoritmos genéticos
(c) Bottom-up com tabela
O que significa a sobreposição de subproblemas em programação dinâmica?
Significa que o mesmo subproblema é resolvido várias vezes em uma abordagem recursiva. Na programação dinâmica, esses subproblemas são resolvidos uma única vez e seus resultados são armazenados.
Em programação dinâmica, como a abordagem bottom-up evita chamadas recursivas?
Ela resolve subproblemas menores primeiro e usa seus resultados para construir a solução dos subproblemas maiores, preenchendo uma tabela de forma iterativa.
Qual é o propósito da otimização de espaço em programação dinâmica?
Reduzir a quantidade de memória usada armazenando apenas os resultados dos subproblemas necessários para os cálculos subsequentes, em vez de toda a tabela.
Qual é a diferença entre subestrutura ótima e sobreposição de subproblemas?
Subestrutura ótima refere-se a resolver o problema combinando soluções ótimas de subproblemas, enquanto sobreposição de subproblemas significa resolver os mesmos subproblemas repetidamente.
Por que o algoritmo de Floyd-Warshall é considerado um exemplo de programação dinâmica?
Porque ele usa uma tabela para armazenar distâncias mínimas entre pares de nós e resolve o problema combinando subproblemas menores (distâncias intermediárias).
Qual é o benefício principal de usar programação dinâmica para problemas de otimização?
Ela reduz significativamente a complexidade computacional ao evitar cálculos redundantes e utilizar subestruturas ótimas.
Em programação dinâmica, como a estrutura dos subproblemas indica qual abordagem é a mais eficiente entre top-down e bottom-up?
Se todos os subproblemas devem ser resolvidos ao menos uma vez, a abordagem bottom-up é mais eficiente. Por outro lado, se alguns subproblemas podem não ser resolvidos, é melhor usar a abordagem top-down.
