Questão da Décima Quarta Semana

MO417 - Questão para a prova oral
Número:

Enunciado: Dada uma linguagem L, sua decisão sobre um algoritmo A depende de:

1  A linguagem L ser um mapeamento binário da instância do problema.

2  Da aceitação da Linguagem L pelo algoritmo A.
3  Da não aceitação do complemento da Linguagem L .

a. Todas as afirmações estão corretas
b. Somente a afirmação 1 é correta.
c. Somente a afirmação 2 é correta.
d. Somente as  afirmações 2 e 3 são corretas.
e. NDA

Ideia original de: Edson Riberto Bollis

Questão da Décima Segunda Semana

MO417 - Questão para a prova oral
Número:

Enunciado: Imagine que tomemos  as operações normais de soma e multiplicação definidas na matemática para operação de matrizes provindas de grafos. Imagine também que grafos tenham apenas peso iguais a 1.
Então afirma-se que:

1  A potenciação da matriz pelo expoente x, pode nos mostrar os caminhos de tamanho x.
2  Se for feita a potenciação de matriz pelo expoente x, os valores 0 nos mostrarão que não existe caminho de tamanho n entre dois vértices.
3 Existe a possibilidade de se calcular os menores caminhos utilizando as operações normais de matrizes.

a. Todas  as afirmações estão corretas
b. Somente a afirmação 1 é correta.
c. Somente a afirmação 2 é correta.
d. Somente as afirmações 1 e 2 são corretas.
e. NDA

Ideia original de: Edson Riberto Bollis

Questão da oitava semana

MO417 - Questão para a prova oral
Número:

Enunciado: Dada uma implementação de conjuntos disjuntos aplicada a n valores distintos quaisquer, o número mínimo de operações necessária para fazer a união destes n conjuntos é dado por:
(leve em consideração as operações MAKE-SET, UNION e FIND-SET)

a. n +  (n^2)/2
b. 2n
c. n + n^2.
d. n^2.
e. NDA
Ideia original de: Edson Riberto Bollis

Questão da sexta semana

MO417 - Questão para a prova oral

Número:

Enunciado: Dada uma área retangular fixa, um conjunto de quadrados ordenados pela medida de seus lados e o problema de preencher esta área com o maior número de quadrados possíveis, considere as afirmações:

    I - Se a posição dos quadrados não for levada em consideração para a resposta, podemos utilizar um algoritmo guloso e este problema será parecido com o da bolsa fracionária para carregar itens mais valiosos.
   II - Se a posição dos quadrados for levada em consideração para a resposta, não podemos utilizar um algoritmo guloso e este será um problema parecido com o da bolsa fracionária para levar itens mais valiosos.

Escolha a alternativa correta:

1. I e II são afirmações verdadeiras
2. Apenas a afirmação I é verdadeira.
3. Apenas a afirmação II é verdadeira.
4. Todas as afirmações estão erradas.
5. NDA

Ideia original de: Edson Riberto Bollis

Questão da quinta semana

MO417 - Questão para a prova oral

Número:

Enunciado: O que impediria de transformar um problema de ordenação em um problema de Programação Dinâmica?

1. Os sub-problemas ótimos seriam dependentes das soluções de outros problemas.
2. A  impossibilidade de separar os problemas em sub-problemas ótimos.
3. A não existência da reutilização de informação para diminuir o retrabalho.
4. O overhead de memória necessário para armazenar as sub-soluções calculadas.
5. NDA

Ideia original de: Edson Riberto Bollis

Questão da terceira semana

MO417 - Questão para a prova oral

Número:
 
Enunciado: Dada uma arvore de decisão de um algoritmo de ordenação por comparação, sabemos que dentre seus ramos ela tem um cujo tamanho é nlg(n), de onde vem a prova de que todo algoritmo por comparação é Ω(nlg(n)) para seu pior caso, porém alguns algoritmos como o insertionsort para o pior caso é O(n^2).
Dentro da perspectiva de arvore de decisão e do algorítmo insertion sort, é incorreto afirmar que:

1. Assumimos a hipotese de que n! é o número de folhas mínimo de uma arvore de decisão para provarmos que todo algoritmo de comparação é Ω(nlg(n)).
2. Devido a assumirmos a hipótese de que no "melhor" dos piores casos somente existirá uma comparação entre dois locus distintos da array para a prova de que todo algoritmo de comparação é Ω(nlg(n)).
3. Devido ao insertion-sort fazer mais de uma comparação entre dois Locus distintos de um array, isso permite que ele passe do  número de O(nlog(n)) e varie entre Ω(nlg(n)) e O(n^2) no seu pior caso.
4. Devido ao insertion-sort fazer no pior caso a comparação de um elemento i qualquer com seus i-1 elementos anteriores para seus n elementos.
5. NDA

Ideia original de: Edson Riberto Bollis

Questões da primeira e segunda semana

Segue as questões da primeira e segunda semana como foram escritas, pode se ver no end:
http://algorithmic-complexity-issues.webnode.com/noticias/


Questão para segunda semana de aula
15/03/2013 22:25

========================================================================

MO417 - Questao para a prova oral

Numero:

Ideia original de: Edson Riberto Bollis

Recursivamente, o algorhitmo que não  é O(nlg n) e nem O(n^2lg n) é dado por
a) T(n) = 2T(n/2) + cn.
b) T(n) = 3T(n/4) + nlgn.
c) T(n) = 9T(n/3) + n
d) T(n) = 2T(n/2) + nlgn
e) NDA



Questão da primeira semana de aula
08/03/2013 23:14

======================================================================

Qual a família de funções que segundo a definição da notação Θ torna possível as constânte c1 = c2=1 tq n0≤n, para k pertencente aos naturas?
a) n^k
b)2*n^k
c)k*log(n)
d)(n/4)*log(n)
e)NDA

Reposta: a, pois   c*n^k≤n^k≤c*n^k <=> C=1