A Classe de Problemas

18/03/2020

[pic 1]

CLASSES DE PROBLEMAS:

P, NP, NP-COMPLETO

---

Aspectos Teóricos da

Computação

Prof. Leandro Fernandes

1

		• Problemas de Decisão:
		• Solucionáveis e Indecidíveis.
		• Exemplos de problemas (decisão
		e de busca).
		• Caráter de crescimento:
		Polinomial e Exponencial.
	Roteiro	• Classes de problemas:
		• Classe P
		• Classe NP
		• A questão P vs NP.
		• Redutibilidade e a Classe NP-
		Completo.
2

[pic 2]

1

18/03/2020

[pic 3]

O problema é Solucionável. Será mesmo?

• Os problemas de decisão podem ser agrupados em duas categorias:

• Os que não tem solução algorítmica, ditos Indecidíveis; e

• Tais como: o Problema da Parada e o Entscheindungsproblem.

• Os que têm solução algorítmica.

• Entretanto para muitos destes problemas a solução acaba não podendo ser aplicada em situações reais dado o excessivo consumo de recursos (em termos de tempo e/ou de memória).

3

[pic 4]

PROBLEMA:

Coloração de Grafos

---

• Dados =   , e , achar   : → tal que se (  ,   ) ∈ , então   (  ) ≠   (  ). O número cromático de é a mínima |            (  (  ))|, denotado   (  ).

PROBLEMA DE OTIMIZAÇÃO:

• dado , determine   (  ) e produza uma coloração ótima.

PROBLEMA DE DECISÃO:

• dados e ≥ 0, determine se existe com |            (  (  ))| ≤ .

4

2

18/03/2020

[pic 5]

	• Dadas sequências 1, … ,1, … ,   1, … ,
	1, … ,  representando, respectivamente,
	tarefas, tempos de execução, prazos limite e
PROBLEMA:	penalidades, uma execução das tarefas é
uma permutação  de [1, … ,   ].
• A penalidade de  é:
Execução de
=  (1) + ⋯ +     >      ℎ                 0
Tarefas com	=1
penalidade	PROBLEMA DE OTIMIZAÇÃO:
• determine a penalidade mínima.
	PROBLEMA DE DECISÃO:
	• dado, adicionalmente  ∈ ℕ, determine se
	existe um execução  com   ≤  .

5

[pic 6]

PROBLEMA:

Empacotamento (binary packing)

---

• Dado um número ilimitado de caixas de capacidade 1 e objetos com tamanhos 1, … , , onde 0 ≤ ≤ 1, para todo 1 ≤ ≤ .

PROBLEMA DE OTIMIZAÇÃO:

• determine o menor número de caixas para empacotar os objetos.

PROBLEMA DE DECISÃO:

• dado, adicionalmente ∈ ℕ, determine se existe um empacotamento dos objetos em caixas.

6

3

18/03/2020

[pic 7]

PROBLEMA:

Mochila

(knapsack)

---

• Dado uma mochila de capacidade e objetos com tamanhos 1, … , , com índices de proveito 1, … , .

PROBLEMA DE OTIMIZAÇÃO:

• encontre o máximo de proveito de subconjunto de objetos que não excedam a capacidade da mochila.

PROBLEMA DE DECISÃO:

• dado, adicionalmente ∈ ℕ, determine se existe um subconjunto de objetos que não exceda a capacidade da mochila e apresenta um índice de proveito de pelo menos .

7

[pic 8]

PROBLEMA:

 CNF-Satisfabilidade (CNF-SAT)

---

• Um literal é uma variável booleana p ou sua negação ¬p. Uma cláusula é uma disjunção de literais. Uma fórmula lógica em forma normal conjuntiva é uma conjunção de cláusulas.

• Exemplo:

∨        ∨        ∨¬   ∧        ∨¬  ∨¬   ∧        ∨¬  

PROBLEMA DE DECISÃO:

• determine se existe uma atribuição de valores para as variáveis de uma expressão em FNC tal que ela resulte em verdadeiro.

8

4

18/03/2020

[pic 9]

PROBLEMA:

Caminhos e Circuitos Hamiltonianos

---

• Dado um grafo não dirigido (dígrafo),

= 1, … , , , um caminho Hamiltoniano em é uma permutação de [1, … ,   ], tal que para todo 1 ≤ ≤ ,

  (  ),          (  +1)        ∈        .