Lezione del 29 novembre 2010

Esplicazione del passaggio logico fondamentale su cui si fonda la definizione attualmente più diffusa di computer: Considerando i due stati di memoria dell'esempio precedente,

 

  

 si può notare come il funzionamento del programma di fatto si riduca alla trasformazione di una serie di simboli contenuti nella memoria. Il programma trasforma sequenze di simboli in altre sequenze di simboli. Il significato di queste sequenze viene attribuito da NOI e non risiede nelle sequenze in sé. Si può tranquillamente pensare a un programma composto da una sequenza casuale di istruzioni: anche questo programma opererà esattamente nello stesso modo: trasformando simboli (o valori numerici) nella memoria stessa del programma, senza la pretesa che ciò abbia un qualsivoglia significato. La possibilità di dare alle sequenze un certo significato è definita esclusivamente da noi, e non appartiene né alla "natura" dei dati, né alla "natura" del programma. Il programma è un cieco esecutore di istruzioni. Questo ci permette (ed è la definizione "generale") di definire un computer come un manipolatore universale di simboli. Un computer è tale se è possibile programmarlo in modo da trasformare (teoricamente) qualsiasi sequenza di simboli in qualsiasi altra sequenza di simboli. (Approfondimento: la Macchina di Turing). I simboli che vengono manipolati non necessariamente hanno collegamento col mondo esterno: il collegamento viene presupposto e realizzato da noi. E se il programma è fatto bene ci permette, con la sua elaborazione, di ripercuotere i calcoli sul mondo reale che è stato modellizzato, ma questo NON È un vincolo teorico del computer.

Introduzione della struttura "Ripeti" come ristrutturazione concettuale del ciclo già visto per l'esempio di ordinamento nelle lezioni precedenti.

α = 1
(**) ß = α + 1
(*) SE Carte[α] > Carte[ß] ALLORA Scambia Carte[α] con Carte[ß]
ß = ß + 1
SE ß < N+1 ALLORA torna alla istruzione (*)
α = α + 1
SE α < N ALLORA torna alla istruzione (**)
FINE

Diventa, racchiudendo il blocco di istruzioni da ripetere tra parentesi {graffe}:

α = 1
  {ß = α + 1
    {SE Carte[α] > Carte[ß] ALLORA Scambia Carte[α] con Carte[ß]
    ß = ß + 1 
    } RIPETI SE ß < N+1 
  α = α + 1 
  } RIPETI SE α < N 
FINE 

Questo formalismo (del tutto equivalente al precedente da un punto di vista operativo) ci permette di strutturare il codice in modo più sofisticato e coerente e di evitare le istruzioni di "salto" che sono sempre poco leggibili e possibili fonti di errore. Questo tipo di programmazione si chiama "strutturata".

Altro argomento fondamentale è il concetto di complessità computazionale. Abbiamo visto che il problema dell'ordinamento può essere affrontato e risolto usando molti diversi algoritmi. Ma come misuriamo il grado di efficienza di un algoritmo? Una definizione molto superficiale (ma sufficientemente intuitiva e operativa) è la seguente: la complessità coputazionale di un algoritmo misura il numero di ripetizioni della "istruzione fondamentale" di un algoritmo in funzione della dimensione dell'input. Il numero delle ripetizioni non deve necessariamente essere esatto, si possono normalmente trascurare le costanti additive e moltiplicative.

Per esempio la complessità dell'algoritmo di ricerca lineare già introdotto ha complessità N (se N è la dimensione del vettore) perché mediamente per trovare un elemento nel vettore dovremo confrontare un valore con ogni elemento del vettore per valutare se è uguale o no: l'operazione "fondamentale" è quella di confronto, e nel caso peggiore l'elemento non c'è (quindi si fanno N confronti). Nel caso medio se ne faranno N/2, ma come detto le costanti moltiplicative non sono rilevanti nella nostra valutazione. In altre parole la "classe" di complessità è comunque N.

La classe di complessità dell'algoritmo di ordinamento descritto sopra è più difficile da calcolare. L'operazione fondamentale è quella di confronto, quindi è nostra intenzione cercare di contare quanti confronti vengono fatti in base al numero di valori da ordinare. Se N è il numero di valori, al primo giro (per  α=1) verranno fatti N-1 confronti, al secondo giro (per α=2) verranno fatti N-2 confronti (perché il primo elemento è ora ordinato e non viene più confrontato), al terzo giro (α=3) N-3 confronti... e così via fino alla fine quando ne verranno fatti 2 e poi 1 solo (per confrontare il penultimo elemento, per α=N-1, con l'ultimo, ß=N). Quindi per N elementi, il numero di confronti che si fanno sarà (N-1)+(N-2)+(N-3)+...+3+2+1. Questa è una successione matematica notevole  che (come scoprì Gauss a 10 anni) ha come somma (N-1)*(N-2)/2 cioè (sempre per il criterio di "semplificare la forma") di fatto la complessità è N^2 (N al quadrato) perché i termini con "crescita" inferiore  (N "cresce" meno velocemente di N^2) vengono trascurati.

Per approfondire il concetto di complessità computazionale si è presentato un algoritmo di ordinamento più efficiente, quello considerato in generale il più efficiente (partition sort, detto anche quick sort). L'algoritmo richiede un certo numero di complicazioni tecniche e può operare "in sito" cioè sul vettore stesso, ma per semplicità verrà esposto come se noi ogni volta noi copiassimo i valori in un nuovo vettore.
La descrizione del funzionamento può essere la seguente:
Prendi il valore dell'ultimo elemento del vettore (elemento "pivot") e costruisci un nuovo vettore inserendo da sinistra i valori più bassi del pivot e a destra i valori più alti. (vedere l'animazione della pagina di wikipedia linkata) Nella posizione rimanente inserisci l'elemento pivot. La proprietà del pivot a questo punto è quella di trovarsi NELLA POSIZIONE GIUSTA all'interno del vettore (perché è preceduto da tutti e soli gli elementi inferiori e seguito da tutti e soli gli elementi superiori). L'elemento è quello che partiziona (da qui il nome) il vettore in due parti, una contenente solo gli elementi inferiori e l'altra solo gi elementi superiori. Ci si trova a questo punto con due "metà" (o meglio due porzioni complementari) disordinate, che si possono ordinare usando lo stesso sistema considerando le due porzioni di vettore rimanenti come due vettori a sé stanti. (Questa tecnica si chiama "programmazione ricorsiva").

Esempio di esecuzione del QuickSort. I numeri in grassetto sono quelli che vengono inseriti (o riconosciuti essere) nella posizione giusta. Si può comprendere facilmente che a ogni "livello" il numero di confronti è N (anche se, per essere precisi, sono N-1), infatti al primo livello (per effettuare la prima partizione) bisogna confrontare "8" con tutti gli altri valori. Al secondo livello la stessa operazione va fatta per ogni elemento dei due "mezzi" vettori, che si possono approssimare come N/2 ciascuno. Quindi N/2 + N/2 = N, e così via: al quarto livello saranno N/4 + N/4 + N/4 + N/4 = N... Per calcolare quanti livelli sono necessari bisogna chiedersi: Quando ci fermiamo a dividere in due parti? quando non possiamo ulteriormente dividere, quindi quando siamo arrivati alla dimensione minima degli elementi, quando stiamo in pratica trattando vettori di dimensione N=1. Il numero di livelli L corrisponde a questo. Come lo possiamo calcolare? Se consideriamo che ogni divisione divide un vettore già diviso (quindi si divide in mezzi, quarti, ottavi...) ci rendiamo conto che se chiamiamo dk la dimensione del sottovettore al k-esimo livello, dk = N/(2^k). (d2, per esempio, vale N/4, cioè un quarto del vettore, infatti alla seconda ricorsione consideriamo i quarti di vettore). Ma se ci chiediamo per quale valore di k, arriviamo alla dimensione 1 (cioè quella minima) dobbiamo risolvere questa semplice equazione:

1=N/(2^k) ... cioè... N=2^k... passando per i logaritmi... log N = k

Quest'ultimo valore è di fatto il numero di livelli su cui dobbiamo ripetere la divisione perché si arrivi a singoli elementi (quindi a vettori di misura 1). Quello che nel grafico si chiama L (= log N).

Mettendo insieme i pezzi, otteniamo che la complessità computazionale del QuickSort  è C=N*L (numero di confronti per livello moltiplicato per il numero di livelli) = N*log N.

 Questo che può apparire un risultato di esclusivo interesse matematico permette invece di comprendere i limiti degli elaboratori (che sono di fatto i limiti degli umani). Per comprendere la ragione confrontiamo i due algoritmi di ordinamento su un problema di dimensione consistente: 1.000.000 di elementi. Consideriamo che l'elaboratore su cui li facciamo funzionare sia in grado di effettuale 100.000 operazioni al secondo.

Insertion Sort (algoritmo delle carte da gioco): C=N^2
per N=1.000.000, C=1.000.000.000.000 (mille miliardi). Quanto tempo impiega? C/100.000 = 10.000.000 di secondi = circa 115 giorni!!!

Quick Sort: C=N log N
per N=1.000.000, C= 1.000.000*23,25=23.250.000 . Quanto tempo impiega? C/100.000 = 232 secondi = circa 4 minuti!!!

Notate la differenza abissale dello stesso problema risolto in due modi diversi. Anche pensando che di qui a un anno la velocità dei computer possa raddoppiare, il primo sistema ci metterà pur sempre quasi 60 giorni, il secondo circa 2 minuti. Questo evidenzia come i limiti dei calcolatori non siano "dei calcolatori", ma esclusivamente umani (o matematici). Dare la colpa a un computer se non si capisce il suo funzionamento, è come dare la colpa all'automobile se non si sa guidare.