1

Corso di Informatica

(Programmazione)

Lezione 3 (22 ottobre 2008)

Problemi e algoritmi

2

Il problemaUn problema P viene definito dai suoi DATI IN INGRESSO e dalla sua SOLUZIONE

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

Si definisca:

IP insieme delle istanze di P

SP insieme delle soluzioni di 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}

EsempioP: problema del commesso viaggiatoreINPUT: N città con le relative distanze e un valore prefissato bOUTPUT: esiste un percorso che passa una sola volta per tutte le città e che ha una lunghezza totale

minore di b?

8

Tipi di problemi

Ricerca EsempioP: problema del commesso viaggiatore (problema di ricerca)INPUT: N città con le relative distanze e un valore prefissato bOUTPUT: trovare 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 (problema di

enumarazione)INPUT: N città con le relative distanze e un valore prefissato bOUTPUT: contare tutti i 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 (problema di

ottimizzazione)INPUT: N città con le relative distanzeOUTPUT: 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 per risolvere un problema e può essere implementato, ovvero

può essere tradotto in un programma attraverso un linguaggio di programmazione

Un algoritmo esiste indipendentementedalla 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 p=b1+b2+b3+b4+b5

14

L’algoritmoEsempio

Algoritmo A:

1: p=02: p=p+b1

3: p=p+b2

4: p=p+b3

5: p=p+b4

6: p=p+b5

7: stampo p

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

p

15

L’algoritmo

Un algoritmo in genere viene rappresentato in pseudocodice, cioè in un linguaggio, simile ad un linguaggio di programmazione (codice), che però non è direttamente compilabile o interpretabile su un calcolatore. Spesso lo pseudocodice è definito da una sintassi Pascal-like o C-like

16

L’algoritmoL’algoritmo precedente può essere riscritto in pseudocodice Pascal-like:

Procedura 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

17

L’algoritmo

Un algoritmo è composto da istruzioni

Istruzione descrizione di una certa operazione (l’algoritmo precedente è composto da 7 istruzioni)

L’esecuzione di una certa istruzione è il passo

18

L’algoritmoEsempioProcedura Raddoppia_Pari(a)begin

SE a è pari{1: b:=a*22: stampa b

}altrimenti{

3: stampa a}

end

La procedura è compostada 3 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