Programação com Restrições
Código
11164
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Informática
Créditos
6.0
Professor responsável
Francisco de Moura e Castro Ascensão de Azevedo, Pedro Manuel Corrêa Calvente Barahona
Horas semanais
4
Total de horas
46
Língua de ensino
Inglês
Objectivos
Esta UC está focada no estudo de problemas de restrições sobre conjuntos e em domínios contínuos, nomeadamente na sua modelação e métodos de resolução. É adotado um paradigma de programação declarativo, em que a declaração das restrições é especificada separadamente da sua resolução. A resolução destes problemas é baseada na propagação de restrições, utilizando diferentes técnicas de redução do espaço de pesquisa e, no caso dos domínios contínuos, usando aritmética de intervalos para circunscrever as possíveis soluções.
Nesta UC, pretende-se que os alunos obtenham conhecimento e experiência significativos na modelação e resolução destes problemas, permitindo-lhes identificar para um dado problema, quais os melhores modelos a adoptar na sua especificação, quais os métodos de propagação mais adequados às características do problema, e ferramentas informáticas que os implementem.
Pré-requisitos
Um conhecimento básico de programação, programação em lógica, restrições, e de pesquisa combinatória.
Conteúdo
1. Problemas de Satisfação de Restrições: Conceitos Básicos
Variáveis, Domínios e Soluções
Conjuntos
Domínios Contínuos: Intervalos
2. Conjuntos
Conjuntos e multiconjuntos: relações, operações, e funções
Modelação
Variáveis de conjuntos: representação, domínios, intervalos de conjuntos, cardinalidade
Resolvedores de restrições sobre conjuntos: Cardinal, e outros
3. Cardinal
Semântica operacional
Enumeração
Exemplos e aplicações
4. Otimização
Branch and bound
Extensões do Cardinal
Lógica estendida, para circuitos digitais
Pesquisa local
5. Domínios Contínuos e Aritmética de Intervalos
Representação de Domínios Contínuos
Aritmética de Intervalos
Funções de Intervalos
Método de Newton para intervalos
6. Associação de Funções de Contração a Restrições
Funções de projeção e sua envolvente
Método de decomposição de funções
Método de Newton para restrições
Abordagens complementares
7. Propagação de Restrições e Imposição de Consistência
Tipos de Consistência
Consistência de arco, de intervalo, de envolvente e de caixa
Propagação de restrições
Funções de contração e suas propriedades
Algoritmos de propagação de restrições
8. Resolução de Problemas
Técnicas de modelação
Exemplos de linguagens e ferramentas
Benchmarking
Alguns problemas típicos
Bibliografia
• Francisco Azevedo, Constraint Solving over Multi-valued Logics - Application to Digital Circuits, vol 91 of Frontiers of Artificial Intelligence and Applications, ISBN: 1 58603 304 2, IOS Press, xviii + 204 pages, 2003.
(Basicamente capítulos 6 e 7)
• Francisco Azevedo, Cardinal: A Finite Sets Constraint Solver, in Constraints journal, Volume 12, Number 1, Springer, pages 93-129, 2007.
• Jorge Cruz, Constraint Reasoning for Differential Models, 126 Frontiers in Artificial Intelligence and Applications, IOS Press, 2005
• Eldon Hansen, G. William Walster, Global Optimization Using Interval Analysis, Marcel Dekker, 2003
• Jaulin, L., Kieffer, M., Didrit, O., Walter, E., Applied Interval Analysis, Springer, 2001
• Ramon E. Moore, Interval Analysis, Prentice-Hall, 1966
Método de ensino
O programa é lecionado em aulas teóricas e práticas. Nas primeiras são lecionados os conceitos e técnicas relevantes, bem como possíveis implementações.
Nas aulas práticas são estudadas formas de implementação, sendo utilizados dois sistemas de resolução de restrições (um sobre conjuntos, outro sobre intervalos), sendo explorados modelos e técnicas de pesquisa neles disponibilizadas, nomeadamente na elaboração dos projetos.
Método de avaliação
A avaliação (contínua) integra 4 componentes: 2 testes escritos e 2 projetos práticos, todos avaliados na escala de 0-20, com as partes teóricas e práticas a pesar 50% cada uma.
Os testes e projetos são feitos individualmente, embora neste último caso alguma das componentes possa ser feita em grupos de 2, com o acordo do regente.
Para obter frequência, é necessário uma média de 10 valores nas componentes de projeto. A aprovação de um aluno com frequência é obtida com a média final ponderada das 4 componentes de avaliação, não inferior a 10 valores.
Os alunos com frequência são admitidos a exame de recurso cuja nota, em caso de melhoria, substitui a nota dos testes.