Lista de exercícios de Algoritmos e complexidade com respostas

Qual notação descreve um limite inferior de crescimento?

1. AΘ (Theta grande)
2. Bo (o pequeno)
3. CO (O grande)
4. DΩ (Ômega grande)

Um problema costuma ser chamado de tratável se:

1. ASó pode ser resolvido testando todas as possibilidades
2. BPode ser resolvido em tempo constante
3. CNão tem solução
4. DPode ser resolvido em tempo polinomial

O que é memoização?

1. AEscrever comentários ao lado de cada linha de código
2. BArmazenar os resultados de chamadas de função para que chamadas repetidas sejam respondidas da memória
3. CLiberar memória depois que uma função retorna
4. DConverter automaticamente a recursão em um laço equivalente, de modo que não seja preciso pilha de chamadas

O que o algoritmo de Floyd–Warshall calcula, e com que rapidez?

1. AUma árvore geradora mínima em O(E log V)
2. BCaminhos mínimos de um vértice de origem para todos os outros em O(V + E)
3. CUma ordenação topológica em O(V²)
4. DCaminhos mínimos entre todos os pares de vértices em O(V³)

Qual é a complexidade de tempo de: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

1. AO(n log n)
2. BO(log n)
3. CO(n)
4. DO(n²)

Por que a base do logaritmo costuma ser omitida no O grande, como em O(log n)?

1. AA base só importa para n pequeno
2. BLogaritmos de bases diferentes diferem apenas por um fator constante
3. CTodos os logaritmos em computação têm base 10, então ela fica implícita
4. DOs logaritmos são sempre arredondados para inteiros

O que o teorema de Cook–Levin estabeleceu?

1. ATodo problema NP pode ser resolvido em tempo exponencial
2. BP é diferente de NP
3. CO problema da parada é indecidível
4. DO problema da satisfatibilidade booleana (SAT) é NP-completo

Caminhos simples mínimos podem ser encontrados em tempo polinomial. O que se sabe sobre encontrar o caminho simples mais longo entre dois vértices num grafo geral?

1. AÉ NP-difícil
2. BPode ser resolvido pelo algoritmo de Dijkstra com os pesos negados
3. CÉ sempre solúvel em O(V + E)
4. DÉ indecidível