Programação com Restrições para Otimização Combinatória

Código:

PRODEI009

Sigla:

PROC

Áreas Científicas
Classificação	Área Científica
OFICIAL	Ciências e Tecnologia da Programação

Ocorrência: 2022/2023 - 1S

Ativa?	Sim
Unidade Responsável:	Departamento de Engenharia Informática
Curso/CE Responsável:	Programa Doutoral em Engenharia Informática

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
PRODEI	0	Plano de estudos Oficial	1	-	6	28	162

Língua de trabalho

Português - Suitable for English-speaking students

Objetivos

O investimento realizado pelas empresas/instituições de desenvolvimento de sistemas de informação para suportarem as suas operações permite recolher mais e melhores dados sobre elas. Essa informação permite conhecer melhor o funcionamento da organização e cria oportunidades de otimizar os seus processos. Esta Unidade Curricular debruça-se sobre uma abordagem para a resolução de problemas de otimização, a programação com restrições.

Assim, os objetivos principais desta Unidade Curricular (UC) são:

• Motivar para a utilização de técnicas de programação com restrições para a resolução de problemas complexos de otimização
• Desenvolver a capacidade de utilizar corretamente essas técnicas e as ferramentas que as implementam para a resolução de problemas reais. 

Distribuição percentual:

• Componente científica: 70%
• Componente tecnológica: 30% 

 

Resultados de aprendizagem e competências

Ao concluir a disciplina, um aluno deve ser capaz de:

• Identificar problemas combinatórios e classificá-los de acordo com as categorias conhecidas
• Criar modelos de programação linear e programação inteira para um problema de optimização
• Descrever o processo de resolução de problemas usado nas linguagens de programação com restrições
• Descrever os efeitos dos algoritmos de propagação de restrições numa rede de restrições
• Distinguir linguagens de programação com restrições baseadas em paradigmas diferentes
• Comparar, para um mesmo problema, soluções usando programação com restrições e programação matemática
• Criar um modelo de restrições para um problema de optimização, escolhendo variáveis, restrições, métodos de pesquisa e critérios de optimização e desenvolver um protótipo de aplicação usando programação com restrições. 

Modo de trabalho

Presencial

Programa

• Problemas combinatórios. Classes de problemas. Modelos.


• Programação matemática. Modelos de programação linear e de programação inteira. 


• Restrições. Domínios. Modelação com restrições. 


• Operações sobre restrições. Simplificação de restrições. Consistência. Soluções.


• Modelos com restrições de problemas combinatórios.


• Linguagens de programação com restrições. Programação em Lógica com restrições.


• Desenvolvimento de restrições para categorias de problemas. Restrições globais.


• Optimização. Pesquisa de soluções. Métodos completos e incompletos.

Bibliografia Obrigatória

Rina Dechter; Constraint Processing, Morgan Kaufmann, 2003
Kim Marriott, Peter J. Stuckey; Programming with Constraints- An Introduction, MIT Press, 1998
Krysztof R. Apt; Principles of Constraint Programming, Cambridge University Press, 2003

Métodos de ensino e atividades de aprendizagem

As aulas combinam a apresentação dos temas da disciplina com a discussão de textos recomendados para leitura e com o acompanhamento de trabalhos práticos.

A avaliação é distribuída e consiste em 2 trabalhos práticos.

Software

ECLiPSe

Tipo de avaliação

Avaliação distribuída sem exame final

Componentes de Avaliação

Designação	Peso (%)
Participação presencial	0,00
Trabalho escrito	50,00
Trabalho laboratorial	50,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Elaboração de projeto	74,00
Elaboração de relatório/dissertação/tese	34,00
Frequência das aulas	54,00
Total:	162,00

Fórmula de cálculo da classificação final

0.50* Nota do trabalho 1 + 0.5 * Nota do trabalho 2

Provas e trabalhos especiais

A disciplina obriga à realização de dois trabalhos práticos

• relatório sobre o estado da arte numa sub-área de programação com restrições
• desenvolvimento de solução baseada em programação com restrições para um problema prático.

 

Avaliação especial (TE, DA, ...)

Os alunos com estatuto que isenta da frequência das aulas têm que realizar os trabalhos práticos.

 

Melhoria de classificação

A classificação pode ser melhorada na edição seguinte da disciplina.