Ata – Aula do dia 21/03/2003
Redatora: Daniele Constant Guimarães – ra: 012108

Tópicos:

1. Introdução
    1.1. Definições
2. Mínimo e Máximo
    2.1. Descrição
    2.2. Algoritmos
    2.3. Discussão em aula
3. Seleção do i-ésimo em tempo esperado linear
    3.1. Descrição
    3.2. Algoritmo
    3.3. Discussão em aula
4. Seleção do i-ésimo em tempo linear
    4.1. Descrição
    4.2. Análise do tempo de execução
    4.3. Discussão em aula
5. Conclusões

    1.1. Definições

• i-ésima estatística de ordem de um conjunto de “n” elementos: é o i-ésimo menor elemento.
• Mediana: é o ponto médio de um conjunto. Quando “n” é ímpar, a mediana é única, ocorrendo em i = (n + 1)/2. Quando “n” é par, existem duas medianas, i = piso((n + 1)/2) (mediana inferior) e i = teto((n + 1)/2) (mediana superior).
• O problema a ser tratado é o problema de seleção da i-ésima estatística de ordem de um conjunto de “n” elementos distintos. Esse problema pode ser formalmente descrito como:

        Entrada: um conjunto A de n números (distintos) e um número i, com 1 <= i <= n.
        Saída: o elemento x "pertencente a" A que é maior que exatamente i – 1 outros elementos de A.
• O problema de seleção pode ser resolvido no tempo O(n lg n), usando o heapsort e em seguida indexando o i-ésimo elemento do arranjo de saída. Porém, existem algoritmos que fazem isso mais rápido. São eles:
• Selecionar o mínimo e o máximo de um conjunto de elementos
• Seleção geral usando um algoritmo com tempo esperado linear no caso médio
• Seleção geral usando um algoritmo com tempo linear no pior caso

    2.1. Descrição

 Para determinar o mínimo (máximo) de um conjunto, deve-se examinar cada elemento do conjunto isoladamente e manter o controle do mínimo (máximo) visto até agora. O limite superior é de n – 1 comparações. Pode-se encontrar o mínimo e o máximo simultaneamente, localizando ambos independentemente usando n – 1 comparações para cada um deles, o que resulta em 2n – 2 comparações. Para diminuir o número de comparações para 3*piso(n/2) basta, ao invés de comparar cada elemento com o mínimo e o máximo atuais, comparar os elementos de entrada aos pares e depois comparar o maior como o máximo atual e o mínimo com o mínimo atual.

A definição dos valores iniciais para o mínimo e o máximo atuais depende do fato de n ser par ou ímpar. Se n for ímpar, tanto o mínimo quanto o máximo recebem o valor do primeiro elemento do arranjo de entrada. Se for par, primeiro deve-se comparar os dois primeiros valores do arranjo. O menor é atribuído ao mínimo e o maior ao máximo.
 

    2.3. Discussão em aula

O primeiro item a ser abordado pelo professor foi: Dado um vetor, como se calcula o mínimo e o máximo? O tempo de execução para calcular o mínimo e o máximo é O(n) para cada um ou para os dois juntos. Quando o elemento é mínimo ele não pode ser máximo, então, deve-se colocar um “else” no algoritmo (MINIMUM acima) e para encontrá-los, basta percorrer o vetor armazenando o menor e/ou o maior valor.

    3.1. Descrição

Para resolver o problema de seleção geral, é apresentado um algoritmo de dividir e conquistar aleatório (baseado no algoritmo quicksort – Capítulo 7). Ele particiona o arranjo de entrada recursivamente, mas só executa um lado da partição (onde está o elemento que procurado). Isso faz com que o tempo de execução seja Theta(n). No pior caso, quando a paritição é sempre feita em torno do maior elemento restante, o tempo de execução do algoritmo é de Theta(n^2).
 

RANDOMIZED-SELECT(A, p, r, i)
1 if p == r then
2         return A[p]
3 q = RANDOMIZED-PARTITION(A, p, r)
4 r = q – p + 1
5 if i == k then //o valor pivô é a resposta
6          return A[q]
7 elseif i < k then
8          return RANDOMIZED-SELECT(A, p, q – 1, i)
9 else  return RANDOMIZED-SELECT(A, q + 1, r, i – k)

    3.3. Discussão em aula

Após uma série de perguntas e respostas, que foi iniciada com a pergunta “Como é a seleção do i-ésimo em tempo esperado linear?”, o que se pôde concluir sobre a seleção do i-ésimo em tempo esperado linear foi que:

• O livro usa uma abordagem de dividir e conquistar parecido com a que é usada no Quicksort. Como ele fixa o lado em que o “i” está, não é necessário verificar os dois lados da partição. A seleção é feita para o i-ésimo menor elemento, onde o 1º menor é o mínimo.
• O i-ésimo menor elemento é maior que exatamente “i-1” elementos.
• O livro não trata quando existe uma igualdade entre os valores do arranjo, mas ele afirma que a abordagem continua válida mesmo para esse caso. Nesse ponto o professor comentou que deveríamos confiar no autor e que, nesse caso, a afirmação de que o i-ésimo menor elemento é maior que exatamente “i-1” elementos está correta.

O aluno continuou, descrevendo o funcionamento do algoritmo RANDOMIZED-SELECT. Este algoritmo cria uma rotina que particiona o vetor (em duas partes). Para cada partição é gerado um pivô. Em seguida, ele compara para ver se o pivô é o i-ésimo. Se for o algoritmo termina e ele retorna o elemento daquela posição. Senão, ele diz se o elemento está do lado de baixo da partição ou do lado de cima e chama a rotina recursivamente. Nesse ponto, foram feitos alguns comentários sobre o RANDOMIZED-PARTITION, que é usado pelo RANDOMIZED-SELECT. Foi dito que o algoritmo RANDOMIZED-PARTITION foi comentado no capítulo de quicksort e retorna o pivô. A diferença entre ele e a versão 1 (PARTITION), é que a versão randômica escolhe aleatoriamente o pivô.

Depois dos comentários sobre o RANDOMIZED-PARTITION, o professor fez um resumo sobre o funcionamento do RANDOMIZED-SELECT: "ele também escolhe aleatoriamente o pivô, particiona aí ele vê quantos estão abaixo e quantos estão acima. Caso seja o elemento que ele quer então retorna, senão ele sabe em que região ele vai. Se for para o lado de cima da partição, ele troca o “i”".

Antes de passar para o próximo tópico, o professor ainda pergunta qual o tempo esperado e o tempo no pior caso para o algoritmo (cujas respostas são O(n) e O(n^2) respectivamente) e comenta que a análise sobre o tempo de execução desse algoritmo deve ser pulada.

    4.1. Descrição

O algoritmo de seleção com tempo de execução O(n) no pior caso seleciona o elemento desejado particionando recursivamente o arranjo de entrada. Essa partição deve garantir uma boa divisão desse arranjo.

O algoritmo SELECT determina o i-ésimo menor elemento de um arranjo de entrada com n > 1 elementos, executando 5 etapas:

1. Dividir os n elementos do arranjo de entrada em piso(n/5) grupos de 5 elementos cada e no máximo 1 grupo com menos de 5 elementos.
2. Encontrar a mediana dos teto(n/5) grupos, usando primeiro a ordenação por inserção dos elementos do grupo para em seguida, escolher a mediana dos grupos.
3. Usar o SELECT recursivamente para encontrar a mediana x das teto(n/5) medianas encontradas.
4. Particionar o arranjo de entrada em torno da mediana de medianas x. Seja k uma unidade maior que o número de elementos no lado de baixo da partição, de forma que x seja o k-ésimo menor elemento e existam n – k elementos no alto da partição.
5. Se i == k, retorne k. Caso contrário, usar o SELECT recursivamente para encontrar o i-ésimo menor elemento no lado baixo da partição, se i <= k, ou então o (i – k)-ésimo menor elemento no lado alto da partição, se i > k.

Primeiro deve-se determinar um limite inferior sobre o número de elementos que são maiores que o elemento de particionamento x. Como pelo menos metade das medianas encontradas é maior que a mediana das medianas x, temos que, pelo menos metade dos teto(n/5) grupos contribui com 3 elementos maiores que x, exceto pelo único grupo que tem menos de 5 elementos quando n não divide 5 exatamente e pelo único grupo que contém x. Logo, o número de elementos maiores que x é pelo menos 3( teto(1/2 * teto(n/5)) – 2) >= 3n/10 – 6. De modo semelhante, o número de elementos menores que x é no mínimo 3n/10 – 6.

Assim sendo, no pior caso, SELECT é chamado recursivamente sobre no máximo 7n/10 + 6 elementos.

A recorrência para o tempo de execução é:

Pelo método da substituição é O(n).

OBS: o número 140 foi calculado na página 154 do livro.
 

O professor iniciou esse tópico pedindo que o aluno falasse sobre a seleção do i-ésimo em tempo linear no pior caso, que já é linear. O aluno inicia falando que o algoritmo pega o arranjo, divide em sub-arranjos, encontra a mediana de cada sub-arranjo e a mediana das medianas. Nesse ponto o professor pergunta se o objetivo então é encontrar a mediana e depois comenta que a mediana é quando o “i” é mais ou menos “n/2”.

Iniciou-se então, uma discussão sobre o algoritmo SELECT. O que se pode concluir, é que, o algoritmo usa a mediana para melhorar o posicionamento do pivô. E que a possibilidade do pivô ser ruim, causa “problemas” no algoritmo, pois a partição pode ficar desbalanceada. O autor mostra uma técnica para balancear as partições, fazendo com que a área alvo seja menor. Portanto, “nada muda. O particionamento fica igual. A única coisa que muda é que o pivô vai mudar”, conclui o professor. O aluno continuou dizendo como o algoritmo funciona: Ele divide o arranjo “n” em “n/5” subarranjos, acha as medianas e a mediana das medianas e com isso chega em uma região menor e nessa região procura a posição desejada. Isso gerou uma discussão sobre o tamanho dos grupos: porque divide em grupos de 5, e não de 3, ou de 7 ou um número ímpar?  Como essa questão foi pedida em exercício a reposta ficou para a aula seguinte.

Visto o funcionamento geral do algoritmo, foi levantada uma dúvida sobre a etapa 3 do mesmo: “ela foi definida corretamente? Ele (o autor) fala: “usar SELECT recursivamente para encontrar a mediana x das teto(n/5) medianas”. A dúvida é: ele (o algoritmo) vai dividir em grupos de medianas de tamanho 5 cada um. E aí depois ele quer encontrar a mediana desses grupos. A questão é que ele chama recursivamente o SELECT. E pelo que entendi o SELECT é o processo todo”. Depois de uma longa discussão, chegou-se a conclusão que a dúvida foi gerada porque o algoritmo não foi escrito. Para resolver esse problema, o professor sugeriu escrever o algoritmo. Cada etapa do algoritmo foi escrita por um aluno. No final é apresentada uma versão final para ele.
 

Etapa 1: divide o conjunto em grupos

Importante: não esquecer os parâmetros.
Sugestões:

Colocar um intervalo na lista de parâmetros para a chamada recursiva.

Colocar um “for”

Fazer a divisão dos grupos: são “teto(n/5)” grupos

Colocar o teto para pegar o último grupo

SELECT (A, p, r, i)
1 n = r - p + 1 //número de elementos
2 q = teto(n/5) //número de grupos
3 for j = 1 to q do

Etapa 2: dividir para conquistar

Dúvidas e sugestões:
• Só chama a subrotina: não precisa colocar o código. Como não existe essa subrotina, basta “inventar” uma chamada.
• Na primeira etapa o algoritmo divide o conjunto em grupos. Cada grupo tem 5 elementos. Quando ele fala em encontrar a mediana, ele vai ordenar os conjuntos para depois achar a mediana ou somente pega a mediana sem mexer nos conjuntos? Essa pergunta gerou uma pequena discussão e a conclusão foi que o algoritmo ordena o conjunto para depois pegar a mediana. Ele vai usar essa ordenação mais tarde.
• Qual a diferença para ordenar 5 elementos com insertion sort ou com qualquer outro algoritmo? Não é importante usar o insertion sort, pois, como ele ordena um arranjo de 5 elementos, a ordem é O(5), que é constante. O que deve ser retornado é a mediana.
• OBS feita pelo professor: O nome de uma função tem que ser o que ela retorna. Já o procedimento pode ser um verbo.
• Vai ter que usar um vetor auxiliar de tamanho “q”, para guardar as medianas e não mexer no vetor original.
• O último grupo pode dar problema, porque ele pode ter menos elementos. Para resolver esse problema, deve-se usar o mínimo para não passar.

4 B[j] = MEDIANA (A, 5(j-1) + p, min (5j + p –1, r))

           Importante: colocar a condição de parada (essa condição de parada será acrescentada na versão final).
           Sugestões:

• Usa o SELECT recursivamente para achar a mediana de “B”
 
5 x = SELECT (B, 1, q, piso(q/2))

Etapa 4: particionar o arranjo de entrada em torno da mediana de medianas x.

Houve uma discussão sobre o que o SELECT retorna. Índice ou o i-ésimo menor elemento? A conclusão foi que ele retorna o i-ésimo menor elemento. Além disso, ficou a dúvida, sobre o valor de x. Foi dito que x não é o índice e sim o elemento do arranjo.
Sugestões:

O índice deve ser guardado para saber qual o índice do elemento em “A”.

Modificar o algoritmo PARTITION da pág 118. Modificações sugeridas:

Tirar as linhas 1 (o “x” deve ser passado como parâmetro e não usar o valor de “A[r]”)

Tirar a linha 7

Mudar a linha 3 para: for j = p to r

6 q1 = PARTITION1 (A, p, r, x)

Etapa 5: particionar o arranjo de entrada em torno da mediana de medianas x.

Discussão: Qual o valor de “k”? “q1” é o “k” direto? Pela definição de “k” na página 153 do livro, temos que “k” é uma unidade maior que o número de elementos no lado baixo da partição. O número de elementos no lado baixo da partição é “q1–p”.
Dúvida: cada SELECT retorna uma coisa diferente? Sim

7 k = q1 – p + 1
8 if i == k then
9        return x
10 elseif i < k then
11      return SELECT(A, p, q1-1, r)
12 else return SELECT(A, q1 + 1, r, i - k)

Após uma breve discussão sobre o algoritmo encontrado (se ele realmente funciona ou não) e sobre o PARTITION, chegou-se à conclusão que ele teria que ser bastante modificado. A modificação seria: fazer uma busca no início do PARTITION para saber qual o índice de “x”, trocá-lo com o último e continuar. Nesse ponto surgiu uma dúvida: será que não vai aumentar a complexidade? Segundo o professor, não vai aumentar a complexidade porque o PARTITION já leva O(n), e a mudança também vai levar O(n). Vai dobrar a busca total. Ao invés de passar uma vez, vai passar 2.

Para “limpar” o código, foi sugerido que se fizesse uma pesquisa do lado de fora e depois mandar o índice para o PARTITION, uma vez que a alteração no PARTITION foi feita para receber o elemento ao invés do índice.
 

SELECT (A, p, r ,i)
1 if p == r  then
2         return A[p]
3 else
4         n = teto ((r – p + 1)/5) //n passa a ser o tamanho de B
5         for j = 1 to n do
6             B[j] = MEDIANA (A, 5(j – 1) + p, min (5j + p – 1, r))
7         x = SELECT (B, 1, n, teto (n/2))
8         j = busca (A, p, r, x)
9         troca A[j] com A[r]
10       q = PARTITION (A, p, r)
11        k = q – p + 1
12        if i == k then
13           return x
14        elseif i < k then
15           return SELECT (A, p, q-1, i)
16        else return SELECT (A, q+1, r, i-k)

Na verdade, a linha 3 (q = RANDOMIZED-PARTITION (A, p, r)) do algoritmo da página 149 do livro foi substituída pelas linhas 4 a 10.

Para mostrar que esse algoritmo é linear, basta mostrar sua recorrência. A análise feita para a seleção em tempo linear no pior caso, diz que para esse particionamento, com esse pivô, ele garante que qualquer um dos lados da partição não fica com menor que 3/10, ou seja, 30%. Depois ele monta a recorrência colocando o pior caso que é 7/10. Como 7/10 + 1/5 < 1, é linear.

Dúvida levantada por um aluno: de onde aparece o “c” na resolução da recorrência? (Segunda linha da página 154).
Resposta do professor: quando ele faz teto(n/5), ele arredonda pra cima. Na linha de baixo ele substitui pro n/5 + 1, porque quando arredonda pra cima, você soma uma unidade, e esse “+1” multiplicado por “c” deu origem a esse “c” que aparece.

Foram abordados todos os tópicos previstos. O ponto alto da aula ocorreu com a criação do algoritmo SELECT pelos alunos, a partir dos passos citados pelo autor no tópico “Seleção do i-ésimo em tempo linear”.