classes e subclasses NP

PONTIFÍCIA UNIVERSIDADE CATÓLICA DE CAMPINAS
CENTRO DE CIENCIAS EXATAS, AMBIENTAIS E DE TECNOLOGIAS

CLASSE DE ALGORITMOS E PROBLEMAS

JÚLIA COELHO FURLANI, RA: 13027958
FERNANDO BARBOSA GOMES, RA: 12194122

CAMPINAS – SP
2015
JÚLIA COELHO FURLANI
FERNANDO BARBOSA GOMES

CLASSE DE ALGORITMOS E PROBLEMAS

Relatório apresentado como requisito parcial para obtenção de aprovação na disciplina de
Análise de algoritmos e Teoria dos Grafos, no
Curso de Engenharia de Computação, na Ponti- fícia Universidade Católica de Campinas, Profª.
Lúcia Guimarães

CAMPINAS – SP
2015
RESUMO
Este trabalho procura explorar o significado da classe de algoritmos NP (não determinístico polinomial) assim como suas “subclasses”. Os problemas NP englobam soluções desde problemas computacionalmente simples até problemas conhecidos como difíceis ou intratáveis. A classe NP tem como “subclasses” os problemas: P (polinomiais), NP – Completo, Intermediário, NP – Difícil. O trabalho procura explorar soluções para estes tipos de problemas e é concluído com um exemplo de problema de classe NP, demostrando uma possível solução para ele.

ABSTRACT
This paper explores what it means to be an NP problem (non-deterministic polynomial) and its "subclasses". The NP problem class include problems from simple computational problems to problems known as difficult or unresolvable. The NP class contains the following subclasses: P (polynomial), NP - Complete, Intermediate, NP - Hard. This paper also seeks to explain solutions for these kinds of problems. Finally it shows an NP class problem and demonstrates a possible solution for it.

SUMÁRIO

1. INTRODUCÃO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2. DESENVOLVIMENTO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1. A Classe e Suas Subclasses. . . . . . . . . . . . .