Pesquisa e Optimização

Cód.: INF13257M

6 ECTS

Duração: 15 semanas/156 horas

Área Científica: Informática

Língua(s) de lecionação: Português, Inglês

Língua(s) de apoio tutorial: Português, Inglês

Regime de Frequência: Presencial

Objetivos de Desenvolvimento Sustentável

Educação de qualidade - Assegurar a educação inclusiva, e equitativa e de qualidade, e promover oportunidades de aprendizagem ao longo da vida para todos.

Objetivos de Aprendizagem

Adquirir uma visão geral da satisfação e otimização de problemas combinatórios.
Aplicar estas metodologias a problemas concretos, sabendo discernir da eficácia de cada método perante situações concretas.
Adquirir conhecimentos que permitam iniciar investigação em áreas relacionadas.

Conteúdos Programáticos

Grafo de estados; percursos sobre o grafo. Algoritmo A*
Problemas de satisfação de restrições (CSPs)
Técnicas de resolução de restrições
Programação por restrições
Problemas de otimização combinatória (COPs)
Técnicas de pesquisa local
Metaheurísticas
Aplicações

Métodos de Ensino

As aulas dividem-se em aulas teóricas, em que são expostos os problemas e as técnicas a usar, e em que são desenvolvidos e analisados algoritmos, e aulas práticas, onde são usadas as técnicas expostas e onde é proposto aos estudantes a aplicação a problemas práticos.
Procura-se uma aprendizagem que direcione o aluno para a aplicação dos diversos conhecimentos adquiridos, e para a capacitação do aluno para pesquisar e adquirir novos conhecimentos, sendo suportada pela plataforma informática de ensino (e.g. moodle), permitindo incluir componentes de ensino por e-learning.
A avaliação é realizada através da elaboração dum trabalho prático e de testes escritos ao longo do semestre ou, em alternativa a estes, de um exame final.

Avaliação

Avaliação escrita (2 testes ou 1 exame) ~ 70%
Trabalho ~ 30%

Bibliografia

A bibliografia da disciplina baseia-se em diversos recursos incluindo recursos de acesso livre, e/ou através do sistema b-On, acessíveis via internet por todos os alunos da universidade, e atualizados sempre que necessário:

Artigos | Papers:
(To be assigned during the course)
Livros | Books:
K. Apt: Principles of Constraint Programming, Cambridge University Press 2003
K. Marriott and P. J. Stuckey: Programming with Constraints: An Introduction, MIT Press, 1998
F. Rossi, P. Van Beek and T. Walsh: Handbook of Constraint Programming, Elsevier 2006
A. Biere, M. Heule, H. van Maaren & T. Walsh: Handbook of Satisfiability, IOS Press 2009
P. Van Hentenryck and L. Michel: Constraint-based Local Search, MIT Press 2005