MO417 - Questão para a prova oral

Número:

Enunciado: Analise as seguintes afirmativas e indique a alternativa INCORRETA:

a) Um problema de decisão A que seja NP-difícil pode ser mostrado ser NP-completo exibindo um algoritmo determinista polinomial para A.
b) Apenas problemas de decisão (“sim/não”) podem ser NP-completo.
c) Problemas de otimização podem ser NP-difícil, mas geralmente, se A é um problema de decisão e B um problema de otimização, é bem possível que A é polinomialmente transformável em B.
d) A dificuldade de um problema NP-difícil não é menor do que a dificuldade de um problema
NP-completo
e) NDA

Ideia original de: Marleny Luque Carbajal

MO417 - Questão para a prova oral

Número:

Enunciado:
No seguinte fluxo em rede G=(V,E), indique qual é o fluxo máximo entre os vértices S (origem) e T (sorvedor).

a) 800
b) 1000
c) 1200
d) 1400
e) NDA

Idéia original de: Marleny Luque Carbajal

MO417 - Questão para a prova oral

Número:

Enunciado: No seguinte grafo não orientado ponderado aplique o algoritmo de Kruskal e responda corretamente:

Qual dos seguintes conjuntos de arestas não são parte de nenhuma das possíveis árvores espalhadas mínimas:

a) {(a,b), (b,d), (d,e)}
b) {(a,d), (c,b), (c,f)}

c) {(b,c), (d,e), (f,g)}

d) {(b,c), (b,d), (f,g)}

e) NDA

Idéia original de: Marleny Luque Carbajal

MO417 - Questão para a prova oral

Número:

Enunciado: Uma das seguintes listas de adjacências representa um grafo não orientado G=(V,E) com cinco arestas e quatro vértices: a, b, c, d. Analise as representações e indique a alternativa CORRETA:

a) A representação II de G=(V,E) é correta e a soma dos comprimentos de todas as listas de adjacências é |E|
b) A representação III de G=(V,E) é correta e a quantidade de memoria que ela exige é Θ(V+E)
c) A representação I de G=(V,E) é correta e a soma dos comprimentos de todas as listas de adjacências é 2|E|
d) A representação II de G=(V,E) é correta e a quantidade de memoria que ela exige é Θ(V+E)
e) NDA

Idéia original de: Marleny Luque Carbajal

MO417 - Questão para a prova oral

Número:

Enunciado: Seja a seguinte árvore vermelho e preto :

Depois de inserir o número 3 na árvore, indique a resposta CORRETA:


a) O nó 7 é preto e seu pai é o nó 13
b) O nó 2 é vermelho e não tem filho esquerdo
c) O nó 4 é preto e seu filho esquerdo é o nó 3
d) O nó 13 é a raiz e seu filho esquerdo é o nó 14
e) NDA

Idéia original de: Marleny Luque Carbajal

MO417 - Questão para a prova oral

Número:

Enunciado:
Um algoritmo top-down memoizado e um algoritmo bottom-up de programação dinâmica tiram proveito da propriedade de subproblemas superpostos. Na pratica, se todos os subproblemas devem ser resolvidos pelo menos uma vez, podemos AFIRMAR que:

a)  Um algoritmo bottom-up de programação dinâmica normalmente supera um algoritmo top-down memoizado por um fator constante.
b)  Um algoritmo top-down memoizado normalmente supera um algoritmo bottom-up de programação dinâmica.
c)  Nenhum algoritmo terá vantagem.
d)  Sempre que há sobrecarga para recursão o algoritmo top down é melhor.
e)  NDA

Idéia original de: Marleny Luque Carbajal

MO417 - Questão para a prova oral

Número:

Enunciado: Seja a seguinte versão do algoritmo Fibonacci:

FIBONACCI(n)
1 Criar arranjo Fib[0..n]
2 for i=0 to n
3    do Fib[i]=-1
4 Fib[0]=1
5 Fib[1]=1
6 return LOOKUP-FIB(Fib,n)

LOOKUP-FIB(Fib,n)
1 if (Fib[n]>0)
2   then return Fib[n]
3   else
4       return Fib[n]=LOOKUP-FIB(Fib,n-1) + LOOKUP-FIB(Fib,n-2)

Podemos AFIRMAR que:

a) É um algoritmo memoizado com tempo de execução O(n)
b) Não é um algoritmo memoizado mas seu tempo de execução é O(lg n)
c) Somente é um algoritmo recursivo com tempo de execução O(2^n)
d) É um algoritmo memoizado com tempo de execução O (lg n)
e) NDA


Idéia original de: Marleny Luque Carbajal

MO417 - Questão para a prova oral

Numero:

Enunciado:

Seja o algoritmo SELECT:

1: Dividir os n elementos do arranjo de entrada em grupos de 5 elementos cada e no máximo um grupo formado pelos n mod 5 elementos restantes.

2: Encontrar a mediana de cada um dos n/5 grupos, primeiro através da ordenação por inserção dos elementos de cada grupo (dos quais existem 5 no máximo), e depois escolhendo a mediana da lista ordenada de elementos de grupos.

3: Usar SELECT recursivamente para encontrar a mediana x das n/5 medianas localizadas na Etapa 2. (Se existe um número par de medianas, então, por nossa convenção, x é a mediana inferior.)

4: Particionar o arranjo de entrada em torno da mediana de medianas x, usando uma versão modificada de PARTITION. Seja k uma unidade maior que o número de elementos no lado baixo da partição, de forma que x seja o k-ésimo menor elemento e existam n - k elementos no lado alto da partição.

5: Se i = k, então retornar x. Caso contrário, usar SELECT recursivamente para encontrar o i-ésimo menor elemento no lado baixo se i <= k, ou então o (i - k)-ésimo menor elemento no lado alto, se i>k.

No processo de obter a 2° estatística de ordem do arranjo: {3,1,2,6,9,10,15,4,5,8,7,13,12}, indique quais são as medianas encontradas na Etapa 2, depois da primeira chamada recursiva do algoritmo SELECT na Etapa 5:

a) 2 y 6

b) 2 y 4

c) 3 y 5

d) 3 y 8

e) NDA

Ideia original de: Marleny Luque Carbajal

MO417 - Questão para a prova oral

Numero:

Enunciado: Leia os seguintes enunciados:

I. Os elementos são números inteiros “pequenos”; mais precisamente, inteiros x ∈ O(n)
II. Os elementos são números inteiros de comprimento maximo constante, isto e, independente de n.
III. Os elementos são números reais uniformemente distribuídos no intervalo [0..1).

Indique a relacão correta entre os enunciados e os algoritmos lineares para ordenacão:

 a) I - Counting Sort; II-Radix Sort; III-Bucket Sort
 b) I - Bucket Sort ; II-Radix Sort; III-Counting Sort
 c) I - Counting Sort; II-Bucket Sort; III-Radix Sort
 d) I - Radix Sort; II-Counting Sort; III-Bucket Sort
 e) NDA


Ideia original de: Marleny Luque Carbajal

MO417 - Questão para a prova oral

Numero:

Enunciado: Indique a alternativa onde o método mestre não pode ser aplicado:

a) T(n)= 4T(n/2) + n²/lg n 
b) T(n)= 4T(n/2) + n² 
c) T(n)= 3T(n/4) + n lg n
d) T(n) = T(n/3) + n
e) NDA

Ideia original de: Marleny Luque Carbajal

MO417 - Questão para a prova oral

Numero:

Enunciado: Sejam as funções seguintes:  

nlogn
n²logn
n⁸
(n²+8n+log³n)⁴
n²/logn

Qual das seguintes afirmacões é verdadeira?

a) O(nlogn)⊂ O(n²/logn) ⊂ O(n²logn)⊂ O(n⁸) ⊂ O((n²+8n+log³n)⁴) 

b) Ω(nlogn)⊃  Ω(n²logn)⊃ Ω(n²/logn) ⊃ Ω(n⁸) = Ω((n²+8n+log³n)⁴) 

c) Θ(n⁸) = Θ ((n²+8n+log³n)⁴)

d) O(n²/logn) ⊃ O(n²logn)

e) NDA

Idéia original de: Marleny Luque Carbajal

BEM VINDO

O objetivo deste blog é postear os exercicios da materia MO417 Complexidade de Algoritmos 2013