... Dalla teoria alla pratica.
Questa lezione inaugura la rotta di avvicinamento al computer come oggetto reale, cercando di comprendere come applicare gli algoritmi visti a lezione al mondo reale del computer.
In primo luogo bisogna riconoscere che anche i semplici programmi che abbiamo scritto possono essere (precisamente come le lettere e i caratteri) codificati con dei numeri. I programmi stessi quindi diventano dei dati e trovano una loro collocazione fisica nella memoria, nella stessa memoria che abbiamo finora considerato dedicata solo ai dati. (i programmi SONO dati, in fin dei conti. Dati che vengono interpretati in un certo modo dal computer, che vengono interpretati come istruzioni ed eseguite sugli altri dati presenti in memoria)
Per ragioni di tipo tecnologico, le prime memorie erano molto contenute ed estremamente costose, quindi se da una parte la teorizzazione di una memoria infinita è un comodo concetto, dall'altra è decisamente irrealistica, almeno per quello che erano i computer ai loro primordi. Ma sono queli che hanno dato il modello di quelli attuali quindi, anche se la tecnologia cambia rapidamente, lo schema base di funzionamento è ancora quello degli anni '50.
Programmi e dati devono essere in memoria per poter operare insieme, ma non tutti i dati devono necesariamente stare in memoria nello stesso tempo. Per esempio, se i nostri dati fosero i nomi degli iscritti all'università, non sarebbe sempre necessario averli interamente in memoria. Potremmo pensare di scriverli da qualche parte con un apparecchio esterno, e richiamarli ogni volta che diventano necessari, e magari solo quei dati che ci sono necessari. Questo "apparecchio esterno" è quello che oggi si chiama Hard Disk. Quando vogliamo che un dato resista all'"azzeramento" della memoria che avviene ogni volta che si toglie la corrente al computer, bisogna registrarlo su un qualche supporto che abbia la caratteristica di poterlo mantenere per un tempo indeterminato, e di poterlo recuperare quando è necessario. Questa modalità di gestione della memoria è utile anche per ragioni di efficienza, e permette di non sprecare una risorsa preziosa come la memoria operativa (la RAM, Random Access Memory). I programmi quindi, attraverso specifiche istruzioni, sono in grado di scrivere da qualche parte il contenuto di alcune aree della propria memoria, e di scrivere nella memoria valori letti dal disco. Questa serie di operazioni però è molto impegnativa, e non vorremmo dover scrivere in ogni programma delle istruzioni dettagliate su come fare. Sarebbe utile che ci fosse una specie di "servizio" cui noi chiediamo di salvare una certa area di memoria sul disco, e questo lo fa a nostro nome.
Inoltre nei nostri esempi è semrpe stato dato per implicito che un computer potesse eseguire solo un programma. Nella nostra espeirnza quotidiana sappiamo che così non è, che in un computer più programmi possono essere eseguiti contemporaneamente. Come è possibile ottenere questo risultato? La soluzione consiste nel creare un mega-programma il cui funzionamento sia quello fondamentale, e che si occupi di gestire tutte le risorse connesse al computer, come le periferiche, ma anche gestire il funzionamento dei programmi veri e propri del genere che noi abbiamo visto negli esempi. Questo programma deve essere il primo che viene eseguito e deve rimanere sempre in esecuzione. Deve permettere di recuperare dati dall'hard disk e anche programmi (che, per quanto detto all'inizio SONO dati anche loro). Il nome di questo programma speciale è sistema operativo.
Il sistema operativo permette l'esecuzione (apparentemente) contemporanea di diversi programmi, compreso se stesso. La simulazione della contemporaneità di esecuzione avviene perché il sistema operativo effettua fondamentalmente le seguenti operazioni:
1) gestisce la memoria RAM disponibile del sistema, creando delle sotto-aree che vengono assegnate ai programmi (i programmi vedono questo assegnamento come se cominciasse dalla cella 1 quindi il funzionamento dei programmi dentro un sistema operativo è identico al funzionamento dei programmi che abbiamo visto finora negli esempi).
2) gestisce tutti i programmi in esecuzione, e li porta avanti "in parallelo" concedendo a ognuno di loro un tempo di esecuzione (di frazioni di secondo) per poi bloccarlo e dare il controllo al programma successivo. In questo modo è possibile far funzionare "contemporaneamente" più programmi, anche se in ogni momento solo uno è in effetiva esecuzione (il processore può eseguire solo una istruzione alla volta!)
Quindi ogni programma in funzione nel sistema operativo, dal "proprio" punto di vista è l'unico: ha una sua memoria e vene eseguito seguendo il proprio programma.
Il sistema operativo si prende in carico la gestione di tutti quegli aspetti estranei (o non strettamente inerenti) al programma vero e proprio: la lettura della pressione dei tasti nella tastiera (e la trasmissione al programma opportuno di quei tasti), il movimento del mouse (con il clic, anche in questo caso da applicare al programma "giusto"), l'accesso al disco e alle altre periferiche, la visualizzazione, la stampa e così via.
Parlando di ambienti dove è possibile eseguire più di un programma, si può pensare di estendere una delle caratteristiche che sono state elencate sopra: la possibilità di registrare parti della memoria su un disco. Come si è ripetuto più e più volte, i dati in sé non sono che numeri. La memoria non è altro che una lunghissima sequenza di numeri privi di senso intrinseco. La semantica di quei numeri è data dal programma che li crea e gestisce, in base a come li manipola e organizza. Quindi quei dati, perché creati e gestiti unicamente da un programma, sarebbero in un certo senso di sua esclusiva proprietà visto che il loro significato è definito solo mediante l'uso che ne fa il programma corrispondente. Sarebbe però interessatne cercare il modo di memorizzare questi dati secondo un formato che contenesse già in sé almeno alcune delle informazioni riguardo i dati. Per esempio, se il programma in esecuzione fosse una rubrica, nella memoria potremmo leggere MARCO/TONTI/MARCO.TONTI@UNISALENTO.IT dove per nostra convenzione decidiamo che la barra separa i diversi campi. Senza avere l'informazione della barra però un programma, o una persona, non avrebbe nessuna informazione diretta sul significato di quella sequenza di simboli (se ci fossero stati nomi strani come SMEDSLUND o DIJKSTRA non sarebbe stato tanto chiaro che si trattava di un nome! oppure se fosse stato SERGIO/SALVATORE non avremmo avuto modo di sapere, senza guardare nel programma, qual è il nome e qual è il cognome). Cerchiamo quindi un modo per arricchire di semantica i nostri dati grezzi, anche allo scopo di renderli fruibili da programmi o da persone diverse dal nostro programma o da noi stessi.
La proposta che adottiamo è quella dello standard XML. Secondo questo standard (tralasciando alcuni dettagli tecnici) ogni valore deve essere circondato da tag che lo circostanziano. L'obiettivo è quello di arricchire con informazioni semantiche i dati "grezzi", in modo da renderli intelligibili e portabili su piattaforme, sistemi operativi e programmi diversi. Nel caso del nostro esempio, l'XML corrispondente potrebbe essere:
<persona>
<nome>Marco</nome>
<cognome>Tonti</cognome>
<email>marco.tonti@unisalento.it</email>
</persona>
<persona>
...
</persona>
ecc.
Dentro le parentesi angolari (coppie di maggiore e minore) ci sono i nomi dei valori contenuti da il tag di apertura e quello di chiusura (contrassegnato da una barra all'inizio: </nome> per esempio indica che lì finisce il nome). Notate come sia possibile non solo includere singoli valori, ma anche altri tag. Questo particolare è utilissimo e ci permette di creare strutture anche molto complesse.
giovedì 2 dicembre 2010
Lezione del 2 dicembre 2010 /1
Lezione conclusiva sulla crittazione. Concetto di crittazione Asimmetrica.
Riferimenti:
http://it.wikipedia.org/wiki/Infrastruttura_a_chiave_pubblica
http://it.wikipedia.org/wiki/Differenza_fra_cifratura_simmetrica_e_asimmetrica
L'idea di fondo della crittazinoe asimmetrica è che, divesamente dal sistema simmetrico che prevede un unica chiave per entrambi i partecipanti, in questo caso le chiavi sono due: K1 e K2. Se crittiamo con la chiave K1 possiamo decrittare solo con la chiave K2, e se crittiamo con la chiave K2 possiamo decrittare solo con la chiave K1.
Le caratteristiche di un sistema PKI sono riassunte nell'acronimo PAIN: Privatezza, Autenticità, Integrità, Non ripudiazione.
Solitamente una delle due chiavi viene tenuta segreta (Ks) e l'altra viene resa pubblica (Kp). L'obiettivo è permettere a tutti coloro che vogliono comunicare in modo sicuro con la persona di poter crittare i messaggi con la chiave pubblica del ricevente, in modo che solo lui possa decrittare il messaggio. In questo modo si assicura la privatezza della comunicazione, perché una volta crittato dal mittente con la chiave pubblica del destinatario, il messaggio diventa decrittabile solo dal destinatario con la propria chiave privata.
Questo risolve il problema della Privacy, ma non ci dà nesuna garanzia sull'identità di chi manda il mesaggio (proprio per il fatto che la chiave che viene usata è pubblica).
Se al contrario non siamo interessati alla privatezza dei dati ma solo alla autenticazione, per le caratteristiche del sistema, è possibile che il mittente critti il messaggio con la propria chiave privata (che solo lui/lei possiede) in modo che chiunque possa riconoscerlo come mittente, dato che quel messaggio può esere decifrato solo con la chiave pubblica della persona. In altre parole SOLO quella persona può crittare usando la propria chiave segreta, e tutti possono decrittare il messaggio usando la chiave pubblica di quella persona (compreso il destinatario che così è certo di parlare con la persona giusta). Questo sistema però garantisce solo l'autenticità, non la privatezza della comunicazione.
Per risolvere il problema si possono comporre le due modalità: il messaggio per prima cosa viene crittato con la propria chiave privata, e successivamente di nuovo crittato con la chiave pubblica del destinatario. In questo modo si uniscono i due sistemi: viene garantita sia l'autenticità che la privatezza della comunicazione, infatti solo il destinatario può decifrare il messaggio del mittente (privatezza), e nuovamente decrittarlo usando la chiave pubblica del mittente (perché il mittente è l'unico che può crittarlo in modo che venga decrittato con la propria chiave pubblica, quindi autenticità).
Quest'ultimo aspetto dell'autenticazione dà luogo anche alla caratteristica che si chiama "non ripudiazione". Quando il mittente certifica di essere chi dice di essere crittando il messaggio con la propria chiave privata, visto che lui/lei è l'unico che può farlo, contemporaneamente sta facendo un gesto che gli impedirà di ripudiare il messaggio. Visto che la crittazione è con la propria chiave privata un'operazione deliberata che solo lui/lei può fare, quella persona non potrà in seguito affermare di non averlo fatto: non potrà ripudiare di essere il mittente di quel messaggio.
Questo è anche il meccanismo di base della firma digitale. Un documento che viene crittato con la propria chiave privata è implicitamente firmato, dato che nessun altro può effettuare quell'operazione. In realtà quello che viene crittato con la propria chiave privata (per firmare) è il codice hash del documento, che in questo modo rimane in chiaro. Il fatto che si usi il codice hash garantisce che sia PROPIO quel documento che viene firmato, e quindi si possono escludere modifiche successive. E anche chi ha firmato, per la non ripudiazione, non può negare di averlo fatto. Questo tipo di firma in Italia ha valore anche in tribunale (e per certi versi è persino più sicuro della firma autografa).
Per la diffusione e l'accertamento dell'effettivo proprietario di una chiave pubblica esistono società dette Certification Authorities che mantengono elenchi aggiornati delle chiavi pubbliche delle persone, in modo che quete chiavi possano essere sostituire in caso di smarrimento della corrispondente chiave privata, o per semplice prudenza.
Riferimenti:
http://it.wikipedia.org/wiki/Infrastruttura_a_chiave_pubblica
http://it.wikipedia.org/wiki/Differenza_fra_cifratura_simmetrica_e_asimmetrica
L'idea di fondo della crittazinoe asimmetrica è che, divesamente dal sistema simmetrico che prevede un unica chiave per entrambi i partecipanti, in questo caso le chiavi sono due: K1 e K2. Se crittiamo con la chiave K1 possiamo decrittare solo con la chiave K2, e se crittiamo con la chiave K2 possiamo decrittare solo con la chiave K1.
Le caratteristiche di un sistema PKI sono riassunte nell'acronimo PAIN: Privatezza, Autenticità, Integrità, Non ripudiazione.
Solitamente una delle due chiavi viene tenuta segreta (Ks) e l'altra viene resa pubblica (Kp). L'obiettivo è permettere a tutti coloro che vogliono comunicare in modo sicuro con la persona di poter crittare i messaggi con la chiave pubblica del ricevente, in modo che solo lui possa decrittare il messaggio. In questo modo si assicura la privatezza della comunicazione, perché una volta crittato dal mittente con la chiave pubblica del destinatario, il messaggio diventa decrittabile solo dal destinatario con la propria chiave privata.
Questo risolve il problema della Privacy, ma non ci dà nesuna garanzia sull'identità di chi manda il mesaggio (proprio per il fatto che la chiave che viene usata è pubblica).
Se al contrario non siamo interessati alla privatezza dei dati ma solo alla autenticazione, per le caratteristiche del sistema, è possibile che il mittente critti il messaggio con la propria chiave privata (che solo lui/lei possiede) in modo che chiunque possa riconoscerlo come mittente, dato che quel messaggio può esere decifrato solo con la chiave pubblica della persona. In altre parole SOLO quella persona può crittare usando la propria chiave segreta, e tutti possono decrittare il messaggio usando la chiave pubblica di quella persona (compreso il destinatario che così è certo di parlare con la persona giusta). Questo sistema però garantisce solo l'autenticità, non la privatezza della comunicazione.
Per risolvere il problema si possono comporre le due modalità: il messaggio per prima cosa viene crittato con la propria chiave privata, e successivamente di nuovo crittato con la chiave pubblica del destinatario. In questo modo si uniscono i due sistemi: viene garantita sia l'autenticità che la privatezza della comunicazione, infatti solo il destinatario può decifrare il messaggio del mittente (privatezza), e nuovamente decrittarlo usando la chiave pubblica del mittente (perché il mittente è l'unico che può crittarlo in modo che venga decrittato con la propria chiave pubblica, quindi autenticità).
Quest'ultimo aspetto dell'autenticazione dà luogo anche alla caratteristica che si chiama "non ripudiazione". Quando il mittente certifica di essere chi dice di essere crittando il messaggio con la propria chiave privata, visto che lui/lei è l'unico che può farlo, contemporaneamente sta facendo un gesto che gli impedirà di ripudiare il messaggio. Visto che la crittazione è con la propria chiave privata un'operazione deliberata che solo lui/lei può fare, quella persona non potrà in seguito affermare di non averlo fatto: non potrà ripudiare di essere il mittente di quel messaggio.
Questo è anche il meccanismo di base della firma digitale. Un documento che viene crittato con la propria chiave privata è implicitamente firmato, dato che nessun altro può effettuare quell'operazione. In realtà quello che viene crittato con la propria chiave privata (per firmare) è il codice hash del documento, che in questo modo rimane in chiaro. Il fatto che si usi il codice hash garantisce che sia PROPIO quel documento che viene firmato, e quindi si possono escludere modifiche successive. E anche chi ha firmato, per la non ripudiazione, non può negare di averlo fatto. Questo tipo di firma in Italia ha valore anche in tribunale (e per certi versi è persino più sicuro della firma autografa).
Per la diffusione e l'accertamento dell'effettivo proprietario di una chiave pubblica esistono società dette Certification Authorities che mantengono elenchi aggiornati delle chiavi pubbliche delle persone, in modo che quete chiavi possano essere sostituire in caso di smarrimento della corrispondente chiave privata, o per semplice prudenza.
mercoledì 1 dicembre 2010
Lezione del 1 dicembre 2010
Oggi si è introdotto il concetto alla base della crittografia classica moderna (per una storia della crittografia pre-moderna vedere qui). (A posteriori, in base all'evoluzione teorica recente, viene definita "simmetrica" per il fatto che la chiave di cifratura deve esere condivisa da entrambe le parti: dall'emittente per crittare un messaggio e dal ricevente per decrittarlo).
Il primo elemento che riguarda crittografia e sicurezza è stato l'introduzione del concetto di codice HASH. Una funzione di hash è una procedura che, dato in ingresso una serie di dati, produce un codice (in linea di massima) diverso per ogni diversa serie di dati, ma identico per la stessa serie. Da questo codice deve essere impossibile risalire ai dati originali. Un esempio molto semplice che illustra il principio di base è quello basato sulla somma: se noi abbiamo una sequenza di numeri, sommandoli otteniamo un valore unico. Questo valore è sempre lo stesso per la stessa sequenza di numeri, ma da quel valore è impossibile risalire alla esatta sequenza che lo ha generato.
Questo sistema viene normalmente usato per registrare le password nei siti e per la posta elettronica. In questo modo non mantengono intatta l'informazione "delicata" della password, ma sono in grado di riconoscere una persona quando inserisce la propria password applicando ad essa la stessa procedura e confrontando i risultati.
Le operazioni di base della crittografia si basano sull'operatore XOR, che ha come simbolo un più in un circoletto: ⊕. Questo operatore si applica a due valori binari e restituisce un valore binario che vale 1 se i due operandi sono diversi tra loro (1 e 0 oppure 0 e 1) e restituisce 0 se sono uguali. XOR è la forma contratta di EXCLUSIVE OR (or esclusivo).
Questo operatore si può applicare anche a interi byte e produce dei byte composti dai risultati di 8 operazioni "in colonna". L'aspetto interessante dello XOR è che se aplicato due volte con lo stesso valore, esso restituisce il valore iniziale. Per esempio 1010 ⊕ 1100 = 0110 , ma se applichiamo di nuovo al risultato lo stesso XOR otteniamo: 1001 ⊕ 1100 = 1010 cioè il valore iniziale. Si può dire anche che N⊕K⊕K = N. Praticamente ripetere lo XOR la seconda volta con lo stesso valore annulla il primo XOR e ripristina il valore originale.
L'idea è quella di usare questa caratteristica per "fondere" in modo reversibile un messaggio con la chiave di crittazione. Se abbiamo un messaggio che è composto da una sequenza di bit (che rappresentano dei caratteri di testo) e una chiave composta da un'altra sequenza di bit (la traduzione in binario di "quiquoqua" per esempio) si possono comporre queste due sequenze di valori in modo da ottenere una sequenza di valori (successivamente reinterpretabili come caratteri) incomprensibile per chi non conosca la chiave di crittazione. Il ricevente, applicando la stessa trasformazione usando la stessa chiave, può decifrare il messaggio e riportarlo in chiaro. In pratica il nostro messaggio M viene elaborato con la chiave K (ripetendo la chiave se serve per coprire tutto il messaggio, che in genere è più lungo della chiave) con lo XOR: C=M⊕K. C è il messaggio cifrato che viene spedito al destinatario. A questo punto il destinatario, conoscnedo la chiave K, la può applicare al messaggio cifrato C⊕K e ottenere M.
Il problema della crittografia simmetrica è che, almeno per gli algoritmi più vecchi, è abbastanza vulnerabile. Conoscendo abbastanza informazioni sulla lingua del messaggio e osservando regolarità statistiche molto sofisticate è possibile spesso decifrare il messaggio. Questo non è più molto vero dato che gli algoritmi moderni di crittazione simmetrica sono molto molto sicuri. La fragilità del sistema simmetrico è intrinseca al sistema stesso: l'informazione più importante, la chiave, si deve trovare in due posti contemporaneamente. Inoltre quanto più spesso viene usata, tanto più vulnerabile diventa la crittazione (la statistica si fonda sui grandi numeri, più mesaggi crittati allo stesso modo sono disponibili, più appigli ci sono per decrittarli). Inoltre ci deve essere un accordo preventivo sulla chiave da usare, questo accordo deve essere fatto lungo un canale "sicuro", altrimenti la crittazione è inutile. La chiave di quando in quando va rinnovata, per quei problemi di vulnerabilità già detti, quindi la nuova chiave deve essere ritrasmessa in qualche modo tra i due partecipanti (le classiche valigette blindate legate con le manette al polso delle spie!) e questa è certamente un'enorme vulnerabilità del sistema. Non è nemmeno possibile pensare di trasmettere la nuova chiave sfruttando la vecchia crittazione, perché se qualcuno ha scoperto la vecchia chiave e intercetta il messaggio può venire a conoscenza anche della nuova chiave, e così via.
Un'ulteriore vulnerabilità (non detta a lezione) è che se malauguratamente qualcuno entrasse in possesso di UN messaggio cifrato, e dello STESSO messaggio non cifrato, potrebbe conoscere perfettamente la chiave, proprio per quelle caratteristiche dello XOR che dicevamo: se C=M⊕K, per ottenere K è sufficiente fare C⊕M!!! (praticamente decrittiamo la chiave col messaggio, invece che il messaggio con la chiave). C=M⊕K, conoscendo C e M possiamo fare M⊕C = M⊕M⊕K = K
Infatti (preso da Wikipedia nella voce di un sistema nazistra di cifratura, il sistema Lorenz):
Con la crittografia ha esordito una delle menti più brillanti del Novecento, Alan Turing, che ha una storia straordinaria degna di essere letta e conosciuta. Con le sue idee ha dato vita a una serie enorme di riflessioni e di filoni scientifici, primo fra tutti quello della concezione dell'informatica come scienza, e non più solo come tecnologia. I computer fino a quel momento erano appunto questo: calcolatori. Con Turing sono diventate delle entità teoriche, matematiche, dei modelli teoretici sui quali si possono costruire concetti rivoluzionari.
Il primo elemento che riguarda crittografia e sicurezza è stato l'introduzione del concetto di codice HASH. Una funzione di hash è una procedura che, dato in ingresso una serie di dati, produce un codice (in linea di massima) diverso per ogni diversa serie di dati, ma identico per la stessa serie. Da questo codice deve essere impossibile risalire ai dati originali. Un esempio molto semplice che illustra il principio di base è quello basato sulla somma: se noi abbiamo una sequenza di numeri, sommandoli otteniamo un valore unico. Questo valore è sempre lo stesso per la stessa sequenza di numeri, ma da quel valore è impossibile risalire alla esatta sequenza che lo ha generato.
Questo sistema viene normalmente usato per registrare le password nei siti e per la posta elettronica. In questo modo non mantengono intatta l'informazione "delicata" della password, ma sono in grado di riconoscere una persona quando inserisce la propria password applicando ad essa la stessa procedura e confrontando i risultati.
Le operazioni di base della crittografia si basano sull'operatore XOR, che ha come simbolo un più in un circoletto: ⊕. Questo operatore si applica a due valori binari e restituisce un valore binario che vale 1 se i due operandi sono diversi tra loro (1 e 0 oppure 0 e 1) e restituisce 0 se sono uguali. XOR è la forma contratta di EXCLUSIVE OR (or esclusivo).
Questo operatore si può applicare anche a interi byte e produce dei byte composti dai risultati di 8 operazioni "in colonna". L'aspetto interessante dello XOR è che se aplicato due volte con lo stesso valore, esso restituisce il valore iniziale. Per esempio 1010 ⊕ 1100 = 0110 , ma se applichiamo di nuovo al risultato lo stesso XOR otteniamo: 1001 ⊕ 1100 = 1010 cioè il valore iniziale. Si può dire anche che N⊕K⊕K = N. Praticamente ripetere lo XOR la seconda volta con lo stesso valore annulla il primo XOR e ripristina il valore originale.
L'idea è quella di usare questa caratteristica per "fondere" in modo reversibile un messaggio con la chiave di crittazione. Se abbiamo un messaggio che è composto da una sequenza di bit (che rappresentano dei caratteri di testo) e una chiave composta da un'altra sequenza di bit (la traduzione in binario di "quiquoqua" per esempio) si possono comporre queste due sequenze di valori in modo da ottenere una sequenza di valori (successivamente reinterpretabili come caratteri) incomprensibile per chi non conosca la chiave di crittazione. Il ricevente, applicando la stessa trasformazione usando la stessa chiave, può decifrare il messaggio e riportarlo in chiaro. In pratica il nostro messaggio M viene elaborato con la chiave K (ripetendo la chiave se serve per coprire tutto il messaggio, che in genere è più lungo della chiave) con lo XOR: C=M⊕K. C è il messaggio cifrato che viene spedito al destinatario. A questo punto il destinatario, conoscnedo la chiave K, la può applicare al messaggio cifrato C⊕K e ottenere M.
Il problema della crittografia simmetrica è che, almeno per gli algoritmi più vecchi, è abbastanza vulnerabile. Conoscendo abbastanza informazioni sulla lingua del messaggio e osservando regolarità statistiche molto sofisticate è possibile spesso decifrare il messaggio. Questo non è più molto vero dato che gli algoritmi moderni di crittazione simmetrica sono molto molto sicuri. La fragilità del sistema simmetrico è intrinseca al sistema stesso: l'informazione più importante, la chiave, si deve trovare in due posti contemporaneamente. Inoltre quanto più spesso viene usata, tanto più vulnerabile diventa la crittazione (la statistica si fonda sui grandi numeri, più mesaggi crittati allo stesso modo sono disponibili, più appigli ci sono per decrittarli). Inoltre ci deve essere un accordo preventivo sulla chiave da usare, questo accordo deve essere fatto lungo un canale "sicuro", altrimenti la crittazione è inutile. La chiave di quando in quando va rinnovata, per quei problemi di vulnerabilità già detti, quindi la nuova chiave deve essere ritrasmessa in qualche modo tra i due partecipanti (le classiche valigette blindate legate con le manette al polso delle spie!) e questa è certamente un'enorme vulnerabilità del sistema. Non è nemmeno possibile pensare di trasmettere la nuova chiave sfruttando la vecchia crittazione, perché se qualcuno ha scoperto la vecchia chiave e intercetta il messaggio può venire a conoscenza anche della nuova chiave, e così via.
Un'ulteriore vulnerabilità (non detta a lezione) è che se malauguratamente qualcuno entrasse in possesso di UN messaggio cifrato, e dello STESSO messaggio non cifrato, potrebbe conoscere perfettamente la chiave, proprio per quelle caratteristiche dello XOR che dicevamo: se C=M⊕K, per ottenere K è sufficiente fare C⊕M!!! (praticamente decrittiamo la chiave col messaggio, invece che il messaggio con la chiave). C=M⊕K, conoscendo C e M possiamo fare M⊕C = M⊕M⊕K = K
Infatti (preso da Wikipedia nella voce di un sistema nazistra di cifratura, il sistema Lorenz):
Sul ponte-radio Vienna-Atene della Wehrmacht, in funzione dal 1941, ancora durante la fase sperimentale della macchina cifratrice, fu inviato uno stesso messaggio di circa 4.000 caratteri, due volte, una poco dopo l'altra, cifrato con la medesima posizione iniziale dei cilindri-chiave. Il destinatario aveva chiesto di ritrasmettere il messaggio poiché la parola iniziale SPRUCHNUMMER era stata sostituita con SPRUCHNR. Questo grave errore di un radiotelegrafista, commesso già all'inizio, doveva diventare decisivo per la futura violazione del sistema di cifratura Lorenz.Tutti queti problemi venono risolti grazie ai moderni sistemi di cifratura a chiave Asimmetrica, dove esiste una chiave per crittare e una per decrittare, che verranno spiegati nella prossima lezione.
Con la crittografia ha esordito una delle menti più brillanti del Novecento, Alan Turing, che ha una storia straordinaria degna di essere letta e conosciuta. Con le sue idee ha dato vita a una serie enorme di riflessioni e di filoni scientifici, primo fra tutti quello della concezione dell'informatica come scienza, e non più solo come tecnologia. I computer fino a quel momento erano appunto questo: calcolatori. Con Turing sono diventate delle entità teoriche, matematiche, dei modelli teoretici sui quali si possono costruire concetti rivoluzionari.
martedì 30 novembre 2010
Lezione del 30 novembre 2010
Si conclude oggi la definizione dei concetti di base per descrivere gli algoritmi. Rimaneva da definire un criterio formale per descrivere i sottoprogrammi, e regolarne il loro scambio con "l'esterno", cioè con i programmi che chiamano procedure dedicate a compiti specifici. Già gli algoritmi di ordinamento introdotti hanno quella caratteristica: prendendo in input il vettore da ordinare (e il numero dei suoi elementi) procedono a effettuare quel compito, modificando la memoria dove si trovano i dati di input trasformandoli in dati di output).
Si è convenuto di scrivere descrivere questa struttura così:
ORDINA (N, dati)
{.....
}
Qindi quando ci troviamo di fronte a una serie di dati che vogliamo ordinare, ci è sufficiente richiamare ORDINA perché questi dati risultino ordinati.
A ben guardare un esempio di sottoprocedura l'avevamo già vista negli algoritmi di ordinamento presentati: lo SCAMBIA.
Scambiare due elementi è un'operazione complessa che però si può scomporre in passi semplici. Descriviamo l'operazione:
SCAMBIA (a, b, dati)
dove a e b sono gli indici degli elementi da scambiare, e dati è il vettore che contiene gli elementi.
La procedura SCAMBIA è scomponibile in passi semplici in questo modo:
SCAMBIA (a, b, dati)
{
temporaneo = dati[a]
dati[a] = dati[b]
dati[b] = temporaneo
}
L'argomento principale di questa lezione è però una questione teorica. Molto teorica. Riguarda il fatto che possiamo riconoscere almeno due categorie di problemi nel mondo: ci sono problemi "facili" e problemi "difficili". I problemi "facili" sono quelli che ammettono algoritmi risolutivi efficienti e in classi di complessità al più polinomiali.
Le classi di complessità (semplificando molto) si possono sostanzialmente dividere secondo questa gerarchia di complessità crescente
C=1 (tempo costante, per esempio trovare il valore minimo di un vettore ordinato: è sempre il primo elemento! Il numero di operazioni quindi non dipende dalla dimensione dell'input)
C=Log N (Tempo logaritmico: per esempio la ricerca dicotomica -- vedere le lezioni precedenti)
C=N (tempo lineare: per esempio la scansione di un vettore alla ricerca di un elemento)
C=N Log N (tempo semilineare, o loglineare: per esempio il quicksort)
C=N^2 (per esempio il prodotto di matrici, o l'ordinamento poco efficiente che avevamo visto nelle prime lezioni)
Le complessità comprese in queste categorie si chiamano POLINOMIALI e sono caratteristiche di problemi che ammettono delle "buone" soluzioni, cioè delle soluzioni efficienti. Tutti i problemi che abbiamo visto finora hanno la caratteristica di ammettere algoritmi "veloci" che li risolvano. Possiamo perciò dire che il problema di ordinare un elenco di valori è un problema che rientra nella categoria dei problemi facili. Questa categoria è detta P (che sta per "problemi che ammettono un algoritmo risolutivo di complessità al più polinomiale").
Esistono quindi problemi di natura diversa, che non ammettono algoritmi risolutivi efficienti? Sì, esistono. E sono problemi alla prova dei fatti molto comuni, per esempio trovare il percorso migliore per fare un tour di varie città, o pesare un kg di mele, o aspettarci che un navigatore satellitare non ci faccia fare strade assurde. Questi possono apparire problemi facili, ma sono tali solo per via della quantità normalmene ristretta di informazioni che si devono gestire. (Infatti quando la dimensione diventa più complessa, come per i tragitti stradali, i risultati spesso sono tutt'altro che buoni). I problemi che non ammettono soluzioni "efficienti" appartengono alla cosiddetta categoria NP (Nondeterministicamente polinomiali).
Quali sono questi problemi? e quali sono le categorie di complessità che li caratterizzano?
Il problema con cui si è affrontta la questione è il seguente: data una funzione binaria che opera su n valori binari, esiste almeno una combinazione di questi valori per cui il risutlato di questa funzione sia 1? Cioè, la funzione è soddisfacibile per almeno una delle posibili combinazioni di input? Per rispondere a questa domanda è necessario provarle tutte, e come è noto dalle prime lezioni il numero di combinazioni di una numero binario di N elementi è 2^N. Lo stesso principio si applica alle password: solo una password può farci passare. Se qualcuno vuole entrare nella nostra posta senza conoscere la password dovrà provare tutte le possibili combinazioni di caratteri (fino a che una e una sola lo farà entrare). Se supponiamo che i caratteri utilizzabili siano lettere maiuscole, minuscole e numeri, per una password di 8 caratteri, il numero di tentativi è 218 miliardi (= 62^8). Mettendo anche di poterne fare 1000 al secondo, per esaurire tutte le combinazioni ci vorrebbero oltre 6923 anni! L'affidabilità del sistema a password si basa sulla natura "difficile" del compito.
Altri problemi apparentemente facili:
- La cricca (CLIQUE): dato un insieme di persone, per cui ogni persona è amico di qualcuno ma non di altri, trovare la cricca di questo gruppo, cioè il sottoinsieme di persone di dimensioni massime per cui tutti i componenti si conoscono tra loro. Determinare quale sia questa cricca è un problema DIFFICILE.
- Il dramma del fruttivendolo (SUBSET-SUM): data una cassetta di mele, trovare la particolare combinazione di mele che pesa esattamente (per esempio) un kg. È necessario provare TUTTE le combinazioni, per scoprire se ne esiste una. Determinare l'esistenza di queta combinazione di mele è un problema DIFFICILE.
- Il ciclo hamiltoniano (HAM-CYCLE): dato un insieme di città e di strade che le collegano, trovare un percorso che parte da una certa città, tocca tutte le altre solo una volta, e torna "a casa". Determinare l'esistenza di questo percorso è un problema DIFFICILE.
- Il dramma del navigatore satellitare (o "del commeso viaggiatore", Travelling-Salesman Problem, TSP): dato un insieme di città e di strade che le collegano, e sapendo la lunghezza di ogni strada (o il costo del biglietto aereo, o della benzina...) trovare il percorso che da una certa città permetta di visitare tutte le altre una volta sola percorrendo la minor strada possibile. Questo è un problema DIFFICILE. (in particolare il numero di casi da esaminare è N fattoriale, N! = N*(N-1)*(N-2)... *3*2*1 che è certamente > 2^N)
Questa è la ragione di fondo per cui i computer NON POSSONO fare cose incredibili, impossibili, inimmaginabili: possono solo fare in modo molto efficinte quel che NOI gli diciamo di fare. Ma se noi non possediamo l'intelligenza sufficiente (o il mondo non offre appigli nella sua struttura) siamo perduti: i computer non possono risolvere nulla che non sia già stato affrontato da noi in modo efficiente. I navigatori satellitari che devono esaminare centinaia di combinazioni di strade e stradine per decidere qual è la migliore sono condannati al fallimento perenne, le compagnie di trasporti aerei, di spedizione, lo smistamento di telefonate, persino le coincidenze dei treni, affrontano tutti problemi minati da questa difficoltà insuperabile di fondo. Ovviamente esistono sistemi per ottenere soluzioni "abbastanza buone", ma LA soluzione migliore è al di là della potenza di qualsiasi computer (o meglio, richiederebbe talmente tanti millenni da essere di fatto inutile). Questo genere di problemi si applica anche a giochi, per esempio il master-mind, il nonogramma, il sudoku, il tetris, il campo minato (o campo fiorito) di Windows, e la creazione di parole crociate (perdonate i refusi e qualche definizione un po' forzata):
La prossima volta che ve la prendete col vostro stupido navigatore satellitare, o che trovate scandaloso un disservizio di una rete telefonica, che il sito delle ferrovie vi dà coincidenze assurde, riflettete su questo fatto: è con gli inrinseci limiti dell'intelligenza umana (e della complessità del mondo) che vi state scontrando.
Lezioni straordinarie
Nei giorni di Giovedì 2 e Venedì 3 sono introdotte le seguenti lezioni straordinarie:
Giovedì 15-17 (si aggiunge quella dalle 9 alle 11)
Venerdì dalle 10 alle 13.
Pur aderendo idealmente allo sciopero contro lo sfruttamento didattico dei ricercatori, mi vedo costretto non solo a proseguire le lezioni ma (col gentile consenso dei docenti coinvolti) a utilizzare alcuni dei loro spazi dedicati alle lezioni.
Vi invo in ogni caso a partecipare domani martedì mattina alla manifestazinone contro il decreto Gelmini di riforma universitaria, in partenza dall'Ateneo alle 9 e che si svolgerà per le vie della città.
La lezione di martedì pomeriggio è comunque confermata, come tutte le altre previste.
Giovedì 15-17 (si aggiunge quella dalle 9 alle 11)
Venerdì dalle 10 alle 13.
Pur aderendo idealmente allo sciopero contro lo sfruttamento didattico dei ricercatori, mi vedo costretto non solo a proseguire le lezioni ma (col gentile consenso dei docenti coinvolti) a utilizzare alcuni dei loro spazi dedicati alle lezioni.
Vi invo in ogni caso a partecipare domani martedì mattina alla manifestazinone contro il decreto Gelmini di riforma universitaria, in partenza dall'Ateneo alle 9 e che si svolgerà per le vie della città.
La lezione di martedì pomeriggio è comunque confermata, come tutte le altre previste.
lunedì 29 novembre 2010
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.
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.
domenica 28 novembre 2010
Anticipo lezione del 29/11/2010
La lezione di Lunedì 29/11 è anticipata alle 15.30. Dato il breve anticipo dello sposamento cercate di diffondere l'informazione a chi potrebbe non esserne informato.
Iscriviti a:
Post (Atom)