Usuário:Renato Madeira/Testes

Origem: Wikipédia, a enciclopédia livre.

Problema do Emparelhamento Estável[editar | editar código-fonte]

O Problema do Emparelhamento Estável ("Stable Matching Problem") possui diversas aplicações em nosso cotidiano. Algumas das principais são os processos seletivos para universidades, o problema da estabilidade do casamento ("stable marriage problem"), a seleção de estagiários e a escolha de colegas de quarto ("roomate problem").

Os pesquisadores americanos D. Gale (1921-2008) e L. S. Shapley (1923- ) foram os primeiros a desenvolver um algoritmo eficiente para resolver esses problemas. Esse algoritmo foi apresentado em um artigo da revista American Mathematical Monthly, Vol. 69, No. 1 de janeiro de 1962[1], que abordava principalmente os processos de admissão em universidades e o problema da estabilidade do casamento ("stable marriage problem"). Esse trabalho, e seus desenvolvimentos posteriores, inclusive, valeram a L. S. Shapley e A. E. Roth o prêmio Nobel em Economia no ano de 2012 .

Será apresentado um resumo das ideias constantes no artigo citado acima e como essa metodologia poderia ser aplicada ano processo seletivo para as universidades no Brasil, o Sisu.

Processo Seletivo para Universidades[editar | editar código-fonte]


Vamos supor que um determinado estudante foi aceito pela universidade A e encontra-se na lista de espera da universidade B (que ele prefere em relação à A). Caso por algum motivo, o estudante venha a ser chamado pela universidade B, ele provavelmente abandonaria a universidade A para estudar na universidade B, e deixaria A com uma vaga ociosa. Isso levaria A a também chamar algum candidato de sua lista de espera, e deixaria uma vaga ociosa em alguma outra universidade. Essa situação poderia fazer com que terminássemos o processo seletivo com vagas ociosas em algumas universidades e alunos interessados nelas, mas que não foram aceitos em nenhuma universidade.


O objetivo do algoritmo que será apresentado a seguir é distribuir os candidatos entre as vagas de forma a satisfazer ambos os grupos, candidatos e universidades.

Considere um processo seletivo no qual n candidatos devem ser designados para m universidades, onde é a quantidade de vagas na i-ésima universidade. Cada candidato deve listar as universidades por ordem de preferência (sem empates), excluindo apenas aquelas em que não deseja estudar em hipótese alguma. Da mesma forma, cada universidade deve listar os candidatos (dentre os que aplicaram para ela), excluindo apenas aqueles estudantes que não admitiria de forma alguma (essa lista poderia ser baseada nas notas de um exame de seleção, onde as universidades poderiam atribuir pesos diferentes às diversas matérias e excluir os candidatos que estivessem abaixo da nota mínima estipulada).

Considere um processo seletivo em que haja dois candidatos e e duas universidades A e B com uma vaga cada uma. O candidato prefere a universidade A e o candidato prefere a universidade B, mas a universidade A prefere o candidato e a universidade B prefere o candidato . Nesse caso, não há uma distribuição que satisfaça todas as preferências. Considerando que as universidades existem para atender os estudantes, e não o contrário, vamos designar para universidade A e para a universidade B. Assim, será adotada como premissa que, quando outros aspectos forem iguais, o desejo dos candidatos terá prioridade em relação ao das universidades.

O ponto central é obter uma distribuição onde não ocorra a situação definida a seguir.


DEFINIÇÃO: Uma designação de candidatos para universidades é considerada instável se há dois candidatos e designados para as universidades A e B, respectivamente, embora prefira a universidade A à universidade B, e a universidade A prefira o candidato ao candidato .


Supondo que a situação definida acima ocorra, o candidato tentaria transferir-se para a universidade A, que o admitiria em detrimento do candidato . Essa mudança seria vantajosa tanto para quanto para A. Dessa forma, a distribuição original é considerada instável, pois pode ser subvertida por e A agindo juntos, de maneira que ambos sejam beneficiados.

A condição essencial que deve ser satisfeita para uma designação de candidatos para universidades é que ela não tenha instabilidades. Entretanto, não sabemos se é sempre possível obter uma designação sem instabilidades (ou seja, um "emparelhamento estável") para qualquer combinação de candidatos universidades e preferências.

Por enquanto, vamos assumir que existam soluções estáveis e analisar dentre essas soluções qual escolher, ou seja, qual delas é a "melhor", tendo em vista a premissa estabelecida de que o desejo dos candidatos têm prioridade em relação ao das universidades. A definição a seguir estabelece a condição para que uma designação seja considerada "ótima".

DEFINIÇÃO: Um emparelhamento estável é considerado ótimo se cada candidato está tão satisfeito quanto em qualquer outro emparelhamento estável.

Da mesma forma que os emparelhamentos estáveis, não é possível afirmar que haja uma designação ótima, mas, assumindo que ela exista, a designação ótima será única. Supondo que houvessem duas designações ótimas distintas e lembrando que na lista de preferências não há empates, então pelo menos um dos candidatos estaria mais satisfeito em uma das designações do que na outra e, portanto, uma delas não seria ótima (de acordo com a definição acima).

Assim, se conseguirmos garantir a existência de um emparelhamento estável e ótimo, teremos a certeza de que essa solução é única.

Problema do Casamento Estável (Stable Marriage Problem)[editar | editar código-fonte]

A fim de analisar as questões de existência, vamos estudar um problema mais simples: o Problema do Casamento Estável. Esse problema consiste tentar casar de maneira satisfatória as pessoas de um grupo de n homens e n mulheres, onde cada uma das pessoas deve classificar todas as do sexo oposto por ordem de preferência para o casamento. Neste caso, um emparelhamento será dito instável se houver um homem e uma mulher que não estão casados, mas preferem um ao outro a seus atuais parceiros.

TEOREMA: Sempre existe um conjunto de casamentos estáveis.

Demonstração:
Primeira parte: Determinação dos casais
O teorema será provado apresentando-se um método para encontrar o emparelhamento estável. Inicialmente, cada homem propõe casamento à sua mulher favorita. Cada mulher rejeita todas as propostas que recebeu,exceto a sua favorita. Os casais formados são então considerados noivos. Na segunda etapa, os homens que foram rejeitados propõem casamento a sua próxima escolha. Cada mulher então escolhe o seu favorito entre os novos proponentes e seu noivo. O favorito torna-se então (ou permanece sendo) seu noivo. Esse procedimento então continua sendo repetido. Os homens rejeitados no segundo estágio propõem casamento à sua próxima escolha e as mulheres escolhem para noivo o melhor entre os novos proponentes e seu noivo. Em algum momento (não mais do que n2 estágios), todas as mulheres terão recebido propostas, pois se alguma mulher não recebeu proposta, ela não está noiva e ainda há homens disponíveis efetuando propostas. Além disso, os homens não podem propor casamento à mesma mulher duas vezes. Assim, que a última mulher recebeu sua proposta, o procedimento é encerrado, e cada mulher deve então casar-se com seu noivo. Note que como todas as mulheres recebem propostas, todas ficam noivas, pois uma mulher só troca seu noivo por outro melhor.
Segunda parte: O conjunto de casamentos assim obtido é estável
Suponha que um homem H e uma mulher M não estão casados, mas H prefere M à sua mulher.Então em algum momento H propôs a M e em algum momento foi rejeitado em favor de alguém que M preferia. Dessa forma, M prefere seu marido a H e, não há instabilidade.

Observe que o procedimento acima funciona de maneira similar quando a quantidade de homens e mulheres não é a mesma. No caso de haver mais mulheres do que homens, o procedimento termina assim que todas as mulheres ficam noivas. No caso de haver mais homens que mulheres, o procedimento termina assim que todos os homens ou estão noivos ou foram rejeitados por todas as mulheres.

O procedimento descrito no qual os homens propõem casamento às mulheres resulta em uma solução ótima para os homens. Adotando um procedimento análogo no qual as mulheres é que propõem casamento aos homens, a solução é ótima para as mulheres. As soluções obtidas nesses dois procedimentos somente serão iguais quando houver um único conjunto de casamentos estáveis.

A fim de ilustrar a aplicação do procedimento descrito acima, foi desenvolvido um código na linguagem Python para a solução do Problema dos Casamentos Estáveis[2].

De volta ao Processo Seletivo para Universidades[editar | editar código-fonte]

Vamos adequar o procedimento descrito para o Problema dos Casamentos Estáveis ao Processo Seletivo para Universidades. Por comodidade, vamos assumir que se uma universidade não está disposta a aceitar um estudante em hipótese alguma (por exemplo, porque ele não atingiu a nota mínima no exame de admissão), então ele não pode se candidatar para essa universidade.
Inicialmente, todos estudantes se candidatam para sua primeira escolha. Cada uma das universidades inclui em sua lista de espera os candidatos com a melhor classificação limitado ao seu número de vagas e rejeita os outros. Os estudantes rejeitados se candidatam à sua segunda opção e as universidades incluem em sua lista de espera os candidatos com melhor classificação limitado ao número de vagas dentre os novos candidatos e os que já estavam em sua lista de espera, rejeitando os outros. O procedimento termina quando todos os estudantes estão em uma lista de espera ou foram rejeitados por todas as universidades a que poderiam se candidatar. Nesse momento as universidades aceitam em definitivo todos os estudantes em sua lista de espera. A distribuição assim obtida é um emparelhamento estável (a demonstração é análoga àquela feita para o Problema dos Casamentos Estáveis).

A designação dos estudantes para as universidades obtida de acordo com o procedimento acima é ótima para os estudantes.

TEOREMA: Na designação obtida pelo procedimento descrito acima, cada estudante está tão satisfeito quanto estaria em qualquer outra designação estável.

Demonstração:
Vamos apresentar uma demonstração por indução. Consideremos uma universidade possível para um estudante se existe um emparelhamento estável no qual ele é aceito nessa universidade. Assumindo que em um determinado ponto do desenvolvimento do procedimento, nenhum candidato ainda foi rejeitado por uma universidade A que é possível para um estudante . Suponha que a universidade A recebeu candidaturas de v estudantes mais bem classificados do que preenchendo todas as suas v vagas, o que a levou a rejeitar o estudante . Cada um dos candidatos prefere A a todas as outras universidades, exceto àquelas que já o rejeitaram anteriormente. A nossa hipótese de indução é que essa universidades são impossíveis para eles. Vamos provar que a universidade A é impossível para . Consideremos, por absurdo, uma distribuição que designa para A e todos os outro estudantes para universidades que são possíveis para eles. Pelo menos um dos estudantes irão para uma universidade que ele deseja menos do que A. Mas essa distribuição é instável, visto que prefere A em relação à universidade para a qual foi designado e A prefere em relação à . Portanto, a universidade A é impossível para
Conclui-se que, no curso do procedimento descrito, apenas são rejeitados por universidades estudantes que não seriam designados para essas universidades em nenhum emparelhamento estável. Logo, a designação obtida é ótima.

O Sisu[editar | editar código-fonte]

O Sistema de Seleção Unificada (Sisu) foi desenvolvido pelo Ministério da Educação do Brasil para selecionar os candidatos às vagas das instituições públicas de ensino superior que utilizarão a nota do Exame Nacional do Ensino Médio (Enem) como única fase de seu processo seletivo. A seleção é feita pelo Sistema com base na nota obtida pelo candidato no Enem. No sítio[3], os candidatos podem consultar as vagas disponíveis, pesquisando as instituições e os seus respectivos cursos participantes.
Em 2013, foram oferecidas pelo Sisu 39.724 vagas em 1.179 cursos de 54 instituições de nível superior para mais de 1,4 milhão de candidatos.
No Sisu o candidato pode escolher até duas opções de curso, sendo permitidas alterações durante o período de inscrições. Algumas instituições reservam algumas vagas ou adotam bônus na nota do candidato de acordo com políticas de ações afirmativas ou sistema de cotas. As instituições também podem estabelecer pesos diferentes por matéria para cada curso e nota mínima por curso.
A nota de corte é a menor nota para ficar entre os selecionados em um curso, com base no número de vagas e no total de candidatos. Uma vez por dia, o Sisu calcula e divulga a nota de corte para cada curso.
Dessa forma, o candidato deve efetuar as suas opções de curso e alterá-las durante o período de inscrição de modo a adequá-las às notas de corte divulgadas diariamente. Como a nota de corte varia diariamente, é possível que num dia você esteja acima da nota de corte de um curso, mas no outro esteja abaixo, ou vice-versa. Dessa forma, é necessário que os candidatos monitorem as notas de corte todos os dias durante o período de inscrição a fim de conseguir a sua inscrição no melhor curso possível dentre aqueles que ele almeja e evitar não ser aceito em nenhum curso.
Notadamente, o procedimento descrito nos itens anteriores poderia ser implementado com vantagens no Sisu. Ele permite a adoção de pesos diferentes e a adoção de notas mínimas por curso. Para a questão das vagas reservadas pelas políticas afirmativas ou sistema de cotas, o procedimento de emparelhamento estável deveria ser aplicado primeiro para o preenchimento dessas vagas e depois novamente para as vagas remanescentes. Além disso, o candidato precisaria acessar o sistema apenas uma vez e escolher quantos cursos quisesse dentre aqueles que ele atingiu a nota mínima. O resultado do processo seletivo alocaria cada estudante no melhor curso possível com a sua nota.
É de se notar que esse procedimento já foi adotado em uma situação bem similar que foi o Concurso de Educadores de Infância e de Professores dos Ensinos Básico e Secundário, relativo ao ano escolar de 2004/05 em Portugal, conforme pode-se consultar no Technical Report DCC-05-02 (Emparelhamentos, Casamentos Estáveis e Algoritmos de Colocação de Professores) de autoria de Ana Paula Tomás da Universidade do Porto.


Referências[editar | editar código-fonte]

Bibliografia[editar | editar código-fonte]

• J. Kleinberg e Éva Tardos, Algorithm Design; Pearson Education, Inc., 2006.
• D. Gusfield e R. W. Irving, The Stable Marriage Problem: Structure and Algorithms; MIT Press, 1989.
P. M. Rodrigues, Notas Sobre Elementos de Matemática Finita, cap. 5, 2013.
L. Evered e W. May, A Java Program for the Gale-Shapley Algorithm
C. P. Teo, J. Sethuraman e W. P. Tan, Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications, Management Science, vol. 47, no. 9, set 2001.
N. Schulz, The Roommates Problem Discussed, 2008.
The Prize in Economic Sciences 2012 (Nobel Prize)- Information for the Public, Stable matching: Theory, evidence, and practical design
Al Roth: An economist who saves lives.
Stable Marriage Problem

Links sobre o Sisu[editar | editar código-fonte]

Página de perguntas frequentes sobre o Sisu da UFC
Infográfico com informações sobre o Sisu 2013
Instruções do site Brasil Escola sobre o funcionamento do Sisu

Categoria:Estruturas de dados Categoria: Ciência da computação Categoria: Matemática aplicada