Classificazione problemi di calcolo

Question 1

5 problemi nuovi analizzati

Answer 1

Commesso viaggiatore: trovare il percorso di peso minimo che passa per le città e poi torna all’origine.

Trovare la cricca di dimensione k.
Trovare la massima cricca.

Trovare l’insieme indipendente di dimensione k.
Trovare il massimo insieme indipendente.

Per nessuno di questi esiste un algoritmo polinomiale o meno.

Question 2

Algoritmy Greedy e Hill climbing

Answer 2

Cercano di raggiungere una soluzione ottima seguendo dei criteri.

Problema dell’hill climbing è che si potrebbe rimanere intrappolati in un massimo locale.

Question 3

3 tipologie di problemi

Answer 3

Problemi trattabili (al più polinomiali) sono della classe P: Polynomial Time.

Problemi per i quali la verifica della soluzione è possibile in tempo polinomiale classe NP: Non deterministic Polynomial Time.
(es problema ricerca cricca e insieme indipendente)

Problemi EXPTime classe dei problemi risolubili con algoritmo di complessità O(2^p(n)).

Question 4

DUBBIO GRANDE

Answer 4

NP = P oppure NP != P?