Heap Sort. L’algoritmo heap sort è il più lento di quelli di ordinamento O(n * log n) ma, a differenza degli altri (fusione e quick sort) non richiede una ricorsività massiccia o vettori multipli.

Ciò ne fa l’alternativa più attrattiva per grandi insiemi di milioni di dati.

Come il nome suggerisce, all’inizio l’heap sort forma un mucchio dall’insieme dei dati, quindi rimuove da esso l’elemento maggiore e lo colloca alla fine del vettore ordinato.

Quindi ricostruisce il mucchio, rimuove l’elemento più grande e lo colloca nella successiva posizione libera a partire dalla fine del vettore ordinato.

Ripete questo procedimento fino a che non vi siano più elementi nel mucchio e il vettore ordinato sia pieno.

Le implementazioni elementari richiedono due vettori: uno per contenere il mucchio e l’altro gli elementi ordinati.

Per eseguire un ordinamento sul posto e risparmiare lo spazio che sarebbe necessario per il secondo vettore, l’algoritmo seguente “bara” usando lo stesso vettore per memorizzare sia il mucchio sia il vettore ordinato.

Ogni qualvolta un elemento sia rimosso dal mucchio, esso libera uno spazio alla fine del vettore, in cui l’elemento rimosso può essere collocato.

I vantaggi dell’heap sort sono quindi l’ordinamento sul posto e la non ricorsività, che lo rendono una buona scelta per insiemi di dati estremamente grandi.

Per contro è più lento degli ordinamenti per fusione e quick sort.

Segue il codice della funzione spostaGiù, che costruisce e ricostruisce il mucchio

Efficienza dell’algoritmo heap sort

Ordinamento per fusione (merge). Gli algoritmi di ordinamento visti finora presentano lo svantaggio che i tempi di esecuzione crescono molto in fretta al crescere del numero n di elementi da ordinare.

Un metodo completamente diverso di ordinamento e assi più veloce per n grande è l’ordinamento per fusione (merge sort), che viene descritto in maniera semplice facendo uso della ricorsività.

Esso applica la tecnica del divide et impera, consistente nel suddividere il problema di partenza in due problemi analoghi, ma di minore ampiezza. In questo caso:

1. si divide il vettore iniziale a in due sotto-vettori di uguali dimensioni, uno contenente le sue componenti di posto dispari (a1, a3, a5, ...), l’altro quelle di posto pari (a2, a4, a6, ...);

2. si ordina separatamente ciascuno dei due sotto-vettori (in maniera ricorsiva);

3. si fondono i due sotto-vettori ordinati.

1. Suddivisione. La suddivisione è un problema banale, e si ottiene con il semplicissimo ciclo for seguente:

for (k = 1 ; k <= n/2 ; k ++) b[k] = a[k*2];

Per risparmiare spazio, esso lascia le componenti di posto dispari nel vettore iniziale a, limitandosi a copiare quelle di posto pari nel vettore b.

2. Ordinamento. L’ordinamento può essere eseguito, per ciascuno dei due sotto-vettori a[k], b[k], con uno qualsiasi dei metodi visti in precedenza, tenendo conto delle relative osservazioni.

A questo punto è opportuno rinumerare le componenti del sotto-vettore a, in modo che gli indici coincidano con i primi termini della successione dei numeri interi, per esempio con il seguente ciclo for:

for (k = 1 ; k <= n/2 ; k++) a[k] = a[k*2 – 1];

3. Fusione. Anche la fusione risulta particolarmente semplice, in quanto si dispone ora di due vettori

a = a[1], ... , a[l]e

b = b[1], ... , b[m]

aventi per componenti dei numeri interi ordinati.

Si tratta di costruire un vettore v con l + m = n componenti in cui compaiono tutte le componenti di a e di b ordinate nella stessa maniera.

Supponiamo che l’ordinamento sia non decrescente, cioè che risulti

a[i] <= a[i+1] e b[i] <= b[i+1]

per qualsiasi valore di i.

1. si confronta a[1] con b[1] e si pone il minore (o uno qualsiasi, se sono uguali) in v[1].

2. se si è scelto a[1], si confronta a[2] con b[1], altrimenti si confronta a[1] con b[2],

3.si pone il minore in v[2].

Il procedimento continua fino a che si sono confrontate tutte le componenti, dopo di che il vettore a è stato ordinato nel vettore v.

Un algoritmo che risolve questo problema può essere il seguente:

Osserviamo che l’ordinamento per fusione richiede un numero di operazioni proporzionale a l + m = n.

Questo algoritmo presenta il vantaggio di essere leggermente più veloce dell’ordinamento heap per grandi liste.

Per contro richiede almeno il doppio di memoria di altri metodi, essendo di tipo ricorsivo.

Le implementazioni elementari fanno uso di tre vettori, uno per ciascuna metà del vettore di partenza, e uno per il vettore ordinato.

L’algoritmo seguente fonde i vettori sul posto, cosicché sono necessari solo due vettori.

Esistono versioni non ricorsive dell’ordinamento per fusione, ma sulla maggior parte delle macchine non producono alcun significativo miglioramento di prestazioni.

L’ordinamento per fusione si può eseguire in modo semplice se si rappresenta l’elenco dei dati da ordinare nella forma non già di un vettore, ma di una lista concatenata.

Questa è una struttura dati che si può pensare costituita da tante celle o record, ciascuna delle quali è suddivisa in due sotto-celle o campi.

Le celle sono rappresentate da rettangoli, la cui parte sinistra contiene un dato della lista, mentre la parte destra contiene un puntatore, rappresentato da una freccia.

Il puntatore è un dato che viene interpretato come l’indirizzo del record che segue quello attuale nell’ordinamento della lista.

Un punto al posto di un puntatore indica che quel record non punta ad altri record.

In tal modo risulta particolarmente semplice non solo cambiare l’ordine dei dati, ma anche eseguire su di essi le fondamentali operazioni di

• inserimento• cancellazione• ricerca.

Efficienza dell’algoritmo di ordinamento per fusione

Quicksort. Sebbene l’algoritmo shell sort sia decisamente migliore di quello per inserimento, non lo è in senso assoluto.

Infatti il migliore metodo di ordinamento per vettori fino a oggi conosciuto è senz’altro l’algoritmo pubblicato nel 1961 da C.A.R. Hoare.

Le sue prestazioni sono così spettacolari che il suo inventore lo chiamò Quicksort (ordinamento veloce).

Quicksort partiziona il vettore da ordinare in due sezioni, la prima di elementi “piccoli”, la seconda di elementi “grandi”. Quindi ordina separatamente gli elementi piccoli e i grandi, in modo ricorsivo.

Idealmente il partizionamento dovrebbe avvenire rispetto a un elemento, detto pivot, che sia la mediana dei valori dati.

Poiché però la ricerca della mediana richiede la scansione dell’intero vettore, e ciò rallenterebbe l’algoritmo, si può scegliere per semplicità come pivot l’elemento che occupa il posto mediano del vettore.

Nell’esempio seguente viene selezionato come pivot l’elemento del vettore contenente il valore 42.

Quindi si fa scorrere un indice, min, a partire dall’estremità sinistra del vettore fino a che incontra il primo elemento maggiore del pivot (in questo caso il 44), e un indice, max, a partire dall’estremità destra fino a che incontra il primo elemento minore del pivot (in questo caso il 18).

Questi due elementi vengono scambiati fra loro, dando luogo alla situazione seguente:

Il processo viene quindi ripetuto facendo scorrere gli indici verso il pivot, e individuando gli elementi 55 e 06

Anch’essi vengono scambiati, dando luogo alla situazione seguente:

Nel passo successivo i due indici min e max vengono a coincidere, e ciò determina la fine del processo, con tutti gli elementi a sinistra del pivot <= di esso, e tutti gli elementi alla sua destra >= di esso.

Quindi, come si suole dire, il vettore a è stato partizionato.

Il programma a fianco chiede di scrivere 8 numeri da tastiera, assume come pivot il quarto ed esegue su essi il partizionamento indicato in precedenza:

#include <stdio.h>#define NUMEL 8void main(void){ int min, max, pivot, temp, a[NUMEL]; for (min = 0; min < NUMEL; min++) { printf("Scrivi un numero: "); scanf("%d", &a[min]); } min = 0; max = NUMEL-1; pivot = a[3]; while (min < max) { while (a[min] < pivot) min ++; while (a[max] > pivot) max --; temp = a[min]; a[min] = a[max]; a[max] = temp; min ++; max --; } for (min = 0; min < NUMEL; min++) printf("\n%d ", a[min]); }

Naturalmente a questo punto il vettore non è stato ancora ordinato, ma solo partizionato.

Per ottenere l’ordinamento sarà però sufficiente applicare questo procedimento a entrambe le partizioni ottenute, poi alle partizioni delle partizioni e così via, fino a quando ogni partizione sarà costituita da un solo elemento.

Per meglio comprendere la struttura del programma definitivo, conviene scrivere un programma intermedio, che esegue il partizionamento chiamando dall’interno della funzione principale una funzione quickSort.

Questa si ottiene riscrivendo il programma precedente senza le istruzioni di ingresso e uscita, che vanno invece riportate nel programma principale.

Avremo quindi il seguente programma:

#include <stdio.h>#define NUMEL 8void main(void){ int i, a[NUMEL];

int quickSort(int []); /* dichiara quickSort */

for (i=0; i < NUMEL; i++) { printf("Scrivi un numero: "); scanf("%d", &a[i]); }

quickSort(a); /* chiama quickSort */

for (i = 0; i < NUMEL; i++) printf("\n%d ", a[i]);}

/* definisce la funzione quickSort */

int quickSort(int a[]){ int min, max, pivot, temp; min = 0; max = NUMEL-1; pivot = a[3]; while (min < max) { while (a[min] < pivot) min ++; while (a[max] > pivot) max --; temp = a[min]; a[min] = a[max]; a[max] = temp; min ++; max --; }}

Osserviamo che all’interno della funzione main() la funzione quickSort è dichiarata (con l’istruzione int quickSort (int []);) in modo da ricevere come parametro un vettore di interi e fornire un risultato intero (in questo caso un vettore).

A questo punto, il programma precedente va riscritto in modo che effettui una chiamata ricorsiva alla funzione di ordinamento. Vedremo più avanti il listato completo.

Per assegnare un valore al pivot, la funzione q_sort sceglie semplicemente il primo elemento (a[min]). I restanti elementi del vettore sono confrontati con il pivot, e messi alla sua sinistra o alla sua destra a seconda del loro valore.

Efficienza. Quicksort è un algoritmo di ordinamento non-stabile e non sul posto, in quanto richiede spazio nello stack.

Esso risulta poco efficiente nel caso in cui il vettore sia già ordinato.

In tale caso la funzione q_sort selezionerebbe l’elemento minore come valore da assegnare al pivot e dividerebbe il vettore con un elemento nella partizione di sinistra, e max-min elementi nell’altra.

Ogni chiamata ricorsiva a q_sort ridurrebbe solo di un’unità la dimensione del vettore da ordinare. Sarebbero quindi necessarie n chiamate ricorsive per effettuare l’ordinamento, portando a un tempo di esecuzione di O(n2).

Se però si scegliesse a caso un elemento come pivot, sarebbe estremamente improbabile il verificarsi del caso peggiore.

Se poi il pivot fosse la mediana di tutti i valori, che divide il vettore in due parti uguali, il vettore verrebbe diviso in due a ogni passo, e il tempo di esecuzione sarebbe O(n * lg n).

Quindi Quicksort ha complessità O(n * lg n) nel caso medio, e O(n2) nel caso peggiore.

Efficienza dell’algoritmo quick sort

Miglioramenti. All’algoritmo Quicksort di base si possono apportare diversi miglioramenti:

1. Nella funzione q_ sort si sceglie come pivot l’elemento centrale. Se la lista è parzialmente ordinata, questa risulta una buona scelta. Il caso peggiore si verifica quando l’elemento centrale è l’elemento più piccolo o più grande a ogni chiamata a q_sort.

2. Per vettori piccoli viene chiamata la funzione insertSort. A causa della ricorsività e di altri costi addizionali, Quicksort non

è un algoritmo efficiente su vettori di piccole dimensioni. Di conseguenza, ogni vettore con meno di 12 elementi viene ordinato usando l’ordinamento per inserimento. Il valore ottimale di questa soglia non è critico, e varia con la qualità del codice generato.

elementitempo (µs) dimensione stack

prima dopo prima dopo

16 103 51 540 28

256 1.630 911 912 112

4.096 34.183 20.016 1.908 168

65.536658.00

3460.73

72.436 252

La tabella seguente mostra le statistiche di tempo e l’uso dello stack prima e dopo l’introduzione dei miglioramenti.

3. Si ha ricorsività di coda quando l’ultima istruzione di una funzione è una chiamata alla funzione stessa. La ricorsività di coda può essere sostituita dall’iterazione, ottenendo un utilizzo migliore dello stack.

4. Dopo che il vettore è stato partizionato, la partizione più piccola viene ordinata per prima. Ciò determina un migliore utilizzo dello stack, considerato che le partizioni più piccole sono ordinate - e quindi eliminate - più velocemente.

Confronto. Come conclusione confrontiamo i principali algoritmi di ordinamento trattati: per inserimento, shell sort, e quicksort. Ci sono molti fattori che influenzano la scelta di un algoritmo di ordinamento:

Ordinamento stabile. Ricordate che un algoritmo di ordinamento stabile lascia gli elementi uguali nella stessa posizione relativa al termine dell’ordinamento. L’ordinamento per inserimento è l’unico algoritmo stabile fra quelli trattati.

Spazio. Un algoritmo sul posto non richiede memoria aggiuntiva per portare a termine l’ordinamento. Sia l’ordinamento per inserimento sia shell sort sono algoritmi sul posto. Quicksort richiede spazio nello stack per la ricorsività, quindi non è un algoritmo sul posto. L’invenzione di artifici ha ridotto notevolmente il tempo richiesto dall’algoritmo.

• Tempo. Non è difficile che il tempo richiesto per ordinare un insieme di dati raggiunga ordini di grandezza astronomici, come abbiamo visto nella tabella delle funzioni di n. La tabella seguente mostra le complessità relative di ogni metodo.

metodo istruzionicomplessità

mediacomplessità

del caso peggiore

inserimento 9 O(n2) O(n2)

shell sort 17 O(n1.25) O(n1.5)

quicksort 21 O(n lg n) O(n2)

Nella tabella seguente sono riportati i tempi di ordinamento, partendo da un insieme di dati ordinati in modo casuale.

elementi da ordinare inserimento shell quicksort

16 39 µs 45 µs 51 µs

256 4.969 µs 1.230 µs 911 µs

4.096 1,315 sec 0,033 sec 0,020 sec

65.536 416,437 sec 1,254 sec 0,461 sec

Semplicità. La tabella dellavideata precedente mostra il numero di istruzioni necessarie per ogni algoritmo. Algoritmi più semplici portano a meno errori in fase di codifica.

Ordinamento esterno

GIi algoritmi di ordinamento visti finora prevedevano tutti i seguenti passi:

• caricare i dati in memoria• ordinare i dati (in memoria), quindi• scrivere i risultati.

Essi non possono venire applicati quando i dati da ordinare non trovano posto nella memoria principale del computer e sono, invece, memorizzati in un dispositivo periferico di memoria secondaria, per esempio un’unità a nastro.

In questo caso i dati sono rappresentati con un file sequenziale, la cui caratteristica è di rendere accessibile una, e una sola, componente in qualsiasi momento.

Si tratta di una severa restrizione, a confronto con le possibilità che offre la struttura vettore, che richiede una tecnica di ordinamento esterno.

La tecnica più importante è l’ordinamento per fusione, che combina due (o più) sequenze ordinate in una sola mediante ripetute selezioni tra le componenti che sono correntemente accessibili.

L’algoritmo di ordinamento detto fusione diretta consiste nei seguenti quattro passi:

1. si suddivide la sequenza a in due metà, chiamate b e c;

2. si fondono b e c combinando elementi singoli in coppie ordinate;

3. detta a la sequenza ottenuta, si ripetono i passi 1 e 2, questa volta fondendo coppie ordinate in quadruple ordinate;

4. si ripetono i passi precedenti, fondendo quadruple in ottuple e così si continua, raddoppiando ogni volta la lunghezza delle sottosequenze che vengono combinate, fino al completo odinamento della sequenza iniziale.

Consideriamo, per esempio, la seguente lista

Nel passo 1. essa viene suddivisa nelle nelle due sequenze

La fusione delle singole componenti (che sono sequenze ordinate di lunghezza 1) in coppie ordinate dà luogo a

Suddividendo un’altra volta nel mezzo e combinando le coppie ordinate otteniamo:

Una terza suddivisione, seguita dalla fusione, produce finalmente il risultato desiderato:

Ogni operazione che tratta l’intero insieme dei dati viene chiamata fase. Il più piccolo sottoprocesso che, per ripetizione, costituisce il processo di ordinamento, viene chiamato passata o stadio.

Nell’esempio precedente sono state necessarie tre passate per ordinare, ognuna delle quali era costituita da una fase di suddivisione e da una di fusione.

Per potere eseguire l’ordinamento sono necessari tre nastri; perciò il processo viene chiamato fusione con tre nastri.

Fusione bilanciata (a una fase). In verità, le fasi di suddivisione non contribuiscono all’ordinamento, poiché esse non permutano in alcun modo gli elementi. In un certo senso, sono azioni improduttive, anche se costituiscono la metà di tutte le azioni di copia.

Ebbene, le fasi di suddivisione possono essere eliminate, combinandole con quelle di fusione.

Invece di creare una sola sequenza, il risultato del processo di fusione viene immediatamente redistribuito su due nastri, che saranno le sorgenti per la passata successiva.

Questo metodo viene chiamato ordinamento per fusione bilanciata o fusione a una fase, in antitesi al precedente ordinamento a due fasi.

È evidente che il nuovo metodo è superiore al vecchio, perché necessita solo della metà di operazioni di copia.

Il prezzo di questo miglioramento è un quarto nastro.

Aho, Alfred V. and Jeffrey D. Ullman [1983].Data Structures and Algorithms.Addison-Wesley, Reading, Massachusetts.

Cormen, Thomas H. [2001].Introduction to Algorithms.McGraw-Hill, New York.

Knuth, Donald E. [1998].The Art of Computer Programming, Volume 3, Sorting and Searching.Addison-Wesley, Reading, Massachusetts.

Pearson, Peter K. [1990].Fast Hashing of Variable-Length Text Strings.Communications of the ACM, 33(6):677-680, June 1990.

Pugh, William [1990].Skip Lists: A Probabilistic Alternative to Balanced Trees. Communications of the ACM, 33(6):668-676, June 1990.

Bibliografia

Algoritmo di cifratura RSA

L’algoritmo RSA è stato pubblicato nel 1978 da R. L. Rivest, A. Shamir e L. Adelman (da cui il nome), sebbene la sua prima descrizione si debba a James H. Ellis (1970) e le sue prime implementazioni pratiche a C. C. Cocks (1973) e Malcom J. Williamson (1974).

Ellis, Cocks e Williamson lavoravano all’epoca nel Communications Electronics Security Group delle forze armate britanniche.

RSA è il più moderno algoritmo di cifratura, ed è applicato per garantire un elevato livello di sicurezza ai cosiddetti documenti elettronici, in particolare nel caso di trasmissione attraverso reti telematiche.

La cifratura avviene di solito sostituendo i caratteri di cui è composto un messaggio m, detto messaggio in chiaro, con altri in base a un determinato criterio, detto chiave; si produce così un messaggio cifrato c.

L’operazione inversa di decifrazione avviene sostituendo i caratteri del messaggio cifrato c in modo da riottenere quello originario in chiaro m.

Questa seconda operazione può essere effettuata usando la stessa chiave impiegata per la cifratura – e allora si parla di chiavi simmetriche – oppure una chiave diversa - e allora si parla di chiavi asimmetriche.

L’algoritmo RSA è di tipo asimmetrico, in quanto usa due chiavi diverse, una per cifrare i messaggi, l’altra per decifrarli; ciò fa sì che il mittente e il destinatario non si debbano scambiare la chiave di cifratura/decifrazione prima di potere comunicare, con un evidente vantaggio in termini di sicurezza.

Infatti la chiave di cifratura può tranquillamente essere resa pubblica, ad es. mettendola a disposizione su Internet o stampandola su un bollettino, in quanto la sua conoscenza non permette affatto (o permette con molta difficoltà) di risalire alla chiave di decifrazione, che deve invece rimanere privata (cioè segreta).

In altri termini, la conoscenza della chiave pubblica di una persona A permette a chiunque di mandare un messaggio cifrato ad A, messaggio che solo A potrà decifrare con la propria chiave privata, ma non fornisce alcuna informazione sulla chiave privata di A.

La cifratura di un testo richiede dapprima che esso sia convertito in una serie di numeri (digitalizzazione); questi potrebbero essere per esempio i codici ASCII o EBCDIC dei suoi caratteri.

A questo punto, come indica la figura,

il mittente A usa la chiave pubblica del destinatario B per cifrare il messaggio m da inviargli; ottiene così il messaggio cifrato c, che può essere inviato senza alcuna precauzione a B.

Questi impiega la propria chiave privata per decifrare il messaggio cifrato c, ricostruendo quello originario m.

Costruzione della coppia di chiavi asimmetriche. La costruzione delle due chiavi di cifratura e decifrazione si basa sul fatto che, mentre è abbastanza semplice moltiplicare tra loro due numeri primi anche molto grandi, l’operazione inversa di trovare i fattori primi di un numero abbastanza grande è assai più difficile.

La costruzione avviene attraverso i seguenti passi:

1. si moltiplicano tra loro due numeri primi p, q sufficientemente grandi, ottenendosi come prodotto il numero n

[per fare un esempio semplice, supponiamo p = 3, q = 5, quindi p*q = n = 15]

2. si sceglie un intero D che non sia divisibile né per p-1 né per q-1

[nel nostro esempio scegliamo D = 11, che non è divisibile né per 2 né per 4].

[1] Ricordiamo che la funzione modulo, indicata con mod, indica il resto della divisione di due numeri interi. Perciò la precedente condizione si esprime dicendo che deve risultare E*D = 1 mod(p-1)*(q-1)

3. si calcola un intero E tale che il resto della divisione di E*D per (p-1)*(q-1) sia uguale a 1[1].

Ciò equivale a risolvere il seguente problema:

k*(p-1)*(q-1)+1E = --------------- D

Trovare un valore di k tale che l’espressione

abbia un valore intero

Osserviamo che tale equazione è detta diofantea, e non può essere risolta con una formula, ma solo per tentativi, cioè sostituendo a k i successivi valori 1, 2, 3,... finché si trova per E un valore intero.

L’operazione si può eseguire automaticamente con un programma di foglio elettronico, trovandosi le soluzioni dell’equazione indicate in tabella.

k E

4152637...

3111927...

Scegliamo, ad es., k = 4 a cui corrisponde E = 3.

La chiave pubblica di cifratura, da comunicare, è la coppia

(E,n).

La chiave privata di decifrazione, da tenere segreta, è la coppia

(D,n).

[1] In termini matematici ciò si esprime dicendo che c = mE mod n[2] In termini matematici ciò si esprime dicendo che m = cD mod n

Cifratura e decifrazione. Il messaggio cifrato, c, è il resto della divisione di mE per n [1].

Il messaggio originario, m, è il resto della divisione di cD per n [2].

Se scegliamo come chiave pubblica la coppia

(E = 3, n = 15)

come chiave privata la coppia

(D = 11, n = 15)

e come messaggio m i primi 10 numeri interi, otteniamo i valori indicati in Tabella.

Mettiamoci adesso dalla parte di un cracker il quale intercetti il messaggio cifrato, c, e voglia da esso ricavare il messaggio originario, m.

Dato che egli sa che E=3 e che n=15, tutto ciò di cui ha bisogno è di conoscere i due numeri primi, p, q, che moltiplicati tra loro danno 15.

Infatti dalla conoscenza di p, q, troverebbe p-1 (=2) e q-1 (=4), e da essi risalirebbe facilmente al numero D, non divisibile né per 2 né per 4.

Come abbiamo visto, una volta trovato D il messaggio originario, m, si ottiene da quello cifrato, c, dalla formula

m = mod(cD, n)

già usata nella Tabella precedente.

Ebbene, la inviolabilità dei messaggi cifrati con l’algoritmo RSA risiede proprio nella difficoltà di fattorizzare numeri che siano il prodotto di numeri primi molto grandi (ricordiamo che di recente è sato scoperto il numero primo più grande, lungo oltre 9 milioni di caratteri).