17 DEZEMBRO / DOMINGO / 13:56
FCUP PT 
 EN
 
 
APRESENTAÇÃO
PESSOAS
ENSINO
INVESTIGAÇÃO
BIBLIOTECA
NOTÍCIAS
CONTACTOS

Technical Report: DCC-2005-02

Emparelhamentos, Casamentos Estáveis e Algoritmos de Colocação de Professores

Ana Paula Tomás

DCC-FC & LIACC, Universidade do Porto
R. do Campo Alegre 823, 4150-180 Porto, Portugal
Phone: 351 22 6078830, Fax: 351 22 6003654
E-mail: apt @ ncc.up.pt
Março 2005

Resumo

Este relatório apresenta os resultados dum estudo sobre problemas de afectação com preferências, em que se analisou, em particular, algoritmos para resolução do problema da colocação de educadores e professores por concurso nacional, no contexto da actual legislação portuguesa. Estabelece a relação entre esse problema de colocação e variantes dum problema clássico em optimização combinatória, designado por problema dos casamentos estáveis. Tal permitiu deduzir algumas propriedades interessantes e importantes das listas de colocações admissíveis. Mostra que não se pode pressupor que as listas de preferências dos candidatos estão totalmente ordenadas sem se perder a garantia de obtenção de listas de colocações justas, as quais são designadas por listas de colocações óptimas segundo os candidatos. Define exactamente este conceito em termos matemáticos, o qual, em cada fase do concurso, traduz a atribuição a cada candidato da melhor posição, sem prejuízo da observância do mesmo para todos os que o precedam na lista ordenada de candidatos. Prova a existência de algoritmos polinomiais para a determinação dessas listas óptimas. Considerando a dimensão das instâncias reais deste problema, propõe métodos alternativos para a sua resolução, que, podendo não ser polinomiais, podem contudo ter na prática melhor desempenho. Embora não tenha sido acompanhado duma análise experimental que melhor o pudesse suportar, face à complexidade das instâncias reais, conjectura a necessidade de, a curto ou médio prazo, introduzir alterações à lei, de forma a garantir que o problema da determinação de listas óptimas (justas) se possa resolver em tempo útil.


FCUP 2017