Questão semana - 12/06

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado as afirmações abaixo

I. Cada problema em NP pode ser resolvido no tempo exponencial.
II. Se houver um problema X que pode ser reduzido a um problema NP-difícil conhecido, então X deve ser NP-difícil.
III. Se P é igual a NP, então NP é igual a NP-completo.
|V. O seguinte problema está em NP: dado um número n = p.q, em que p e q são números primos de N-bits, encontre p ou q.

Quantas dessas afirmações são verdadeiras ?

(a) 1

(b) 2

(c) 3

(d) 4

(e) NDA

Ideia original de: Lucas Miguel de Carvalho

Questão - Semana 29/05

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Algumas vezes, arestas em grafos possuem uma capacidade mínima que deve ser cumprida. Por exemplo, no grafo abaixo, a aresta AB tem máxima capacidade igual a 6 e mínima igual a 4, isto nos fornece que o fluxo nesta aresta tem de estar entre 4 e 6.

Dado o grafo abaixo, qual deve ser os valores de x e y, representando respectivamente a capacidade mínima e máxima da aresta AC , para que seja possível obter um eventual fluxo para a rede?

(a) x=7 e y=10

(b) x=4 e y=5

(c) x=1 e y=8

(d) x=3 e y=12

(e) NDA

Ideia original de: Lucas Miguel de Carvalho

1ª QUESTÃO - semana 16/05

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Considere um tabuleiro 3x4. Cada quadrado contém um número:

O objetivo do jogo consiste em deslocar sua peça do canto superior esquerdo até o canto inferior direito,através de uma sequência de movimentos para a direita ou para baixo, de forma de minimizar o somatório dos pontos correspondentes aos quadrados que você passou. 

O jogo pode ser descrito como um problema de caminho mínimo, onde cada quadrado tem sua posição correspondente, mostrado na figura abaixo:

Nessas condições, ao aplicarmos o algoritmo de Dijkstra para resolver o jogo, quantos nós (quadrados) pares não estarão no caminho ótimo ?

(a) 4

(b) 3

(c) 2

(d) 5

(e) NDA

Ideia original de: Lucas Miguel de Carvalho

2ª QUESTÃO - semana 16/05

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado:  Você está jogando um jogo online chamado DotA. Percebendo que você pode converter o mapa do jogo em um grafo com vértices representando as posições no mapa e as arestas os caminhos até eles, você observa que cada passagem no grafo provoca uma quantidade diferente de danos à você no jogo. É possível ainda alterar o grafo para usar pesos para representar os danos causados ​​por cada aresta. Você então, usa o algoritmo de Dijkstra para encontrar o caminho de A a H, com o menor dano possível. Anote a ordem em que os vértices são removidos da fila de prioridade ao executar o algoritmo de Dijkstra.

(a) A, B, D, C, F, E, G, H 

(b) A, B, C, D, F, E, G, H

(c) A, B, D, C, E, F, G, H

(d) A, B, C, D, E, F, G, H

(e) NDA

Ideia original de: Lucas Miguel de Carvalho

Questão semana 29/04 - 1ª questão

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Você está jogando um jogo online chamado DotA. Percebendo que pode converter o mapa do jogo em um grafo com os vértices representando as posições no mapa e as arestas os caminhos até eles, você quer usar o algoritmo que acabou de aprender para navegar neste grafo.Considere o seguinte mapa do jogo convertido em um grafo:

                                                     

Suponha que você queira encontrar um caminho saindo do vértice 0 (zero) a fim de chegar no vértice 1 (um) passando por todas as posições no mapa ( vértices ). Anote a ordem em que os vértices são inseridos na fila de vértices ao executar o algoritmo de BFS para encontrar este caminho:

(a) 0-2-5-7-6-3-4-1

(b) 0-2-6-7-5-4-3-1

(c) 0-5-2-4-7-3-6-1

(d) 0-5-2-7-4-3-6-1

(e) NDA

Ideia original de: Lucas Miguel de Carvalho

Questão semana 29/04 - 2ª questão

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado as afirmações abaixo sobre algoritmos em grafos (considerando um grafo por G(V,E), onde V é o número de vértices e E o número de arestas )

I. A árvore BFS de um grafo é única.
II. A análise agregada do algoritmo BFS resulta em uma complexidade Θ(V+E).
III. Uma ordenação topológica não pode ser resolvida por DFS.
IV. Trabalhar com matrizes de adjacência é mais vantajoso do que com listas de prioridade.
V. A multiplicação da matriz de adjacência por ela mesma fornece o grafo complementar (GT(V,E)) do original, sendo G(V,E) direcionado.

A alternativa que representa as afirmações incorretas é:

a) I, II, III, IV, V
b) I, II , III, V
c) I, III , IV
d) I, II, IV
e) NDA.



Ideia original de: Lucas Miguel de Carvalho

Pergunta das aulas 16/04 e 18/04

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Após transformar um heap máximo em uma árvore binária, observou-se que ela possuía no máximo k elementos. Então a altura da árvore binária é:

a) lg(k+1) - 1
b) lgk
c) lgk +1
d) lg(k-1) + 1
e) NDA

Ideia original de: Lucas Miguel de Carvalho

Questão das aulas do dia 01/04 e 03/04 - 1ª questão

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: A principal diferença entre Programação Dinâmica e algoritmos de Divisão e Conquista é:

a) A Divisão e Conquista é mais eficiente quando todos os subproblemas são dependentes.
b) As soluções parcias em Programação Dinâmica são armazenadas e em Divisão e Conquista não.
c) A Programação Dinâmica é mais eficiente quando os subproblemas são independentes.
d) A Programação Dinâmica é mais adequada quando há sobreposições de subproblemas.
e) NDA

Ideia original de: Lucas Miguel de Carvalho

Questão das aulas do dia 01/04 e 03/04 - 2ª questão

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Vamos considerar o problema de encontrar a Cadeia Comum mais Longa (LCS) , definindo  como LCS(A,B) a Cadeia Comum mais Longa entre as strings A e B.

Por exemplo, se considerarmos A={ALFABETO} e B={HABITAT} e os subproblemas A'={ALFA} e B'={HABI}, então podemos afirmar que:

a) LCS(A',B') + LCS(A-A',B-B') = LCS(A,B)
b) LCS(A',B') + LCS(A-A',B-B') ≠ LCS(A,B)
c) Não existe Cadeia Comum mais Longa entre os subproblemas A' e B'.
d) Só existe uma Cadeia Comum mais Longa entre A e B, ou seja, LCS(A,B) é única.
e) NDA.

Ideia original de: Lucas Miguel de Carvalho

Pergunta da semana do dia 26/03 - 1ª questão

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Sobre o algoritmo da PESQUISA-BINÁRIA-ITERATIVA:

BINARY-SEARCH(A, x)

1  if x < A[1] then
2     return 0
3  if x ≥ A[n] then
4     return n
5  // aqui A[1] ≤ x < A[n]
6  start ← 1
7  end ← n
8  // invariante: A[start] ≤ x < A[end]
9  while start + 1 < end do
10    middle ← (start + end)/2
11    if A[middle] ≤ x then
12       start ← middle
13    else
14       end ← middle
15 return start

é correto afirmar que a comparação da linha 11 é executada pelo menos :

a) ⌊lg n⌋  vezes
b) ⌊n/2⌋ vezes
c) ⌈(n+1)/2⌉ vezes
d) lg n +1  vezes
e) NDA



Ideia original de: Lucas Miguel de Carvalho

Pergunta da semana do dia 26/03 - 2ª questão

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Sobre as afirmações 

I. O Insertion Sort em uma implementação estável utiliza, além do vetor original, um espaço de armazenamento = Θ(1).

II. Os algoritmos de ordenação em tempo linear se diferenciam dos algoritmos de ordenação convencionais (O(nlg(n)) por precisarem de uma característica específica de entrada.

III. O pior caso do Quicksort ocorre quando a entrada já está ordenada, sendo o tempo de execução O(n lg n).

Podemos afirmar que:

a) Todas são verdadeiras.
b) I e II são verdadeiras.
c) I e III  são verdadeiras.
d) II e III são verdadeiras.
e) NDA


Ideia original de: Lucas Miguel de Carvalho

Pergunta das aulas de 18/03 e 20/03

MO417 - Questao para a prova oral

Numero:

Enunciado: Sobre algoritmos de ordenação, assinale a alternativa que contém o algoritmo que seja local, estável e com tempo de execução no pior caso de pelo menos Ω( nlgn) :

a) Mergesort
b) Quicksort
c) Bucket Sort
d) Counting Sort
e) NDA.

Ideia original de: Lucas Miguel de Carvalho

Pergunta das aulas 11/03 e 13/03

MO417 - Questao para a prova oral

Numero:

Enunciado: Dada as seguintes afirmações

I. Se produz um heap máximo a partir de um vetor de tamanho n não ordenado em O(n).

II. A função f(n)=1/(2^n) não satisfaz condição de regularidade do teorema mestre a.f(n/b)<=c.f(n), para um c<1.

III. O tempo de execução de um algoritmo A é descrito pela recorrência T(n) = 7T(n/2) + n²,
um outro algoritmo A' tem um tempo de execução descrito pela recorrência T'(n) = aT'(n/4) + n²
O maior valor inteiro de a para que A' seja assintoticamente mais rápido que A é 49.

assinale a alternativa correta:

a) Apenas a afirmação I é verdadeira.
b) As afirmações I e II são verdadeiras.
c) Apenas a afirmação II é verdadeira.
d) As afirmações II e III são verdadeiras.
e) NDA.

Ideia original de: Lucas Miguel de Carvalho

Questão da semana referente as aulas do dia 04/03 e 06/03.

Dada as seguintes afirmações

I. O pior caso de tempo de funcionamento e tempo de execução esperado são iguais dentro de fatores constantes para qualquer algoritmo randomizado.

II. Para toda função f(n) positiva, temos que f(n) + o( f(n) ) = Θ( f(n) ).

III. Sobre crescimento de funções, podemos dizer que

assinale a alternativa correta:

a) Apenas a afirmação I é verdadeira.

b) As afirmações I e II são verdadeiras.

c) Apenas a afirmação II é verdadeira.

d) As afirmações II e III são verdadeiras.

e) NDA.