Algoritmos para Problemas Combinatórios – TIN0144

Optativa – 60 horas – 4 créditos
Pré-requisitos: Análise de Algoritmos
Professor Responsável: Adriana Alvim

Objetivos da Disciplina

O objetivo deste curso é capacitar o aluno a resolver, de forma heurística, problemas de otimização combinatória difíceis através da aplicação de técnicas fundamentais e avançadas para a construção de heurísticas eficientes. Outro objetivo do curso é capacitar o aluno a conduzir experimento computacional com o objetivo de avaliar e analisar os resultados obtidos e elaborar relatório técnico sobre o experimento.

Ementa

Problemas de otimização combinatória. Programação Dinâmica. Algoritmos Gulosos. Branch&bound.e A*. Heurísticas e metaheurísticas. Simulated annealing, busca tabu, algoritmos genéticos, GRASP e VNS.

Conteúdo Programático

• Revisão sobre a teoria da complexidade.
• Problemas de otimização combinatória.
• Soluções. Representação e construção. Vizinhança. Busca local.
• Metaheurísticas:
  • Simulated annealing
  • Busca tabu
  • Algoritmos genéticos
  • GRASP
  • VNS/VND
  • Iterated local search (ILS)
• Aplicações
• Tópicos sobre trabalhos experimentais com algoritmos

Metodologia

Exposição de conteúdos: aulas expositivas de apresentação de conteúdo teórico.
Aprendizagem baseada em projetos: projeto prático de implementação para resolver, de forma heurística, um dado problema de otimização combinatória difícil. Condução de experimento computacional com o objetivo de avaliar e analisar os resultados obtidos pela proposta de solução.
Aprendizagem colaborativa: cada aluno (ou grupo) deverá apresentar um seminário com sua proposta de solução incentivando os demais colegas à participação e discussões sobre o tema abordado.

Avaliação

A avaliação se dará de forma contínua. Ao longo do período o aluno (ou grupo) deverá apresentar, por escrito, relatórios intermediários da sua proposta de solução que serão avaliados pelo professor. Como resultado deste processo dinâmico, onde o aluno apresenta suas ideias e resultados parciais e o professor comenta e discute, será produzido, pelo aluno, um relatório final com sua proposta de solução e análise dos resultados. A avaliação final levará em consideração o relatório final, o seminário e a participação em sala.

Bibliografia

• Notas de aula.
• Holger H. Hoos; Thomas Stützle, Stochastic Local Search Foundations and Applications, Morgan Kaufmann / Elsevier, 2004.