MO417- Questão para a prova oral
Numero:
Um dos problemas de Karp, os quais foram provados pertencerem a NP-Completo, é o problema do clique máximo em um grafo não direcionado.
O clique máximo de um grafo G é o maior subgrafo, em número de vértices, os quais todos os vértices estejam conectados, ou seja o subgrafo completo com maior número de vértices de G.
Um uso do clique máximo é achar nas redes sociais, com usuários como vértices e as arestas a relação entre eles, o maior grupo, ou subgrafo, onde todos os usuários estejam conectados entre si, e assim direcionar alguns recursos como notícias e propagandas.
Sobre esse problema:
I. O problema de se achar o clique máximo em G , no complemento de G, é mais fácil do que em G.
II. Seria possível encontrar um k-clique máximo de G=(V,E), ou um clique com k vértices para k <|V| , em tempo polinomial através de buscas em grafos.
III. Se for possível enumerar todos as componentes fortemente conexas de G em tempo polinomial, o problema do clique também seria resolvido em tempo polinomial para o tamanho da entrada.
IV. Como se trata de um problema de decisão, é possível propor um algoritmo guloso que pode encontrar pelo menos um i-clique, onde i é menor ou igual ao clique máximo.
São verdadeiras apenas:
a. I e II
b. II e III
c. III e IV
d. II e IV
e. N.D.A
Ideia original de: Otavio Augusto A. Silva
sexta-feira, 14 de junho de 2013
sexta-feira, 31 de maio de 2013
MO417- Questão para a prova oral
Numero:
Existem diversas abordagens para resolver o problema do menor caminho entre todos os pares de vértices em um grafo. Analise o grafo direcionado ponderado abaixo e as afirmações sobre ele.
I. É possível executar o algoritmo de Dijkstra para cada um dos vértices como fonte, assim obtendo o menor caminho entre cada par de vértices.
II. Como não se trata de um grafo esparso, o custo de execução do algoritmo de Bellman Ford, para cada um dos vértices como fonte, será inferior ao custo do Floyd-Warshall.
III. Caso o peso da aresta entre os vértices 5 e 2 fosse -2, apenas o algoritmo Floyd-Warshall resolveria o problema do enunciado, pois é o único que faz uso de Programação Dinâmica.
IV. Suponha a seguinte alteração nos laços aninhados do algoritmo Floyd-Warshall:
Sobre aquelas afirmativas , é(são) correta(s) apenas:
a. I e II
b. I e III
c. II e IV
d. I e IV
e. N.D.A
Ideia original de: Otavio Augusto A Silva.
Numero:
Existem diversas abordagens para resolver o problema do menor caminho entre todos os pares de vértices em um grafo. Analise o grafo direcionado ponderado abaixo e as afirmações sobre ele.
I. É possível executar o algoritmo de Dijkstra para cada um dos vértices como fonte, assim obtendo o menor caminho entre cada par de vértices.
II. Como não se trata de um grafo esparso, o custo de execução do algoritmo de Bellman Ford, para cada um dos vértices como fonte, será inferior ao custo do Floyd-Warshall.
III. Caso o peso da aresta entre os vértices 5 e 2 fosse -2, apenas o algoritmo Floyd-Warshall resolveria o problema do enunciado, pois é o único que faz uso de Programação Dinâmica.
IV. Suponha a seguinte alteração nos laços aninhados do algoritmo Floyd-Warshall:
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
if d[i][k] + d[k][j] < d[i][j] then
d[i][j] ← d[i][k] + d[k][j]
salvo[i][j] ← k
Seria possível, em O(V), imprimir o menor caminho entre quaisquer pares de vértices, pois basta varrer o caminho {i,...j} em "salvo" .
Sobre aquelas afirmativas , é(são) correta(s) apenas:
a. I e II
b. I e III
c. II e IV
d. I e IV
e. N.D.A
Ideia original de: Otavio Augusto A Silva.
sexta-feira, 17 de maio de 2013
MO417 - Questão para a prova oral
Numero:
O algoritmo de Dijkstra resolve o problema do caminho mais curto em um grafo, dada uma fonte desse caminho, com tempo de execução em O(E+VlogV), caso seja usada um Heap de Fibonacci como a fila de prio deste algoritmo.
Entretanto diversas aplicações estão interessadas em um caminho mais curto entre A e B, ou de uma fonte A ao destino B. Sobre a alteração deste algoritmo para dijkstra_ab(G,A,B) , é correto afirmar:
I. Como o algoritmo funciona apenas em grafos direcionados, não existe a garantia de sempre encontrar B partindo de A.
II. Caso haja uma aresta de peso negativo entre A e B, o menor caminho pode estar contido em um ciclo.
III. Não é possível escrever dijkstra_ab(G,A,B) fazendo-se apenas uma alteração em dijkstra(G,A).
IV. Apesar de na média dijkstra_ab(G,A,B) ter um tempo de execução inferior, este ainda é O(E+VlogV).
a. I e III estão corretas.
b. I e IV estão corretas.
c. III está correta.
d. II e IV estão corretas.
e. N.D.A
Ideia original de: Otavio Augusto A Silva.
Numero:
O algoritmo de Dijkstra resolve o problema do caminho mais curto em um grafo, dada uma fonte desse caminho, com tempo de execução em O(E+VlogV), caso seja usada um Heap de Fibonacci como a fila de prio deste algoritmo.
Entretanto diversas aplicações estão interessadas em um caminho mais curto entre A e B, ou de uma fonte A ao destino B. Sobre a alteração deste algoritmo para dijkstra_ab(G,A,B) , é correto afirmar:
I. Como o algoritmo funciona apenas em grafos direcionados, não existe a garantia de sempre encontrar B partindo de A.
II. Caso haja uma aresta de peso negativo entre A e B, o menor caminho pode estar contido em um ciclo.
III. Não é possível escrever dijkstra_ab(G,A,B) fazendo-se apenas uma alteração em dijkstra(G,A).
IV. Apesar de na média dijkstra_ab(G,A,B) ter um tempo de execução inferior, este ainda é O(E+VlogV).
a. I e III estão corretas.
b. I e IV estão corretas.
c. III está correta.
d. II e IV estão corretas.
e. N.D.A
Ideia original de: Otavio Augusto A Silva.
sexta-feira, 3 de maio de 2013
MO417 - Questão para a prova oral
Numero:
Seja H=(V,E) um grafo não direcionado, representado por uma Matriz de Adjacência, onde existe apenas um caminho entre cada par (u,v) ∈ V, e as propriedades de um heap-máximo sejam verdadeiras.
Sobre o custo de implementarmos as funções pai(u) e raiz(H), é correto afirmar:
a. Se apenas acessássemos v ∈ V na diagonal superior de H, poderíamos em o(V) obter pai(u) e raiz(H).
b. Caso H seja transformado em uma Lista de Adjacência , ambas as funções terão custo O(V).
c. Se H fosse um grafo direcionado, o custo de pai(u) seria O(E).
d. Sendo O(depth) o custo de uma busca em profundidade em H, e O(root) o custo de raiz(H), para qualquer tamanho de V, root=Ω(depth) .
e. N.D.A
Numero:
Seja H=(V,E) um grafo não direcionado, representado por uma Matriz de Adjacência, onde existe apenas um caminho entre cada par (u,v) ∈ V, e as propriedades de um heap-máximo sejam verdadeiras.
Sobre o custo de implementarmos as funções pai(u) e raiz(H), é correto afirmar:
a. Se apenas acessássemos v ∈ V na diagonal superior de H, poderíamos em o(V) obter pai(u) e raiz(H).
b. Caso H seja transformado em uma Lista de Adjacência , ambas as funções terão custo O(V).
c. Se H fosse um grafo direcionado, o custo de pai(u) seria O(E).
d. Sendo O(depth) o custo de uma busca em profundidade em H, e O(root) o custo de raiz(H), para qualquer tamanho de V, root=Ω(depth) .
e. N.D.A
Ideia original de: Otávio Augusto Araújo Silva
sexta-feira, 19 de abril de 2013
MO417 - Questão para a prova oral
Numero:
Bob e Alice gostariam de troca mensagens entre eles sem que outras pessoas soubessem, assim eles estipularam o seguinte protocolo:
1. Converter toda a mensagem em representação numérica, ex: letra "A" se transforma 42.
2. Insere todas os números em uma árvore Red/Black
3. Definem em segredo qual número será a raiz e um caminhamento para a leitura desta árvore.
Desta forma, Bob envia para Alice o caminhamento pós-ordem da árvore, entretanto a mensagem, que nunca contém letras repetidas, só pode ser entendida caso seja feito o caminhamento inter-ordem para os nós a esquerda da raiz e pre-ordem para os nós a direita da raiz.
Em relação a uma algoritmo que implementaria essa pequena confusão na mensagem, é correto afirmar.
I. Só seria atingido o balanceamento ótimo da árvore caso a mensagem fosse ordenada, com o elemento na posição mediana sendo a raiz.
II. Custo de realizar todos os três caminhamentos na árvore será sempre o mesmo independente do balanceamento da árvore.
III. A mensagem {12,9,47,27,11,5} é válida para Bob e Alice
IV. Caso Bob enviasse [a,b...z], para Alice, todas as varreduras resultariam na mesma mensagem, dado que a arvore seria uma "tripa", ou com todos os nós a direta do pai.
a. I e III
b. II e IV
c. I e IV
d. II
e. N.D.A
Numero:
Bob e Alice gostariam de troca mensagens entre eles sem que outras pessoas soubessem, assim eles estipularam o seguinte protocolo:
1. Converter toda a mensagem em representação numérica, ex: letra "A" se transforma 42.
2. Insere todas os números em uma árvore Red/Black
3. Definem em segredo qual número será a raiz e um caminhamento para a leitura desta árvore.
Desta forma, Bob envia para Alice o caminhamento pós-ordem da árvore, entretanto a mensagem, que nunca contém letras repetidas, só pode ser entendida caso seja feito o caminhamento inter-ordem para os nós a esquerda da raiz e pre-ordem para os nós a direita da raiz.
Em relação a uma algoritmo que implementaria essa pequena confusão na mensagem, é correto afirmar.
I. Só seria atingido o balanceamento ótimo da árvore caso a mensagem fosse ordenada, com o elemento na posição mediana sendo a raiz.
II. Custo de realizar todos os três caminhamentos na árvore será sempre o mesmo independente do balanceamento da árvore.
III. A mensagem {12,9,47,27,11,5} é válida para Bob e Alice
IV. Caso Bob enviasse [a,b...z], para Alice, todas as varreduras resultariam na mesma mensagem, dado que a arvore seria uma "tripa", ou com todos os nós a direta do pai.
a. I e III
b. II e IV
c. I e IV
d. II
e. N.D.A
Ideia original de: Otávio Augusto Araújo Silva
sexta-feira, 5 de abril de 2013
MO417 - Questão para a prova oral
Numero:
Sobre a técnica de programação dinâmica e os problemas os quais ela se aplica, podemos dizer que:
a. Dizemos que um problema possui subestrutura ótima quando podemos dividi-lo em problemas menores cujas soluções são superpostas
b. Alguns dos problemas onde é possível utilizar a técnica de divide-and-conquer são bons candidatos para o uso da programação dinâmica caso seja garantido a independência dos subproblemas.
c. Dada a matriz A(i,p) de (sub)soluções ótimas, usada por um algoritmo que emprega a programação dinâmica, o custo deste algoritmo sempre é dominado assintoticamente por O(i*p).
d. Se a solução de um problema pode ser obtida através das escolhas das melhores soluções dos subproblemas, podemos aplicar a programação dinâmica apenas se aquela escolha foi feita com uma abordagem top-down .
e. N.D.A
Numero:
Sobre a técnica de programação dinâmica e os problemas os quais ela se aplica, podemos dizer que:
a. Dizemos que um problema possui subestrutura ótima quando podemos dividi-lo em problemas menores cujas soluções são superpostas
b. Alguns dos problemas onde é possível utilizar a técnica de divide-and-conquer são bons candidatos para o uso da programação dinâmica caso seja garantido a independência dos subproblemas.
c. Dada a matriz A(i,p) de (sub)soluções ótimas, usada por um algoritmo que emprega a programação dinâmica, o custo deste algoritmo sempre é dominado assintoticamente por O(i*p).
d. Se a solução de um problema pode ser obtida através das escolhas das melhores soluções dos subproblemas, podemos aplicar a programação dinâmica apenas se aquela escolha foi feita com uma abordagem top-down .
e. N.D.A
Ideia original de: Otávio Augusto Araújo Silva
sexta-feira, 29 de março de 2013
MO417 - Questão para a prova oral
Numero:
Uma empresa de telefonia recebeu reclamações sobre má qualidade do sinal ou ausência do mesmo. Ao analisar a distribuição de suas torres e a cobertura das mesmas, foi observado a má distribuição das torres.
Em duas regiões a e b, hora as torres se sobrepunham a cobertura, hora elas não cobriam uma certa área.
Sendo os pontos em negritos a posição da torre, dado por tn(x,y), e a área sombreada a cobertura total das mesmas.Dada uma função f(tn) que retorna um índice de cobertura da torre, essa empresa resolveu o problema através da disposição de pares de torres, cujos índices fossem os k-ésimos maiores e menores respectivamente do conjunto de torres. O que é correto afirmar sobre um melhor algoritmo, em custos temporal e de comparação, que retornaria simultaneamente o maior e menor elemento de um vetor, de tamanho n dos índices de cobertura.
a. Esse algoritmo teria como caso médio O(n) e pior caso O(n²)
b.Seria necessária uma ordenação por comparação, logo é certo que o melhor caso nunca seria menor que Θ(nlogn)
c. O algoritmo:
for 1 to n do { if (menor(i) { menor =i} if(maior(i) {maior=i} }
É o mais eficiente em custos temporal e de comparação.
d. É possível realizar em média menos que duas comparações por elemento desse vetor para obtermos os elementos cujo índice seja o maior e menor respectivamente.
e. N.D.A
Numero:
Uma empresa de telefonia recebeu reclamações sobre má qualidade do sinal ou ausência do mesmo. Ao analisar a distribuição de suas torres e a cobertura das mesmas, foi observado a má distribuição das torres.
Em duas regiões a e b, hora as torres se sobrepunham a cobertura, hora elas não cobriam uma certa área.
Sendo os pontos em negritos a posição da torre, dado por tn(x,y), e a área sombreada a cobertura total das mesmas.Dada uma função f(tn) que retorna um índice de cobertura da torre, essa empresa resolveu o problema através da disposição de pares de torres, cujos índices fossem os k-ésimos maiores e menores respectivamente do conjunto de torres. O que é correto afirmar sobre um melhor algoritmo, em custos temporal e de comparação, que retornaria simultaneamente o maior e menor elemento de um vetor, de tamanho n dos índices de cobertura.
a. Esse algoritmo teria como caso médio O(n) e pior caso O(n²)
b.Seria necessária uma ordenação por comparação, logo é certo que o melhor caso nunca seria menor que Θ(nlogn)
c. O algoritmo:
for 1 to n do { if (menor(i) { menor =i} if(maior(i) {maior=i} }
É o mais eficiente em custos temporal e de comparação.
d. É possível realizar em média menos que duas comparações por elemento desse vetor para obtermos os elementos cujo índice seja o maior e menor respectivamente.
e. N.D.A
Ideia original de: Otávio Augusto Araújo Silva
Assinar:
Postagens (Atom)