1

Corso di Laurea in Biotecnologie

Informatica(Programmazione)

Problemi e algoritmi

Anno Accademico 2009/2010

2

Il problemaUn problema computazionale P viene definito dai suoi DATI IN INGRESSO (o INPUT) e dalla sua SOLUZIONE (o OUTPUT)

Esempio

P: somma di due interi

DATI IN INGRESSO: due interi a e b

SOLUZIONE: somma s=a+b

3

Il problema

Istanza di un problema P

realizzazione di particolari dati in ingresso

Esempio

la coppia (2,3) è un’istanza del problema P dell’esempio precedente a

cui corrisponde la soluzione 5

(2,3) 5

4

Il problema

Definiamo:

IP l’insieme delle istanze del problema P

SP l’insieme delle soluzioni del problema P

5

Il problema

Esempio per P=“somma di due interi”

(2,3)

(4,1)

(100,50)

IP

SP

5 150

6

Il problemaDato un problema P, esiste una relazione rP che lega gli elementi in IP (istanze) agli elementi in SP (soluzioni)

rP: IP -> SP

e che rappresenta quindi il problema P.

Nel caso di P=“somma di due interi” si ha che rP è la funzione univoca:

s=rP(a,b)=a+b

7

Tipi di problemi

Decisione SP={1,0} o SP={SI’, NO}

Ad esempio:P: problema del commesso viaggiatoreINPUT: N città con le relative

distanze e un valore prefissato bOUTPUT: “yes” (oppure 1) se esiste un percorso che passa una sola volta per

tutte le città ed è di lunghezza totale minore di b, “no” (oppure 0) se un tale percorso non esiste

8

Tipi di problemi

Ricerca Ad esempio:P: problema del commesso viaggiatore (nella versione di ricerca)INPUT: N città con le relative

distanze e un valore prefissato bOUTPUT: tutti i percorsi che

passano una sola volta per tutte le città e che hanno una lunghezza totale minore di b

9

Tipi di problemi

Enumerazione Esempio

P: problema del commesso viaggiatore (nella versione di

enumerazione)INPUT: N città con le relative

distanze e un valore prefissato bOUTPUT: il numero dei percorsi che passano una sola volta per tutte le città

e che hanno una lunghezza totale minore di b

10

Tipi di problemi

Ottimizzazione Esempio

P: problema del commesso viaggiatore (nella versione di ottimizzazione)

INPUT: N città con le relative distanze

OUTPUT: trovare il percorso che passa una sola volta per tutte le città e che ha minima lunghezza totale

Questo è unproblema di minimo.

Da notare chele soluzioni per una

data istanzapossono essere più

di una (esistonocioè più percorsiche hanno una

lunghezza totaleminima)

11

L’algoritmoCos’è un algoritmo?

In Informatica è un metodo di calcolo per risolvere un

problema computazionale e può essere implementato, cioè può essere tradotto in programma attraverso un linguaggio di programmazioneUn algoritmo esiste indipendentemente

dalla macchina che lo esegue!

12

L’algoritmo

Cos’è un algoritmo?

E’ una procedura, costituita da una sequenza finita di operazioni

elementari, che trasforma un set di dati iniziali (INPUT) in un set di dati finali (OUTPUT)

13

L’algoritmo

Esempio di problema da risolvere tramite un algoritmo

P: somma di 5 numeri interi

DATI IN INGRESSO: un set B={b1, b2, b3, b4, b5} di 5 interi

SOLUZIONE: somma s=b1+b2+b3+b4+b5

14

L’algoritmoEsempio

Algoritmo somma_5_interi:

somma_5_interi

B={b1, b2, b3, b4, b5}

s

15

L’algoritmoUn algoritmo in genere viene scritto in pseudocodice, cioè in un linguaggio, simile ad un linguaggio di programmazione (codice), che però non è direttamente compilabile o interpretabile su un calcolatore. Spesso il linguaggio di pseudocodice imita il linguaggio Pascal e viene perciò chiamato Pascal-like

16

L’algoritmoL’algoritmo precedente può essere riscritto in pseudocodice nel seguente modo (Pascal-like):

Procedura Somma_interi(b1, b2, b3, b4, b5)begin

s:=0s:=s+b1

s:=s+b2

s:=s+b3

s:=s+b4

s:=s+b5

end

17

L’algoritmoUn algoritmo è composto da un certo numero di istruzioni e viene eseguito in un certo numero di passi in dipendenza del particolare input

Istruzione descrizione di un’operazione elementare (ad esempio l’algoritmo precedente è composto da 6 istruzioni di assegnamento)

Passo esecuzione di una certa istruzione

18

L’algoritmoEsempioProcedura Raddoppia_Pari(a)Begin1: b=a

SE a è pari{2: b=a*2

}end

La procedura è compostada 2 istruzioni e compie

2 passi se a in inputè pari, mentre

ne compie uno solose a in input è dispari

19

L’algoritmoUn algoritmo deve:

essere composto da un numero finito di istruzioni e terminare in un numero finito di passi, ovvero deve essere finito

essere realizzabile

gestire tutte le situazioni che si possono verificare durante la sua esecuzione, ovvero deve essere completo

20

L’algoritmo

Un algoritmo deve:

essere riproducibile, ovvero gli stessi dati in input devono dare in esecuzioni successive gli stessi dati in output

essere corretto

essere efficiente

Vedere il seguito…

21

Correttezza di un algoritmoDato un algoritmo A, si definisca:

IA insieme degli input di A

OA insieme degli output di A

22

Correttezza di un algoritmoDato un algoritmo A, esiste una relazione rA che lega gli elementi in IA (input) agli elementi in OA (output)

rA: IA -> OA

e che rappresenta quindi l’algoritmo A.

Nel caso di A=“somma di 5 interi” si ha che rA è la funzione univoca:

p=rA(b1,b2,b3,b4,b5)=b1+b2+b3+b4+b5

23

Correttezza di un algoritmoUn algoritmo A rappresentato da una relazione rA: IA->OA si definisce corretto per un problema P, rappresentato da una relazione rP: IP->SP, se e solo se rA “coincide” con rP. Cioè se ad ogni input i in IA corrisponde un output o che è anche la soluzione di P per l’ingresso fornito da i.

Attenzione al “coincide” che non è in senso stretto!Per i problemi di ottimizzazione ad esempio basta che l’algoritmo trovianche solo una delle possibili soluzioni ottime (di minimo o di massimo)

24

Efficienza di un algoritmoL’efficienza di un algoritmo è misurata in termini del tempo di computazione e dello spazio di memoria che userebbe se venisse implementato ed eseguito su di una macchina di riferimento ipotetica.

Un algoritmo è tanto più efficiente quanto meno tempo e spazio spreca.

La misura di efficienza (in tempo e spazio) viene in genere espressa in funzione della dimensione n dell’input

25

Efficienza di un algoritmoEsempio di tempo T di computazione funzione della dimensione n dell’inputProcedura Somma_interi(b1, b2, b3, b4, b5)begin

p:=0p:=p+b1

p:=p+b2

p:=p+b3

p:=p+b4

p:=p+b5

stampa pend

n=5 costante sull’intero insieme IA

La dimensione n dell’input è il numero diinteri b1, b2, b3, b4, b5 (n=5) che è costante

per ogni input possibile.Immaginando di implementare ed eseguirela procedura su una macchina di riferimento

(modello) che esegue ogni istruzionein un tempo unitario, si ha che il tempo di

computazione T per ogni input è:T=n+2 le n=5 istruzioni di assegnamento

p:=p+bi, l’istruzione p:=0 e l’istruzione“stampo p”. Di conseguenza si ha che T è

costante per ogni input.

26

Efficienza di un algoritmo

Procedura Stampa(a)begin

Per a voltestampa “ciao” e vai a capo

end

n=a non costante sull’insieme IA

La dimensione n dell’input è l’intero a (n=a) che non è costante per ogni input.Immaginando di implementare ed eseguire la procedura su una macchinadi riferimento (modello) che esegue ogni istruzione in un tempo unitario,

si ha che il tempo di computazione T per un input a è: T=n=a viene eseguita a voltel’istruzione di stampa. Di conseguenza si ha che T è funzione lineare di a.

E’ evidente che non ci sono due input che hanno la stessa dimensione

Esempio di tempo T di computazione funzione della dimensione n dell’input

27

Efficienza di un algoritmoEsempio di dimensione n dell’inputProcedura Commesso_viaggiatore(insieme_di_città)begin

…end

n=N non costante sull’insieme IA

La dimensione n dell’input è il numero N delle città n=N.Il tempo di computazione dell’algoritmo sarà funzione di N.

In questo caso due input diversi possono anche avere la stessadimensione. Ad esempio i1={Roma, Napoli Pisa} ei2={Milano, Genova, Venezia} che hanno n=N=3

28

Efficienza di un algoritmoIndicando con TA(x) il tempo che l’algoritmo A impiega a processare l’input x appartenente a IA, si definisce complessità in tempo nel caso peggiore la grandezza:

TAP(n)=max{TA(x) tale che |x|=n}

cioè per ogni valore di n, TAP(n) è il

massimo tra i tempi di computazione degli input x che hanno dimensione n |x|=n

29

Efficienza di un algoritmoIndicando con TA(x) il tempo che l’algoritmo A impiega a processare l’input x appartenente a IA, si definisce complessità in tempo nel caso medio la grandezza:

cioè per ogni valore di n, TAM(n) è la media

dei tempi di computazione degli input x che hanno dimensione n |x|=n e |In| numero degli input di dimensione n

A

x nMA

n

T x

T nI

30

Efficienza di un algoritmoIn genere, dato un algoritmo A si vuole vedere cosa succede alle sue funzioni TA

P(n) e a TAM(n) al tendere di n

all’infinito. Si vuole cioè indagare il comportamento asintotico di A.

Analogo discorso può essere fatto per misurare lo spazio di memoria che l’algoritmo usa su un’ipotetica macchina modello.

31

Efficienza di un algoritmoGli algoritmi efficienti sono quelli per cui la funzione TA(n) (TA

P o TAM) è un polinomio di

grado k>=0:

TA(n)=a0+a1n1+a2n2+…+aknk

Per k=0 tempo costante

Per k=1 tempo lineare

All’aumentare di k l’algoritmo A diventa sempre più oneroso dal punto di vista computazionale

32

Efficienza di un algoritmoTempi di calcolo su input di varie dimensioni (prima riga) per sei algoritmi che hanno una complessità pari a n (lineare), nlog2n (logaritmica), n2 (polinomiale), n3 (polinomiale), 2n (esponenziale), 3n (esponenziale)

Si supponga che la macchina di riferimento esegua un’operazione elementare (istruzione) in 1 microsecondo (10-6 secondi).

Notazioni: ms (microsecondi), ms (millisecondi), s (secondi), mn (minuti), h (ore), g (giorni), a (anni), c (secoli)

Da: A. Bertoni e M. Goldwurm, Progetto e Analisi di Algoritmi, Rapporto Interno n. 230-98, Dipartimento di Scienze dell’Informazione, Università degli Studi di Milano

33

Problematiche degli algoritmiSINTESI

dato un problema P, progettare (disegnare) un algoritmo A che risolva P

ANALISI

dato un algoritmo A per un problema P, dimostrare che A risolve P (è corretto) e valutare le risorse (tempo e spazio) utilizzate da A