INTRODUZIONE ALL' ALGORITMICA

Accade spesso che, anche in settori diversi da quello puramente informatico, si senta oggi la necessità di risolvere determinate problematiche in maniera automatizzata, sfruttando le potenzialità che i moderni computer mettono a disposizione. Perchè questo avvenga, occorre istruire la macchina, passo dopo passo, su tutte le operazioni che dovrà compiere.

Questo processo di “insegnamento”, va sotto il nome di Programmazione.

Per programmare un computer occorrono due cose: 1] La conoscenza di almeno un linguaggio di programmazione, necessario per impartire i nostri ordini alla macchina, 2] La conoscenza dettagliata del problema da risolvere, in modo da estrarre un algoritmo.

Con ALGORITMO intendiamo un procedimento mentale che, attraverso una sequenza finita di operazioni univoche e non banali (anche di tipo ciclico), porta alla risoluzione di determinato problema.

Un programma è quindi l’espressione di un determinato algoritmo in un opportuno linguaggio di programmazione. Questo passaggio prende il nome di implementazione. Le lingue naturali (Italiano, Inglese, Francese, etc) sono ricche di ambiguità. L’uso di una lingua naturale per scrivere programmi, potrebbe provocare quindi non pochi problemi. Per questo motivo si preferisce adoperare i cosiddetti linguaggi di programmazione che, se pur ognuno con le sue caratteristiche, sono progettati in modo che ogni enunciato utilizzato, abbia un unico significato.

Solitamente, per presentare un algoritmo informatico, non si adopera il linguaggio naturale per evitare le sopraccitate ambiguità, ma nemmeno uno specifico linguaggio di programmazione (poichè richiederebbe l’introduzione di troppi dettagli tecnici). Ci si basa allora sull’uso di uno Pseudocodice, che offre tutti i vantaggi di una maggiore astrazione.

Ogni algoritmo è caratterizzato da un INGRESSO (INPUT) ed una USCITA (OUTPUT):

Ogni algoritmo può prendere, solitamente prima di iniziare ad operare, da zero a più input e deve rilasciare, alla fine della sua operazione, uno o più output. L’output è quindi il risultato che l’algoritmo fornisce al problema ed è in specifica relazione con l’input.

Esempio:

Consideriamo un generico algoritmo di ordinamento numerico. In input daremo una sequenza numerica randomica (4, 1, 98, 30, 22, 50), l’output sarà la sequenza ordinata in maniera crescente (1, 4, 22, 30, 50, 98).

Knuth definisce ogni algoritmo caratterizzato dall’essere:

Definito:
Ogni operazione del mio procedimento logico deve essere definita in modo chiaro e non ambiguo.

Finito:
L’insieme di operazioni necessarie per andare dall’input all’output deve essere finito, cioè ogni algoritmo deve terminare dopo l’esecuzione di un numero finito di operazioni.

Effettivo:
Ogni operazione deve essere sufficientemente di base da poter essere eseguita “carta e penna”.

[Torna su]





PROGETTAZIONE, VALIDAZIONE, ANALISI e VERIFICA

La Progettazione di un algoritmo è un’arte che non potrà mai essere completamente automatizzata. Essa si basa su di una completa ed approfondita conoscenza del problema da risolvere, su una analisi degli approcci adoperati e su una buona dose di personale creatività.

La Validazione di un algoritmo, una volta che è stato progettato, serve a provarne la correttezza, ovvero bisogna provare che fornisca l’output corretto per ogni possibile input. Questa verifica riguarda la “filosofia” dell’algoritmo e quindi deve essere indipendente dal linguaggio di programmazione eventualmente adoperato per implementare l’algoritmo stesso. Una volta che l'algoritmo è stato validato, esso può essere implementato, cioè trasformato in programma. Bisognerà poi testare il programma in modo da verificare che esso esprima in modo corretto l’algoritmo che implementa.

L’Analisi di un algoritmo serve per determinare quanto tempo di computazione e quanta occupazione di risorse (processore e memoria), esso richiede in funzione all’input. Si testa in questa fase la cosiddetta efficienza di un algoritmo, vedremo in seguito di cosa si tratta.

La Verifica o test del programma finale avviene, come si è detto, dopo la validazione dell’algoritmo. Il testing di un programma comprende due classiche fasi: (1) Eliminazione degli errori (debugging) e (2) Misura delle prestazioni (profiling).

[Torna su]





ALGORITMI BUONI ED ALGORITMI CATTIVI

Si supponga di dover sommare i primi n numeri interi. L’algoritmo presentato in basso risolve correttamente questo problema seguendo un metodo derivato direttamente dalla definizione del problema stesso.

Algoritmo per la somma dei primi n numeri interi

Programma somma 1 (n : intero)

1. begin
2. somma <- 0
3. for i = 0 to n
4.   somma <- somma + i
5. return somma
6. end

Es: se n = 6 allora somma = 1 + 2 + 3 + 4 + 5 + 6 = 21

Una analisi più approfondita del problema porta ad osservare che la somma fra il primo elemento e l’ultimo, fra il secondo ed il penultimo, e così via, si mantiene costante.

Analizzando lo schema riportato a lato, possiamo facilmente vedere come elementi “simmetrici” sommano sempre ad n + 1. Questa considerazione, che secondo la tradizione matematica è dovuta a Gauss quando frequentava la scuola elementare, ci permette di arrivare ad un diverso algoritmo, mostrato in basso:





Algoritmo di Gauss per la somma dei primi n numeri interi

Programma somma 2 (n : intero)

1. begin
2. somma <- (n * (n + 1)) / 2
3. return somma
4. end

Es: se n = 6 allora somma = (6*(6 + 1))/2 = 21

Analizziamo adesso i due algoritmi:

- Entrambi risolvono il problema posto.
- Entrambi ricevono in input e restituiscono in output un numero intero.

Possiamo però chiaramente dire che il secondo algoritmo è più EFFICIENTE del primo per i seguenti motivi:

TEMPO DI ESECUZIONE MINORE: Il primo algoritmo deve fare un numero di somme pari ad n, se n è grande, grande sarà il tempo di esecuzione (si dice che è lineare in input). Il secondo algoritmo ottiene invece lo stesso risultato con tre operazioni aritmetiche elementari, risulta pertanto essere indipendente dalla grandezza di n (si dice che è costante in input).

MINORE NECESSITA’ DI RISORSE DI SISTEMA: Il primo algoritmo contiene una variabile “i” in più rispetto al secondo, necessaria per il ciclo for.

MAGGIOR COMPATTEZZA DEL CODICE: Il primo algoritmo si conclude in 6 righe di codice mentre il secondo in appena 4.

Un algoritmo quindi, oltre ad essere corretto, dovrebbe tener conto, quando possibile, dei punti sopra citati. Parlare di un algoritmo buono significa parlare di un algoritmo che sia quanto più efficiente possibile. Capita a volte che, un dato problema, sia talmente complesso da non riuscire a sviluppare un algoritmo efficiente per la sua risoluzione. In questi casi si cerca di sviluppare un algoritmo che si avvicini quanto più possibile alla soluzione esatta del problema, si parla allora di “algoritmi approssimati”.

[Torna su]