Programação com Restrições

Objetivos

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.
 

Caracterização geral

Código

11164

Créditos

6.0

Professor responsável

Carlos Augusto Isaac Piló Viegas Damásio, Jorge Carlos Ferreira Rodrigues da Cruz

Horas

Semanais - 4

Totais - 54

Idioma de ensino

Português

Pré-requisitos

N/A

Bibliografia

Bibliografia Principal:

  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

Método de ensino

O programa é leccionado em aulas teóricas e práticas. Nas primeiras são leccionados os conceitos e técnicas relevantes bem como a forma como estão implementados nas linguagens e nos sistemas de modelação e resolução utilizados.

Nas aulas práticas são resolvidos problemas retirados de benchmarks típicos destas áreas, sendo explorados e desenvolvidos modelos e técnicas de pesquisa apropriados.

Método de avaliação

A avaliação de conhecimentos, inclui:

  • 2 testes individuais teóricos (domínios finitos e domínios contínuos), onde é avaliado oconhecimento que os alunos adquiriram dos conceitos e características das técnicas leccionadas.
  • 2 trabalhos práticos que incidem sobre a resolução de problemas de restrições de média dimensão (em domínios finitos e domínios contínuos), e avaliam a capacidade dos alunos na modelação dos problemas e na utilização e adaptação das técnicas exploradas nas aulas práticas (em problemas mais simples).

A nota final é a média das 4 componentes (com notas arredondadas às centésimas), sendo necessária uma nota não inferior a 8.0 valores quer na média dos 2 testes, quer na média dos dois trabalhos prático.

A nota dos testes teóricos pode ser substituída pela nota no exame final. Só têm acesso a este exame os alunos com média não inferior a 8.0 valores na média dos dois trabalhos práticos.

Conteúdo

  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.

Cursos

Cursos onde a unidade curricular é leccionada: