1.4 Programação de um computador

Otávio (O): J > L > N > I Isabella (I): T > O > R >

> M S > P

Pedro (P): I > J > L > M Joana (J): T > S > R > O

> N > P

Rodrigo (R): I > M > J > Laura (L): T > P > O > R

L > N > S

Sérgio (S): J > L > M > I Marina (M): P > R > S >

> N T > O

Thiago (T): M > J > I > L Natália (N): R > O > S >

> N P > T

Resultado: Os pares formados quando os homens propõem são: O – N, P – L, R – I, S – J, T – M. Os pares formados quando as mulheres propõem são: I – R, J – T, L – P, M – S, N – O. Consequentemente, não há um emparelhamento ótimo para todos, porque as alocações diferem e os pares Sérgio–Joana e Thiago– Marina são trocados.

1.4 Programação de um computador

Esta seção é voltada ao leitor interessado na programação do algoritmo Gale-Shapley em um computador; em outras palavras, como o mesmo pode ser implementado em uma linguagem de programação sequencial.

A importância da noção de algoritmo e de ter algoritmos para resolver problemas é que tais métodos são totalmente especificados em uma sequência de passos ou etapas, não deixando nenhum procedimento ou escolha a critério de quem os utiliza. Desse modo, primeiramente, tais procedimentos podem ser delegados a máquinas que trabalham muito rápido, mas sem nenhuma criatividade: os computadores.

Em segundo lugar, se duas pessoas seguirem o mesmo algoritmo para resolver um mesmo problema (com as mesmas informações), elas deverão obter o mesmo resultado, ainda que trabalhem de modo independente. (Algoritmos podem, sim, utilizar fontes aleatórias de informação, com fins de simular um mesmo experimento ou montagem muitas vezes e variadamente, mas produzirão o mesmo resultado toda vez que a mesma sequência de informação for utilizada.) O resultado obtido com o algoritmo, por sua vez, é definido pelo método e passível de estudo formal, como vimos ao identificar a otimalidade de Gale-Shapley para os agentes proponentes, o que não seria possível para uma escolha arbitrária de emparelhamento estável, nem demonstrável sem conhecer o funcionamento do método.

A principal diferença desta seção em relação à apresentação anterior, que já é "procedural", consiste na representação apropriada das informações no computador, mas, fazemos, também, uma pequena modificação no procedimento em que, antes, as mulheres avaliavam todas as propostas recebidas, inclusive aquela selecionada na rodada anterior, enquanto agora avaliarão cada proposta assim que for recebida. Essa alteração pode diminuir o número de rodadas ou antecipar a rodada de rejeição para cada homem, mas mantém o mesmo resultado.

Utilizamos alguns raciocínios e estruturas presentes em Knuth (1997), especialmente sua Aula 6. Porém, não o seguimos totalmente; utilizamos alguma redundância e trabalhamos com nossa hipótese atual de um mesmo número de homens e mulheres, digamos n.

O programa representará tanto os homens como as mulheres como números de 1 a n. A primeira tarefa é ler e armazenar suas listas de preferência. Começamos com uma matriz ListasHomens, cuja posição (i,j) registra a j-ésima opção do homem i em ordem decrescente. Desse modo, ListasHomens é semelhante à listagem que fizemos no texto:

para i de 1 a n:

para j de 1 a n:

leia k (identificação da mulher);

armazene k em ListasHomens (i,j).

As listas das mulheres serão armazenadas de um modo diferente, para facilitar a comparação das propostas recebidas: a posição (i,j) da matriz NotasMulheres identificará, para a mulher i, qual é a "nota" do homem j em sua lista, de modo que o primeiro homem tem nota n o segundo tem nota n – 1 e assim por diante, até o último, que tem nota 1. Observe que os homens mais preferidos têm notas mais altas. Essa lista requer cuidado em seu carregamento, a partir das listas, como feitas nos exemplos:

para i de 1 a n:

para k de 1 a n:

leia j (identificação do homem);

armazene n + 1 – k em NotasMulheres (i,j).

Agora precisamos criar um registro de onde está a moldura nas listas dos homens e das mulheres. Para os homens, registraremos a posição da moldura, mas, para as mulheres, registraremos o conteúdo da moldura. Usaremos, para começar, o número 0, mas pode ser necessário adotar outro número ou símbolo, dependendo do uso dos índices acima na linguagem de programação. Também precisamos saber quem está rejeitado ou sem propostas.

para i de 1 a n:

armazene 0 em MoldurasHomens(i) e NoivosMulheres(i);

armazene SIM em HomensLivres(i) e MulheresLivres(i);

Agora, fazemos com que cada homem realize sua proposta e seja avaliado pela mulher eleita, que pode ou não o substituir em detrimento do anterior (se houver). Ela fará isso em uma cadeia de condicionais "se–caso contrário":

(*) para i de 1 a n:

se HomensLivres(i) = SIM então:

aumente MoldurasHomens(i) uma unidade;

armazene MoldurasHomens(i) em j;

se MulheresLivres(j) = SIM então:

armazene i em NoivosMulheres(j)

armazene NÃO em MulheresLivres(j) e HomensLivres(i).

caso contrário, se

NotasMulheres (j,i) > Notas Mulheres(j), NoivosMulheres(j)

então:

armazene SIM em

HomensLivres(NoivosMulheres(j);

armazene NÃO em HomensLivres(i);

armazene i em NoivosMulheres(j).

Devemos verificar se algum homem foi rejeitado, o que requer uma nova rodada de propostas:

para i de 1 a n:

se HomensLivres(i) = SIM então:

retorne ao ponto (*).

No caso de um número distinto de homens e mulheres, veremos, futuramente, que se deve incluir nessa condição o teste de ainda não ter percorrido toda a sua lista de preferência.

Finalmente, podemos imprimir os casais formados:

para i de 1 a n:

escreva "i casado com MoldurasHomens(i)".

Uma preocupação moderna com algoritmos é sobre sua eficiência, isto é, o número de passos ou operações que o algoritmo requer que o computador faça, especialmente em função do tamanho do problema especificado, aqui, o número n de homens ou mulheres. Mesmo com os últimos avanços da tecnologia, preocupações com o tempo de execução e com o espaço necessário (tamanho da memória) são cotidianos, porque as dimensões dos problemas a serem tratados na prática também crescem rapidamente.

Informações mais apropriadas sobre eficiência, sua definição e seu cálculo, constituem um tema da ciência da computação e podem ser inicialmente obtidas em Knuth (1997) e Gusfield; Irving (1989). Aqui, relatamos apenas que Gale-Shapley, na forma desta seção, pode requerer passos da ordem de até 2 n para terminar; por "ordem", aqui, entende-se que esse número de passos, em função de n, é um polinômio de segundo grau ou é limitado por um tal polinômio; para valores muito grandes de n, o termo de segundo grau domina os demais. Note que também a entrada de dados, isto é, a leitura das listas de preferência, já requer 2 2 n operações de leitura simples; então, é significativo que o procedimento em si não supere essa ordem.