Resolução do Teste 11 de Construção e Análise de Algoritmos
a) O adversário poderia ter respondido à pergunta “a2<a4?” com uma resposta negativa. Assim o algoritmo não teria ganhado o par <a4,a1> por transitividade e ainda de perguntar “a1<a4?”.
b) As primeiras perguntas são: “a2<a1?” e “a3<a4?”. Seja M1 o maior da primeira pergunta e M2 o maior da segunda pergunta e sejam m1 o menor da primeira pergunta e m2 o menor da segunda pergunta.
Então perguntamos quem é o maior dos maiores: “M1<M2?”. Temos duas possibilidades:
- M2> M1 , então ganhamos o par <m1,M2> por transitividade.
- M2< M1 , então ganhamos o par <m2,M1> por transitividade.
até aqui gastamos 3 comparações e já temos 4 pares. Resta saber ainda qual a relação entre m1e m2 e entre M2 e m1 ou M1 e m2, dependendo da última resposta. Estes últimos dois casos são análogos, vamos análisar só um. A pergunta é “M2 < m1?”. Temos duas possibilidades:
- M2< m1 , então ganhamos o par <m2,m1> por transitividade.
- m1< M2 , e ai não ganhamos nada.
Se houver o primeiro caso então o problema terminou só com 4 comparações. Senão, ainda temos uma comparação e ainda falta descobrir qual a relação entre m1e m2. Gastamos com isto nossa quinta e última pergunta: “m1< m2?”. Qualquer que seja a resposta não ganharemos nada por transitividade (m1e m2não era maior que ninguem). Mas agora sabemos a ordem total P com no máximo 5 perguntas.
c) Modelemos um jogo como um grafo, onde os vértices representam os elementos a serem ordenados e uma aresta sai do menor para o maior.
Exemplo:
TerÃamos um conjunto P = {<a,b>;<b,c>;<a,c>}. Suponha um grafo G que tenha sido construÃdo usando a estratégia pedida. Então não existe nenhum nó que tenha grau de entrada e saÃda maior que 1. Ou seja, alguem que seja menor que alguem e ao mesmo tempo maior que alguem. Até porque se houvesse então haveria pelo menos um par ganho por transitividade.
Agora vamos adicionar um novo nó X em G. Vamos fazer o seguinte para mantermos a propriedade de não haver transitividades:
- Seja Y alguem que tenha grau de entrada 0. Vamos adicionar a aresta <X,Y>.
- Seja Z alguem que tenha grau de saÃda 0. Vamos adicionar a aresta <X,Z>.
Em ambos os casos a propriedade é mantida e é usada a estratégia do algoritmo. Podemos repetir o raciocÃcio o quanto se quiser.
d) Vamos considerar como critério de eficiência o tamanho de P. Ou seja, vamos adotar uma estratégia que tente máximar o tamanho de P.
Temos n elementos e n-1 comparações a fazer. Nas n/2 comparações vamos tomar elementos não comparados com ninguem:
Se n for Ãmpar então fazemos uma comparação fugindo da regra e tentando ganhar um par. Por simplicidade doravante não vou mais considerar os casos Ãmpares. Ainda nos restam (n-2)/2 comparações.
Vamos agora pegar esses pares comparados e compara-los em par, sendo que comparando o menor de um par com o maior do outro par. Vamos repetindo essa idéia recursivamente.
e) Suponha que temos dois pares já comparados, e comparamos o seu menor e seu maior. No melhor caso teremos isso:
Na esquerda dois pares já comparados e uma nova comparação no meio, entre o menor de um e o maior do outro. Na direita temos um exemplo de arestas ganhas (em cinza) por transitividade. Nesse caso o ganho foi o máximo, de 3 arestas.
Suponha que temos dois grafos P e Q onde sabemos sua ordem total. Seja o elemento p o maior elemento de P. Seja o elemento q o menor elemento de Q. Se p > q, então nós vamos colocar uma aresta saindo de p para q, e vamos colocar por transitividade arestas de p para todos os elementos de Q. Ou seja, ganhamos por transitividade |Q|-1 arestas.
Be First to Comment