Revisão G2 - Complexidade

Qual das seguintes afirmações é verdadeira sobre algoritmos de backtracking?

• Sempre encontra a solução ótima na primeira tentativa.
• Explora todas as possibilidades até encontrar a solução desejada.
• Utiliza estruturas de dados como filas para armazenar estados.
• É eficiente para resolver problemas de otimização em tempo polinomial.
• Evita a exploração de todas as possibilidades através de uma análise a priori.

Em qual dos seguintes cenários um algoritmo de backtracking seria ideal?

• Calcular a sequência de Fibonacci.
• Encontrar a menor distância entre duas cidades em um mapa.
• Resolver um quebra-cabeça de sudoku.
• Determinar o caminho mais curto em um grafo com pesos negativos.
• Ordenar uma lista de números.

Qual dos seguintes algoritmos utiliza a abordagem de divisão e conquista?

• Dijkstra
• Kruskal
• Quicksort
• Prim
• Breadth-First Search

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

• Divide o problema em subproblemas menores, resolve-os independentemente e combina as soluções.
• Explora todas as soluções possíveis.
• Utiliza heurísticas para encontrar uma solução aproximada.
• Resolve o problema de forma iterativa utilizando uma única pilha.
• Baseia-se em grafos para encontrar a solução ótima.

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

• Explora todas as soluções possíveis.
• Resolve subproblemas e os combina para encontrar a solução final.
• Escolhe a melhor opção local em cada etapa, na esperança de encontrar a solução ótima global.
• Utiliza programação dinâmica para garantir a solução ótima.
• Baseia-se em uma abordagem recursiva para explorar todas as combinações.

Qual dos seguintes problemas pode ser resolvido de forma eficaz usando um algoritmo guloso?

• Problema da Mochila 0/1.
• Problema do Caixeiro Viajante.
• Algoritmo de Dijkstra para encontrar o caminho mais curto.
• Problema de N-Rainhas.
• Problema de coloração de grafos.

Qual das seguintes estratégias é essencial para a programação dinâmica?

• 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.

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.

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

• P representa problemas que podem ser resolvidos em tempo exponencial, enquanto NP representa problemas que podem ser resolvidos em tempo polinomial.
• P representa problemas que podem ser verificados em tempo polinomial, enquanto NP representa problemas que podem ser resolvidos em tempo polinomial.
• P representa problemas que podem ser resolvidos em tempo polinomial, enquanto NP representa problemas cuja solução pode ser verificada em tempo polinomial.
• P representa problemas que não podem ser resolvidos, enquanto NP representa problemas que podem ser resolvidos em tempo polinomial.
• P e NP são classes equivalentes e não há diferença entre elas.

Qual dos seguintes problemas é um exemplo de um problema NP-completo?

• Ordenação de números.
• Multiplicação de matrizes.
• Problema do Caixeiro Viajante.
• Algoritmo de Dijkstra.
• Pesquisa binária.