Cartões - Revisão G2 - Complexidade (2024-2)

Front

Qual dos seguintes algoritmos utiliza a abordagem de divisão e conquista? Dijkstra (Caminho mínimo)., Caixeiro Viajante., Quicksort., Knapsack (Mochila)., Busca em Largura em Grafo.

Back

Quicksort.

Front

Qual é a principal característica de um algoritmo de divisão e conquista?

Back

Divide o problema em subproblemas menores, resolve-os independentemente e combina as soluções.

Front

Qual das seguintes características descreve melhor um algoritmo guloso?

Back

Escolhe a melhor opção local em cada etapa, na esperança de encontrar a solução ótima global.

Front

Qual dos seguintes problemas pode ser resolvido de forma eficaz usando um algoritmo guloso? Problema da Mochila Binária., Problema do Caixeiro Viajante., Algoritmo de Dijkstra para encontrar o caminho mais curto., Problema de Alocação de Tarefas., Problema de coloração de grafos.

Back

Algoritmo de Dijkstra para encontrar o caminho mais curto.

Front

Qual das seguintes estratégias é essencial para a programação dinâmica?\nOptions: Resolver problemas grandes diretamente., Dividir o problema em subproblemas independentes., Resolver cada subproblema apenas uma vez e armazenar seus resultados., Fazer escolhas locais ótimas em cada etapa., Explorar todas as combinações possíveis de soluções.

Back

Resolver cada subproblema apenas uma vez e armazenar seus resultados.

Front

Qual dos seguintes problemas é comumente resolvido usando programação dinâmica? Problema da Maior Subsequência Comum., Ordenação de uma lista de números., Encontrar o menor caminho em um grafo com pesos negativos., Resolver quebra-cabeças de Sudoku., Encontrar a solução para o problema de n-rainhas.

Back

Problema da Maior Subsequência Comum.

Front

Qual é a principal diferença entre as classes P e NP?

Back

P representa problemas que podem ser resolvidos em tempo polinomial, enquanto NP representa problemas cuja solução pode ser verificada em tempo polinomial.

Front

Qual dos seguintes problemas é um exemplo de um problema NP-completo?\n- Ordenação de números.\n- Multiplicação de matrizes.\n- Problema do Caixeiro Viajante.\n- Algoritmo de Dijkstra.\n- Pesquisa binária.

Back

Problema do Caixeiro Viajante.

Front

Qual das seguintes afirmações é falsa sobre a abordagem de divisão e conquista? Options: Divide o problema original em subproblemas menores., Resolve cada subproblema de forma independente., Sempre utiliza programação dinâmica para combinar subproblemas., Recombina as soluções dos subproblemas para obter a solução do problema original., Exemplos clássicos incluem os algoritmos Quicksort e Mergesort.

Back

Sempre utiliza programação dinâmica para combinar subproblemas.

Front

Qual dos seguintes problemas não é resolvido eficientemente usando a abordagem de divisão e conquista?

• Pesquisa binária.
• Multiplicação de grandes números.
• Algoritmo de Dijkstra.
• Ordenação por Mergesort.
• Determinação da soma máxima em uma subsequência de um array.

Back

Algoritmo de Dijkstra.