Aula xx — Problemas, Instâncias e Algoritmos

O que você vai aprender

Distinguir problema, instância e algoritmo usando o problema de ordenação.

Por que você precisa saber isso

Essa distinção separa três coisas que costumam ser confundidas: o que precisa ser resolvido, quais dados serão processados e qual procedimento produz a saída esperada.

Cai na prova?

Não. É conteúdo conceitual e as provas anteriores não cobram definições.

Símbolos

A, sequência de números recebida como entrada.
A′, sequência com os mesmos números de A, em ordem crescente.
n, quantidade de elementos da sequência.
j, posição do elemento que está sendo inserido.
v, o valor desse elemento, guardado à parte.
i, posição da carta que está sendo comparada com v.

Um problema define a entrada e a saída esperadas, sem dizer como a solução será obtida.

No problema de ordenação, a entrada é uma sequência A de números e a saída é uma permutação A′ de A em ordem crescente. Permutação quer dizer que A′ tem exatamente os mesmos elementos de A, apenas em outra ordem.

Cormen enuncia assim: entrada, uma sequência de n números; saída, uma permutação da sequência de entrada em ordem não decrescente.

Uma instância é uma entrada específica do problema.

Para A = [20, 6, 10, 1], a saída esperada é A′ = [1, 6, 10, 20]. O problema é geral, ordenar uma sequência de números. A instância é particular, ordenar [20, 6, 10, 1].

Cormen define instância como uma entrada que satisfaz as restrições do problema e é o que se precisa para calcular uma solução.

O algoritmo descreve os passos que transformam a entrada na saída esperada.

Imagine as cartas viradas para cima sobre a mesa, em n posições numeradas de 1 a n, da esquerda para a direita. A mesa inteira é o A. A[k] quer dizer a carta que está na posição k. Aqui n = 4 e a mesa começa com 20, 6, 10 e 1. Nenhuma posição é criada ou destruída durante o processo.

Dois sinais aparecem no pseudocódigo. A seta ← quer dizer recebe: o que está à direita é copiado para o que está à esquerda. O símbolo ∧ é o e lógico: as duas condições precisam ser verdadeiras ao mesmo tempo.

A posição 1 já está ordenada antes de qualquer coisa, porque uma carta sozinha nunca está fora de ordem. Por isso a primeira carta a mexer é a da posição 2, e é o que a linha 1 faz ao começar com j ← 2.

O pseudocódigo linha por linha

1. 1 for j ← 2, . . . , n do

   j é a posição da carta que será inserida nesta rodada. A linha manda repetir tudo o que está indentado abaixo dela com j = 2, depois 3, e assim por diante até n. Quando j passa de n não sobrou carta para inserir e o algoritmo acaba. Na mesa: cada valor de j é uma rodada, e a rodada trata da carta que está naquela posição.

2. 2 v ← A[j];

   A[j] é a carta que está na posição j. A linha copia esse valor para v. Na mesa: você levanta essa carta e a segura suspensa. A posição j deixa de ter dono e vira o lugar vazio. Guardar em v é o que torna seguro escrever por cima da posição j depois, na linha 5: o valor original está a salvo fora da mesa. Na primeira rodada, j = 2 e A[2] = 6, então v = 6.

3. 3 i ← j − 1;

   i é a posição da carta que será comparada com v. Ela começa em j − 1, a vizinha imediata à esquerda do lugar vazio. Guarde esta regra, ela vale do começo ao fim: o lugar vazio é sempre a posição i + 1. É por isso que as linhas 5 e 7 escrevem justamente em A[i + 1].

4. 4 while i > 0 ∧ A[i] > v do

   Duas perguntas de uma vez. i > 0 verifica se ainda existe carta à esquerda: a mesa começa na posição 1, então i = 0 significa que acabaram as cartas para comparar. A[i] > v verifica se a carta comparada é maior que a suspensa. Se as duas forem verdadeiras, executa as linhas 5 e 6 e volta a testar. Se qualquer uma falhar, o laço acaba e o algoritmo pula direto para a linha 7.

5. 5 A[i + 1] ← A[i];

   Copia a carta da posição i para a posição i + 1, que é o lugar vazio. Na mesa: a carta maior desliza uma casa para a direita. Nada é perdido, porque o destino estava vazio, e a posição i passa a ser o novo lugar vazio. Repare que a carta ocupa o buraco em vez de ir para uma posição nova.

6. 6 i ← i − 1;

   i anda uma casa para a esquerda, então a próxima carta a comparar é a anterior. Como o lugar vazio também andou uma casa para a esquerda na linha 5, continua valendo que o vazio é i + 1. Terminada esta linha, o laço volta ao teste da linha 4.

7. 7 A[i + 1] ← v;

   Esta linha está fora do while, ela só roda quando o teste da linha 4 falha. Nesse momento i + 1 é o lugar vazio e é exatamente ali que a carta suspensa deve ficar, seja porque a carta da posição i é menor ou igual a v, seja porque não há mais carta à esquerda. Na mesa: você baixa a carta no buraco. A mesa fica cheia de novo, as posições 1 até j estão ordenadas e o algoritmo volta à linha 1 com j + 1.

Para onde vai a carta que sai da frente

Não existe posição 5. A mesa tem n = 4 lugares do começo ao fim. Quem abre espaço é a linha 2: ao levantar a carta da posição j, essa posição fica vazia. Cada execução da linha 5 move uma carta para esse vazio e cria outro vazio uma casa à esquerda. O buraco caminha para a esquerda até parar no lugar onde v será baixada na linha 7.

Sem a linha 2 o algoritmo não funcionaria: a linha 5 escreveria por cima da carta que estava em A[j] e ela sumiria da mesa.

Quando nenhuma carta se move

Pode acontecer de o teste da linha 4 já falhar na primeira vez. É o caso de a carta levantada ser maior que a vizinha da esquerda, ou seja, já estar no lugar certo. Aí o laço não roda nenhuma vez, i continua valendo j − 1 e a linha 7 escreve em A[i + 1], que é o próprio A[j]. A carta desce de volta no lugar de onde saiu e a rodada acaba sem deslocar ninguém.

Os dois laços

São dois laços, um dentro do outro. O laço externo é a linha 1 e o corpo dele são as linhas 2 a 7: uma volta por carta a inserir, com j de 2 até n. O laço interno é a linha 4 e o corpo dele são as linhas 5 e 6, que estão mais indentadas: dentro de uma mesma rodada ele desliza para a direita, uma a uma, todas as cartas maiores que v.

Resumo dos símbolos: n é a quantidade de posições da mesa; A[k] é a carta da posição k; j é a posição da carta levantada nesta rodada; v é essa carta enquanto está suspensa; i é a posição da carta comparada com v; e i + 1 é sempre o lugar vazio.

O que muda ao fim de cada rodada

A parte ordenada cresce exatamente uma posição. Antes da rodada, A[1..j − 1] está em ordem; depois da linha 7, A[1..j] está em ordem. Quando j chega a n e a rodada termina, A[1..n] está ordenado e não sobrou nada a fazer.

Nas próximas seções o mesmo procedimento aparece em fluxograma, pseudocódigo e simulador. No simulador cada clique executa uma linha e mostra o resultado. Faça a conta de cabeça antes de avançar e confira se bate.

O mesmo algoritmo em notação de fluxograma. Vale a leitura das formas: o oval marca começo e fim, o retângulo é uma ação, o losango é uma pergunta com saída sim e não, e a seta indica para onde ir depois.

A primeira ação define n, que é a quantidade de elementos da sequência recebida. Na instância A = [20, 6, 10, 1], n vale 4. Depois j começa em 2, porque a posição 1 já conta como parte ordenada.

São duas perguntas. A de cima, j ≤ n, controla o laço externo e quer saber se ainda sobrou carta a inserir. A de baixo, i > 0 e A[i] > v, controla o laço interno e quer saber duas coisas: se ainda existe carta à esquerda para comparar, i > 0, e se essa carta é maior que v, caso em que ela desliza para o lugar vazio.

O simulador executa o pseudocódigo do slide sobre a instância A = [20, 6, 10, 1], uma linha por clique. A linha em execução fica destacada no código, as células mostram a sequência naquele instante e o texto abaixo explica o que a linha fez e por quê. Avançar executa a próxima linha, Retroceder volta ao estado anterior.

Repare no vaivém entre os dois laços. A linha 1 é o laço externo, uma volta por carta a inserir, com j de 2 até n, que aqui vale 4. As linhas 4, 5 e 6 são o laço interno: enquanto a condição da linha 4 for verdadeira, o código fica girando entre 4, 5 e 6, deslizando cartas para a direita. Quando ela fica falsa, o código sai para a linha 7, baixa v no lugar vazio e volta para a linha 1.

1  for j ← 2, . . . , n do
2      v ← A[j];
3      i ← j − 1;
4      while i > 0 ∧ A[i] > v do
5          A[i + 1] ← A[i];
6          i ← i − 1;
7      A[i + 1] ← v;

INSERTION-SORT(A)

1  for j = 2 to A.comprimento
2      chave = A[j]
3      // Inserir A[j] na sequência ordenada A[1 .. j − 1].
4      i = j − 1
5      while i > 0 e A[i] > chave
6          A[i + 1] = A[i]
7          i = i − 1
8      A[i + 1] = chave

Mesmo procedimento, notação diferente: o slide usa v, n e ←; o Cormen usa chave, A.comprimento e =. O Cormen ainda nomeia o procedimento e inclui um comentário explicativo.

Problema é a definição da entrada e da saída esperadas.
Instância é uma entrada específica do problema.
Algoritmo é a sequência de passos que transforma uma instância válida na saída esperada.

Considere a sequência A = [7, 2, 5].

1. Qual é o problema?

Ver gabarito

Ordenar uma sequência de números.

2. Qual é a instância?

Ver gabarito

A = [7, 2, 5].

3. Qual é a saída esperada?

Ver gabarito

A′ = [2, 5, 7].