Capitolo 1
Problemi e Algoritmi
La programmazione di un calcolatore di svolge essenzialmente in una prima fase, in cui si delinea un algoritmo che risolve un problema di interesse, ed in una seconda fase in cui l’algoritmo è tradotto in un programma scritto in un linguaggio di programmazione.
1.1 Problemi ed istanze
Scopo della programmazione è la soluzione di problemi tramite dei procedimenti chiamati algoritmi. Un problema da risolvere mediante un agente di calcolo (da quella manuale con carta e penna, a quella semimanuale con la calcolatrice, fino a quella completamente automatica con un calcolatore) può essere descritto in termini di dati in ingresso (componenti del problema) e dei dati in uscita (soluzione del problema).
PROBLEMA —> PROCEDIMENTO (ALGORITMO) —> PROGRAMMA
In maniera più formale, un problema P può essere descritto da un insieme I, contenente tutti i possibili valori dei dati in ingresso, un insieme R, contenenti tutti i possibili risultati del problema, e una funzione sol: I è R, che ad ogni combinazione de dati in ingresso associa il risultato corrispondente. Un’istanza di un problema è una possibile combinazione dei dati in ingresso, cioè un elemento di I. In generale il numero delle istanze di un problema è quasi sempre molto elevato. Chiunque esegue l’operazione di risolvere un problema tramite degli algoritmi, viene denominato Agente di Calcolo, esso può essere una persona, un computer ecc…Questo agente di calcolo ha un insieme finito di operazioni che sa eseguire. Ad esempio nel caso dell’algoritmo di Euclide l’agente di calcolo dovrà saper fare le divisioni, le manipolazioni con le variabili, l’assegnamento ecc… In programmazione, dato che il nostro agente di calcolo sarà un computer, non bisogna lavorare con alcuni aspetti con i quali lavoriamo tutti i giorni e cioè:
- NO INTUITO (il computer non ha intuito)
- NO CREATIVITA’ (il computer non può creare da solo)
- NO BUON SENSO (la macchina non è dotata di buon senso)
- NO DECISIONI SOGGETTIVE (le decisioni devono essere già presenti nel programma).
1.2 Gli algoritmi
L’algoritmo più antico e famoso, è sicuramente l’algoritmo di Euclide (detto antenaresis), per calcolare il MCD (Massimo Comune Divisore) tra due numeri interi positivi m ed n.
Dati due numeri diversi, si sottragga ripetutamente il minore dei due dall’altro fino a che i due numeri non diventino uguali: il numero così ottenuto è il massimo comun divisore dei due numeri iniziali.
Ciò dimostra che l’idea di algoritmo è ben distinta dall’idea di programma, inoltre il concetto di algoritmo non è necessariamente connesso con l’informatica.
In generale gli algoritmi possono essere descritti a parole, purchè sia una descrizione
dettagliata e rigorosa dei passi da utilizzare.
Ad esempio un altro algoritmo del problema dell’MCD è il seguente:
1. Calcola il resto della divisione tra m ed n e chiama il risultato r
2. Assegna come nuovo valore di m il valore di n
3. Assegna come nuovo valore di n il valore di r
4. Se n diverso da 0 torna al punto 1
5. Altrimenti hai finito e il valore di m è l’MCD tra i due numeri.
Esempio 1.1
m = 42 n = 70
m/n = 0,6 diverso da 0 quindi torna al punto 1
m = 70; n = 42; è m/n = 1,6 resto diverso da 0 è torna al punto 1è r = 28
m = 42; n = 28; èm/n =1,5 resto diverso da 0 è torna al punto 1è r= 14
m = 28; n = 14; è m/n = 14 resto = 0 è prosegui al punto 5
m = 14; n = 0; è r = 0 è MCD = m = 14
1.3 Proprietà degli algoritmi
Le tre proprietà fondamentali che un algoritmo deve possedere sono:
1.3.1 FINITEZZA
L’agente di calcolo deve utilizzare una quantità finita di risorse per risolvere una qualsiasi istanza del problema. Si richiede che l’algoritmo termini sempre, dopo un numero finito di passi. Se non soddisfa questo requisito l’algoritmo non è considerato valido
1.3.2 CORRETTEZZA
L’algoritmo deve essere in grado di risolvere il problema in tutte le sue possibili istanze. Dimostrare che un algoritmo è corretto non è semplice. Per algoritmi semplici di può fornire una dimostrazione matematica, basata solitamente sul metodo di induzione. L’idea intuitiva con cui si può comprendere il senso dell’induzione matematica è quella di un “effetto domino”: affinché le tessere da domino disposte lungo una fila cadano tutte sono sufficienti due condizioni:
che cada la prima tessera
che ogni tessera sia posizionata in modo tale che cadendo provochi la caduta della successiva.
Il principio di induzione estende questa idea al caso in cui la fila è composta da infinite tessere. Nella maggior parte dei casi si può tentare di capire se l’implementazione dell’algoritmo in programma è corretta utilizzando un insieme di test che riescano a coprire in qualche modo l’insieme, solitamente estremamente grande, delle possibili istanze del problema. Un modo molto usato è quello di trovare degli esempi per diverse classi di istanze. Una possibile variazione sul concetto di correttezza è data dal concetto di algoritmo probabilistico. Un algoritmo probabilistico è un algoritmo che con alta probabilità produce la soluzione corretta dell’istanza data del problema da risolvere. Se no ci riesce può dare soluzione errata o ammettere di non essere stato in grado di risolvere il problema. Spesso un algoritmo probabilistico può dare risposte diverse sulla stessa istanza. Un algoritmo probabilistico benché non sia corretto al 100%, come richiederebbe la teoria, è però utile in situazioni in cui non si conoscono algoritmi corretti efficienti.
1.3.3 EFFICIENZA
L’algoritmo per risolvere il problema deve utilizzare al meglio le risorse di calcolo.
In teoria sarebbe auspicabile utilizzare solo algoritmi “ottimi”, ossia che utilizzano la minor quantità possibile di risorse rispetto a tutti gli altri algoritmi in grado di risolvere il problema in questione, ma non sempre questo è possibile. Infatti per alcuni problemi non si conoscono algoritmi ottimali: in tal caso si usano i migliori algoritmi noti che potrebbero non essere ottimali. Per valutare l’efficienza di un algoritmo bisogna calcolare la quantità di risorse di calcolo necessarie ad un algoritmo.
Vediamo se l’esempio 1.1 da noi considerato soddisfa i tre requisiti:
FINITEZZA? SI, termina dopo un tot di iterazioni poiché n ad ogni passo diminuisce poiché r < n sempre, e per il teorema della DISCESA ALL’INFINITO di FERMAT si fermerà sicuramente.
CORRETTEZZA? SI, ad ogni dato di ingresso, m ed n, l’algoritmo mi restituirà il loro MCD.
EFFICIENZA? SI, è un buon algoritmo poiché il numero dei passi dipende dalla grandezza di m ed n in maniera polinomiale.
1.4 Descrizione di un algoritmo
In generale, un algoritmo da un punto di vista formale, può essere descritto in modi diversi i più conosciuti sono: Diagramma a blocchi, Pseudo-Codice.
1.4.1 Pseudo-Codice
Lo pseudocodice è un modo per descrivere un algoritmo senza utilizzare la sintassi di un linguaggio di programmazione specifico. Come suggerisce il nome, si tratta di pseudo codice: non può essere realmente eseguito da un computer, ma ricorda i veri linguaggi e viene scritto allo stesso livello di dettaglio.
Esistono diverse forme di pseudocodice, sebbene la sua sintassi venga presa in prestito da linguaggi di programmazione abbastanza popolari (come il C, il Lisp o il FORTRAN). Viene utilizzato anche il linguaggio naturale qualora i dettagli dell’implementazione nei linguaggi informatici siano trascurabili o fuorvianti.
I testi di informatica utilizzano spesso lo pseudocodice negli esempi in modo che tutti i programmatori siano in grado di comprenderli, indipendentemente dai linguaggi di
programmazione che conoscono. Poiché lo stile varia da autore ad autore, vi è a volte una introduzione che spiega la sintassi utilizzata.
Un esempio di pseudocodifica per l’algoritmo di Euclide è il seguente:
leggi n e m
ripeti
sia r il resto della divisione di m per n
sia n il nuovo valore di m
sia r il nuovo valore n
mentre n _ 0
restituisci m
fine
1.4.2 Diagramma a blocchi (o Flow Chart o Diagramma di flusso)
Esso consente di descrivere le differenti operazioni sotto forma di uno schema in cui le diverse fasi del processo e le differenti condizioni che devono essere rispettate vengono rappresentati da simboli grafici detti blocchi elementari. I blocchi sono collegati tra loro tramite frecce che indicano la cronologia. Esso consente di descrivere le differenti operazioni sotto forma di uno schema in cui le diverse fasi del processo e le differenti condizioni che devono essere rispettate vengono rappresentati da simboli grafici. I blocchi sono collegati tra loro tramite frecce che indicano la cronologia. Consideriamo ad esempio l’Algoritmo di Euclide, esso può essere così rappresentato
Ogni passo è rappresentato da rettangoli (istruzioni di calcolo) o un parallelogramma
(istruzioni di ingresso/uscita), i punti di scelta dell’algoritmo sono rappresentati con dei rombi contenenti la condizione da controllare.
1.5 Esempi di Algoritmi e complessità computazionale
Esempi di algoritmi sono:
1.5.1 Forza Bruta
Il metodo “forza bruta” è un algoritmo di risoluzione di un problema che consiste nel
verificare tutte le soluzioni teoricamente possibili fino a che non si trova quella effettivamente corretta. Il suo principale fattore positivo è che porta sempre a trovare la soluzione corretta, ma è anche vero che è sempre la soluzione più lenta o dispendiosa; viene utilizzato come ultima risorsa in parti della matematica solamente in quei casi dove sia l’unica soluzione conosciuta e quindi anche la migliore.
1.5.2 Algoritmo ricorsivo
Viene detto algoritmo ricorsivo un algoritmo espresso in termini di sé stesso.
Questo tipo di algoritmo risulta particolarmente utile per eseguire dei compiti ripetitivi su di un set di input variabili. L’algoritmo richiama sé stesso generando un ciclo di chiamate che ha termine al verificarsi di una condizione particolare che chiameremo caso di base, coincidente, in genere, con il presentarsi di particolari valori di input. La tecnica ricorsiva permette di scrivere algoritmi eleganti e sintetici per molti tipi di problemi comuni, sarà tuttavia opportuno verificarne di volta in volta l’efficienza rispetto ad altri tipi di soluzioni, come per esempio cicli elementari.
1.5.3 Crivello di Eratostene
Il crivello di Eratostene è un antico procedimento per il calcolo delle tabelle di numeri primi fino ad un certo numero n prefissato. Deve il nome al matematico Eratostene di Cirene, che ne fu l’ideatore. È a tutt’oggi utilizzato come algoritmo di calcolo dei numeri primi da molti programmi per computer; pur non essendo un algoritmo straordinariamente efficiente, infatti, è in compenso piuttosto semplice da tradurre in un qualsiasi linguaggio di programmazione.
Il procedimento è il seguente: si scrivono tutti i naturali a partire da 2 fino n in un elenco detto setaccio (in programmazione spesso l’elenco è implementato da un array). Poi si cancellano (setacciano) tutti i multipli del primo numero del setaccio (escluso lui stesso). Si prosegue così fino ad arrivare in fondo. I numeri che restano sono i numeri primi minori od uguali a n.
Questi sono solo alcuni degli algoritmi noti per la risoluzione di determinati problemi.
Ma come possiamo dire che un algoritmo è migliore di un altro?
La risposta è la complessità computazionale.
Per calcolo del costo, o complessità computazionale, di un algoritmo si intende la
quantificazione delle risorse utilizzate durante l’esecuzione di un algoritmo.
Due misure comuni di complessità sono la complessità temporale, ossia quanti passi impiega l’algoritmo e la complessità spaziale, ossia di quanta memoria ha bisogno l’algoritmo. La risorsa da noi presa in considerazione in questo corso sarà principalmente il tempo di calcolo (complessità temporale), benché le considerazioni seguenti vanno bene anche per gli altri tipi di risorse. La complessità temporale è usualmente misurata in termini del numero di operazioni svolte.
Dato un algoritmo A su un insieme di input I, può accadere che due istanze i, i‘ di ugual dimensione cioè | i | = | i‘ | diano luogo a tempi diversi di esecuzione per uno stesso algoritmo. Si parla dunque di complessità dell’input e se ne distinguono tre casi:
1. complessità in caso peggiore
2. complessità in caso medio
3. complessità in caso migliore
Il caso peggiore è quello che di fatto viene considerato per la formulazione della complessità di un algoritmo. Il caso migliore è tipicamente O(1), cioè trovare la soluzione al primo passo o occupare una sola cella di memoria. Il caso medio è solitamente calcolato come limite della media aritmetica tra caso peggiore e migliore.
1.5.4 Complessità nel caso peggiore
Per formalizzare meglio il calcolo della complessità temporale nel caso peggiore definiamo TA(n), per un fissato n, come il massimo tempo impiegato da A a risolvere una istanza i di dimensione n. Detto in altri termini, TA(n) rappresenta il tempo necessario a risolvere la peggiore istanza possibile di dimensione n. Quest’ultima considerazione spiega il termine “complessità nel caso peggiore“.
Ad esempio in alcuni algoritmi di ordinamento il caso peggiore è quello di ordinare un
insieme già ordinato ma in senso inverso. Uno svantaggio è che in certi casi la complessità nel caso peggiore offre una stima troppo pessimistica del tempo di calcolo. Un esempio lampante è il celeberrimo algoritmo del simplesso per la programmazione lineare. Nonostante si sappia che nel caso peggiore si comporta veramente male ( con tempi di calcolo che crescono in modo esponenziale rispetto alle dimensioni del problema), questo algoritmo è largamente utilizzato nella pratica perché la stragrande maggioranza delle istanze vengono risolte molto velocemente. Il motivo sembra essere che il caso peggiore di quel problema è un caso patologico, che non si presenterà mai (o quasi) in pratica.
1.5.5 Esempio di calcolo della complessità
Un esempio si ha nel confronto di due algoritmi per il calcolo del massimo di n numeri. Il primo algoritmo, chiamato M1, è basato sulla definizione di massimo, cioè di quel numero che è maggiore uguale a tutti gli altri. Per trovarlo basta prendere a turno ciascuno degli n numeri e controllare se essi soddisfano la condizione di massimo, l’algoritmo si ferma quando un siffatto numero viene trovato.
In pseudocodifica l’algoritmo M1 è:
- Prendi a turno ciascuno degli n elementi, sia Ak l’elemento preso
- Confronta ogni altro numero Ai con Ak contando quanti elementi Ai sono _ Ak
- Se il conteggio da n-1, tutti gli altri sono _ Ak e quindi il numero più grande è proprio Ak,
- Altrimenti continua con il numero successivo.
Il secondo algoritmo, chiamato M2, consiste nel calcolare il massimo parziale, aggiornandolo ad ogni numero preso in considerazione. Si parte ponendo come massimo parziale il primo elemento dell’insieme. Per ogni altro elemento dell’insieme, si confronta l’elemento in questione con il massimo parziale e se l’elemento corrente risulta essere maggiore del massimo parziale, il massimo parziale diventa proprio l’elemento corrente. E’ facile vedere che dopo aver passato in rassegna tutti gli elementi dell’insieme si trova come massimo parziale proprio il massimo elemento dell’insieme.
In pseudocodice l’algoritmo è:
- Memorizza il primo numero in MAX
- Confronta ogni altro numero Ai con MAX: se Ai > MAX allora poni MAX pari a Ai
- Alla fine MAX è il numero più grande
Calcoliamo la complessità di entrambi gli algoritmo nel caso peggiore.
Il caso peggiore per l’algoritmo M1 è quando il massimo è l’ultimo elemento: ad ogni ciclo l’algoritmo fa n-1 confronti per contare gli elementi _ Ak e deve arrivare all’ultimo elemento per trovare il massimo, in totale perciò fa n · (n – 1) confronti. Quindi TA1(n) = O (n2)
Invece M2 fa sempre N – 1 confronti, quindi TA2 (n) = O(n).
Perciò essendo M1 quadratico in n, ed M2 lineare in n, M2 è nettamente superiore a M1 in fatto di efficienza. Per inciso si può vedere che M2 usa il minor numero possibile di confronti quindi è anche un algoritmo ottimale.
Questo è tutto per oggi…. alla prossima..
SP
