1

Informatica Generale

Alessandra Di Pierro email: dipierro@di.unipi.it

Ricevimento: Giovedì ore 14.30-17.30presso Dipartimento di Informatica, Via Buonarroti, 2stanza 362 DE Tel. 050.2212.779o per posta elettronica

Pagina web del corso: http://www.di.unipi.it/~dipierro/IG03.html

2

I problemi risolubili dal computer

Complessità

Problemi intrattabili

Problemi indecidibili

3

La complessità degli algoritmi• Nella prima parte del corso

– abbiamo visto alcuni esempi di algoritmi – abbiamo visto come alcuni algoritmi sono ‘più veloci’

di altri

• Adesso:– vogliamo approfondire introducendo misure

‘quantitative’ della velocità di un algoritmo (la complessità)

• per confrontare due algoritmi fra di loro• per stabilire se un certo problema si può risolvere in tempo

ragionevole o no

4

La complessità degli algoritmi (2)

• Un esempio: ricerca di un Autore in schede ordinate:• algoritmo stupido : controllo tutte le schede dalla prima• algoritmo ‘lettera iniziale’ : troviamo la prima scheda

relativa alla lettera iniziale del campo Autore e da quella procediamo in sequenza

• algoritmo ‘del dizionario’ : dividiamo ripetutamente le schede a metà eliminando ogni volta la metà che sicuramente non contiene la scheda cercata

– la valutazione di complessità associa ad ogni algoritmo una espressione numerica che descrive il numero di operazioni effettuate (in media)

5

La ricerca ‘stupida’

1. Apri il classificatore2. Prendi la prima scheda3. Confronta il campo autore e titolo con quelli cercati4. Se sono uguali, allora la ricerca è terminata, altrimenti prendi la scheda successiva e vai al passo 35. Se le schede sono esaurite, allora il libro cercato non esiste.

6

La ricerca ‘stupida’ (2)• Complessità

1. Apri il classificatore2. Prendi la prima scheda3. Confronta il campo autore e titolo con quelli cercati4. Se sono uguali, allora la ricerca è terminata, altrimenti prendi la scheda successiva e vai al passo 3

5. Se le schede sono esaurite, allora il libro cercato non esiste.

1

Numero operazionielementari richieste

1

1

(lettura)

(confronto)

2 (lettura e confronto)

1 (confronto)

7

La ricerca ‘stupida’ (3)• Complessità

1. Apri il classificatore2. Prendi la prima scheda3. Confronta il campo autore e titolo con quelli cercati4. Se sono uguali, allora la ricerca è terminata, altrimenti prendi la scheda successiva e vai al passo 3

5. Se le schede sono esaurite, allora il libro cercato non esiste.

1

Numero operazionielementari richieste

11

(lettura)(confronto)

2 (lettura e confronto)

1 (confronto)

? Quante volte sono ripetuti 3-4-5 ?

8

La ricerca stupida (4)

schedario

Situazione iniziale

1 N

Numerocomplessivo delleschede

9

La ricerca stupida (5)

schedario

Situazione dopo aver esaminato K schede

1 2 ………. K N

10

La ricerca stupida (6)

schedario

Situazione dopo aver esaminato K schede

1 2 ………. K

I passi 3-4-5 vengono ripetuti finché non trovo la scheda. Supponendo che le schede vengano tutte cercate con la stessa frequenza si ha in media un numero di ripetizioni dell’ordine di N/2

N

11

La ricerca ‘stupida’ (7)• Complessità totale

1. Apri il classificatore2. Prendi la prima scheda3. Confronta il campo autore e titolo con quelli cercati4. Se sono uguali, allora la ricerca è terminata, altrimenti prendi la scheda successiva e vai al passo 3

5. Se le schede sono esaurite, allora il libro cercato non esiste.

1

Numero operazionielementari richieste

11

(lettura)(confronto)

2 (lettura e confronto)

1 (confronto)

(Tl + Tc )*N/2Tl - tempo di letturaTc - tempo di confronto

12

La ricerca ‘stupida’ (8)• Costo complessivo :

– facciamo un conto numerico (Tl = 0.01ms, Tc = 10ns, N= 400 000)

(Tl + Tc )*N/2

(0.01 )*200 000 = 2000 ms= 2 secondi

13

La ricerca stile ‘dizionario’1. Apri il classificatore2. Prendi la scheda X al centro dello schedario3. Confronta il campo autore e titolo di X con quelli cercati4. Se sono uguali, allora termina, altrimenti prosegui5. Se il campo autore di X è minore di quello cercato allora prosegui la ricerca sulla metà inferiore delle schede altrimenti considera la metà superiore 6. Se la metà selezionata al passo 5 è vuota allora termina (lo schedario non contiene il libro cercato) altrimenti scegli come X la scheda al centro della metà scelta e vai al passo 3

14

La ricerca stile ‘dizionario’ (2)

schedario

Situazione iniziale

15

La ricerca stile ‘dizionario’ (3)

Ogni volta elimino la metàdelle schede, oppure mi fermoperché ho trovato la scheda cercata

Ogni volta divido il numeroN delle schede per 2, mi fermo quando N è diventato 1 o 0

Al più eseguo x passi dovex è il logaritmo in base 2 di N(log2 N)

Scheda cercata!

16

La ricerca stile ‘dizionario’ (4)1. Apri il classificatore2. Prendi la scheda X al centro dello schedario3. Confronta il campo autore e titolo di X con quelli cercati

4. Se sono uguali, allora termina, altrimenti prosegui5. Se il campo autore di X è minore di quello cercato allora prosegui la ricerca sulla metà inferiore delle schede altrimenti considera la metà superiore 6. Se la metà selezionata al passo 5 è vuota allora termina ( lo schedario non contiene il libro cercato) altrimenti scegli come X la scheda al centro della metà scelta e vai al passo 3 1

1

1

1

(lettura e confronto)

(confronto)

(confronto)

17

La ricerca stile ‘dizionario’ (5)I passi 3-6 sono effettuati log2 N volte.Quindi la complessità in questo caso è :

che valutato con (Tl = 0.01ms, Tc = 10ns, N= 400 000)da

(Tl + Tc) * log2 N

(0.010001) * log2 400 000 =(0.010001) * 19 = 0.19 ms = 0.0019 sec

18

Complessità : considerazioni

• È importante stabilire la complessità (velocità) di un algoritmo per capire se un problema è o meno risolubile in tempi ragionevoli dal calcolatore

• Esistono problemi per cui non esiste un algoritmo di risoluzione che termina in tempi ragionevoli !

19

Complessità : considerazioni (2)

• Problemi indecidibili : quelli per i quali non può esistere un algoritmo di soluzione che termina sempre (in tempo finito) per qualsiasi insieme dei dati in ingresso– es : problema del barbiere che fa la barba solo a

tutti coloro che non se la fanno da soli (paradosso di Russel) :

• esiste un algoritmo che dato X umano risponde SI se X si fa la barba da solo e NO altrimenti?

20

Complessità : considerazioni (3)

• Il barbiere che fa la barba solo a tutti coloro che non se la fanno da soli (cont.) – la risposta è NO, perché un tale algoritmo A

porterebbe ad una contraddizione se applico A al barbiere stesso (X = barbiere)

• infatti se A(barbiere) risponde SI significa che il barbiere si rade da solo …

21

Complessità : considerazioni (3a)

• Il barbiere che fa la barba a tutti coloro che non se la fanno da soli (cont.) – la risposta è NO, perché un tale algoritmo A

porterebbe ad una contraddizione se applico A al barbiere stesso (X = barbiere)

• infatti se A(barbiere) risponde SI significa che il barbiere si rade da solo …contro la sua caratteristica di radere solo chi non si rade da solo

• analogamente per la risposta NO

22

Complessità : considerazioni (4)

• Altro esempio : trovare un algoritmo che decide se un programma P termina dato un certo insieme dei dati in ingresso D (problema di Turing o della terminazione)– primo tentativo: applicare P a D ed aspettare il

risultato …– …. E se P(D) non termina ?– Turing ha dimostrato che l’esistenza di un

simile algoritmo provocherebbe un paradosso

23

Complessità : considerazioni (5)

• Quindi esistono problemi intrinsecamente insolubili (problemi indecidibili)– per fortuna sono pochi

• Esistono però anche problemi risolubili ma solo con algoritmi di complessità molto elevata (problemi intrattabili)– che sono purtroppo molto frequenti …

24

Complessità : considerazioni (5)• Problemi intrattabili

– Sono problemi che richiedono di esplorare tutte le possibili combinazioni di un insieme di dati in ingresso

– La loro complessità ha fattori come 2N (N numero dei dato in ingresso)

– Con fattori esponenziali nella formula di complessità i tempi di risposta dell’algoritmo crescono rapidamente con il numero N dei dati in ingresso (es. anni)

• nel nostro esempio (ricerca) con N=40, avremo 10995116 sec cioè circa 127 giorni (4 mesi e mezzo)

25

Complessità : considerazioni (6)• Problema dei ponti di Königsberg (Eulero)

problema : stabilire se esiste un itinerario attraverso la città che traversi ciascun ponte una sola volta

Fiume Pregel

Isola Kneiphof

ponti

A

B

C

D

a b

c d

e

f

g

26

Complessità : considerazioni (7)• Problemi dei ponti di Königsberg (Eulero)

grafo di Königsberg : un nodo per ogni pezzo di terra e un arco per ogni ponte

nodoarcoA

B

C

D

a b

cd

e

f

g

27

Complessità : considerazioni (8)• Problemi dei ponti di Königsberg (Eulero)

grafo di Königsberg : un nodo per ogni pezzo di terra e un arco per ogni ponte

A

B

C

D

a b

cd

e

f

g

28

Complessità : considerazioni (9)• Problemi dei ponti di Königsberg (Eulero)

– nel grafo di Königsberg non esiste un itinerario con le caratteristiche cercate– Eulero risolse il problema per un grafo qualsiasi mostrando che

condizione necessaria e sufficiente è la presenza di nodi da cui si dipartono solo numeri pari di archi

– Quindi il problema si risolve esaminando una sola volta tutti i nodi

29

Complessità : considerazioni (10)• Problema del commesso viaggiatore

trovare una cammino che tocchi tutti i nodi una e una sola volta (nodi = città, archi = collegamenti)

A

B

C

D

a b

cd

e

f

g

30

Complessità : considerazioni (11)• Problema del commesso viaggiatore

una soluzione per il grafo di Königsberg

A

B

C

D

a b

cd

e

f

g

31

Complessità : considerazioni (12)• Simile al problema dei ponti

• Però il TSP è intrattabile (NP-completo): per grafi generali TSP non può essere risolto senza considerare tutte le possibili combinazioni di cammini

• Morale :– parecchi problemi pratici sono intrattabili– spesso problemi simili hanno caratteristiche computazionali diverse– per problemi intrattabili bisogna abbandonare l’idea di algoritmo esatto per passare agli algoritmi approssimati