MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado os algoritmos A₁ que decide a linguagem L₁ e A₂ que decide a linguagem L₂ e L₁, L₂ ⊆ {0,1}* podemos afirmar que:

1. Se L₁ ≤p L₂, então A₁ tem o mesmo tempo assintótico que A₂
2. Se  L₁ ≤p L₂ então L₁ ∈ NP implica L₂  ∈ P
3. Seja T(x) o tempo do algoritmo x, se T(A₁) = O(T(A₂))  e T(A₂) é polinomial então L₁ ≤p L₂
4. Se L₁ ∈ P e A₁ também decidir L₂ então L₂ ∈ NP
5. NDA

Ideia original de: Anderson Carlos Sousa e Santos

MO417- QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado o grafo abaixo:

É correto afirmar:

1. O algoritmo de Dijkstra retorna os caminhos máximos.
2. Bellman-Ford é o melhor algoritmo para encontrar os caminhos mínimos neste grafo.
3. Se Bellman-Ford for executado utilizando a mesma ordem de visitação de Dijkstra, eles terão o mesmo tempo de execução.
4. Pode-se encontrar os caminhos mínimos a partir de qualquer origem em tempo O(V + E)
5. NDA 

Ideia original de: Anderson Carlos Sousa e Santos

MO417 - Questão para a prova oral

Número:

Enunciado: Considere uma busca em profundidade no grafo abaixo.

Definimos d[u] como o carimbo de tempo registrado quando u é descoberto e f[u] como o carimbo de tempo registrado quando a busca termina de examinar a lista de adjacências de u.  Visto que a busca pode iniciar a partir de qualquer vértice, é possível afirmar que:

1. Se d[A] > d[E] então f[A] > f[E]
2. Se d[A] < d[B] então f[B] > f[C]
3. Se f[F] < f[B] então d[B] < d[F]
4. Se d[F] < d[B] então d[B] = d[F] + 2
5. NDA

MO417 - Questão para a prova oral

Número:

Enunciado: Considerando as operações sobre conjuntos disjuntos e cenário no qual MAKE-SET é executado n vezes e depois UNION é executado x vezes sobre conjuntos diferentes. Seja k o numero de conjuntos resultantes. assinale a resposta correta:

a) Se x = n/2, então x = k
b) k = n!/x!(n-x)!
c) n > k + x
d) Se k = 2x, então n é par 
e) NDA

Ideia original de: Anderson Carlos Sousa e Santos

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Considere o seguinte texto em um arquivo: ABCACABCC. Se quisermos comprimir o arquivo, utilizando uma codificação. Qual das alternativas abaixo apresenta a codificação que comprime o arquivo a um tamanho mínimo?

1. A = 00  B = 01  C = 11
2. A =  0   B = 01  C = 01
3. A =  0   B = 10  C = 11
4. A = 11  B = 10  C =  0
5. NDA

Ideia original de: Anderson Carlos Sousa e Santos

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Qual das alternativas abaixo é verdadeira?

1. O algoritmo recursivo para um determinado problema  terá sempre um tempo de execução maior que sua versão memoizada.
2. Para ser possível aplicar programação dinâmica o problema deve ter subproblemas ótimos,  independentes e superpostos
3. A programação dinâmica somente se aplica a problemas de otimização.
4. Problemas com subestrutura ótima devem ser resolvidos por programação dinâmica 
5. NDA

Ideia original de: Anderson Carlos Sousa e Santos

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Qual das alternativas abaixo é verdadeira?

1. Se utilizarmos um algoritmo Θ(n³)  para encontrar a medianas no SELECT então este não mais terá tempo linear no pior caso
2. Se o QUICKSORT for modificado para realizar o particionamento da mesma forma que o SELECT o faz, então o tempo no pior caso seria O(nlgn)
3. Se o arranjo fosse dividido em 3 grupos o SELECT ainda teria tempo linear no pior caso
4. O SELECT é a melhor opção para se aplicar em problemas práticos
5. NDA

Ideia original de: Anderson Carlos Sousa e Santos

MO417 - QUESTÃO PARA PROVAL ORAL

Número:

Enunciado: Dada uma sequência de entrada <a₁, a₂,...,an>. Sobre o tempo de execução (T(n)) do Quicksort é possível afirmar:

1. Se an > ai então T(n) = Θ(n²), para i = {1...n-1}
2. Se ai = ai+1 então T(n) = Θ(nlgn), para i = {1...n-1}
3. Se ai < ai+1 então T(n) = Θ(n), para i = {1...n-1}
4. Se ak < an < a(n/2)+k então T(n) = O(n lg n), para k = {1...(n/2)-1}
5. NDA

Ideia original de: Anderson Carlos Sousa e Santos

MO417 - QUESTÃO PARA PROVAL ORAL

Número:

Enunciado: Sejam a ≥ 1 e b > 1 constantes, seja f(n) uma função e T(n) definida sobre os números inteiros não negativos pela recorrência

T(n) = aT(n/b) + f(n)

É INCORRETO  afirmar que: 

1. Se a = b e f(n) = n então T(n) = Θ(n lg n)
2. Se a = b² e f(n) = n então T(n) = Θ(n²)
3. Se a = b e f(n) = n²  então T(n) = Θ(n²)
4. Se a = b²  e f(n) = n² então T(n) = Θ(n lg n) 
5. NDA

Ideia original de: Anderson Carlos Sousa e Santos

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dadas as funções $f(n)$, $g(n)$ assinale a alternativa CORRETA:

1. Se $f(n)=\omicron(g(n))$ então $\underset{n\rightarrow \infty}{\lim}\frac{f(n)}{g(n)}>0$
2. Se $f(n)=\omega(g(n))$ então $\underset{n\rightarrow \infty}{\lim}\frac{f(n)}{g(n)}<0$
3. Se $f(n)=\Theta(g(n))$ então $\underset{n\rightarrow \infty}{\lim}\frac{f(n)}{g(n)}\leq\infty$
4. Se $f(n)=O(g(n))$ então $\underset{n\rightarrow \infty}{\lim}\frac{f(n)}{g(n)}\geq0$
5. NDA

Ideia original de: Anderson Carlos 

Objetivo do blog

Este blog tem como objetivo auxiliar na aprendizagem de complexidade de algoritmos, através do desenvolvimento de questões sobre o tema.