Lezione del 25 Novembre 2010

Presentazione dell'algoritmo di ricerca per scansione lineare e di ricerca dicotomica.

La parte principale della lezione consiste però nella descrizione di come è possibile descrivere (usando un linguaggio naturale sufficientemente preciso) l'algoritmo di ordinamento che è stato presentato nella lezione precedente.

Ci son alcuni concetti preliminari da definire. In primo luogo occorre considerare il fatto che, se un algoritmo deve operare su dati (che descrivono, secondo il nostro modello, una realtà esterna come un mazzo di carte) questi dati devono essere contenuti in uno spazio accessibile alle istruzioni di un programma astratto. Questo luogo è la "memoria". La memoria può essere concettualizzata come una sequenza di byte, ognuno dei quali è identificato in base all'ordine che occupa nella memoria, ci sarà quindi il primo byte, il secondo byte e così via. La memoria si può considerare un nastro seminfinito di byte, cioè che ha inizio in un punto preciso ma non termina mai. Naturalmente l'infinito non esiste in natura, ma a tutti gli scopri pratici e teorici si può considerare illimitata. La caratteristica della memoria è di essere una sequenza INDISTINTA di valori. Da un punto di vista concettuale la memoria è una lunghissima sequenza di numeri, i quali non hanno caratteristiche semantiche intrinseche: il significato dei valori nei byte (e dei bit nei byte) è demandato interamente a noi che a priori decidiamo a priori quali informazioni devono essere contenute nella memoria, come devono essere rappresentate e ne definiano infine l'uso attraverso il programma che agirà su quei dati. Per esempio potremmo decidere di scrivere il valore ell'età di una persona nella 4a cella di memoria, e da quel momento (fino a che ci sarà utile) il significato del valore di quella cella sarà l'età della persona. (cliccare le immagini per vederle ingrandite)

Possiamo dare nomi alle "locazioni di memoria" in modo che sia facile per noi comprenderne il senso (per esempio Età sarà un nome molto più semplice e pratico da usare al posto di MEMORIA[4] che indica la quarta locazione della memoria: al compleanno basterà incrementare Età ). Ogni valore che il programma avrà necessità di usare e conservare, anche valori temporanei, anche utili solo allo svolgimento del compito, deve essere raccolto e mantenuto nella memoria. È possibiel anche dare un nome "collettivo" a una serie di locazioni di memoria (cosa che in gergo si definisce "array"). Per esempio il vettore Carte può contenere i corrispondenti valori di un mazzo di carte da gioco sotto forma di una sequenza di locazioni di memoria, e permettere l'accesso con solo il nome e l'indice all'interno di quel segmento, usando la notazione Carte[3] per specificare la terza posizione nell'array che contiene le carte, che corrisponde alla locazione MEMORIA[5] nella memoria generale. α e ß sono i valori dei due indici che realizzano i due cicli relativi nell'esempio della lezione scorsa.

  

Dato che la memoria è composta da una serie di valori indistinti, e che una locazione non può NON avere un valore, la si considera inizialmente impostata al valore 0 (ma in genere è meglio non fare affidamento a questo fatto, perché nella realtà le locazioni di memoria vengono "riciclate" e quindi non si può essere certi del loro valore iniziale: del resto la memoria è solo una lunga striscia piena di numeri!).

Nella memoria si troverà qundi sia l'input che l'output di un programma: i dati che riceve in ingresso e che dovrà elaborare, e il risultato dell'elaborazione.

La traduzione del procedimento di ordinamento visto nella lezione precedente, una volta espresso in termini naturali ma sufficientemente "spezzettati" e non ambigui, è (ammettendo che in Carte ci sia la rappresentazione delle carte da gioco solo in termini di valore della carta e che ci siano 7 carte da ordinare, dopo il segno // ci sono i commenti) 

α = 1 //il ciclo α comincia dalla carta in prima posizione
(**) ß = α + 1 //il ciclo ß comincia nella posizione subito dopo α
(*) SE Carte[α] > Carte[ß] ALLORA Scambia Carte[α] con Carte[ß] //se i valori delle due carte sono "in disordine" scambia le carte
incrementa ß di 1 //passa alla posizione successiva
SE ß < 8 ALLORA torna alla istruzione (*) //altrimenti "sforiamo" fuori dal'array
incrementa α di 1 //a questo punto abbiamo finito il ciclo ß, quindi si passa all'α succesivo
SE α < 7 ALLORA torna alla istruzione (**) //altrimenti "sforiamo"
FINE

A questo punto i dati che si trovavano nella memoria sotto il nome di Carte sono ordinati. Questo lo stato della memoria prima e dopo l'esecuzione del programma.

  

(provare per credere!)