Lezione introduttiva sugli algoritmi, da intendersi in continuità con le lezioni precedenti. Mentre nelle lezioni precedenti si è discusso su come segmentare un mondo (già in forma discreta, come nel caso del conteggio, o in forma continua, come le onde sonore attraverso l'operazione di campionamento). Il mondo che ci siamo impegnati a concepire concettualmente finora era costituito da codifica di dati estratti dal mondo.
Con gli algoritmi il passaggio è molto più complesso, ma coerente con questa linea: un algoritmo è la segmentazione in elementi elementari delle operazioni che si possono condurre sui simboli richiamati nel paragrafo precedente. Il concetto di algoritmo è la formalizzazione di quello che ognuno compie quotidianamente quando segue intuitivamente un processo per ottenere un certo risultato (fare il caffè, cuocere delle uova, guidare un'auomobile).
A lezione il concetto di algoritmo è stato affrontato con l'uso di normali carte da gioco. Quello che si fa normalmente quando si gioca a carte è di metterle in ordine, una volta distribuita la propria mano, in modo automatico (il nome informatico di questo particolare procedimento è "Exchange sort", molto somigliante al "selection sort"). A lezione si è carcato di riconoscere i passi semplici che si effettuano quando si mettono in ordine le carte: si cerca la carta di valore più basso (in modo indifferente al seme!) e la si pone in prima posizione, quindi tra le carte rimanenti si cerca la carta di valore più basso e la si pone in seconda posizione e così via. Secondo la terminologia del libro, la posizione che stiamo cercando di riempire con la carta giusta è detta "alfa", mentre l'operazione di scorrimento che si effettua sulle carte rimanenti (sulla destra) facendo scorrere il nostro indice (detto "beta") sulle carte rimenti per cercare quella minore.
In pratica il processo è stato quello di, ogni volta che troviamo una carta più bassa rispetto a quella che si trova in posizione alfa, scambiare la carta in posizione beta con quella in posizione alfa. Una volta finita la scansione beta, si passa all'alfa successivo. In questo modo è possibile ordinare tutte le carte, qualunque sia il loro valore e la loro disposizione. Per rendere più evidente il concetto si è provveduto a effettuare le stesse operazioni mantenendo le carte coperte, permettendo il confronto solo di due carte alla volta e ricoprendole subito dopo. Questo è di fatto quello che fa un computer quando segue un algoritmo: non ha una visione di insieme, ma solo informazioni molto limitate, e circoscritte a quelle strettamente necessarie al completamento del compito. Nel caso dell'ordinamento è sufficiente conoscere il risultato del confronto di due carte alla volta (se una è minore o maggiore-uguale dell'altra).
Si è introdotto un ulteriore algoritmo di ordinamento, denominato "bubble sort", più semplice da programmare e in certi casi più efficiente del precedente: si confronta la carta alfa (partendo da alfa=1) con la carta alfa+1 (quella successiva). Se la carta alfa ha valore maggiore della carta alfa+1 le due carte vengono scambiate. Si incrementa allora di uno il valore di alfa (si passa alla carta successiva) e si ripete il confronto. Alla fine di ogni giro la sequenza di carte è "un po' più" ordinata di prima. Si procede a ripetere questo ciclo fino a quando non ci sono più scambi: questo significa che la sequenza di carte ha già il valore massimo di ordinamento e non può essere ulteriormente incrementato, quindi l'algoritmo conclude. E le carte sono ordinate. Notate che in questo caso è necessario che le carte vengano scambiate esclusivamente quando la prima è strettamente maggiore della seconda, altrimenti l'algoritmo continuerebbe a scambiare carte dallo stesso valore senza necessità, e quindi il criterio di arresto non si raggiungerebbe mai (in presenza di carte con lo stesso valore ci sarebbe sempre uno scambio).
Approfondimenti: Algoritmi di ordinamento su Wikipedia (con animazioni nelle pagine dedicate a ogni singolo algoritmo)
Nessun commento:
Posta un commento