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)

 Quotidianamente affrontiamo problemi basati su questa struttura, e siamo in grado di risolverli solo grazie alla piccola dimensione del problema o ad approssimazioni nei nostri metodi. Ma in generale questi problemi quando coinvolgono quantità di dati anche solo poco più alte del normale diventano rapidamente ingestibili. Questo genere di problemi è matematicamente intrattabile. Non esistono algoritmi "furbi" come per l'ordinamento Quicksort: l'unica strada è provare tutte le combinazioni. Ma tutte le combinazioni di un problema anche solo per poche città è un problema quasi sovrumano: con 10 città il TSP produce quasi 4 milioni di combinazioni possibili!

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.

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.

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.

Lezione del 25 Novembre 2010

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

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

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

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

  

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

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

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

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

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

  

(provare per credere!)

Lezione del 24 Novembre 2010

Lezione introduttiva sugli algoritmi, da intendersi in continuità con le lezioni precedenti. Mentre nelle lezioni precedenti si è discusso su come segmentare un mondo (già in forma discreta, come nel caso del conteggio, o in forma continua, come le onde sonore attraverso l'operazione di campionamento). Il mondo che ci siamo impegnati a concepire concettualmente finora era costituito da codifica di dati estratti dal mondo.

Con gli algoritmi il passaggio è molto più complesso, ma coerente con questa linea: un algoritmo è la segmentazione in elementi elementari delle operazioni che si possono condurre sui simboli richiamati nel paragrafo precedente. Il concetto di algoritmo è la formalizzazione di quello che ognuno compie quotidianamente quando segue intuitivamente un processo per ottenere un certo risultato (fare il caffè, cuocere delle uova, guidare un'auomobile).

A lezione il concetto di algoritmo è stato affrontato con l'uso di normali carte da gioco. Quello che si fa normalmente quando si gioca a carte è di metterle in ordine, una volta distribuita la propria mano, in modo automatico (il nome informatico di questo particolare procedimento è "Exchange sort", molto somigliante al "selection sort"). A lezione si è carcato di riconoscere i passi semplici che si effettuano quando si mettono in ordine le carte: si cerca la carta di valore più basso (in modo indifferente al seme!) e la si pone in prima posizione, quindi tra le carte rimanenti si cerca la carta di valore più basso e la si pone in seconda posizione e così via. Secondo la terminologia del libro, la posizione che stiamo cercando di riempire con la carta giusta è detta "alfa", mentre l'operazione di scorrimento che si effettua sulle carte rimanenti (sulla destra) facendo scorrere il nostro indice (detto "beta") sulle carte rimenti per cercare quella minore.

In pratica il processo è stato quello di, ogni volta che troviamo una carta più bassa rispetto a quella che si trova in posizione alfa, scambiare la carta in posizione beta con quella in posizione alfa. Una volta finita la scansione beta, si passa all'alfa successivo. In questo modo è possibile ordinare tutte le carte, qualunque sia il loro valore e la loro disposizione. Per rendere più evidente il concetto si è provveduto a effettuare le stesse operazioni mantenendo le carte coperte, permettendo il confronto solo di due carte alla volta e ricoprendole subito dopo. Questo è di fatto quello che fa un computer quando segue un algoritmo: non ha una visione di insieme, ma solo informazioni molto limitate, e circoscritte a quelle strettamente necessarie al completamento del compito. Nel caso dell'ordinamento è sufficiente conoscere il risultato del confronto di due carte alla volta (se una è minore o maggiore-uguale dell'altra).

Si è introdotto un ulteriore algoritmo di ordinamento, denominato "bubble sort", più semplice da programmare e in certi casi più efficiente del precedente: si confronta la carta alfa (partendo da alfa=1) con la carta alfa+1 (quella successiva). Se la carta alfa ha valore maggiore della carta alfa+1 le due carte vengono scambiate. Si incrementa allora di uno il valore di alfa (si passa alla carta successiva) e si ripete il confronto. Alla fine di ogni giro la sequenza di carte è "un po' più" ordinata di prima. Si procede a ripetere questo ciclo fino a quando non ci sono più scambi: questo significa che la sequenza di carte ha già il valore massimo di ordinamento e non può essere ulteriormente incrementato, quindi l'algoritmo conclude. E le carte sono ordinate. Notate che in questo caso è necessario che le carte vengano scambiate esclusivamente quando la prima è strettamente maggiore della seconda, altrimenti l'algoritmo continuerebbe a scambiare carte dallo stesso valore senza necessità, e quindi il criterio di arresto non si raggiungerebbe mai (in presenza di carte con lo stesso valore ci sarebbe sempre uno scambio).

Approfondimenti: Algoritmi di ordinamento su Wikipedia (con animazioni nelle pagine dedicate a ogni singolo algoritmo)

Lezione del 23 Novembre 2010

In continuità con gli argomenti delle ultime lezioni, oggi si è parlato di rappresentazioni numeriche di caratteristiche fisiche del mondo. IN particolare, la direzione filosofica che si è seguita, è quella della DISCRETIZZAZIONE e della PERTINENTIZZAZIONE delle caratteristiche di segmenti di mondo che ci riguardano.

Quando si sceglie la "quantità" per rappresentare un particolre aspetto del mondo, si fa una scelta: si decide che la quantità di una certa cosa è l'aspetto pertinente per noi. Possono esserci molti aspetti diversi, ma quando decidiamo di digitalizzare una porzione di mondo lo facciamo scegliendo ciò che è rilevante e ciò che non lo è.

Se però la porzione di mondo che ci interessa conoscere ha caratteristiche di continuità (diversamente dalla quantità di mele, che è un valore discreto, o dall'età, o dalla quantità di denaro) occorre un metodo per trasformare queste informazioni continue (analogiche) in informazioni discrete (digitali). Avevamo già visto un esempio con i colori: la descrizione più diffusa in informatica di un colore è utilizzando le sue componenti principali, RGB. Per ognuna di queste componenti viene dato il grado di intensità con un valore che può andare da 0 a 255 (da 00 a FF in esadecimale). Questo è un processo di discretizzazione di un fenomeno che nella realtà è continuo.

È un'operazione che facciamo quotidianamente senza nemmeno accorgercene, per esempio ogni volta che misuriamo una lunghezza, o una temperatura. Lunghezza e temperatura sono valori continui, e sono in ultima analisi fortemente legate agli atomi che compongono l'oggetto o al loro grado di eccitazione (temperatura). QUando misuriamo con un righello approssimiamo un valore continuo a una scala discreta. Esattamente la stessa cosa si fa col termometro: riportiamo una temperatura che è continua in una scala divisa in gradi (o decimi di grado per la temperatura corporea). Operiamo una digitalizzazione, una riduzione in senso numerico di una misura che è impossibile da descrivere con precisione assoluta.

L'esempio portato a lezione riguarda la digitalizzazione dei suoni (musica, parlato...). I suoni possono in generale essere rappresetnati con la loro forma d'onda . Come facciamo a tradurre questo fenomeno continuo in una serie di dati numerici (che sono discreti per definizione)? L'operazione è quella di digitalizzazione. In un certo senso anche in questo caso si tratta di una discretizzazione del mondo: facciamo una serie di misurazioni (campionamento) e riportiamo il valore misurato in formato numerico (secondo una scala prefissata). La discretizzazione avviene quindi in due direzioni: la frequenza del campionamento ("quante misure faccio al secondo?") e la precisione del campione ("Quanto devono essere precise le misurazioni?"). Per digitalizzare la musica secondo lo standard dei CD audio, i valori adottati sono 44100 campionamenti al secondo misurati con la precisione di un numero a 16 bit (quindi su 65536 livelli). In base alla necessità è possibile variare questi parametri per avere registrazioni digitali più o meno accurate.

Altro esempio di digitalizzazione è quando mettiamo un'immagine in uno scanner. L'apparecchio divide l'immagine (discretizza il segmento di mondo di interesse) in piccole aree quadrate, e "legge" il colore prevalente in quell'area. Anche in questo caso la qualità della digitalizzazione dipende fondamentalmente da due parametri: la densità della rilevazione e l'accuratezza della lettura. Più piccola sarà la segmentazione maggiori saranno le informazioni "estratte" dall'immagine, e quindi maggiore sarà la quantità di bit necessaria per descriverla. Stessa cosa per la precisione della lettura: se lo scanner riconoscese solo il bianco e nero la quantità di informazione estratta potrebbe essere descritta da un singolo bit. Per colori più complessi sono necessari un numero maggiore di bit.

Lezione del 22 Novembre 2010

Ulteriore caratterizzazione dei sistemi numerici adattati alla rappresentazione binaria. Presentazione dei sistema esadecimale (la conversione si ottiene facilmente da binario a esadecimale raggruppando i bit in gruppi da 4, ottenendo 16 possibili combinazioni con i valori da 0 a 15, e quindi passando alle cifre esadecimali secondo lo schema: 0 1 2 3 4 5 6 7 8 9 A B C D E F ).
Utilizzo di numeri esadecimali per la rappresentazione RGB dei colori. Uso dei valori binari come "vero" e "falso" della logica classica.
Rappresentazione di caratteri con codici numerici. Nell'esempio fatto a lezione abbiamo usato una codifica basata su 6 bit (64 possibili valori). Allineamento di questa codifica con la divisione in byte dei sistemi informatici: "buttare" due bit ogni 6 per allineare la rappresentazione a quella richiesta dal computer, oppure spezzare la rappresentazione su più byte? La seconda è più macchinosa ma più efficiente.

È importante rendersi conto che queste considerazioni non si applicano strettamente ai computer, ma ai concetti generali di rappresentazione. Le domande fondamentali che affrontiamo sono: "Come possiamo rappresentare in forma numerica il segmento di mondo che ci interessa? Quali sono le informazioni necessarie per averne una rappresentazione corretta? Come conserviamo e organizziamo queste informazioni? Come le manipoliamo in modo che mantengano coerenza con il segmento di mondo cui fanno riferimento?".

Non bisogna già pensare a "come" tutto ciò entra nel computer e quali vincoli formali e ingegneristici siano richiesti, ma pensare che tutto ciò che possiamo immaginare di fare con le informazioni lo possiamo fare, rispettando i vincoli di non distruzione (cioè non dobbiamo perdere informazioni rilevanti), di manipolazione coerente con la realtà rappresentata (se esprimiamo un numero in esadecimale, poi manipoliamo questi valori in modo da scurire il colore ma il colore si schiarisce, la nostra operazione non è coerente con la realtà modellizzata) e di ricollegamento con la rappresentazione del reale. Questa è l'operazione che si fa al mercato contando 3 mele (quindi dal mondo fisico si ha una rappresentazione numerica astratta; noi "distruggeremmo" informazione se dicessimo "c'è qualche mela"), poi si aggiunge 1 (altra rappresentazione astratta di mettere nel sacchetto un'altra mela), per ottenere 4 (si verifica infatti che nel sacchetto ci sono 4 mele): modellizzazione della realtà (la teoria), estrazione dei dati numerici descritti dalla teoria, stoccaggio di quei dati ("quante mele erano, già?!"), manipolazione delle rappresentazioni simboliche (+1), ritorno alla realtà modellizzata ("ah, sono proprio 4 mele!").

Lezione del 18 Novembre 2010

In questa lezione si è trattata la trasformazione dei numeri da una base a un'altra. Si è convenuto che la base di partenza sia, per semplicità, la base 10.

Il processo di trasformazione di espressioni numeriche da una base a un'altra è stato illustrato immaginando che si trattasse di un cambio "di valuta" (non intermini di richezza, che è la quantità denotata e che quindi non cambia) ma in termini veri e propri di una trasformazione di banconote. Le banconote di diversi "tagli" (1, 10, 100, 1000...) rappresentano i blocchi di cifre contenuti nelle diverse posizioni dei numeri (non per niente si parla di notazione "posizionale"). Per compiere la trasformazione, diciamo da € in base 10 a $ in base 7 bisogna: definirsi la corrispondenza fra tagli "tondi" in base 7, quindi banconote da 1$, 10$, 1000$ che corrispondono in € a tagli di 1€, 7€, 49€, 343€.

È necessario imporre che il cambio sia effettuato col numero minimo di banconote, per assicurare una corrispondenza biunivoca tra le due rappresentazioni (cioè 15€ non potranno essere rappresentati da 15 monete da 1€ ma solo ed esattamente da 1 banconota da 10€ e 5 monete da 1€). Considerando questo approccio, la procedura di conversione consiste fondamentalmente nel determinare quante banconore di ogni taglio sono necessarie, partendo dall'euro, e poi convertire ogni singolo valore in $ (e le molteplicità delle banconote in base 7).

Notare che i tagli corrispondenti in € sono le potenze progressive di 7: 7^0 (=1), 7^1(=7), 7^2(=49)... cioè le potenze progressive della base. Questo ci è più familiare ed evidente in base 10, considerando che il numero 1234 può essere scritto come 1*10^3+2*10^2+3*10^1+4*10^0. Il trucco consiste nel trovare una corrispondenza tra le basi dei numeri e procedre infine più "semplicemente" alla conversione.

Questo è il concetto di base, poi esistono metodi meno convoluti per effettuare la trasformazione.

Riferimenti:
http://it.wikipedia.org/wiki/Base_(aritmetica)
Esempi interessanti (e buone definizioni) in : http://it.wikipedia.org/wiki/Numerazione_posizionale
Perché contiamo in base 10? http://it.wikipedia.org/wiki/Sistema_numerico_decimale

Lezione del 17 Novembre 2010

Oggi si è introdotto il concetto di "numero" come formalizzazione simbolica del concetto di "quantità". La rappresentazione della quantità con l'uso di combinazione di simboli (le cifre) avviene attraverso l'uso di:
- una serie di simboli distinti tra loro (nell'uso quotidiano sono le cifre da 0 a 9) e regolati da un ordinamento
- un procedimento che a ogni combinazione di simboli faccia corrispondere esattamente una quantità (e che a ogni quantità faccia corrispondere esattamente una e una sola combinazione di simboli)

Il numero assume quindi la dimensione teorica di "significante" che fa riferimento a un significato, in questo caso la quantità. Con quantità si intende la ripetizione (identica) di un gesto o di un insieme di oggetti (questi due aspetti possono essere assimilati pensando che il "gesto" può essere il mettere un oggetto in un sacchetto).

Il numero quindi è una forma codificata di un segmento di mondo. Il codice si ottiene disponendo i simboli secondo un procedimento ben definito che, nel senso comune, consiste nell'operazione di "conteggio".

In base a questa definizione è possibile pensare a un'infinità di metodi diversi di rappresentare le quantità. Il più rudimentale è fare un segno su un foglio per ogni oggetto (o azione) della realtà (sistema "unario"), ma combinando i simboli in base al procedimento descritto (cioè, nel caso decimale, il passaggio dal 9 al 10, cioè 1 decina più 0 unità) è possibile usare simboli diversi in quantità diverse per esprimere esattamente il corrispondente concetto di "quantità".

Per esempio se si disponesse solo di 9 simboli per contare, i numeri dovrebbero essere combinazioni basate unicamente su questi simboli: 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, ..., 87, 88, 100... (che corrispondono alle stesse quantità rappresentate dai nostri numeri 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, ..., 79, 80, 81) (provate su: http://www.cut-the-knot.org/binary.shtml ). In altre parole, per descrivere il numero quanti asterischi ci sono in "********************" in base 10 useremmo il simbolo "20" (combinazione di cifre), in base 9 useremmo il simbolo "22". Non è importante il simbolo usato, ma il fatto che entrambi si riferiscono alla stessa quantità.

La quantità minima di simboli è 1, che corrisponde al codice unario, dove c'è un segno per ogni elemento della quantità che si vuole rappresentare. Per rappresetnare gli asterischi dell'esempio precedente, in unario scriveremmo "00000000000000000000" cioè uno 0 per ogni simbolo da rappresentare. In binario, cioè la numerazione basata solo sulle prime due cifre, sarebbe "10100", in decimale "20".

La procedura che permette di collegare le quantità al numero è la stessa implementata col meccanismo dei contachilometri: scrivendo le cifre su ogni disco rotante. Per usare un sistema diverso di numerazione è sufficiente scrivere un numero diverso di cifre su ogni disco. Per fare la conversione è sufficiente fare lo stesso numero di km, dopo aver azzerato il contatore, usando i due diversi dispositivi.

Annulamento lezione del 16/11/2010

La lezione di martedì 16 novembre non ci sarà.

Prima lezione, 15/11/2010

(La versione letta a lezione era più breve per ragioni espositive, questa è la versione completa)

Lo scriba di Primo Levi

Due mesi fa, nel settembre 1984, mi sono comprato un elaboratore di testi, cioè uno strumento per scrivere che va a capo automaticamente a fine riga, e permette di inserire, cancellare, cambiare istantaneamente parole o intere frasi; consente insomma di arrivare d'un colpo ad un documento finito, pulito, privo di inserti e di correzioni. Non sono certo il primo scrittore che si è deciso al salto. Solo un anno fa sarei stato giudicato un audace o uno snob; oggi non piú, tanto il tempo elettronico corre veloce. Mi affretto ad aggiungere due precisazioni. In primo luogo: chi vuole o deve scrivere può continuare benissimo con la biro o con la macchina: il mio gadget è un lusso, è divertente, anche entusiasmante, ma superfluo. In secondo, a rassicurare gli incerti e i profani: io stesso ero, anzi sono tuttora, mentre qui scrivo sullo schermo, un profano. Di cosa avviene dietro lo schermo ho idee vaghe. Al primo contatto, questa mia ignoranza mi umiliava profondamente; è accorso a rinfrescarmi un giovane che paternamente mi fa da guida, e mi ha detto: - Tu appartieni alla austera generazione di umanisti che ancora pretendono di capire il mondo intorno a loro. Questa pretesa è diventata assurda: lascia fare all'abitudine, e il tuo disagio sparirà. Considera: sai forse, o ti illudi di sapere, come funziona il telefono o la TV? Eppure te ne servi ogni giorno. E al di fuori di qualche dotto, quanti sanno come funziona il loro cuore o i loro reni? Nonostante questa ammonizione, il primo urto con l'apparecchio è stato pieno d'angoscia: l'angoscia dell'ignoto, che da molti anni non provavo piú. L'elaboratore mi è stato fornito col corredo di vari manuali; ho cercato di studiarli prima di toccare i comandi, e mi sono sentito perduto. Mi è parso che fossero scritti apparentemente in italiano, di fatto in una lingua sconosciuta; anzi, in una lingua beffarda e fuorviante, in cui vocaboli ben noti, come "aprire", "chiudere", "uscire", vengono usati in sensi insoliti. C'è sí un glossario che si sforza di definirli, ma procede all'inverso dei comuni dizionari: questi definiscono termini astrusi ricorrendo a termini famigliari; il glossario pretende di dare un nuovo senso a termini falsamente famigliari ricorrendo a termini astrusi, e l'effetto è devastante. Quanto meglio sarebbe stato inventare, per queste cose nuove, una terminologia decisamente nuova! Ma ancora è intervenuto il giovane amico, e mi ha fatto notare che pretendere di imparare a usare un computer sui manuali è stolto quanto pretendere di imparare a nuotare leggendo un trattato, senza entrare nell'acqua; anzi, mi ha precisato, senza neppure sapere cos'è l'acqua, avendone solo sentito vagamente parlare Mi sono dunque accinto a lavorare sui due fronti, verificando cioè sull'apparecchio le istruzioni dei manuali, e m'è subito tornata a mente la leggenda del Golem. Si narra che secoli addietro un rabbino-mago avesse costruito un automa di argilla, di forza erculea e di obbedienza cieca, affinché difendesse gli ebrei di Praga dal pogrom; ma esso restava inerte, inanimato, finché il suo autore non gli infilava in bocca un rotolo di pergamena su cui era scritto un versetto della Torà. allora il Golem di terracotta diventava un servo pronto e sagace: si aggirava per le vie e faceva buona guardia, salvo impietrirsi nuovamente quando gli veniva estratta la pergamena. Mi sono chiesto se i costruttori del mio apparecchio non conoscessero questa strana storia (sono certo gente colta e anche spiritosa): infatti l'elaboratore ha proprio una bocca, storta, socchiusa in una smorfia meccanica. Finché non vi introduco il disco-programma, l'elaboratore non elabora nulla, è una esanime scatola metallica; però, quando accendo l'interruttore, sul piccolo schermo compare un garbato segnale luminoso: questo, nel linguaggio del mio Golem personale, vuol dire che esso è avido di trangugiare il dischetto. Quando l'ho soddisfatto, ronza sommesso, facendo le fusa come un gatto contento, diventa vivo, e subito mette in luce il suo carattere: è alacre, soccorrevole, severo coi miei errori, testardo, e capace di molti miracoli che ancora non conosco e che mi intrigano. Purché alimentato con programmi adatti, sa gestire un magazzino o un archivio, tradurre una funzione nel suo diagramma, compilare istogrammi, perfino giocare a scacchi: tutte imprese che per il momento non mi interessano, anzi, mi rendono malinconico e immusonito come quel maiale a cui erano state offerte le perle. Può anche disegnare, e questo è per me un inconveniente di segno opposto: non avevo piú disegnato dalle elementari, e trovarmi adesso sotto mano un servomeccanismo che fabbrica per me, su misura, le immagini che io non so tracciare, e a comando me le stampa anche sotto il naso, mi diverte in misura indecente e mi distoglie da usi piú propri. Devo far violenza a me stesso per "uscire" dal programma-disegno e riprendere a scrivere. Ho notato che scrivendo cosí si tende alla prolissità. La fatica e il tempo, quando si scalpellava la pietra, conduceva allo stile "lapidario": qui avviene l'opposto, la manualita è quasi nulla, e se non ci si controlla si va verso lo spreco di parole; ma c'è un provvido contatore, e non bisogna perderlo d'occhio. Analizzando adesso la mia ansia iniziale, m'accorgo che era in buona parte illogica: conteneva un'antica paura di chi scrive, la paura che il testo faticato, unico, inestimabile, quello che ti darà fama eterna, ti venga rubato o vada a finire in un tombino. Qui tu scrivi, le parole appaiono sullo schermo nitide, bene allineate, ma sono ombre: sono immateriali, prive del supporto rassicurante della carta. "La carta canta", lo schermo no; quando il testo ti soddisfa, lo "mandi su disco", dove diventa invisibile. C'è ancora, latitante in qualche angolino del disco-memoria, o l'hai distrutto con qualche manovra sbagliata? Solo dopo giorni di esperimenti "in corpore vili" (e cioè su falsi testi, non creati ma copiati) ti convinci che la catastrofe del testo perduto è stata prevista dagli gnomi gentili che hanno progettato l'elaboratore: per distruggere un testo occorre una manovra che è stata resa deliberatamente complicata, e durante la quale l'apparecchio stesso ti ammonisce: "Bada, stai per suicidarti". Venticinque anni fa avevo scritto un racconto ["Il Versificatore", da "Storie naturali", Einaudi - N. d. M.T.] poco serio in cui, dopo molte esitazioni deontologiche, un poeta professionale si decide a comprare un Versificatore elettronico e gli delega con successo tutta la sua attività. Il mio apparecchio per ora non arriva a tanto, ma si presta in modo eccellente a comporre versi, perché mi permette innumerevoli ritocchi senza che la pagina appaia sporca o disordinata, e riduce al minimo la fatica manuale della stesura: "Cosí s'osserva in me lo contrappasso". Un amico letterato mi obietta che cosí va perduta la nobile gioia del filologo intento a ricostruire, attraverso le successive cancellature e correzioni, l'itinerario che conduce alla perfezione dell'Infinito: ha ragione, ma non si può avere tutto. Per quanto mi riguarda, da quando ho posto freno e sella al mio elaboratore ho sentito attenuarsi in me il tedio di essere un Dinornis, un superstite di una specie in estinzione: l'uggia del "sopravvissuto al suo tempo" è quasi scomparsa. Di un incolto, i Greci dicevano: "Non sa né leggere né nuotare"; oggi bisognerebbe aggiungere "né usare un elaboratore"; non lo uso ancora bene, non sono un dotto e so che non lo sarò mai, ma non sono piú un analfabeta. E poi, dà gioia poter aggiungere un item al proprio elenco dei "la prima volta che" memorabili: che hai visto il mare; che hai passato la frontiera; che hai baciato una donna; che hai destato a vita un golem.

(da Primo Levi "L'altrui mestiere" - Einaudi)

Libri di testo

Durante il corso, oltre al materiale reperibile online che verrà indicato di volta in volta (e sperabimente trovato autonomamente dagli studenti), ci si baserà largamente sugli argomenti trattati in:

• Lawrence Snyder, Fluency - Conoscere e usare l'informatica, Pearson Addison Wesley.
• Gregory Rawlins, Schiavi del computer?, Laterza.

Questi testi non vanno intesi come un manuale di istruzioni per superare l'esame (potete provare, ma il successo sarebbe improbabile) ma come dei validi supporti per l'apprendimento della materia.

Orari delle lezioni A.A. 2010-2011

lunedì (17:00 - 19:00) - Aula Aula 15 (Cnoss ex 4) (Cnos)
martedì (17:00 - 19:00) - Aula Aula 15 (Cnoss ex 4) (Cnos)
mercoledì (09:00 - 11:00) - Aula Aula 15 (Cnoss ex 4) (Cnos)
giovedì (09:00 - 11:00) - Aula Aula 15 (Cnoss ex 4) (Cnos)

Blog del corso di Informatica del corso di laurea in Scienze e Tecniche Psicologiche, Università del Salento.

In questo blog verranno pubblicate le notizie, il programma, i materiali e tutto ciò che riguarda il Corso.