MO 417 - QUESTÃO PARA A PROVA ORAL - 1ª QUESTÃO

Número:

Enunciado: Uma empresa de produtos alimentícios possui uma frota de veículos que realizam entregas por diversas cidades. Os veículos de transporte de mercadoria possuem uma capacidade limitada de carga e devem realizar entregas em diferentes cidades distribuídas em um mapa. O gerente desta empresa deseja minimizar os custos no processo de entrega de mercadorias determinando rotas que minimizem a distância total percorrida e atenda a todas as demandas das cidades do mapa. Os veículos devem partir do depósito e retornar para o mesmo e cada cidade só deve ser visitada uma vez.
A figura abaixo ilustra uma possível solução do problema:

O problema descrito acima pode ser reduzido ao:

a) Ciclo Hamiltoniano
b) Clique
c) Fluxo máximo
d) Caxeiro Viajante
e) NDA

Ideia original de: Lucas Oliveira Batista

MO 417 - QUESTÃO PARA A PROVA ORAL 2ª QUESTÃO

Número:

Enunciado: Sabendo que SAT é NP-Completo e que existem funções polinomiais f(n) e g(n) que possibilitam a redução de SAT ao CLIQUE transformando a entrada de SAT em uma entrada para CLIQUE e transformando o resultado de CLIQUE para o resultado de SAT. É INCORRETO afirmar que:

a) A redução de SAT ao CLIQUE prova que CLIQUE é pelo menos NP-difícil.

b) Se soubessemos que a cota inferior de SAT é omega(h(n)) podemos afirmar que a cota inferior de CLIQUE é igual a cota inferior de SAT, omega(h(n)) apenas se f(n)+h(n)=o(h(n)).

c) Se soubessemos que CLIQUE tem cota superior O(h(n)) podemos afirmar que SAT tem cota inferior O(h(n)).

d) Se soubessemos que CLIQUE tem cota superior O(h(n)) podemos afirmar que SAT tem cota superior O(h(n)) apenas se f(n)+h(n)=o(h(n)).

e) NDA

Definições:

Cota superior: Dado um problema, se conhecemos um algoritmo que resolve tal problema em um modelo computacional em tempo T(n) então T(n) é a cota superior do problema.

Cota inferior: Dado um problema e um modelo computacional, a cota inferior do problema expressa a eficiência mínima para qualquer algoritmo que possa resolver o problema neste modelo computacional. Por exemplo, problemas de ordenação por comparação tem cota inferior = tetha(nlgn).

Ideia original de: Lucas Oliveira Batista

MO417 - 1ª QUESTÃO PARA A PROVA ORAL

Número:
Enunciado: Dada a rede de fluxo abaixo com origem "s" e sorvedor "t", determine o valor do fluxo, o fluxo máximo e o corte mínimo s-t, respectivamente.

a) 15 , 21 , ({s,a,b,c,d,e} {t})
b) 15 , 23 , ({a,b,c,d,e} {s,t})
c) 15 , 21 , ({s,a,b,c,d} {e,t})
d) 23 , 23 , ({s,a,b,c} {d,e,t})
e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - 2ª QUESTÃO PARA A PROVA ORAL

Número:
Enunciado: Sobre o método de Ford-Fulkerson e suas implementações podemos afirmar:

I) Em uma rede de fluxo, um corte (S,T) é definido como um corte em que a origem "s" e o sorvedor "t" encontram-se em conjuntos diferentes.
II) Em uma rede de fluxo, o fluxo máximo com origem "s" e sorvedor "t" é igual a capacidade do corte máximo (S,T)
III) O algoritmo de Edmonds-Karp tem complexidade O(VE²), pois utiliza a busca em largura O(VE) para calcular caminhos aumentantes.
IV) Em uma rede de fluxo G com origem "s" e sorvedor "t", se existe um caminho de "s" até "t" sobre a rede residual Gf então o fluxo em G não é máximo.

a) I, III e IV são verdadeiras
b) II e III são verdadeiras
c) III e IV são verdadeiras
d) I e IV são verdadeiras
e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Considerando os algoritmos de Bellman-Ford, Dag-Shortest-Paths ou Dijkstra, analise os grafos abaixo e indique quais destes algoritmos podem ser utilizados para encontrar um caminho mais curto a partir do vértice s.

 Grafo 1:

Grafo 2:

Grafo 3:

a) Grafo 1: Dijkstra e Dag-Shortest-Paths. Grafo 2: Bellman-Ford e Dijkstra. Grafo 3: Dag-Shortest-Paths e Bellman-Ford

b) Grafo 1: Bellman-Ford. Grafo 2: Bellman-Ford e Dag-Shortest-Paths. Grafo 3: Bellman-Ford e Dijkstra

c) Grafo 1: Nenhum dos algoritmos. Grafo 2: Bellman-Ford e Dag-Shortest-Paths. Grafo 3: Bellman-Ford e Dijkstra

d) Grafo 1: Bellman-Ford. Grafo 2: Bellman-Ford e Dag-Shortest-Paths. Grafo 3: Bellman-Ford, Dag-Shortest-Paths e Dijkstra

e) NDA

Ideia original de: Lucas Oliveira Batista

MO417-QUESTÃO PARA A PROVA ORAL -1ª QUESTÃO

Número:

Enunciado: Quais das arestas devem ser removidas do grafo abaixo para que seja possível obter uma ordenação topológica?

a) 9 e 3

b) 8 e 5

c) 1 e 10

d) 9 e 1

e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - QUESTÃO PARA A PROVA ORAL - 2ª QUESTÃO

Número:

Enunciado: Marque a alternativa que NÃO corresponde a uma possível “breadth-first tree”, construída pela busca em largura com origem no vértice 1 sobre o grafo abaixo:

a)                                                                                b)

                                              

                

 c)                                                                              d)

e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Podemos representar uma expressão contendo operadores e operandos binários em uma árvore binária de forma que a raiz contem um operador que deve ser aplicado ao resultado das expressões das sub-árvores esquerda e direita. Uma expressão em Notação Polonesa os operadores devem preceder os dois valores numéricos associados.

Dado uma expressão e sua árvore correspondente:

5+3*2

Assinale a alternativa que contém o percurso utilizado na árvore e a notação polonesa da expressão:

a) Percorrer a árvore em pós-ordem: 5+3*2

b) Percorrer a árvore em pré-ordem: 532*+

c) Percorrer a árvore em pós-ordem: +5*32

d) Percorrer a árvore em pré-ordem: +5*32

e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - QUESTÃO PARA A PROVA ORAL - 2ª QUESTÃO

Número:
Enunciado: Comparando os pseudo-códigos abaixo que calculam a sequência de Fibonacci podemos afirmar que:
a) Fib1 e Fib2 possuem o mesmo tempo de execução, pois calculam a sequência de Fibonacci resolvendo os mesmos subproblemas várias vezes.
b) Fib1 e Fib2 utilizam a técnica de divisão e conquista, pois esta técnica é utilizada quando o problema é dividido em subproblemas dependentes.
c) Se adicionarmos a Fib1 a técnica de memoização, Fib1 tem tempo de execução menor que Fib2, pois nem todos os subproblemas são resolvidos para encontrar a solução do problema geral.
d) Fib2 utiliza a técnica de programação dinâmica, pois esta técnica é utilizada quando há uma repetição dos mesmos subproblemas os quais não são independentes, ou seja, os subproblemas compartilham subsubproblemas.
e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - QUESTÃO PARA A PROVA ORAL - 1ª QUESTÃO

Número:
Enunciado: Sobre programação dinâmica assinale a alternativa correta marcando V para verdadeiro e F para falso:
( ) Ao contrário da divisão e conquista as técnicas de programação dinâmica utilizam um enfoque tabular de baixo para cima que resolve todos os subproblemas uma única vez. Este enfoque gera algoritmos mais eficientes.
 ( ) Problemas onde a divisão de um problema de tamanho n resulta em a subproblemas de tamanho n-1 geralmente nos levam a algoritmos recursivos exponenciais O(a^n). A programação dinâmica aplicada a estes problemas não gera algoritmos eficientes.
( ) A construção de um algoritmo utilizando programação dinâmica supõe quatro etapas: definição da subestrutura ótima, definição da recursividade, resolução dos subproblemas (bottom-up) e construção da solução ótima.
( ) A programação dinâmica geralmente é aplicada a problemas de otimização, quando os subproblemas são dependentes e superpostos, buscando todas as soluções ótimas para o problema.

a) V – F – V – F
b) V – V – V – F
c) F – F – F – V
d) F – V – V – F
e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - QUESTÃO PROVA ORAL

Numero:

Enunciado: Dado o procedimento FUNCTION (A) abaixo, podemos afirmar que:

FUNCTION (A)

1             if (A.length%2!=0)

2                             max=min=A[1]

3                             iniciaFor=2

4             elseif(A[1] > A[2]){

5                             max = A[1]

6                             min = A[2]

7                             iniciaFor=3

8             else       max=A[2]

9                           min=A[1]

10                         iniciaFor=3

11           for (i= iniciaFor;i<A.length;i=i+2)

12                           if(A[i]>A[i+1])

13                                          if(max<A[i])

14                                                          max=A[i];

15                                          if (min>A[i+1])

16                                                          min=A[i+1];

17                           elseif(max<A[i+1])

18                                          max=A[i+1]

19                                           if (min>A[i])

20                                              min=A[i]

21           RETURN (max,min)

               

a) Busca os elementos máximo e mínimo independentemente, fazendo no máximo 3(n-3)/2 comparações.

b) Busca os elementos máximo e mínimo independentemente, fazendo no máximo 2n – 2 comparações.

c) Busca os elementos máximo e mínimo simultâneos, fazendo no máximo  (3n)/2 -2 comparações.

d) Busca os elementos máximo e mínimo simultâneos, fazendo no máximo 3⌊n/2⌋ comparações.

e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Um estudante de bioinformática possui uma lista com N enzimas e um arranjo A (ilustrado abaixo) que contém inibidores de enzimas associados a uma enzima específica.

1	2	3	4	5	6	7	8	9	10	…	N
A	B	C	F	L	A	A	H	J	Y	…	Z

Tomando os 10 primeiros elementos como exemplo, o estudante deseja ordenar os inibidores de enzimas, de forma que elementos repetidos na entrada tenha a mesma ordem de precedência na saída e sem utilizar uma estrutura de dados adicional, da seguinte forma:

1	2	3	4	5	6	7	8	9	10
A	A	A	B	C	F	H	J	L	Y

Qual algoritmo de ordenação poderia ser utilizado?

a) Bucket-sort, Radix-sort e Heap-sort.

b) Todos os algoritmos classificados como divisão e conquista.

c) Selection-sort, Insertion-sort e Quick-sort.

d) Counting-sort, Insertion-sort e Heap-sort.

e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: Dada a seguinte função recursiva:

        Function (n)

              if (n ≤ 1)

                    PARAR

              else

                    Ativar processo X

                    Function (n/2)

                 

A fórmula de recorrência que representa esta função é:

       
          T(n) = 1 + T(n/2),       n>1
          T(1) = 0

Sendo T(n) o número de ativações do processo X, podemos afirmar que:

a) A recorrência não pode ser resolvida pelo método mestre, pois não existe a constante “a”.

b) T(n) = Θ (lg n), logo o processo x será ativado lg n vezes.

c) T(n) = Θ (n lg n), logo o processo x será ativado n lg n vezes.

d) T(n) = Θ (2ⁿ), logo o processo x será ativado 2ⁿ vezes.

e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - Questão para a prova oral

Número:

Enunciado: Sobre a notação O, Ω e algoritmos, assinale V para verdadeiro e F para falso:

(  ) O (lê-se o maiúsculo) fornece um limite assintótico superior e é formalmente definido como O(g(n)) = {f(n): existem constantes positivas c e n₀ tais que 0 ≤ f(n) ≤ cg(n) para todo n>n₀}
(  ) Ao contrário de O (lê-se o maiúsculo), Ω fornece um limite assintótico inferior e é formalmente definido como Ω(g(n)) = {f(n): existem constantes positivas c e n₀ tais que 0 ≤ cg(n) < f(n) para todo n>n₀}
(  ) Um limite inferior para um problema P é uma função h(n). Todo algoritmo que resolve P efetua pelo menos Ω(h(n)) operações.
(  ) Dado um problema P, se P é Ω(h(n)) e encontramos um algoritmo A com complexidade O(h(n)) entao A é um algoritmo ótimo para P.
(  ) O tempo de execução do algoritmo selection_sort para o pior caso é O(n²) e para o melhor caso O(n)


a. V - V - V F - V
b. F - F - F - V - F
c. V - F - F - F - V
d. V - F - V - V - F
e. NDA

Ideia original de: Lucas Oliveira Batista

MO417 - Complexidade de Algoritmos I

Blog com a finalidade de auxiliar na etapa de aprendizagem pós aula.