Programação com Restrições (2016/2017) - Departamento de Informática

Informação adicional: http://pr.ssdi.di.fct.unl.pt

Descrição

Nesta unidade curricular (UC), oferecida ao Mestrado Integrado em Engenharia Informática e ao Mestrado Europeu em Lógica Computacional, aprofundam-se os conhecimentos de pesquisa referidos como opcionais no ACM 2008 CS Curriculum na área de Sistemas Inteligentes (IS/AdvancedSearch [elective]), e a sua utilização para a resolução de problemas combinatórios.

Problemas combinatórios (de satisfação e/ou otimização) são comuns em vários domínios de aplicação (gestão de recursos, escalonamento, horários) incluindo a própria informática (por exemplo, configuração de hardware/software, verificação de programas). A complexidade destes problemas combinatórios requer a utilização de métodos eficientes de resolução, leccionados nesta Unidade Curricular, e baseados em pesquisa completa em domínios finitos (ou booleanos) utilizando a propagação de restrições para redução de domínios durante a pesquisa. Nesta UC aborda ainda a propagação de restrições adaptada a domínios contínuos, embora neste caso a completude na pesquisa não possa ser em geral garantida.

Objectivos

Saber:

  • Problemas de satisfação de restrições, e sua complexidade combinatória.
  • Domínios discretos (finitos e booleanos) e contínuos. O caso SAT.
  • Propagação de restrições e tipos de consistência.
  • Algoritmos para manutenção de consistência.
  • Heurísticas.

Saber Fazer:

  • Modelação e resolução de problemas.
  • Seleção das restrições e algoritmos mais adequados.
  • Escolha de heurísticas eficientes.

Competências Complementares:

  • Compreensão de especificações informais.
  • Identificação dos modelos mais apropriados.
  • Capacidade de abstração e generalização.
  • Análise e explicação de resultados.
  • Capacidade de pesquisa de literatura.
Programa
  1. Problemas de decisão em domínios discretos.
  2. Modelação de Problemas.
  3. Resolução de Problemas.
  4. Introdução aos problemas de restrições em domínios contínuos.
  5. Restrições e Análise de Intervalos.
  6. Método de Newton para Intervalos
  7. Associação de Funções de Redução de Domínio a Restrições.
  8. Propagação de Restrições e Manutenção de Consistência.
  9. Resolução de problemas em domínios contínuos.
Bibliografia Principal

BibliografiaPrincipal:

  1. Dina Rechter, Constraint Processing, Morgan Kauffman, 2003.
  2. Krzysztof Apt, Principles of Constraint Programming, Cambridge University Press, 2009 (online)
  3. Jaulin, L., Kieffer, M., Didrit, O., Walter, E., Applied Interval Analysis, Springer, 2001.
  4. Eldon Hansen, G. William Walster, Global Optimization Using Interval Analysis, Marcel Dekker, 2003
  5. Jorge Cruz, Constraint Reasoning for Differential Models, 126 Frontiers in Artificial Intelligence and Applications, IOS Press, 2005.

Bibliografia Complementar:

  1. Comet Tutorial, Dynamic Decision Technologies Inc., August 28, 2009.
  2. Handbook on Constraint Programming, (F. Rossi, P. van Beek and T. Walsh, eds.), Elsevier, 2006
  3. Handbook of Satisfiability, (A. Biere, M. Heule, H. Van Maaren and T. Walsh, eds.), IOS Press, 2009
  4. Ramon E. Moore, Interval Analysis, Prentice-Hall, 1966
Esforço do Aluno
  Horas por crédito 28
  Horas p/ semana Semanas Horas
Aulas práticas e laboratoriais 2 12 24.0
Aulas teóricas 2 12 24.0
Avaliação   6.0
Estudo   54.0
Orientação tutorial   6.0
Projectos e trabalhos   54.0
Total de Horas 168
ECTS 6.0