UNIVERSIDADE FEDERAL DO AMAZONAS
INSTITUTO DE COMPUTAÇÃO
MESTRADO EM INFORMÁTICA

Projeto e Análise de Algoritmo - PAA
Segundo Trabalho Prático

Aluno: Carlos Alberto da Costa Barata

Universidade Federal do Amazonas
Mestrado em Informática
Projeto e Análise de Algoritmos
Professor: Edleno Silva de Moura
2° Trabalho Prático - 1° Semestre de 2013
Sumário
Problema caxeiro viajante (PCV) ...................................................................................... 2
Problema de decisão do bin packing ................................................................................ 4
Problema de decisão da coloração de mapas com três cores..................................... 8
Problema de decisão do clique ....................................................................................... 10
Problema de decisão da mochila .................................................................................... 12
Problema de decisão da cobertura de conjuntos ......................................................... 14
Problema de decisão da cobertura de vértices............................................................. 16
Problema de decisão da soma de subconjuntos .......................................................... 17
Problema da soma de subconjuntos - programação dinâmica .................................. 19
Referências