MO417 - Questão para a prova oral

MO417 - Questão para a prova oral

Número: 2013-031

Enunciado: Considere o algoritmo SELECT a seguir, que retorna o i-ésimo menor elemento de um arranjo de entrada de tamanho n:

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 ceil(n/5) grupos, através da ordenação por inserção dos elementos de cada grupo (nos quais existem 5 elementos, no máximo), e posterior escolha do elemento do meio (se houver, dois, tomar o menor).

3: Usar SELECT recursivamente para encontrar a mediana x das ceil(n/5) medianas localizadas na Etapa 2. Se celi(n/5) for par, então x será a mediana inferior.

4: Particionar o arranjo de entrada em torno da mediana de medianas x, em tempo linear. 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 o 2° menor elemento 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) 4 e 2

b) 5 e 3

c) 6 e 2

d) 8 e 3

e) NDA

Ideia original de: Marleny Luque Carbajal

MO417 - QUESTÃO PARA A PROVA ORAL

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-030

Enunciado: Leonardo prestou um concurso público com 30 vagas e está tentando descobrir sua classificação final. Entretanto, foi divulgada apenas uma lista na qual cada elemento possui o número de inscrição de um candidato e sua respectiva nota final. Infelizmente, a lista está ordenada pelo número de inscrição e não pela nota. Para saber se foi aprovado, Leonardo precisa comparar sua nota com a do candidato que ficou em 30o. lugar.

Considerando o estado da arte em teoria de algoritmos, o que podemos oferecer a pessoas que queiram obter o 30o. elemento numa lista de tamanho n?

1. Os melhores algoritmos conhecidos para este problema gastam Ω(n lg n) unidades de tempo.
2. É possível conseguir a resposta desejada em tempo linear em n.
3. Exsitem algoritmos que resolvem tais problemas em tempo O(lg n).
4. Nenhum algoritmo para este problema usa menos do que tempo Ω(n²).
5. N. D. A.

Ideia original de: Hilário Seibel Júnior

MO417 - QUESTÃO PARA A PROVA ORAL

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-029


Enunciado: Tomando-se o algoritmo abaixo, que seleciona o i-ésimo menor elemento de um arranjo a, desde que i esteja entre 1 e o tamanho de a, auxiliado pelo algoritmo PARTICIONA:

01. SELECIONA(a: arranjo, i)
02.    se a.tamanho > 0
03.       inicio = 1
04.       fim = a.tamanho
05.       enquanto inicio < fim
06.          q = PARTICIONA(a, inicio, fim)      
07.          k = q - inicio + 1
08.          se i == k
09.             retorna a[q]
10.          senão se i < k
11.             fim = q - 1
12.          senão
13.             inicio = q + 1
14.             i = i - k
15.       retorna a[inicio]
16.    senão retorna NULO

01. PARTICIONA(a: arranjo, p, r)
02.    x = a[r]
03.    i = p - 1
04.    para j = p até r - 1
05.       se a[j] <= x
06.          i = i + 1
07.          troca a[i] com a[j]
08.    troca a[i + 1] com a[r]
09.    retorna i + 1

Sobre o algoritmo SELECIONA(a: array, i), é INCORRETO afirmar que:

1. Um pior caso ocorre para entradas ordenadas crescentemente, desejando-se saber o menor elemento.
2. Um melhor caso ocorre para entradas ordenadas crescentemente, desejando-se saber o maior elemento.
3. Um melhor caso ocorre para entradas ordenadas decrescentemente, desejando-se saber o maior elemento.
4. As complexidades de tempo esperada e no pior caso são O(n) e Θ(n²), respectivamente, para entradas de tamanho n.
5. N.D.A.

Ideia original de: Daniel Henriques Moreira

MO417 - Questão para a prova oral

Número: 2009-049

Enunciado: O comandante de um pelotão de 10 soldados precisou atribuir uma missão ao sexto homem mais velho de sua equipe. Sem saber as idades dos soldados, escolheu um deles ao acaso e lhe perguntou sua data de nascimento: "Zero-dois, em que dia o senhor nasceu?" O soldado, em alto e bom tom, respondeu: "03 de abril de 1989, senhor!"

O comandante, então, lembrando-se de seu intenso treinamento em Algoritmos, deu a seguinte ordem ao pelotão: "Organizem uma fila da seguinte forma: quem nasceu antes do soldado Zero-dois, que se posicione à frente dele; quem nasceu depois, que se posicione atrás dele." Após o pelotão ter se organizado, o comandante notou que o soldado Zero-dois era apenas o quarto da fila, e percebeu que teria de continuar sua busca. Para chegar mais rápido à resposta, o próximo passo do comandante, então, deveria ser:

1. Continuar procurando somente entre os 3 soldados mais velhos, mas agora buscando o segundo mais velho dentre eles.
2. Continuar procurando somente entre os 6 soldados mais novos, mas agora buscando o segundo mais velho dentre eles.
3. Continuar procurando somente entre os 6 soldados mais novos, mas agora buscando o segundo mais novo dentre eles.
4. Continuar procurando o sexto homem mais velho entre os 10 soldados, mas escolhendo outro soldado ao acaso.
5. NDA

Ideia original de: Fábio de Souza Azevedo