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

• Type: Technical Report
• Date: 2005

Authors

Ana Paula Tomás (Author) FCUP

Scientific classification

FOS: Natural sciences > Computer and information sciences

CORDIS: Physical sciences > Computer science

Other information

Resumo (PT): 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. <br> 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.

Language: Portuguese

Type (Professor's evaluation): Scientific

Notes: http://www.dcc.fc.up.pt/Pubs/TR05/dcc-2005-02.pdf <br> Technical Report DCC, 02/2005<br> Relatório enviado ao Ministério da Educação, com impacto na redação do Decreto-Lei 20/2006 .

Reference: http://www.dcc.fc.up.pt/Pubs/TR05/dcc-2005-02.pdf

No. of pages: 42