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:

Grafo 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:

Primeiro Passo

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:

Primeiro Exemplo

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.