In questo paragrafo verranno esaminate alcuni tipi di elaborazioni sui dati. Alcuni di essi, per la loro generalità, nel tempo sono diventati parte del Sistema Operativo, o sono disponibili come programmi di utilità. Come premessa si definisce cosa si intende per algoritmo.
Algoritmo è un insieme di istruzioni (procedura) per eseguire una trasformazione di dati. Le proprietà di un algoritmo sono:
§ le istruzioni sono precise
§ le istruzioni sono eseguibili
§ l'algoritmo ha dei dati che elabora e produce dei dati
§ l'algoritmo deve terminare
§ l'algoritmo deve essere generale, cioè deve poter agire su dati diversi del medesimo tipo
Esempi di algoritmo sono: la ricerca del minimo comune multiplo di due numeri, la sostituzione dei caratteri A con CB in una stringa di caratteri. Non è un algoritmo le istruzioni per sommare 2 con 2.
La compressione è una tecnica mediante la quale si riduce la dimensione dei dati per occupare meno spazio sui supporti di memorizzazione, e per ottenere maggior velocità di trasferimento dei dati, sia da disco a memoria, che fra un sistema ed un altro. La compressione sfrutta la ridondanza esistente nelle informazioni, specialmente testuali (le lettere dell'alfabeto hanno una diversa frequenza). Nel caso di dati testuali un semplice algoritmo di compressione, dovuto a Huffmann[1], codifica le lettere con un numero di bit proporzionale alla loro frequenza nell'informazione, qui di seguito vi è un esempio di codifica:
A 1000
B 1001
C 101
D 00
…..
Il metodo di compressione di Huffman presuppone la conoscenza del tipo di dati da comprimere. Un metodo di compressione che prescinde dalla conoscenza a priori dei dati è stato proposto da Lempel e Ziv[2].
L'algoritmo di Lempel Ziv con modifiche proposte da Welch (LZW)[3], genera una tabella, detta dizionario, i cui primi 256 elementi contengono i 256 caratteri possibili, nell'ordine indicato dalla tabella dei codici ASCII; nei successivi elementi verranno poste le stringhe che l'algoritmo estrae dal testo da comprimere, la posizione che una stringa ha nel dizionario è detta codeword, ad esempio la codeword di A è 65, perché il suo valore ASCII è 65.
L'analisi e l'estrazione delle stringhe dal testo T avviene secondo la procedura seguente:
Si indichi con + il concatenamento di due stringhe, T è il testo da comprimere, α è una sottostringa del testo già presente nel dizionario. Inizialmente α contiene T(1) il primo carattere del testo (che per costruzione è ovviamente nel dizionario).
per ogni carattere T(i) successivo al primo si applica la procedura seguente:
si verifica se la stringa α+T(i) è presente nel dizionario,
se è presente
α+T(i) diventa la nuova stringa α
altrimenti
la stringa α+T(i) viene inserita nel dizionario e
si scrive in output la posizione della stringa α nel dizionario e
il carattere T(i) diventa la nuova stringa α.
Alla fine della procedura si scrive in output la posizione nel dizionario dell'ultima stringa α.
Durante la ricostruzione del testo viene rigenerato il dizionario, secondo la procedura seguente:
Si genera il dizionario contenente i 256 caratteri possibili, come per la procedura di compressione.
α è una sottostringa del testo, inizialmente α contiene D(C(1)), avendo indicato con C(1)la prima codeword e D(C(1)) il carattere nel dizionario alla posizione indicata dalla codeword C(1).
per ogni codeword C(i) successiva alla prima si applica la procedura seguente:
si verifica se esiste D(C(1)),
se esiste
si scrive la stringa α in output e
si inserisce nel dizionario α+il primo carattere della stringa D(C(i)) e
la stringa DC(i) diventa la nuova stringa α.
altrimenti
si costruisce α' come α + il primo carattere di α e
si inserisce nel dizionario α' e
si scrive la stringa α in output e
la stringa α' diventa la nuova stringa α.
Alla fine della procedura si scrive in output la stringa α.
Come si può notare dall'algoritmo, la compressione avviene se ci sono almeno delle coppie di simboli che si ripetono, in caso contrario si hanno delle sequenze di simboli incomprimibili. Detta n la dimensione dell'alfabeto[4], la stringa più lunga incomprimibile è di n2+1 simboli[5], infatti si ha:
n coppie doppie (AA,BB,..),
n(n-1) altre coppie (AB,BA,AC,CA,…), cioè le disposizioni di n elementi a due a due: n!/(n-2)! = n(n-1)
quindi n + n(n - 1) = n2 coppie
in una stringa di n2 + 1 simboli si possono estrarre n2 coppie consecutive (AABBA -> AA,AB,BB,BA).
(vedasi complementi per la descrizione di una procedura per generare effettivamente una tale massima stringa incomprimibile).
Se, ad esempio, l'alfabeto è {A,B,C}, le n2 = 9 coppie di simboli sono: {AA,BB,CC,AB,BA,AC,CA,BC,CB} e una stringa incomprimibile di 10 simboli è "AABACBBCCA".
La dimensione massima delle stringhe incomprimibili determina anche l'ampiezza delle codeword
La posizione di una stringa nel dizionario è un numero che dipende dall'ampiezza del dizionario, questo, se L è la lunghezza del testo da comprimere, contiene al più 256 + L-1 elementi. Quindi ogni codeword è espressa al massimo con log2(254 + L) + 1 bit.
Un'ulteriore riduzione dei dati di output si ottiene scrivendo le codeword col minimo numero di bit necessari: per il primo simbolo la codeword è di 8 bit, dal secondo in poi la codeword potrebbe essere di 9 bit (es. AAA che genera il dizionario con 257 elementi, in cui il 257-esimo è AA.). La tabella seguente illustra le lunghezze delle codeword per i vari spezzoni di testo da comprimere:
1 8 bit
da 2 a 256 9 bit
da 257 a 512 10 bit
da 513 a 1024 11 bit
…………………….
Ottenimento della massima stringa incomprimibile
Sia n il numero dei simboli, e si abbia una stringa T con tutti i simboli, la stringa α, inizialmente vuota, viene costruita secondo la procedura:
Per ogni simbolo T (i) nella lista, la stringa è
i) α = α + T (i)
ii) e poi per ogni simbolo T (j) con j > i
α = α + T (i) + T (j)
iii) Alla fine α = α + T (1)
Esempio
Sia {A,B,C} l'insieme di simboli; la generazione della stringa è (sottolineato l'ultimo o gli ultimi simboli inseriti):
"A" per la i)
"AAB", "AABAC" per la ii)
"AABACB" per la i)
"AABACBBC" per la ii)
"AABACBBCA" per la iii)
I metodi di compressione fin qui descritti non provocano perdita di informazione, con la decompressione si riottengono i dati originali; per informazioni grafiche o sonore, generalmente di grandi dimensioni, è possibile effettuare delle compressioni, o meglio compattazioni, in cui vengono eliminate parti di informazione poco significative, quali frequenze non udibili dall'orecchio.
La crittografia o cifratura è un particolare tipo di trasformazione di dati con lo scopo di renderli illeggibili da chi non è autorizzato. La sicurezza dei sistemi di cifratura si basa sulla difficoltà di calcolo di certe funzioni: le trasformazioni operate nei dati sono così complesse da rendere economicamente proibitivo il processo di decodifica. Infatti per forzare questi sistemi occorrerebbe disporre di una capacità di calcolo pressochè illimitata, ed in pratica essi risultano inattaccabili.
Non è ancora stata dimostrata la sicurezza computazionale degli attuali sistemi; è sperabile che gli sviluppi della teoria della complessità riescano a fornire gli strumenti necessari a costruire crittosistemi dotati di sicurezza computazionale e nei quali si possa garantire l'assenza di difetti nascosti. I sistemi attuali si basano su un gruppo di problemi matematici caratterizzati da un certo tipo di non trattabilità computazionale e sono detti crittosistemi a chiave pubblica[6].
L'idea di base è di sfruttare quelle funzioni che sono facilmente calcolabili, ma le cui inverse non lo sono, ad esempio è banale calcolare il prodotto di due numeri primi molto grandi, viceversa l'operazione che dato il prodotto ricava i due moltiplicatori è teoricamente semplice, ma lunga da effettuare se il numero è molto grande.
Nell'algoritmo a chiave pubblica RSA chi vuole ricevere messaggi cifrati si procura due numeri primi p e q molto grandi, ed un numero E casuale grande, quindi rende pubblici i due numeri n = p·q ed E.
Il mittente suddivide il testo da cifrare in blocchi tali che il loro valore numerico sia inferiore ad n[7]. Il generico blocco P viene trasformato nel valore C tramite l'operazione:
C = (PE mod n)
Da C il destinatario ricava P, utilizzando un numero D che lui solo conosce, tale che:
P = (CD mod n)
Cioè:
CD = (PE·D mod n) (per la iv) del par. 1.2.2. an ≡ bn mod m (se a ≡ b mod m )
P = (PE·D mod n)
Ciò vale se ED - 1 è un multiplo di (p-1)·(q-1)[8]:
Per ogni numero primo p e ogni intero positivo a vale (piccolo teorema di Pierre de Fermat 1601-1665):
ap - a è divisibile per p, allora essendo n = pq con p e q numeri primi, valgono le relazioni:
ap - a = c1·p e aq - a = c2·q
a·(ap-1 – 1) = c1·p e a(aq-1 – 1) = c2·q
per la iv) del par. 1.2.2. si può elevare ap-1 e aq-1 rispettivamente a (q-1) e (p-1):
a·(a(p-1)·(q-1) – 1) = c1'·p e a·(a(q-1)·(p-1) – 1) = c2'·q
la parte destra delle due relazioni è uguale quindi anche c1'·p = c2'·q = c·p·q
a·(a(p-1)·(q-1) – 1) = c·p·q
in quest'ultima relazione, sostituendo ad a P ed eliminando le parentesi, si ottiene:
P(p-1)·(q-1)+1 – P = c·p·q
poichè P < p·q = n , P è il resto
della divisione di P(p-1)·(q-1)+1 = PE·D per n ■
Per garantire l'autenticità del mittente, questi, oltre al testo cifrato come su descritto, invia una " firma" cioè il testo, o una parte di esso, trasformandolo tramite la propria chiave di decifrazione D: F = (PD mod n), quindi utilizza la chiave pubblica del destinatario per cifrare la firma[9]. Il ricevente prima decifra, poi tramite la chiave pubblica del mittente, riporta in chiaro la firma.
L'occultamento di informazioni o steganografia si differenzia dalla crittografia in quanto il messaggio, (eventualmente crittografato), viene nascosto in altre informazioni. Le informazioni ideali per nascondere messaggi sono le immagini o i suoni digitalizzati.
In una immagine grafica, in formato BitMap (v. il par. 7.3.1.1.), ad alta risoluzione cromatica, per ogni pixel o punto, ci sono 8 bit per ogni colore fondamentale, in tutto 24 bit per ogni pixel. L'informazione da nascondere si inserisce sul bit meno significativo del colore. L'effetto di questo inserimento è praticamente non rilevabile, in quanto la variazione è inferiore allo 0,4%. La quantità di informazione che può essere nascosta è buona: un'immagine 100 x 100 puo ospitare un testo di 3750 Bytes. Nei file di suono la tecnica è analoga e, date le dimensioni di tali file, si possono nascondere una gran quantità di informazioni.
L'ordinamento è un'operazione che si applica ad insiemi omogenei di dati, fra i quali intercorra una relazione di ordine; l'effetto è di individuare un'elencazione degli elementi dell'insieme tale che ogni elemento successivo al primo soddisfa la relazione d'ordine col precedente. Nella pratica informatica, in genere, per ordinamento si intende l'ordinamento alfabetico o lessicografico. Vi sono molti algoritmi di ordinamento, alcuni molto semplici (ed inefficenti), altri più efficenti.
Durante l'ordinamento le informazioni sono spostate anche molte volte prima di raggiungere la loro posizione finale, per cui spesso se la parte dell'informazione per la quale c'è la relazione d'ordine (chiave) è significativamente più piccola di tutta l'informazione conviene non l'informazione originale, ma l'insieme di chiave e puntamento all'informazione: esemplificando invece di ordinare l'archivio dei libri per autore, ordiniamo l'archivio formato da autore e posizione del libro nello scaffale.
E' un algoritmo molto semplice, sebbene non efficiente. Sia n è il numero degli elementi da ordinare:
i) se n = 1, l'ordinamento è finito,
ii) si scorrono gli elementi da ordinare confrontando ogni elemento con il successivo, se il successivo è minore viene scambiato di posto col precedente,
iii) dopo l'ultimo confronto (ed eventuale scambio), l'elemento maggiore si trova in fondo,
iv) se ci sono stati degli scambi, si ripete dal punto i), sui primi n – 1 elementi.
L'algoritmo Shellsort è stato uno dei primi metodi di ordinamento scoperti[10], ed è anche fra i più semplici da implementare. Qui di seguito è illustrato un caso particolare dell'algoritmo prima di esaminarne la forma generale.
i) Per ogni elemento ai (1 < i <= numero elementi) dell'insieme da ordinare, a partire dal secondo, in avanti:
ii)
si memorizza ai
e si cerca all'indietro il primo elemento minore di ai,
iii)
ogni elemento
maggiore di ai viene spostato di una posizione in avanti,
iv)
al posto dell'ultimo
elemento spostato si inserisce ai.
Se i = 2, l'algoritmo eventualmente sposta a1 al posto di a2
e poi a2 memorizzato al posto di a1, quindi i primi 2
elementi sono in ordine.
Se i primi ai elementi sono ordinati,
per la la procedura descritta l'elemento a1+1 rimane al suo poste se
è maggiore di a1, altrimenti si inserisce al posto corretto quindi i
primi a1+1 elementi sono ordinati, ne segue che quando la procedura
è stata applicata all'ultimo elemento, tutto l'insieme è ordinato.
Nell'algoritmo ShellSort c'è una serie di iterazioni con un numero variabile h, tale che:
i) Per ogni elemento ai (h < i <= numero elementi) dell'insieme da ordinare, a partire dal h+1-esimo, in avanti:
ii)
si memorizza ai
e si cerca all'indietro, nelle posizioni i-h, i-2h,.. il primo elemento minore di ai,
iii)
ogni elemento
maggiore di ai viene spostato di h posizioni in avanti,
iv) al posto dell'ultimo elemento spostato si
inserisce ai.
L'ultima iterazione è effettuata con h = 1.
L'effetto delle iterazioni è di mettere parzialmente in ordine l'insieme; di fatto si diminuiscono gli spostamenti rispetto al solo caso con h = 1.
La determinazione di quali valori utilizzare per h è una questione ancora aperta, l'algoritmo originale utilizzava le potenze di due, una sequenza largamente utilizzata, proposta da Knuth è 1, 4, 13, 40, 121, … cioè:
h1 = 1
hi+1 = 3·hi + 1
La ricerca di una informazione, ad esempio il salario dell’impiegato "Jean Valjean", si ottiene leggendo ogni riga della tabella per verificare se il NOME è "Jean Valjean". Ciò puo essere molto costoso in termini di tempo, se la tabella è molto ampia (migliaia di righe). E' per questo motivo che si può associare ad una tabella uno o più indici. L’indice è un archivio ordinato con due campi:
|
INDICE |
Campo o campi di ricerca.
Il campo INDICE è ordinato |
|
POINTER
ALL'INFORMAZIONE |
Posizione
dell'informazione sul disco |
L'archivio indice è mantenuto nell’ordine del o dei campi di ricerca, per
esempio in ordine alfabetico. Ciò permette di trovare l'informazione voluta con
poche letture del disco.
Qui di seguito è esemplificato un metodo di ricerca detto dicotomico. Si debba rcercare “KIREMBA” in un archivio che ha un indice sul campo CITTA.
§ Si esamina la riga a metà dell'archivio
§ Se la riga contiene “KIREMBA”, l'informazione è stata trovata
§ Se la riga contiene un nome di città superiore, per esempio “NGOZI”, allora, con lo stesso procedimento, si cerca nella prima metà,
§ Se la riga contiene un nome di città inferiore, per esempio “GITEGA” , allora, con lo stesso procedimento, si cerca nella seconda metà
§ Se l’intervallo di ricerca è di una riga, si finisce senza aver trovato l'informazione.
Se si è trovato, si legge direttamente la riga con “KIREMBA”[11].
I sistemi che effettuano il riconoscimento ottico di caratteri (Optical Character Recognition) consentono di convertire dei files con immagini di testo in files con il testo convertito, generalmente, in formato ASCII.
I sistemi OCR sono formati da uno scanner ottico e un software, piuttosto sofisticato, per analizzare le immagini. I sistemi più evoluti sono in grado di riconoscere testi con una gran varietà di tipi di carattere (font), e all'occorrenza possono essere "addestrati" a riconoscere nuovi tipi di font. Il riconoscimento di testi manoscritti presenta ancora notevoli difficoltà.
Martin E. Hellman
La crittografia a chiave pubblica
Le scienze n. pag. 110-121
Debra A. Lelewer and
Daniel S. Hirschberg
Data Compression
http://www1.ics.uci.edu/~dan/pubs/DataCompression.html
Robert Sedgewick
Analysis of Shellsort and
Related Algorithms
Princeton University
[1] Huffman D.A. " A method for the
construction of minimum redundancy code" Proc. IRE,40,1952
[2] Ziv J., Lempel A. " A universal algorithm for sequential data compression" IEEE Trans. On Inf. Theory 23(3) 1977.
[3] il brevetto è proprietà della Unisys, a cui occorre chiedere la licenza per l'utilizzo in applicazioni commerciali.
[4] Normalmente n = 256
[5] le stringhe più lunghe di tale valore sono
quindi comprimibili.
[6]
Per la prima volta
proposti da Ralph Merkie, Whitfield Diffie e Martin E. Hellman alla Stanford University. L'algoritmo
descritto si deve a Rivest, Shamir e Adleman.
[7] Si tenga presente che qualsiasi stringa di
caratteri è una sequenza di bit 0 e 1, quindi un numero binario. Ad esempio una
stringa di 10 bytes con tutti i bit
uguali ad 1 corrisponde al numero 280 - 1.
[8] E' il valore della funzione φ(n) di
Eulero. φ(n) è il numero di divisori primi di n minori di n, se n è un
numero primo, essa vale n – 1, se n è il prodotto di due numeri primi p e q,
vale (p-1)(q-1) (v. [FF] Vol 1 pag 271).
[9] Senza questa cifratura, conoscendo chi invia
i dati, sarebbe possibile decifrare la firma.
[10] Donald Lewis Shell [CACM, July, 1959, pages
30-32]
[11] Nel caso peggiore si fanno log2N + 1 letture su disco, per esempio se N = 10000 righe, le letture sono 15.