1 Teoria della Complessità Concetti fondamentali q Loggetto della teoria della complessità è...
-
Upload
silvia-morandi -
Category
Documents
-
view
224 -
download
3
Transcript of 1 Teoria della Complessità Concetti fondamentali q Loggetto della teoria della complessità è...
1
Teoria della ComplessitàConcetti fondamentali
L’oggetto della teoria della complessità è stabilire se un problema sia facile o difficile
La difficoltà di un problema è una caratteristica generale e non associata a particolari istanze del problema stesso
Definizione
Un problema è la richiesta a rispondere ad una
domanda circa le proprietà di una struttura
matematica in funzione di parametri costanti e dei
valori non fissati di variabili
2
Esempio
Dato un grafo G=(V,E), esiste un percorso hamiltoniano di lunghezza <K?
Struttura del problema = grafo G Struttura della soluzione = percorso hamiltoniano Parametri = i particolari nodi, archi ed i pesi degli
archi
3
Definizioni fondamentali
Istanza di un problema
Un particolare caso del problema per cui sono stati specificati i valori assunti dai parametri.
Un problema è l’insieme delle sue infinite istanze.
Problemi di decisione
Risposta SI/NO
(es., un ciclo hamiltoniano di lunghezza <K?)
4
Problemi di ricerca
Trovare una soluzione (una prova della risposta “SI”)
(es., trovare un ciclo hamiltoniano di lunghezza <K)
Problemi di enumerazione
Trovare tutte le soluzioni
(es., trovare tutti i cicli hamiltoniani di lunghezza <K)
Algoritmo
Metodo per passi successivi per risolvere un problema
Definizioni fondamentali
5
Facilità di un problema
Esiste un algoritmo di soluzione
efficiente
Difficoltà di un problema
Non esiste un algoritmo
di soluzione efficiente
Stabilire la difficoltà di un problema misurare l’efficienza del (migliore) algoritmo
risolutore
Misurare l’efficienza di un algoritmo determinare la complessità computazionale
dell’algoritmo
6
Efficienza di un algoritmo
Tempo richiesto per
trovare la soluzione
Quantità di memoria richiesta
per i dati del problema
Dimensione dell’istanza del problema(Numero di variabili, vincoli, grandezza dei dati)
Quantità di informazioni necessarie per codificare un’istanza
7
Codifica di un’istanza di problema
Esempio: Un problema di PLCodificare i dati (n+mxn+m coeff.) ci, i=1,...n; aij, i=1,...,n, j=1,...,m; bj, j=1,...m
Sistema binario (codifica di un numero x):k+1 bit, con klog2k+1 più 1 bit per il segno
Numeri a precisione finita:interi e razionali come rapporto tra interi
Codifica Ragionevole utilizza almeno 2 simboli non introduce dati irrilevanti né richiede una
generazione esponenziale di dati
8
Esempio: Codifica decimale (ragionevole)
1 cifra (0-9) 10 simboli10 (2 cifre) 100 simboli10x10=100 (3 cifre) 1000 simboli100x10=1000 (4 cifre) 10000 simboli
mentre il numero di simboli cresce di fattori 10 il numero di cifre cresce come il logaritmo
Esempio: Codifica unaria (non ragionevole)
1 cifra (1) 1 simbolo10 decimale (10 cifre) 10 simboli100 decimale (100 cifre) 100 simboli1000 decimale (1000 cifre) 10000 simboli
mentre il numero di simboli cresce di fattori 10 il numero di cifre cresce linearmente
9
Esempio: Generazione esponenziale di dati
Problema di decisione difficile:dato un grafo determinare se esiste un ciclo hamiltoniano di lunghezza <K.
Problema di decisione semplice:dati n numeri trovare se esiste un numero <K (sorting)
Con una codifica non ragionevole (codificare il grafo e tutti i suoi cicli) si potrebbe trasformare il problema difficile del ciclo hamiltoniano nel problema semplice del sorting.
La codifica non è ragionevole perché in essa è contenuta la generazione delle soluzioni del problema.
10
Efficienza di un algoritmo
Tempo richiesto per risolvere un’istanza del problema
codificata ragionevolmente
Il tempo di calcolo della soluzione è definito in maniera indipendente dalle caratteristiche del particolare calcolatore utilizzato.
Tempo di soluzione: numero delle operazioni
elementari necessarie all’algoritmo per risolvere
un’istanza di una dimensione data.
Operazioni elementari: addizioni, moltiplicazioni, confronti.
11
Definizione
La funzione di complessità nel tempo, f(k), dove
k è la dimensione di un’istanza, è la funzione che
restituisce il massimo numero di operazioni
elementari necessarie ad un algoritmo per risolvere
le istanze di dimensione k di un problema.
La funzione di complessità nel tempo è determinata
per mezzo della worst case analysis. Un modo alternativo di valutare la complessità è
l’analisi statistica (più complicato).
12
Occorre conoscere solo il comportamento asintotico
(k) della funzione di complessità nel tempo, ossia
l’ordine di f(k)
Definizione
La funzione f(k) è di ordine g(k), indicato come
O(g(k)), se k’ ed una costante c tali che
f(k)cg(k) per kk’
Esempio: un polinomio è O(kn)p c kii
i
n(k)
0
13
Definizione
Un algoritmo è di tipo polinomiale se ha una
funzione di complessità nel tempo che è O(kp) per
un certo p fissato.
Definizione
Un algoritmo è di tipo esponenziale se non ha
una funzione di complessità nel tempo di tipo
polinomiale.
14
Definizione
Una funzione f(k) è di ordine esponenziale se non è
limitata da alcun polinomio, ossia
per kk’, c1, c2>0 e d1, d2>1c d f c dk k1 1 2 2 (k)
Classe P
Appartengono alla classe P tutti i problemi di
decisione che possono essere risolti da algoritmi
di tipo polinomiale (Polynomial time algorithm).
I problemi in P sono ben risolti poiché per essi esiste un algoritmo efficiente
15
Esempio: tre algoritmi su un calcolatore che esegue una operazione in 10-6s
k
O(f(k))
10 30 60
10 9 10 3 6 10
01 24 3 13
2 10 17 9 366
2 4 4 3
5
3
k s s s
k s s m
s m ck
.
. .
.
polinomiale
esponenziale
Legenda: s=secondi, m=minuti, c=secoli (!)
16
La complessità computazionale non dipende dalla velocità del calcolatore utilizzato.
Esempio: un calcolatore 1000 volte più veloce (10-9s) quante operazioni potrebbe eseguire in più per i tre algoritmi?
10 10
3162
3 98
2 10
6 9
2
5
k n n
k n n
n nk
.
.
17
Esempio:Sono algoritmi polinomiali gli algoritmi per determinare il minimo albero ricoprente in un grafo:
Kruskal è O(nlogn), Prim è O(n2)
Il problema (di decisione) dello shortest spanning tree: “dato un grafo stabilire se esiste un albero ricoprente di lunghezza <K” è in P
18
Classe NP
Appartengono alla classe NP tutti i problemi di
decisione per cui, essendo nota una soluzione, è
possibile verificare in tempo polinomiale che la
risposta è affermativa (Non deterministic
Polynomial time algorithm)
La codifica di una soluzione è detta certificato di ammissibilità
19
Esempio:
Problema:Dato il grafo G, esiste un circuito hamiltoniano di lunghezza <K?
Risposta:Si
Certificato di ammissibilità: Una sequenza di nodi del grafo
Verifica: Seguire la sequenza dei nodi verificando che corrisponde ad un circuito hamiltoniano di lunghezza <K (polinomiale)
20
I problemi NP sono quelli che sono risolvibili da un algoritmo di tipo polinomiale non deterministico (Non deterministic Polynomial time algorithm).
Un algoritmo NP:Guessing stage) Un oracolo “indovina” la soluzione
(non deterministico)Checking stage) Verifica in tempo polinomiale della
soluzione
(ovviamente nella realtà non esistono tali algoritmi)
PNP
CongetturaPNP
NP P
21
Esempi di problemi di decisione
Shortest spanning tree: è P e NP PL (determinare se esiste una soluzione >K): è NP
e dal 1979 è stato provato che è P (algoritmo
dell’ellissoide) Ciclo hamiltoniano di lunghezza <K: è NP ma non è
stato provato che sia in P
22
Problemi di decisione e problemi di ottimizzazione
Le definizioni della teoria della complessità fanno
riferimento a problemi di decisione.
Quanto detto si può estendere ai problemi di
ottimizzazioneun algoritmo che risolve un problema di decisione
può essere utilizzato all’interno di un algoritmo di
tipo polinomiale per risolvere il corrispondente
problema di ottimizzazione.
23
Esempio:
Problema di decisione (CH(k))Dato il grafo G, esiste un circuito hamiltoniano di lunghezza <K?
Problema di ottimizzazione (TSP)Determinare il ciclo hamiltoniano di G di lunghezza minima.
24
Sia S l’algoritmo per risolvere CH(k).L’algoritmo per risolvere TSP può essere costituito dalla seguente procedura dicotomica:
1. Siano A e B la minima e massima lunghezza degli archi di G ed m il numero di nodi di G.Allora mAlunghezza circuto hamiltonianomBPorre k= m(B-A)/2
2. Usare S per risolvere CH(k).3. Se la risposta di S è si, porre k=k/2 altrimenti
k=k(3/2) ed andare a 2.
Poichè i coefficienti sono interi, al più ci saranno (log(m(B-A))+1 iterazioni.
25
Problema Complementare
I problemi complementari (co-problemi) sono quelli per cui viene formulata una domanda in termini “negati”.
Esempio:
Il problema complementare del ciclo hamiltoniano di lunghezza<K:“Dato il grafo G, è vero che non esistono cicli hamiltoniano di lunghezza <K?”
26
I problemi complementari dei problemi in P sono ancora in P.
P=co-PCongettura
NPco-NP PNP co-NP
PNP co-NP
Esempio:Il certificato di ammissibilità per il problema complementare del ciclo hamiltoniano:
la lista di tutti i possibili cicli hamiltonianiper un grafo completo con m nodi è pari a m! esponenziale quindi non verificabile in tempo polinomiale
27
Trasformazioni ed NP-completezza
Definizione
Si definiscono come problemi più difficili di una
classe quei problemi appartenenti alla classe che
risultano almeno difficili quanto ogni altro
Se si riuscisse a risolvere efficientemente uno dei problemi più difficili allora si potrebbero risolvere efficientemente anche tutti gli altri problemi della classe
28
Trasformazione polinomiale
E’ un algoritmo che, data un’istanza I di un
problema , produce in tempo polinomiale
un’istanza I’ di un problema ’ in modo tale che,
se la risposta è “SI” per I, allora la risposta è “SI”
anche per I’
La trasformazione polinomiale di a ’
’
( ridotto a ’)
Le trasformazioni polinomiali sono transitive
29
Classe NP-C (NP-Completi)
Appartengono alla classe NP-C tutti i problemi di
decisione della classe NP che sono almeno difficili
quanto ogni altro problema in NP.
Il problema è NP-C se ’NP, è possibile
I problemi NP-C sono quelli a cui possono essere
ridotti con una trasformazione polinomiale tutti i
problemi in NP
30
Conseguenze:
Se fosse possibile risolvere efficientemente un NP-C allora tutti i problemi NP sarebbero stati risolti efficientemente.
Per dimostrare P=NP basterebbe provare che un solo problema NP-C è P
P
NP
co-NPNP-C
31
Il problema della soddisfacilità (SAT)
E’ stato il primo problema NP di cui è stata dimostrata l’appartenenza ad NP-C
SAT Problem
Data un’espressione booleana in forma congiuntiva
normale in n variabili, x1,..., xn, e loro complementi,
dire se l’espressione è soddisfacibile.
Forma congiuntiva normale: un AND di OR:
i
K
i hi ji n ny y con y x x x x
11 1 1... ,..., , ,...,
dove le espressioni in parentesi sono clausole di cardinalità h
32
Esempio: Data
dire se esiste un’assegnazione VERO-FALSO alle variabili per cui E=VERO.
E x x x x x x x x x x x x 1 2 4 1 2 4 1 3 4 2 3 4( )
Teorema di Cook (1971)
Il problema SAT è NP-C se h3.
Per dimostrare che NP è tale che NP-C, per la
transitività di è sufficiente dimostrare che un ‘NP-C
(ad esempio, SAT) si riduce ad esso, .
33
Estensione ai problemi di ottimizzazione.
Problemi NP-hard
Un problema è NP-hard se esiste un problema
NP-C che può essere ridotto ad esso con una
trasformazione polinomiale.
34
Sono NP-hard problemi (anche non NP) almeno
difficili quanto ogni problema NP-C. Se NP-C per alcune delle sue istanze (le più
grandi) non potrà essere trovata la soluzione ottima
in un tempo accettabile per mezzo di algoritmi esatti
(enumerazione esplicita o implicita). In generale è possibili determinare soluzioni
accettabili per NP-C per mezzo di algoritmi approssimati (soluzioni sub-ottime) algoritmi euristici
35
Esempi di problemi
Problemi P Programmazione Lineare Continua Matching Min Spanning Tree Shortest Path (Dijkstra O(m3), Bellman-Ford O(m2)) Sistemi equazioni lineari
Problemi NP-C Travelling Salesman Problem SAT Set partitioning, packing, covering 0-1 Integer programming Knapsack