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

• Tipo: Relatório Técnico
• Data: 2005

Autores

Ana Paula Tomás (Autor) FCUP

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

CORDIS: Ciências Físicas > Ciência de computadores

Outras Informações

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.

Idioma: Português

Tipo (Avaliação Docente): Científica

Notas: 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 .

Referência: http://www.dcc.fc.up.pt/Pubs/TR05/dcc-2005-02.pdf

Nº de páginas: 42