Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Giuseppe Bruno » 5.Fondamenti di teoria della complessità computazionale


Argomenti della lezione

  • Alcune definizioni fondamentali
  • Complessità di un algoritmo
  • Problemi trattabili e problemi intrattabili
  • Problemi decisionali
  • Problemi P ed NP
  • I problemi NP-hard

Alcune definizioni fondamentali

In termini generali un problema di ottimizzazione può essere formulato come

z = f (x)   Max!
x
X

con

  • X di insieme di soluzioni ammissibili
  • z=f(x) funzione obiettivo z=f(x) da massimizzare

Una soluzione x*∈X è un massimo locale se f(x*)≥f(x) per ogni x ∈Iε(x).

Una soluzione x*∈X è un massimo globale se f(x*)≥f(x) per ogni x ∈X.

Alcune definizioni fondamentali (segue)

Per definire un problema di ottimizzazione è necessario individuare:

  • un insieme X di soluzioni ammissibili
  • una funzione obiettivo z=f(x) da massimizzare definita per ogni x∈X che rappresenta il criterio di valutazione.

Una soluzione x*∈X è un massimo (minimo) locale se f(x*)≥f(x)
(f(x*)≤f(x)) per ogni x ∈Iε(x).

Una soluzione x*∈X è un massimo (minimo) globale se f(x*) ≥f(x)
(f(x*)≤f(x)) per ogni x ∈X.

Alcune definizioni fondamentali (segue)

Problema e metodo di risoluzione

Una volta formalizzato un problema di ottimizzazione si pone il problema di individuarne le soluzioni (ottimi globali o locali).

Un metodo di risoluzione è una tecnica che consente di trovare soluzioni del problema.

Un metodo di risoluzione può essere

  • esatto se individua un ottimo globale ammissibile;
  • euristico se è orientato alla ricerca di una buona soluzione (ma non necessariamente ottima).

Alcune definizioni fondamentali (segue)

Istanza e dimensione di un problema

Un’istanza di un problema rappresenta un esempio del problema in esame

Dato un problema Π, si dice che un’istanza I di Π ha dimensione n, nell’alfabeto (finito) Σ, se la sequenza di simboli di Σ necessaria per codificare i dati di ingresso richiede n simboli.

Un alfabeto classicamente adottato per la codifica è l’alfabeto binario (Σ={0,1}); in questo caso la dimensione di I è pari al numero di bit necessari per la codifica dei dati di input.

Complessità di un algoritmo

Notazione O(.)

Una funzione f(n) è detta O(g(n)) (f(n)=O(g(n)) se esistono un n*≥0 e un c≥1 tali che f(n)≤c g(n) per ogni nn*.

La notazione O(.) consente di definire, per una data funzione, un limite superiore rispetto ad un fattore moltiplicativo.


Complessità di un algoritmo (segue)

Notazione Ω(.)

Una funzione f(n) è detta Ω(g(n)) (f(n)=Ω(g(n)) se esistono un n*≥0 e un c≥1 tali che f(n)≤c g(n) per ogni nn*.

La notazione Ω(.) consente di definire, per una data funzione, un limite inferiore rispetto ad un fattore moltiplicativo.


Complessità di un algoritmo

Funzione di complessità di un algoritmo f(n)

Rappresenta, per ogni possibile valore n della dimensione del problema, il massimo numero di operazioni necessario all’algorimo a risolvere un problema di dimensione n.

Un algoritmo è di tipo polinomiale se la sua funzione di complessità f(n)=O(nk).

Ogni algoritmo la cui funzione di complessità non è polinomiale è detto di tipo esponenziale.

Problemi trattabili ed intrattabili

Un problema si dice trattabile se esiste un algoritmo polinomiale in grado di risolverlo.

In caso contrario, ovvero se non può esistere un algoritmo polinomiale in grado di risolverlo, si dice intrattabile.

La ragione di questa distinzione risulta evidente dalla tabella fornita da Garey and Johnson (1979).

Problemi trattabili ed intrattabili (segue)


Problemi trattabili ed intrattabili (segue)

Limiti classificazione

Per dimostrare che un problema è intrattabile bisogna dimostrare che non può esistere un algoritmo polinomiale in grado di risolverlo.

Si pone la questione di come si classifichino quei problemi per i quali

  • non esiste un algoritmo polinomiale in grado di risolverli;
  • non è stato dimostrato che tale algoritmo non può esistere.

Problemi decisionali

La teoria della complessità computazionale o della “NP completezza” (NP-Completeness) punta ad un’ulteriore classificazione dei problemi facendo riferimento ai cosiddetti problemi decisionali.

Un problema decisionale è un problema formulato in modo da ammettere due sole possibili risposte: SI o NO.

Esempio:
Dato un numero intero K, esiste una coppia di numeri interi m ed n (con m,n>1) tali che K=mn ?

Problemi decisionali (segue)

Ogni problema di ottimizzazione può essere formulato come problema decisionale.

Esempio del problema del commesso viaggiatore (TSP)

Problema di ottimizzazione del TSP
Date n città, si individui il circuito di lunghezza minima che un commesso viaggiatore deve effettuare per visitare ciascuna città una sola volta.

Problema decisionale del TSP
Date n città, esiste un circuito che un commesso viaggiatore può effettuare per visitare ciascuna città una sola volta che risulti di lunghezza non superiore ad un valore B (≤B)?

Poiché per risolvere un problema di ottimizzazione si devono risolvere più problemi di decisione ad esso associati, si può concludere che la complessità di un problema di ottimizzazione sarà almeno pari a quello del problema di decisione ad esso associato.

Problemi P ed NP

Un problema decisionale è di tipo P se esiste un algoritmo polinomiale in grado di fornire una risposta di tipo SI o NO, ossia se è trattabile.

Un problema decisionale è di tipo NP se esiste un algoritmo polinomiale in grado di verificare una risposta di tipo SI.

Differenza tra P ed NP
Mentre in un problema P bisogna trovare la risposta in tempo polinomiale, in un problema NP, nel caso ci venga fornita una risposta di tipo SI, bisogna verificare che la risposta fornita sia effettivamente di tipo SI in tempo polinomale.

Ad esempio il TSP non è un problema di tipo P perché non siamo in grado di fornire una risposta in tempo polinomiale. Tuttavia il TSP è di tipo NP, perché, dato un circuito hamiltoniano di lunghezza ≤B, è possible verificare che si tratta di un circuito hamiltoniano di lunghezza ≤B in tempo polinomiale,

Problemi P ed NP (segue)

Risulta evidente che un problema di tipo P è certamente di tipo NP (P ⊆ NP) dal momento che l’algoritmo utilizzato per fornire una risposta in tempo polinomiale può essere utilizzato anche per verificare una risposta di tipo SI.

Non è stato ancora dimostrato che P⊂NP, ovvero che esistono problemi NP che non possano certamente essere risolti in tempo polinomiale.

Anche se non dimostrato formalmente si ritiene (congettura) che P⊂NP ovvero (vedi figura).


NP completezza

All’interno della classe dei problemi NP è possibile individuare un sottoinsieme di problemi “più difficili” detti NP-completi.

A tal fine è necessario introdurre il concetto di riducibilità tra due problemi.

Un problema Π è riducibile ad un problema Π* (ΠΠ*) se ogni istanza di Π può essere trasformato in tempo polinomiale in un’istanza di Π*.

Sia ΠΠ *

  • se Π* è di tipo P allora anche Π è di tipo P
  • se Π* non è di tipo P allora anche Π non è di tipo P

NP completezza (segue)

Esempio di riducibilità
Problema del sequenziamento di operazioni su una macchina

Siano date n operazioni da assegnare ad una macchina. Siano:

  • pj il tempo di esecuzione dell’operazione j e sia
  • sij il tempo che bisogna attendere per iniziare l’operazione j dopo il completamento dell’operazione i (tempo di setup).

Esiste un sequenziamento delle operazioni tale che la somma dei tempi di setup non superi il valore B (Cmax B)?)

Il problema può essere ridotto ad un problema di commesso viaggiatore su n+1 città.


NP completezza (segue)


NP completezza (segue)


NP completezza (segue)


NP completezza (segue)


NP completezza (segue)


NP completezza (segue)

Un problema decisionale Π è di tipo NP-completo se:

  • Π è di tipo NP;
  • qualsiasi altro problema Π‘ di tipo NP può essere ridotto a Π (Π‘∝Π) ovvero tutti i problemi NP possono essere ridotti a (vedi figura).

NP completezza (segue)

Importanza della classe dei problemi NP-completi

La classe dei problemi NP-completi è una classe di problemi più difficili all’interno della classe NP.

Se si individuasse un algoritmo polinomiale per risolvere un qualsiasi problema NP-completo allora tutti i problemi NP sarebbero trattabili ovvero P=NP.

Se si dimostrasse che un problema NP-completo è intrattabile, allora tutti i problemi NP sarebbero intrattabili ovvero P≠NP.

Un problema di ottimizzazione la cui versione decisionale appartiene alla classe dei problemi NP-completi è detto NP-hard (NP-difficile).

NP completezza (segue)

Per dimostrare che un Π è di tipo NP-completo bisogna:

  • dimostrare che Π è di tipo NP (ovvero che esiste un algoritmo polinomiale in grado di verificare una risposta SI);
  • individuare un qualsiasi altro problema Π‘ che già è stato dimostrato essere NP-completo;
  • mostrare che Π‘ può essere ridotto a Π (Π‘∝Π).

Per poter applicare questa procedura è necessario conoscere un primo problema di tipo NP-completo (vedi figura).


NP completezza (segue)

Nel 1971 il matematico inglese Cook individuò un primo problema tipo NP-completo.

Da allora, attraverso il procedimento descritto, sono stati individuati numerosi problemi NP-completi.

Anche se non è stato dimostrato formalmente si adotta la congettura (l’ipotesi) P≠NP, ovvero si ritiene che i problemi NP siano intrattabili.


Conclusioni

La teoria della NP-completezza consente di classificare nella classe dei problemi NP e NP-completo, problemi che non risultano né trattabili, né intrattabili.

Anche se non è stato dimostrato formalmente si adotta la congettura (l’ipotesi) P≠NP, ovvero si ritiene che i problemi NP siano intrattabili.

Ne consegue che i problemi NP vanno trattati, in pratica, come se fossero intrattabili. Pertanto poiché i tempi di calcolo di algoritmi risolutivi esatti applicati a questi problemi risultano esponenziali, nelle applicazioni pratiche bisogna ricorrere ad algoritmi di risoluzione euristici.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion