Libro Vento (1) - PDF

Indice 1 Concetti di base dell’informatica 1 1.1 l’Informatica 1 1.2 Informazione 3 1.2.1 Rappresentazione binaria dell’informazione 4...

Indice 1 Concetti di base dell’informatica 1 1.1 l’Informatica 1 1.2 Informazione 3 1.2.1 Rappresentazione binaria dell’informazione 4 1.2.2 Rappresentazione dei numeri naturali 6 Dalla rappresentazione binaria a quella decimale 7 Dalla rappresentazione decimale a quella binaria 8 La base ottale e esadecimale 9 Dalla rappresentazione decimale a quella esadecimale 9 1.2.3 Rappresentazione dei numeri interi 10 Rappresentazione degli interi in segno e modulo 10 Rappresentazione degli interi in complementi 11 Rappresentazione in complementi diminuiti 12 1.2.4 Aritmetica sui numeri naturali e interi 13 Aritmetica sui naturali 13 Aritmetica sugli interi in segno e modulo 14 Aritmetica sugli interi in complementi 16 1.2.5 Rappresentazione dei numeri reali 16 1.2.6 Codifica e decodifica di un’informazione 18 Le unità di misura dell’informazione 20 1.3 Algoritmo, programma, esecutore 20 1.3.1 Algoritmo e Esecutore 21 1.3.2 Programma e Linguaggio 25 1.3.3 Risorse e Processo 27 1.4 Macchina di Von Neumann 30 1.4.1 La memoria principale 31 1.4.2 La CPU 32 1.5 Il ciclo generale del processore 34 1.6 La mappa dei concetti fondamentali dell’informatica 36 1.7 Conclusioni 37 1.8 Esercizi 38 i 2 Controllo di flusso 39 2.1 Le istruzioni semplici 39 2.1.1 L’istruzione di assegnazione 40 2.1.2 Le operazioni di ingresso e uscita 42 2.2 La rappresentazione degli algoritmi 43 2.3 I costrutti di programmazione 44 2.4 I costrutti nella programmazione strutturata 46 2.4.1 Costrutto sequenza 48 2.4.2 Costrutti selettivi 48 if-then e if-then-else 48 Case 51 2.5 Costrutti iterativi 53 2.5.1 Ciclo while 53 2.5.2 Ciclo repeat-until 55 2.5.3 Ciclo do-while 56 2.5.4 Ciclo for 56 2.6 Innesto di costrutti 58 2.7 Da un problema al diagramma di flusso 60 2.8 Conclusioni 68 2.9 Esercizi 68 3 Concetti di base della programmazione 73 3.1 I linguaggi di programmazione 73 3.2 Gli elementi di un programma 78 3.2.1 Costanti e variabili 78 3.2.2 Il sistema dei tipi 78 3.2.3 Sistema degli operatori 80 3.2.4 Operatori e tipologia 81 Gli operatori aritmetici 83 Operatori relazionali 83 Operatori logici 84 Precedenza e associatività degli operatori 84 3.3 Espressioni 87 3.4 Struttura di un programma C 88 3.4.1 Tipi e operatori in C 89 3.4.2 Istruzioni di ingresso e uscita 91 3.4.3 Strutture di controllo in C 93 Strutture di controllo selettive 93 Strutture di controllo iterative 95 3.5 Conclusioni 97 4 Algoritmi elementari 101 4.1 Problemi e Pattern di base 101 4.2 Un primo esempio di pattern 105 4.3 Algoritmi di base su sequenze di dati 107 4.3.1 Generazione di sequenze 109 4.3.2 Visita di sequenze 111 Visita di una sequenza con tappo 113 Visita di una sequenza di lunghezza nota 116 4.3.3 Accumulazione su una sequenza 118 4.3.4 Selezione di un elemento in una sequenza 121 4.3.5 Selezione di un elemento in una sequenza con interruzione di visita 131 4.4 Conclusioni 132 5 Sottoprogrammi 135 5.1 Astrazione 135 5.2 Sottoprogrammi 138 5.2.1 Funzioni e Procedure 142 5.3 Ambiente del sottoprogramma 145 5.3.1 Associazione dei parametri 147 Associazione per valore 147 Associazione per riferimento 148 5.4 Prototipi di funzioni e procedure 152 5.5 Struttura dell’ambiente 153 Visibilità e esistenza 154 Problematicità delle variabili globali 155 5.6 Esercizi 158 6 Tipi strutturati 159 6.1 Informazioni strutturate 159 6.2 Strutture 163 6.3 Array 164 6.3.1 Array multidimensionali 165 6.4 File 166 6.5 Esercizi 167 7 File 169 7.1 Introduzione ai file 169 7.1.1 Tipi di files 170 7.1.2 Formato dei files 171 7.1.3 Modalità di accesso 173 7.2 Operazioni sui file 174 7.2.1 Apertura e chiusura 174 7.2.2 Lettura e scrittura 176 Lettura e Scrittura su file di testo non formattati 176 7.3 Esercizi 177 8 Vettori e Sequenze 179 8.1 Pattern su vettori 179 8.2 Pattern su sequenze memorizzate in vettori 180 8.2.1 Memorizzazione di una sequenza in un vettore 181 8.2.2 Visita di una sequenza memorizzate 182 8.2.3 Accumulazione su una sequenza memorizzate 182 8.2.4 Selezione su una sequenza memorizzate 186 8.3 Implementazione dei pattern in C 188 8.4 Esercizi 196 9 Algoritmi di base 197 9.1 Problema della ricerca 197 9.1.1 Ricerca Lineare 200 Struttura dell’algoritmo 200 Implementazione dell’algoritmo 200 9.1.2 Ricerca Dicotomica (Binary Search) 202 Struttura dell’algoritmo 203 Implementazione dell’algoritmo 205 Variazione: ricerca dell’elemento piú vicino 206 9.1.3 Minimo e massimo 208 Struttura dell’algoritmo 208 Implementazione dell’algoritmo 209 9.2 Problema dell’ordinamento 209 9.2.1 Selection Sort 212 Struttura dell’algoritmo 212 Implementazione dell’algoritmo 213 9.2.2 Insertion Sort 214 Struttura dell’algoritmo 215 Implementazione dell’algoritmo 218 9.2.3 Bubble Sort 220 Struttura dell’algoritmo 220 Implementazione dell’algoritmo 223 9.2.4 Merge Sort 224 Struttura dell’algoritmo 224 Implementazione dell’algoritmo 228 9.2.5 Quick Sort 230 Struttura dell’algoritmo 231 Implementazione dell’algoritmo 233 9.2.6 Limite inferiore alla complessità degli algoritmi di ordinamento235 9.3 Esercizi 239 10 Strutture dati di base 243 10.1 Strutture dati dinamiche 243 10.1.1 Convenzioni per l’uso dell’allocazione dinamica 245 10.2 Array dinamici 247 10.2.1 Struttura dati, allocazione e deallocazione 247 10.2.2 Ridimensionamento di un array dinamico 249 10.2.3 Esempio d’uso 252 10.3 Pile 253 10.3.1 Operazioni su una pila 254 10.3.2 Realizzazione di una pila mediante array 255 10.3.3 Implementazione con un array a dimensione fissa 256 10.3.4 Implementazione con un array dinamico 259 10.4 Code 260 10.4.1 Operazioni su una coda 261 10.4.2 Realizzazione di una coda mediante array 261 10.4.3 Implementazione con un array a dimensione fissa 265 10.4.4 Implementazione con array dinamico * 265 10.5 Esercizi 270 11 I puntatori 271 11.1 I puntatori 271 11.1.1 Indirezione 273 11.1.2 Puntatori tipati 275 11.2 Aritmetica dei puntatori 276 11.3 Allocazione dinamica dei dati 279 11.4 Esercizi 282 Capitolo 1 Concetti di base dell’informatica Scrissi il mio primo programma a tredici anni. Serviva per giocare a tris. Il computer usato era ingombrante, lento e assolutamente irresistibile. Bill Gates Sommario L’obiettivo del presente capitolo è quello di introdurre i concetti fondamentali dell’informatica. In particolare viene pre- sentato il concetto di algoritmo e di sua rappresentazione, come i diagrammi di flusso e i linguaggi in pseudo-codice, anche se tali aspetti verranno ripresi e approfonditi nei capitoli successivi. Si chia- riscono inoltre i concetti di programma, di esecutore e di processo. Tali aspetti sono presentati mediante un semplice algoritmo in un campo diverso da quello dei calcolatori: la preparazione di un piatto di pasta al sugo, al fine di chiarire al lettore quanto sia importante il ricorso a linguaggi artificiali, specificamente pensati per superare l’ambiguità dei linguaggi che siamo soliti parlare. 1.1 l’Informatica L’informatica è una scienza molto recente che, in poco più di cinquant’anni di storia, ha rivoluzionato il nostro modo di vivere I cosiddetti digital natives, ovvero coloro che sono nati negli ultimi anni del ventesimo secolo, nel pieno del- Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. 2 Capitolo 1 la rivoluzione digitale, che sin da piccoli sono entrati in contatto forte con gli strumenti tecnologici, possono rendersene conto solo marginalmente. Solo chi ha vissuto, come l’autore di questo libro, a ridosso dell’inizio dell’era di- gitale, negli anni 70, ha reale contezza di cosa fosse la vita quando l’informatica era ai primi passi, in contrapposizione ad oggi; purtroppo le parole non sono sufficienti a rappresentare quel mondo, cosı̀ diverso e nel contempo vicino temporalmente. La diffusione capillare dell’informatica risale alla metà degli anni ottanta, ma non era accessibile a tutti: il costo dei primi personal computer si aggirava sui quindici milioni di lire che rapportati ai valori attuali del costo della vita potrem- mo quotare intorno ai trentamila euro; in quel mondo, senza internet, privo di posta elettronica, di telefonini e relativi sms, dove ascoltare musica e vedere film significava portare con sè ingombranti apparati con cassette magnetiche, e ancora i videogiochi erano agli albori, tutto era diverso. Certo non è questo il luogo dove abbandonarsi a pensieri nostalgici, ma una sola cosa può essere affermata con assoluta certezza: se dall’oggi al domani spegnessimo tutti i computers il mondo collasserebbe in quanto gran parte delle apparecchiature non potrebbe più funzionare. Può essere infatti utile evidenziare che quando parliamo di computer non biso- gna erroneamente pensare a quelli destinati ad uso personale (i portatili o i fissi), ma a tutti i sistemi che al loro interno usano un computer per espletare le loro funzioni, in gergo tecnico i sistemi embedded. Non volendo addentrarci in inutili definizioni, possiamo citare alcuni esempi: il motore di una qualsiasi auto moder- na usa una centralina che sovrintende al funzionamento ottimale del motore. Tale centralina altro non è che un computer senza tastiera e monitor (per questo detto embedded) equipaggiata con opportuni programmi che garantiscono le funzioni che la centralina deve assolvere. Già questo ci può apparire strano, un computer che governa il motore, ma se restiamo in tale ambito possiamo elencare altri si- stemi embedded presenti in un’autovettura moderna: quello che gestisce l’ABS, quello preposto a governare il sistemi antislittamento ASR, per poi citare ancora quello presente nel sistema di attivazione degli AIRBAG e ancora quello presente nell’eventuale antifurto satellitare. Più evidenti, ma non da trascurare, sono quelli presenti nei navigatori satellitari e nei sistemi per il parcheggio automatico, ormai in ampia commercializzazione. Ma i sistemi computerizzati risiedono anche nei televisori, nei lettori Mp3, nei nostri elettrodomestici, in definitiva nei posti più disparati: non è lontana dal vero l’affermazione che ogni oggetto associato al concetto di funzionamento possiede al suo interno uno o più sistemi computerizzati per la sua gestione e realizzazione. Per questi motivi, parlare oggi di informatica significa far riferimento ad un ambito disciplinare estremamente vasto, con dei contorni che anno dopo anno si espandono sempre più, diventando meno netti e chiari: è informatica la costru- zione di apparati computerizzati, la progettazione di programmi, l’applicazione di sistemi per il controllo computerizzato, la definizione di nuovi linguaggi e model- li per la progettazione, la realizzazione di nuovi modi per agevolare l’interazione dell’uomo con le macchine (usando grafiche avanzate o la voce), l’immaginare le applicazioni utili alla vita di tutti i giorni. Certo è lusinghiero, per chi opera in questo settore, immaginare che in pochis- Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. Concetti di base dell’informatica 3 simi anni l’informatica ha conquistato, e già da tempo, un dignitoso spazio tra le scienze esatte, registrando innovazioni metodologiche e tecnologiche da primato assoluto; è però non facile inseguire il fortissimo progresso tecnologico e metodolo- gico che si registra nella disciplina. Fermarsi anche pochi mesi nell’aggiornamento professionale significa restare indietro di molto. Il nostro compito è quindi quello di partire da zero, ma arrivare in poco tempo a padroneggiare i concetti fondamentali di questa affascinante disciplina: abbando- niamo quindi le chiacchiere motivazionali e passiamo alla trattazione dei concetti fondamentali, non prima però di esserci posti la prima fondamentale domanda: Che cosa è l’informatica? CURIOSITÀ Il termine informatica è stato introdotto da Philippe Dreyfus nel 1962; l’eti- mologia deriva dal termine francese informatique, come fusione di inform(ation electronique ou autom)atique. Il termine voleva rappresentare di conseguenza il trattamento dell’informazione mediante uno strumento automatico (il calco- latore). Tutti coloro che ritengono l’informatica come una scienza che parla inglese rimarranno stupiti dal fatto che in tale lingua non esiste l’equivalente di informatica; viene invece usato un termine molto più generico, ‘computer science’, che letteralmente si traduce in ‘scienza degli elaboratori’. Come il termine stesso suggerisce l’informatica è la convergenza di due aspet- ti distinti: l’informazione e la sua elaborazione automatica, ovvero mediante strumenti automatici. Corre l’obbligo di chiarire che per strumento automatico possiamo anche pensare ad un elaboratore meccanico, anche se oggigiorno tale disciplina è indissolubilmente legata all’impiego di calcolatori elettronici. Nei successivi paragrafi si presenterà dapprima il concetto di informazione, affrontando le problematiche di rappresentazione e codifica in un sistema di elabo- razione, successivamente saranno trattati i concetti di base della programmazione. Infine si daranno dei cenni all’architettura di base di un elaboratore elettronico. 1.2 Informazione Cominciamo con il chiarire il concetto di informazione: questo è legato indissolu- bilmente al concetto di scelta. Se non esiste scelta non c’è informazione, e solo dove esiste una scelta parliamo di informazione; possiamo ancora dire che, quanto più ampia è la scelta, maggiore è l’informazione. Proviamo a fare alcuni semplici esempi per convincercene. 1. La luce è accesa 2. Il semaforo è verde 3. Mario ha 37 anni Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. 4 Capitolo 1 La luce può trovarsi in uno tra due possibili stati {accesa, spenta}; dire che la luce è accesa significa dare un’informazione, precisare cioè che assume uno di tali due stati. Questa situazione è anche la più semplice in assoluto: è quella che prevede il numero minore di alternative. In questo caso si parla di scelta binaria; la quantità di informazione ad essa associata è la più piccola in assoluto e viene detta bit. La luce di un semaforo presuppone una scelta più ampia, nell’intervallo {verde, giallo, rosso}, aumentando di conseguenza la quantità di informazione associata; ancora più grande è l’informazione associata alla terza frase, dal momento che l’età di una persona può assumere valori interi compresi tra 0 e 130 (risulta ad oggi che la persona più longeva in assoluto è stata Jeanne Calment che ha superato i 122 anni). Da un punto di vista formale un’informazione può essere considerata come di seguito: Definizione Un’informazione è una tripla I={Attributo,Tipo, Valore} dove: l’Attributo è il nome associato all’informazione, che ne chiarisce anche il significato il Tipo è l’insieme di tutti i possibili valori che l’informazione può assumere il Valore è la scelta di uno specifico elemento all’interno del Tipo A titolo di esempio, per i tre casi in precedenza riportati, possiamo rispettiva- mente dire: 1. I1 = {Attributo= ‘luce’, Tipo ={accesa, spenta}, Valore= accesa} 2. I2 = {Attributo= ‘semaforo’, Tipo ={verde, giallo, rosso}, Valore= verde} 3. I3 = {Attributo= ‘età di Mario’, Tipo ={n ∈ N |0 ≤ n ≤ 130}, Valore= 37}, avendo denotato con N l’insieme dei numeri interi positivi. Attenzione! Bisogna prestare attenzione alla cardinalità del tipo, ovvero da quanti elementi esso si compone: un tipo deve essere finito, altrimenti non può essere adeguatamente rappresentato in un calcolatore elettronico o su un qualunque altro mezzo o supporto fisico. 1.2.1 Rappresentazione binaria dell’informazione Strettamente legato ad un’informazione è il concetto di rappresentazione. La rap- presentazione è il risultato di un procedimento che adotta delle regole per trovare una codifica non ambigua dell’informazione in un particolare linguaggio. Anche in questo caso può essere utile fare un esempio che ci chiarisca le idee: consi- deriamo l’informazione I3 in precedenza introdotta. L’età di Mario può essere equivalentemente rappresentata in uno dei seguenti modi: Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. Concetti di base dell’informatica 5 APPROFONDIMENTO L’informazione si misura in bit, o meglio attraverso il numero di bit minimo per rappresentarne il tipo T (ovvero tutte le possibili scelte associate all’informa- zione stessa); quindi se la cardinalità di T è n, la quantità q dell’informazione relativa è pari a: q = dlog2 ne, dove la notazione dxe (detta ceil) indica il nu- mero intero immediatamente più grande di x. Per convincerci che esiste una relazione di tipo logaritmico tra la cardinalità di T e la quantità di bit minima per rappresentare l’informazione relativa, consideriamo che con q bit possiamo creare 2q stringhe diverse, ognuna delle quali può essere associata ad un valore dell’informazione da codificare. Deve quindi essere 2q ≥ n, e cioè q ≥ log2 n, da cui la precedente q = dlog2 ne. Le informazioni I1 , I2 e I3 hanno le relative quantità q1 , q2 e q3 pari rispettivamente a: q1 =dlog2 2e=d1e=1, q2 =dlog2 3e= d1.58e=2 e q3 =dlog2 130e= d7.02e=8. trentasette: ovvero scrivendo l’età a lettere nella lingua italiana; 37: ovvero rappresentando la stessa informazione mediante un numero (nel sistema decimale); XXXVII: usando il sistema di numerazione romano; thirthy-seven: scrivendo l’età a lettere in lingua inglese; 100101: usando cioè un sistema di numerazione diverso da quello a cui siamo abituati, il sistema binario, con il quale saremo costretti a familiarizzare presto. A questo punto è lecito chiedersi: quante altre tecniche di rappresentazione posso adottare? La risposta è semplice: infinite tecniche, ma la cosa importante è che per trasferire un’informazione tra due persone chi la produce e chi la consulta deve conoscere il metodo di rappresentazione usato, altrimenti nascono ambiguità o addirittura non si è in grado di risalire al suo valore. Ad esempio se non dichiaro il metodo di rappresentazione usato, qualcuno potrebbe ritenere, che la frase “età di Mario=100101” (ottenuta usando la rappre- sentazione binaria) voglia dire che Mario ha centomilacentouno anni, interpretando come decimale un numero che invece è espresso in base due. In questo caso Mario si porterebbe bene i suoi anni! Per i motivi appena citati i metodi per trattare le informazioni è necessario definire accuratamente le regole usate per la sua rappresentazione. Tra tutti i metodi adottabili, quello certamente più importante per un informa- tico è la rappresentazione binaria, dal momento che tutti i sistemi di elaborazione la adottano. Essa si basa sulla rappresentazione nelle due cifre binarie (0 e 1), dette digit da cui il termine rappresentazione digitale. La rappresentazione digitale di un’informazione ha un’importanza fondamen- tale: infatti, solo nel caso in cui l’informazione può essere rappresentata come sequenze di cifre binarie, può essere memorizzata, trasferita o elaborata da un Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. 6 Capitolo 1 CURIOSITÀ Il termine bit deriva dalla fusione di due parole: Binary e digIT; poiché digit in inglese vuol dire cifra, bit è l’abbreviazione di cifra binaria. computer. Un esempio tra i molti: il trasferimento di musica su internet, la possi- bilità di ascoltarla con un opportuno programma su un computer, di creare archivi di brani sulle memorie oggi disponibili, passa attraverso un passo imprescindibi- le: la musica è rappresentata numericamente, o meglio attraverso una sequenza (lunghissima) di bit. Ovviamente trattare i metodi per rappresentare digitalmente un qualunque tipo di informazione non è compito semplice, anche perché gli standard oggi di- sponibili sono tanti. Ci limiteremo a presentare in questo libro gli aspetti essenziali, soffermandoci prevalentemente sui contenuti concettuali e metodologici. 1.2.2 Rappresentazione dei numeri naturali Il sistema di numerazione binario è un sistema posizionale e pesato, come quello decimale che siamo abituati a trattare quotidianamente, con l’unica differenza che la base adottata è 2 anziché 10. Definizione Un sistema di numerazione si dice posizionale se le cifre (o più in generale i simboli) usate per scrivere i numeri assumono valori diversi a seconda della posizione che occupano. Si dice pesato perché ad ogni posizione è associato un peso espresso come potenza della base. Ad esempio nel sistema posizionale pesato decimale (quello comunemente usa- to), leggendo da destra verso sinistra le varie cifre, queste assumono valori diversi; in particolare l’ultima posizione rappresenta le unità, la penultima le decine, suc- cessivamente le centinaia, le migliaia, e cosı̀ discorrendo. Il numero può essere quindi visto come una somma di prodotti: si moltiplica ogni cifra per il suo peso e si sommano tutti i risultati parziali ottenuti. Pertanto alla sequenza di cifre 432 viene associata la seguente interpretazione: 2 unità, 3 decine e 4 centinaia, ovvero 400 + 30 + 2, quattrocentotrentadue. Ad un’analisi più attenta possiamo notare che, sempre partendo da destra verso sinistra, i pesi associati alle varie posizioni sono potenze crescenti della base: in particolare il peso della prima posizione (indicata con posizione 0) è 100 = 1, quello della successiva è 101 = 10; generalizzando, alla posizione i-ma corrisponde il peso 10i−1. Per formalizzare la trattazione, come risulta evidente dalla figura 1.1, indiche- remo con ci le cifre di un numero (la loro numerazione parte da zero e cresce da destra verso sinistra) , e con pi i relativi pesi; in tal modo per la sequenza 432 si ha: c0 = 2, c1 = 3, c2 = 4, p0 = 100 = 1, p1 = 101 = 10, p2 = 102 = 100. Pertanto il numero ad esso associato sarà: Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. Concetti di base dell’informatica 7 n = c0 p0 + c1 p1 + c2 p2 = 2 × 1 + 3 × 10 + 4 × 100 = 2 + 30 + 400. 102 101 100 P esi 4 3 2 Cif re c2 c1 c0 Figura 1.1 Il sistema posizionale pesato in base dieci: ogni cifra ci è pesata per la relativa potenza di 10, in funzione del suo posto; ad esempio la cifra di posto 2 c2 =4 è pesata per 102 =100. Quanto appena detto per il sistema posizionale pesato decimale si generalizza semplicemente al caso di una base b qualsiasi; l’unica precisazione è che se la base è b, avremo bisogno di b cifre, esattamente come in base 10 abbiamo bisogno delle dieci cifre tradizionali. In tal caso, una stringa in base b: cn cn−1 cn−2 · · · c1 c0 |b , dove il simbolo |b denota che essa è espressa in base b, rappresenta il numero: n X n X N= ci p i = ci bi. (1.1) i=0 i=0 Dalla rappresentazione binaria a quella decimale Il passaggio dalla rappresentazione binaria a quella decimale è molto semplice alla luce delle considerazioni appena fatte; basta infatti applicare la formula 1.1, con la sostituzione b = 2. Cominciamo a familiarizzare con i pesi in aritmetica binaria: p0 = 20 = 1 p1 = 21 = 2 p2 = 22 = 4 p3 = 23 = 8 e via via procedendo per valori crescenti delle potenze di 2: 16, 32, 64, 128, 256, 512, 1024, 2048, etc., come riportato nell figura 1.2. A titolo di esempio riprendiamo la stringa relativa all’informazione I3 , l’ormai famosa ‘età di Mario’: 100101|2 ; applicando la formula 1.1 si ottiene: 100101|2 = 1 × 20 + 0 × 21 + 1 × 22 + 0 × 23 + 0 × 24 + 1 × 25 = 1 + 4 + 32 = 37 Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. 8 Capitolo 1 b2 b1 b0 P esi c2 c1 c0 128 64 32 16 8 4 2 1 P esi 0 0 1 0 0 1 0 1 Cif re c7 c6 c5 c4 c3 c2 c1 c0 Figura 1.2 Il sistema posizionale pesato in base b e, in basso, particolarizzato in base due, nel caso di 8 bit, ovvero di un byte. Nell’esempio viene riportata la rappresentazione del numero 37; poichè per rappresentare 37 sarebbero sufficienti 6 bit, la sua rappresentazione su 8 bit si ottiene aggiungendo degli zeri a sinistra. Dalla rappresentazione decimale a quella binaria Mentre il procedimento per passare da un una stringa in base b all’equivalente numero in base 10 è cosı̀ immediato da poter effettuare la conversione a mente, il procedimento inverso è più oneroso. Esso si basa sulla divisione successiva del numero da convertire per la base b, memorizzando i valori dei resti di tali divisioni successive. Il procedimento continua fintantoché il numero (successivamente di- viso) assume valore zero. Particolarizziamo il procedimento, per il numero 37|10 , cercandone la rappresentazione in base 2. 37 : 2 = 18, R0 = 1; dividendo 37 per 2, si ottiene 18 con un resto di 1; il procedimento viene riapplicato al risultato ottenuto dalla prima divisione, ovvero 18; 18 : 2 = 9, R1 = 0; si ottiene 9, con zero resto; continuando; 9 : 2 = 4, R2 = 1; 4 : 2 = 2, R3 = 0; 2 : 2 = 1, R4 = 0; 1 : 2 = 0, R5 = 1; A questo punto leggendo i resti Ri per valori decrescenti di i si ottiene la sequenza 100101|2 che è quella attesa. L’implementazione dell’algoritmo per la conversione di base verrà presentato nel capitolo 4. Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. Concetti di base dell’informatica 9 La base ottale e esadecimale Molte delle considerazioni fatte nelle precedenti sezioni possono essere estese per analogia anche ad altre basi, diverse da quella binaria; a titolo di esempio, con- sideriamo due basi molto comunemente impiegate in informatica: quella ottale (base 8) e quella esadecimale (base 16). Tali basi, come tutte quelle potenze di 2 (4,8,16), hanno importantissime proprietà che vengono trattate nei testi avanzati. In base ottale, si usano le 8 cifre che vanno da 0 a 7, e i pesi sono 1, 81 = 8, 82 = 64, e cosı̀ via. Per tale base si applicano immediatamente tutte le considerazioni finora fatte, sia in merito alla conversione in base dieci, che dalla base 10 a quella ottale. A titolo di esempio, per convertire in base 10 il numero 43|8 , basta semplice- mente applicare la formula 1.1, con b = 8, ottenendo: 43|8 = 3 × 80 + 4 × 81 = 3 + 32 = 35 Per quanto riguarda la base esadecimale, l’unica ulteriore precisazione da fare è legata alle cifre da impiegare: abbiamo bisogno di 16 cifre, ma noi (in base 10) ne impieghiamo solo dieci: bisogna introdurre altre sei cifre, quelle che vanno da 10 a 15. Convenzionalmente sono indicate con le prime lettere dell’alfabeto: a=10, b=11, c=12, d=13, e=14, f=15. Si converta in base 10 il numero 4d|16 ; basta semplicemente applicare la formula 1.1, con b = 16, ottenendo: 4d|16 = 13 × 160 + 4 × 161 = 13 + 64 = 77 CURIOSITÀ Passare in una base più grande di 10, ad esempio esadecimale, può essere un buon metodo per non raccontare bugie al compleanno, ma far apparire molto meno anni, almeno agli occhi di quelli che non padroneggiano i sistemi di numerazione in base diversa da dieci. Considerate ad esempio una bella torta con due cifre di zucchero 3 e 2; il festeggiato non chiarisce che ha espresso la propria età in base sedici, e tutti credono stia bluffando sulla propria età. Dopo aver spento le candeline il festeggiato si esibisce in una lezione sulle aritmetiche in basi diverse, e nel chiarire che ormai Lui ragiona solo in base 16, fa presente che 32|16 è eguale a 50 (in base dieci); infatti 32|16 = 2 + 3 × 161 = 50. Dalla rappresentazione decimale a quella esadecimale Proviamo a generalizzare l’algoritmo presentato nella precedente sezione per con- vertire la rappresentazione di un numero dalla base 10 a quella esadecimale. Con- sideriamo a tale scopo il numero 50. Applicando divisioni successive per la base 16, si ha: 50 : 16 = 3, R0 = 2; dividendo 50 per 16, si ottiene 3 con un resto di 2; passiamo a dividere per 16 il numero ottenuto Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. 10 Capitolo 1 3 : 16 = 0, R1 = 3; si ottiene 0, con resto 3 Leggendo i resti Ri per valori decrescenti di i si ottiene: 50|10 = 32|16 1.2.3 Rappresentazione dei numeri interi La rappresentazione dei numeri interi Z = {0, ±1, ±2, ±3,... } in un calcolatore riveste una notevole importanza pratica, dal momento che tali numeri sono larga- mente impiegati nelle elaborazioni numeriche. Esistono diverse rappresentazioni possibili di cui le più comuni sono: per segno e modulo per complementi alla base per complementi alla base diminuiti Rappresentazione degli interi in segno e modulo Questa rappresentazione è la più semplice e immediata: il numero intero z da rappresentare viene preliminarmente diviso nelle sue componenti di base, il segno e il modulo, ognuna delle quali è rappresentata separatamante. La semplicità di tale soluzione risiede nel fatto che il segno è un’informazione binaria, che può assumere i due valori ’+’ e ’-’, mentre il modulo di un intero è un numero naturale, la cui rappresentazione è stata trattata nel precedente paragrafo. Tipicamente il segno viene rappresentato con la seguente convenzione: il segno ’+’ è rappresentato con il bit ’0’, mentre il segno ’-’ con il bit ’1’; il bit che si usa per il segno è quello più a sinistra della parola usata (comunemente detto MSB che sta per Most Significant Bit). Qualche esempio può essere utile per chiarire il concetto. Supponiamo di voler rappresentare su 8 bit il numero z = −2. Il segno viene rappresentato con l’MSB a 0, mentre il modulo di z, pari a 2, nei rimanenti 7 bit, usando la rappresentazione per i numeri naturali. Nella figura 1.3 si riportano alcuni esempi. La rappresentazione in segno e modulo, sebbene molto semplice, non è utiliz- zata nei sistemi di elaborazione. I motivi di ciò sono molteplici. Da un lato la doppia rappresentazione dello zero crea un grosso problema: se abbiamo un nume- ro e vogliamo confrontarlo con zero, dobbiamo effettuare il doppio confronto con -0 e +0, e ciò è molto scomodo, specialmente se questa operazione viene effettuata in hardware con dei circuiti. Un altro aspetto non trascurabile è che per effettuare le operazioni aritmetiche di base abbiamo bisogno sia di un sottrattore che di un sommatore: ciò sembra naturale ad un primo sguardo, in quanto noi siamo abi- tuati a fare ciò. Se dobbiamo sommare -5 a 2, essendo i numeri di segno discordi, si opera una sottrazione tra i moduli e successivamente si stabilisce il segno del risultato: questo coincide ovviamente con il segno del numero con il modulo più grande. Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. Concetti di base dell’informatica 11 0 0 0 0 0 0 1 0 a) s m6 m5 m4 m3 m2 m1 m0 1 0 0 1 1 0 0 0 b) s m6 m5 m4 m3 m2 m1 m0 1 0 0 0 0 0 0 0 c) s m6 m5 m4 m3 m2 m1 m0 0 0 0 0 0 0 0 0 d) s m6 m5 m4 m3 m2 m1 m0 Figura 1.3 Alcuni esempi di rappresentazione di numeri interi in segno e mo- dulo. a) la rappresentazione del numero 2 e b) di -24. Si noti come lo zero è suscettibile di due rappresentazioni: in c) è rappresentato come -0 e in d) come 0. In particolare quest’ultimo aspetto ha determinato uno scarso successo della rappresentazione per segno e modulo a vantaggio della rappresentazione per com- plementi trattata nella successiva sezione; quest’ultima permette di effettuare le operazioni aritmetiche di somma e sottrazione (anche per numeri negativi) usando solo due circuiti: un sommatore e un complementatore, che, come vedremo è molto semplice. Rappresentazione degli interi in complementi Questo schema deriva il suo nome dal fatto che nella rappresentazione del numero, qualora risuti negativo, viene utilizzato un suo trasformato, detto per l’appunto complemento a due; prima di addentrarci nei dettagli è necessario definire il com- plemento a due di un numero, che richiede di conoscere il numero n di bit usati per la rappresentazione. Definizione Sia z ∈ Z un numero intero, definiamo complemento a due di z su n bit il seguente valore: z = 2n − z Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. 12 Capitolo 1 Un esempio può senz’altro servirci a fissare il concetto appena introdotto; con- sideriamo il caso in cui n = 8. Se z = 15 allora applicando la precedente definizione abbiamo che: z = 28 − z = 256 − 15 = 241. A questo punto possiamo introdurre la rappresentazione per complementi a due su n bit. Dato un numero z la sua rappresentazione negli n bit cambia a seconda che z pia positivo o negativo. In particolare se indichiamo con m il numero effettivamente rappresentato (che può non coincidere con z), abbiamo: ( z if z ≥ 0 m= (1.2) z if z < 0 In definitiva quindi se il numero è positivo o nullo viene rappresentato il suo modulo, altrimenti, se negativo, viene rappresentato il suo complemento. Nella figura 1.4 si riportano alcuni esempi. Può essere utile fare alcune con- siderazioni sulla rappresentazione per complementi. I numeri che hanno il MSB eguale a zero sono rappresentazione di numeri positivi. Il massimo numero rap- presentabile è quindi quello con tutti i rimanenti 7 bit pari a uno e vale quindi 27 − 1. Viceversa le rappresentazioni che hanno il MSB pari a 1 corrispondono a numeri negativi. Il numero negativo più piccolo rappresentabile è quello costituito da tutti i rimanenti bit pari a zero, che corrisponde, come abbiamo visto nella figura 1.4 al valore -128. Infatti essendo in quest’ultimo caso il numero negati- vo viene rappresentato il complemento; pertanto applicando la definizione risulta m = z e risultando rappresentato in binario z = 0, si ha che 28 − z = 0, da cui z = −28 = −256. Rappresentazione in complementi diminuiti Un’evoluzione della rappresentazione per complementi è quella per complementi diminuiti; l’idea alla base di tale rappresentazione non è molto diversa da quella per complementi: i numeri negativi sono rappresentati mediante il loro complemento alla base diminuito. Definizione Sia z ∈ Z un numero intero, definiamo complemento diminuito di z su n bit il seguente valore: z = 2n − z − 1 Il complemento diminuito è quindi pari al complemento alla base diminuito di uno, e da ciò deriva il suo nome. Il vantaggio di tale rappresentazione, che mantiene tutti i vantaggi già ana- lizzati per la rappresentazione in complementi alla base, risiede nella semplicità del complementatore. Infatti il complemento diminuito di un numero si ottiene immediatamente: basta complementare il numero bit a bit, invertendo gli ’0’ in ’1’ e viceversa. Ometteremo quindi ulteriori dettagli su tale rappresentazione, lasciando al lettore il compito di familiarizzare con essa mediante qualche esercizio. Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. Concetti di base dell’informatica 13 0 0 0 0 0 1 0 1 a) m7 m6 m5 m4 m3 m2 m1 m0 1 1 1 0 1 0 0 0 b) m7 m6 m5 m4 m3 m2 m1 m0 1 1 1 1 1 1 1 1 c) m7 m6 m5 m4 m3 m2 m1 m0 0 0 0 0 0 0 0 0 d) m7 m6 m5 m4 m3 m2 m1 m0 1 0 0 0 0 0 0 0 e) m7 m6 m5 m4 m3 m2 m1 m0 Figura 1.4 Alcuni esempi di rappresentazione di numeri in complementi alla base. a) la rappresentazione del numero 5 e b) di -24. Per quest’ultimo il numero effettivamente rappresentato in binario è 256-24=232, come si comprende leggendo il numero rappresentato come se fosse un numero naturale. c) la rappresentazione del numero -1, effettivamente rappresentato come 256-1=255. Si riportano inoltre due rappresentazioni notevoli; in d) la rappresentazione dello zero e in e) quella di -128. 1.2.4 Aritmetica sui numeri naturali e interi In questa sezione analizziamo gli algoritmi per effettuare le operazioni aritmetiche di somma e sottrazione sui numeri interi e naturali. Aritmetica sui naturali Avviamo la disamina con i numeri naturali. L’algoritmo della somma è pratica- mente identico a quello che si utilizza nell’aritmetica decimale, con la somma delle cifre di posto omologo e la propagazione del riporto. Come nella numerazione decimale anche in questo caso si genera un riporto quando si supera il valore della Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. 14 Capitolo 1 CURIOSITÀ Esiste un algoritmo molto semplice per calcolare il complemento a due di un numero negativo. A partire dalla definizione dovremmo sottrarre il numero dato da 2n ; proviamo invece a rappresentare il modulo del numero in binario. Successivamente invertiamo tutti i suoi bit e infine, partendo da destra verso sinistra trasformiamo gli 1 in 0 fino a raggiungere il primo 0 che sarà l’ultimo bit a essere invertito. Quest’ultima operazione equivale a sommare uno alla rappresentazione ottenuta. Ad esempio consideriamo il complemento di -24: 24 → -24 → 0 0 0 1 1 0 0 0 → 1 1 1 0 0 1 1 1 → 1 1 1 0 1 0 0 0 che coincide con la rappresentazione ottenuta nella figura 1.4 con il metodo classico. base; tale riporto viene aggiunto alla somma delle cifre immediatamente a sinistra. L’unica nota di rilievo è quindi il fatto che 1+1=0 con la generazione di un riporto. Nella tabella 1.1 si riportano alcuni esempi di somma su numeri naturali; l’u- nica accortenza da avere è il controllo dell’overflow, nel quale si incorre quando il risultato supera il massimo valore rappresentabile. Per questo motivo la somma tra due addendi a n bit genera il risultato a n + 1 bit, di cui quello più a sinistra è di overflow. Se il bit di overflow assume il valore 1, vuol dire che il risultato eccede l’intervallo di rappresentazione. Anche l’operazione di sottrazione è simile a quella in base 10, con la propagazio- ne dei prestiti da destra verso sinistra. L’operazione può generare nel risultato un underflow quando il minuendo è più piccolo del sottraendo; basta qualche esempio per acquisire la giusta padronanza. Aritmetica sugli interi in segno e modulo L’aritmetica degli interi rappresentati in segno e modulo è quella più immediata per chi si avvicina all’informatica in quanto è molto simile a quella che noi siamo abituati a usare quotidianamente in base dieci. Le operazioni si effettuano tra i moduli dei numeri in esame, mentre il segno viene trattato separatamente. In particolare, a partire dall’operazione richiesta e dal segno degli operandi, si determina l’effettiva operazione da effettuare sui moduli e il segno del risultato. Può apparire strano che l’operazione effettuata sui moduli non coincida con quella effettivamente richiesta, ma con un semplice chiarimento scopriremo che tale aspetto è naturale e immediato. Se viene richiesta una somma tra due numeri z1 e z2 , e questi risultano entrambi positivi o negativi viene effettivamente svolta la somma tra i moduli. Il segno del risultato sarà positivo se entrambi i numeri sono positivi o negativo se entrambi sono negativi. Se invece bisogna sommare due numeri di segno opposto, viene svolta un’operazione di sottrazione tra il numero con il modulo più grande e quello con il modulo più piccolo. Il risultato in questo caso avrà il segno del numero con il modulo più grande. Se invece viene richiesta una sottrazione tra due numeri e il segno di minuendo e sottraendo sono discordi si effettua la somma tra i moduli. Il segno risultante è quello del minuendo. Un ultimo caso è quando i segni sono concordi: si effettua la Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. Concetti di base dell’informatica 15 15+5 131+18 139+203 0 0001 1110 Carry 0 0000 0100 Carry 1 0001 0110 Carry 0000 1111 + (15) 1000 0011 + (131) 1000 1011 + (139) 0000 0101 (5) 0001 0010 (18) 1100 1011 (203) ====== ====== ====== 0001 0100 (20) 1001 0101 (149) 0101 0110 OF (86) a) b) c) 15-5 131-18 139-203 0 0000 0000 Carry 0 110 0000 Carry 1 1000 0000 Carry 0000 1111 - (15) 1000 0011 - (131) 1000 1011 - (139) 0000 0101 (5) 0001 0010 (18) 1100 1011 (203) ====== ====== ====== 0000 1010 (10) 0111 0001 (113) 1100 0000 UF (-64) d) e) f) Tabella 1.1 Alcuni esempi di somme e differenze tra numeri naturali. Sulla prima riga ci sono i riporti (in inglese detti carry) via via generati. Il MSB del curry rappresenta il bit di overflow (per le somme) o di underflow (per le differenze). sottrazione tra i moduli e il segno risultante è quello del minuendo se il suo valore assoluto è maggiore di quello del sottraendo, altrimenti è quello opposto. Nella figura 1.2 si riportano alcuni esempi; questi non sono esaustivi rispetto alle casi- stiche appena riportate, ma ampiamente sufficienti a comprendere il meccanismo in base al quale si opera. 15+5 15+(-24) 24-121 0 001 1110 Carry 0 001 1110 Carry 1 111 0000 Carry 000 1111 + (15) 001 1000 - (24) 111 1001 - (121) 000 0101 (5) 000 1111 (15) 001 1000 (24) ====== ====== ====== s=0 001 0100 (20) s=1 000 1001 (-9) s=1 110 0001 (-97) a) b) c) Tabella 1.2 Alcuni esempi di operazioni tra interi rappresentati in segno e mo- dulo. In a) una somma tra due numeri dello stesso segno. Si sommano i moduli e il segno è quello degli addendi. In b) una somma tra numeri di segno opposto: 15-24; si effettua la differenza tra 24 e 15 e il risultato è negativo. In c) un esempio di sottrazione tra due numeri, 24 e 121, che si riconduce alla sottrazione tra 121 e 24, attribuendo al risultato il segno meno. Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. 16 Capitolo 1 Aritmetica sugli interi in complementi Le operazioni sugli interi per complementi sono particolarmente semplici; come chiarito in precedenza con questa rappresentazione è necessario disporre solo di un sommatore, in quanto anche la differenza viene eseguita attraverso un som- matore. Ovviamente è anche necessario disporre di un complementatore, ovvero di un algoritmo (spesso reallizzato in hardware mediante un opportuno circuito) in grado di calcolare il complemento. Un’altra importante caratteristica di tale rappresentazione è che, a differenza di quella per segno e modulo, tutti i bit della rappresentazione (compreso il MSB che gioca il ruolo del segno) sono trattati co- me se fossero cifre utili del numero, provvedendo a semplificare ulteriormente la circuiteria necessaria. Nel caso della somma tra due numeri le operazioni avvengono con l’algoritmo già analizzato in precedenza per i naturali, ovvero sommando in binario le rappre- sentazioni bit a bit e tenendo in conto del riporto. Ovviamente bisogna avere cura di trasformare in complementi alla base gli addendi negativi. Nel caso in cui si volesse operare una differenza tra due numeri, ci si riconduce semplicemente alla somma, complementando il sottraendo, ovvero: z = z1 − z2 = z1 + z2. A questo punto ci si riconduce alla somma. Nella figura 1.3 si riportano alcuni esempi. Si noti esplicitamente il fatto che si usano tutte le cifre della rappresentazione, compreso il segno, e come quest’ultimo sia correttamente determinato semplicemente sommando bit a bit i numeri. 15+5 15+(-24) 121-24 = 121+(-24) 0 0001 1110 Carry 0 0001 0000 Carry 1 1111 0000 Carry 0000 1111 + (15) 0000 1111 + (15) 0111 1001 - (121) 0000 0101 (5) 1110 1000 (-24) 1110 1000 (24) ====== ====== ====== 0001 0100 (20) 1111 0111 (-9) 0110 0001 (97) a) b) c) Tabella 1.3 Alcuni esempi di operazioni tra interi rappresentati con comple- menti alla base. In a) una somma tra due numeri dello stesso segno e in b) una somma tra numeri di segno opposto con risultato negativo che risulta correttanen- te rappresentato. In c) un esempio di sottrazione tra due numeri, 121 e 24, che può essere ricondotto alla somma tra 121 e -24, evitando cosı̀ il sottrattore. 1.2.5 Rappresentazione dei numeri reali La rappresentazione di numeri reali nei sistemi di elaborazione è molto importante, dal momento che essi vengono impiegati in moltissimi algoritmi di calcolo. Sebbene esistano due diverse tipologie di rappresentazione dei numeri reali, rispettivamente dette in virgola fissa e in virgola mobile, noi ci limiteremo a trattare esclusivamente Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. Concetti di base dell’informatica 17 COMPLEMENTI ALLA BASE: I RIPORTI Nel caso della rappresentazione in complementi alla base la gestione dei riporti è più complessa di quella relativa ai numeri naturali. Può essere utile citare la problematica che si crea, senza approfondirla. In particolare nel caso in cui si stia effettuando una somma tra un positivo e un negativo con il positivo più grande si genera un riporto inaspettato che NON deve essere interpretato come overflow. Il caso c) della tabella 1.3 ne è un esempio. Analoga situazione avviene nel caso in cui si sommino due numeri negativi. quest’ultima. Il motivo di questa scelta risiede nel fatto che la rappresentazione in virgola mobile è oggigiorno molto più diffusa in virtù anche dei suoi innumerevoli vantaggi. I REALI IN VIRGOLA FISSA Come il nome suggerisce, nella rappresentazione in virgola fissa un numero reale è rappresentato con un numero prefissato di cifre intere e decimali; sebbene semplice questo tipo di rappresentazione presenta l’inconveniente che non si sfruttano al meglio le cifre a disposizione. A titolo di esempio si consideri di avere (in base 10) 5 cifre intere e tre decimali: il numero a 5 cifre significative 6.3453 viene troncato nella parte decimale. Infatti nonostante siano disponibili 8 cifre significative, siamo vincolati ad averne 3 decimali. Il numero viene rappresentato come 00006.345 forzatamente. In particolare un numero in virgola mobile è costituito da due parti: la mantissa e l’esponente. Prima di analizzare come si opera in base 2, può essere utile fare qualche esempio in base 10, allo scopo di fissare alcuni concetti essenziali. Supponiamo di considerare un numero reale qualsiasi r ∈ R; r in generale può avere un numero infinito di cifre dopo la virgola (si pensi ad esempio ai numeri periodici). Bisogna quindi rinunciare a rappresentare tutte le cifre dal momen- to che avremmo bisogno di spazio infinito (carta o bit che siano); il numero è quindi rappresentato mediante un numero finito di cifre (accettando quindi un’ap- prossimazione o troncamento) che costituiscono la mantissa e il prodotto per una potenza opportuna della base. Mantissa e esponente della base sono quindi i due elementi della rappresentazione. Si consideri ad esempio il numero reale periodico: r = 123.9 Questo può rappresentarsi (si ricordi la notazione scientifica) nella forma: r = M · 10e = (M, e) con M mantissa e e esponente. Ovviamente, come è ben noto, le rappresentazioni di uno stesso numero r sono molteplici; nel caso in esame se la mantissa è di 6 cifre sono possibili tutte le seguenti: r = 123.9 = 123.999 · 100 = (123.999, 0) r = 123.9 = 123999 · 10− 3 = (123999, −3) Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. 18 Capitolo 1 r = 123.9 = 12.3999 · 101 = (12.3999, 1) r = 123.9 = 0.123999 · 103 = (0.123999, 3) Quest’ultima rappresentazione è detta normalizzata: gode della proprietà che la mantissa ha parte intera minore di uno e la sua prima cifra decimale è diversa da zero. Si noti come in questa rappresentazione la parte intera della mantissa si può omettere (essendo sempre zero). Nella grande maggioranza dei sistemi di elaborazione i numeri reali vengono rappresentati in accordo allo standard IEEE 754. In particolare essendo la base di numerazione binaria, la rappresentazione (della lunghezza di base di 32 bit) è effettuata in segno e modulo per la mantissa e come numero naturale per l’espo- nente, dopo che a quest’ultimo è stato applicato una polarizzazione. In effetti gli esponenti sono negativi e vanno da -126 a 127; per evitare la rappresentazione del segno, non si rappresenta il reale esponente e bensı̀ e + 127, avendo cura poi di tenerne conto di tale polarizzazione quando si tratta il numero. Facciamo un semplice esempio, provando a codificare il numero r = 118.625. Il primo passo è quindi quello di determinare l’esponente e la mantissa. Il numero in binario è: r = 1110110.101 Infatti abbiamo: r = 1·26 +1·25 +1·24 +1·22 +1·21 +1·2−1 +1·2−3 = 64+32+16+4+2+1/2+1/8 A questo punto si procede alla normalizzazione, spostando la virgola verso sinistra, lasciando solo un uno alla sua sinistra: r = 1110110.101 = 1.110110101 · 26 Quindi la mantissa è la parte a destra della virgola, e l’esponente è pari a 6, ma dobbiamo convertirlo in forma binaria e polarizzarlo, aggiungendo 127. Quindi e = 133 che in binario su 8 bit è e = 10000101. In definitiva quindi: r = 1.110110101 · 210000101 = (M, e) = (110110101, 10000101) Allocando i bit nei quattro byte disponibili e riempendo la mantissa con tutti zeri a sinistra fino a riempire i 23 bit a disposizione si ottiene la rappresentazione del numero in formato IEEE 754 mostrata nella figura 1.5. 1.2.6 Codifica e decodifica di un’informazione Dopo aver introdotto i concetti di base della rappresentazione di numeri in base binaria, bisogna affrontare il problema di rappresentare una qualsiasi informazione in termini di bit; solo cosı̀ sarà infatti possibile memorizzarla e trattarla in un sistema di elaborazione elettronico. Tale problematica verrà trattata presentando solo gli aspetti fondamentali, con l’obiettivo di dare al programmatore tutte le conoscenze necessarie a comprendere come i dati sono memorizzati e trattati; si rimanda ad altre fonti per una trattazione esaustiva degli argomenti correlati. Codificare un’informazione è un problema suscettibile di differenti soluzioni: accade spesso che persone diverse codifichino una medesima informazione in modi diversi; ciò non vuol dire che una soluzione sia necessariamente migliore di un’altra, Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. Concetti di base dell’informatica 19 poiché bisogna prima stabilire cosa ci aspettiamo: una codifica che usa il numero minore di bit, o quella più semplice da codificare e decodificare o altro ancora. Definizione Sia data un’informazione di tipo T di cardinalità n, e un alfabeto di k simboli A={s1 ,s2 , sk }; sia inoltre S l’insieme di tutte le stringhe composte da m simboli di A. La codifica di T è una funzione C(T ) che ad ogni valore possibile dell’infor- mazione associa una stringa s ∈ S; in formule: C : ∀v ∈ T, v → s ∈ S Particolarmente importanti sono le codifiche che a valori diversi associano stringhe codificate diverse: C : ∀v1 , v2 ∈ T, v1 → s1 ∈ S, v2 → s2 ∈ S, v1 6= v2 Ovviamente affinché l’informazione si possa codificare in maniera biunivo- ca, il numero dei codici (cardinalità di S) deve essere superiore alla cardinalità dell’insieme T; se m è la lunghezza della stringa codificata, deve essere: 2m ≥ n → m = dlog2 ne (1.3) Facciamo un piccolo esempio. Immaginiamo di voler codificare l’informazione giorno della settimana in binario. Essendo in tal caso n=7, applicando la precedente formula 1.3 si ha m=3. Nella figura 1.6 vengono riportate le tabelle relative a due possibili schemi di codifica; si osserva che essendo la cardinalità di S pari a otto e i giorni della settimana sette, ci sarà una stringa di S non usata. La trattazione può essere approfondita con un esempio leggermente più com- plesso, che coinvolge un’informazione naturalmente composta da due parti distinte; in questo caso si codificano singolarmente le due parti, anche se questo può portare in generale a delle inefficienze. Si consideri il problema di voler codificare i giorni dell’anno; il modo più sem- plice è di ripercorrere quanto fatto per la codifica dei giorni della settimana, ovvero elencando i 365 giorni ed associando ad ognuno una stringa di bit di lunghezza opportuna; tale stringa deve avere almeno m=dlog2 365e=9 bit. Un modo alternativo è invece quello presentato nella figura 1.7, in cui si usa una cosiddetta codifica parlante; vengono cioè usate due stringhe per codificare separatamente il mese e il giorno. Lo schema di codifica proposto è particolarmente utile in fase di decodifica, per le ipotesi con le quali è stato costruito: infatti si è adottato per i mesi e il giorno del mese una codifica numerica binaria. Il giorno del mese, trasformato in binario, è codificato in 5 bit; analogamente il mese, inteso come numero, è codificato in binario e rappresentato in 4 bit. Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. 20 Capitolo 1 1 0 0 0 0 1 0 1 a) e7 e6 e5 e4 e3 e2 e1 e0 0 1 1 0 1 1 0 1 b) sm m22 m21 m20 m19 m18 m17 m16 0 1 0 0 0 0 0 0 c) m15 m14 m13 m12 m11 m10 m9 m8 0 0 0 0 0 0 0 0 d) m7 m6 m5 m4 m3 m2 m1 m0 Figura 1.5 La rappresentazione del numero reale r = 118.625. In a) il byte di esponente, e poi i 3 byte della mantissa; m0 rappresenta il bit meno significativo della mantissa, m2 il più significativo e ms il segno della mantissa, nel caso in questione positivo. Decodifichiamo la stringa 011001001; i bit 01100 rappresentano la codifica nu- merica del giorno, e quindi passando in decimale (con la formula 1.1: 01100 = 8+4= 12|10. Analogamente per il mese 1001=9|10 corrispondente a Settembre. Si tratta del 12 Settembre, onomastico dell’autore! Le unità di misura dell’informazione Comunemente si usa un’aggregazione di 8bit, detto byte, e le unità di misura dell’informazione sono multipli (in genere grandi) del byte. L’unità di misura più piccola è il kilobyte; poiché il termine deriva dalla unione del prefisso kilo con byte, un kB indica 1000 byte. Talvolta impropriamente per kB si fa riferimento alla potenza di 2 più vicina a 1000, ovvero la decima: 210 =1024. Quest’ultima quantità è detta kibibyte, per distinguerla dalla precedente. La figura 1.8 riporta le principali unità di misura dell’informazione. 1.3 Algoritmo, programma, esecutore Definire cosa sia un algoritmo in maniera formalmente rigorosa non è cosa sem- plice; ci accontenteremo quindi di un’introduzione meno precisa, ma senz’altro Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. Concetti di base dell’informatica 21 ampiamente sufficiente agli scopi. Definizione Un algoritmo è una sequenza finita di passi che portano alla realiz- zazione di un compito. In questa definizione sono presenti due termini il cui significato non è com- pletamente determinato: i passi e il compito. Con il termine passo intendiamo un’operazione di natura qualsiasi, ma elementare e determinata; in particolare l’enfasi che si vuole dare è che i passi vengono visti come operazioni elementari con i quali costruire procedimenti più articolati. Sono proprio questi ultimi ad assumere il significato di compito. La finitezza, richiamata nella precedente defini- zione, è un aspetto da non trascurare: il compito per essere utilmente risolto non può e non deve coinvolgere infiniti passi: se cosı̀ fosse non terminerebbe mai. 1.3.1 Algoritmo e Esecutore A titolo di esempio si consideri un esempio di algoritmo, in un campo che dovrebbe essere ai più ben noto: ‘la cucina’. Pensiamo ad un algoritmo, rintracciato su un noto libro di ricette, per preparare un piatto di spaghetti condito con un sugo già pronto. I passi per conseguire l’obiettivo, sono descritti nella figura 1.9. Affinché l’algoritmo possa produrre un buon risultato e soprattutto ripetibile, esecutori, anche diversi, devono essere in grado di interpretare tutte le azioni in maniera univoca. Due sono gli elementi fondamentali affinché ciò sia possibile: in primo luogo l’esecutore deve comprendere le azioni da interpretare, ovvero deve avere delle competenze a priori che chi ha scritto l’algoritmo ipotizza siano note. In secondo luogo ogni azione deve essere descritta con un livello di dettaglio tale da essere compresa senza ambiguità. Quanto alle competenze necessarie a eseguire correttamente le azioni, l’esecu- tore deve: saper riempire un contenitore saper pesare oggetti saper versare qualcosa nel contenitore (azione usata per versare il sale e gli spaghetti) saper accendere e spegnere il fornello e posizionarvi sopra una pentola essere in grado di capire che l’acqua bolle saper misurare il tempo, con la precisione dei minuti saper scolare la pasta saper condire la pasta Questa ricetta può apparire in prima battuta banalissima da eseguire e con risultati scontati, ma basta poco per convincerci che ci stiamo sbagliando, e anche Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. 22 Capitolo 1 T={domenica, lunedı̀, martedı̀, mercoledı̀, giovedı̀, venerdı̀, sabato} A={0, 1} S={000, 001, 010, 011, 100, 101, 110, 111} Elemento C C’ domenica 000 111 lunedı̀ 001 101 martedı̀ 010 000 mercoledı̀ 011 110 giovedı̀ 100 001 venerdı̀ 101 010 sabato 110 100 Tabella di codifica per C e C’. S C C’ 000 domenica martedı̀ 001 lunedı̀ giovedı̀ 010 martedı̀ venerdı̀ 011 mercoledı̀ - 100 giovedı̀ sabato 101 venerdı̀ lunedı̀ 110 sabato mercoledı̀ 111 - domenica Tabella di decodifica per C e C’. Figura 1.6 Due possibili schemi di codifica C e C’ per codificare i giorni della settimana, e le relative tabelle di codifica e decodifica. Le tabelle di codifica forniscono la corrispondenza da valori del tipo alla stringa codice, la tabella di decodifica la corrispondenza inversa, utile per codificare l’informazione. di molto. Chi ha scritto la ricetta ha dato per scontato tantissime valutazioni di tipo quantitativo: esecutori diversi produrranno risultati profondamente diversi (forse tutti culinariamente scadenti). Un primo esecutore usa una pentola di 5 litri di acqua, e versando un cucchiaio di sale, ottiene la pasta insipida; inoltre usa un barattolino di sugo pronto di 50 g, con un condimento in quantità adeguate. Un secondo esecutore usa una pentola di un litro d’acqua e 150g di condimento, con il risultato di un piatto di pasta estremamente condito e eccessivamente salato. Un terzo ancora usa una pentola di mezzo litro, con il risultato che gli spaghetti non cuociono uniformemente, perché non entrano bene nella pentola. Un quarto esecutore usa una pentola da 4 litri, Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. Concetti di base dell’informatica 23 Mese m3 m2 m1 m0 Mese m3 m2 m1 m0 Gennaio 0 0 0 1 Luglio 0 1 1 1 Febbraio 0 0 1 0 Agosto 1 0 0 0 Marzo 0 0 1 1 Settembre 1 0 0 1 Aprile 0 1 0 0 Ottobre 1 0 1 0 Maggio 0 1 0 1 Novembre 1 0 1 1 Giugno 0 1 1 0 Dicembre 1 1 0 0 Giorno g4 g3 g2 g1 g0 Giorno g4 g3 g2 g1 g0 1 0 0 0 0 1 17 1 0 0 0 1 2 0 0 0 1 0 18 1 0 0 1 0 3 0 0 0 1 1 19 1 0 0 1 1 4 0 0 1 0 0 20 1 0 1 0 0 5 0 0 1 0 1 21 1 0 1 0 1 6 0 0 1 1 0 22 1 0 1 1 0 7 0 0 1 1 1 23 1 0 1 1 1 8 0 1 0 0 0 24 1 1 0 0 0 9 0 1 0 0 1 25 1 1 0 0 1 10 0 1 0 1 0 26 1 1 0 1 0 11 0 1 0 1 1 27 1 1 0 1 1 12 0 1 1 0 0 28 1 1 1 0 0 13 0 1 1 0 1 29 1 1 1 0 1 14 0 1 1 1 0 30 1 1 1 1 0 15 0 1 1 1 1 31 1 1 1 1 1 16 1 0 0 0 0 0 0 1 0 1 0 0 0 1 g4 g3 g2 g1 g0 m3 m2 m1 m0 Figura 1.7 Una possibile codifica dei giorni dell’anno. Si codificano separata- mente i mesi e i giorni: per i mesi saranno necessari dlog2 12e=4 bit; per i 31 giorni ce ne vorranno dlog2 31e=5. Le tabelle mostrano una possibile codifica binaria dei mesi e dei giorni. Si provi a decodificare la sequenza riportata in fondo alla figura: la stringa dei mesi m3 m2 m1 m0 = 0001, come si deduce dalla tabella dei mesi, è associata a Gennaio. Analogamente la stringa dei giorni g4 g3 g2 g1 g0 = 00101, come evidente dalla relativa tabella, è associata giorno 5. Si tratta del 5 Gennaio, compleanno dell’autore. ma su un fuoco piccolo e deve aspettare due ore prima che vada in ebollizione. Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. 24 Capitolo 1 CURIOSITÀ La definizione di Kilobyte pari a 1024 byte è stata espressamente vietata nel sistema internazionale di unità di misura da diversi organi di standardizza- zione, quali la Commissione Elettrotecnica Internazionale (IEC), l’Institute of Electrical and Electronics Engineers (IEEE) e l’ISO; infatti il prefisso Kilo è impiegato per indicare 1000 e non 1024, anche se ciò può risultare più utile nell’informatica. Quindi attenti al Kilo in informatica, potrebbe dare origine a interpretazioni differenti. Grandezza Simb. Mult. dec. Grandezza Simb. Mult. bin. kilobyte kB 103 kibibyte KiB 210 =1.024 megabyte MB 106 mebibyte MiB 220 =1024 KiB gigabyte GB 109 gibibyte GiB 230 =1.024 MiB terabyte TB 1012 tebibyte TiB 240 =1.024 GiB petabyte PB 1015 pebibyte PiB 250 =1.024 TiB Figura 1.8 La misura dell’informazione: i multipli del bit e del byte comunemente impiegati. CURIOSITÀ L’impressionante progresso tecnologico ha fatto aumentare sensibilmente la dimensione dei dispositivi di memoria in pochi anni: si pensi che il primo disco rigido fu costruito dalla IBM nel 1956: era grande quanto un grosso frigorifero, pesava una tonnellata, aveva una capacità di 5MB (milioni di byte), e aveva un costo elevatissimo (dell’ordine di diverse centinaia di migliaia di euro di oggi). Un disco rigido attuale ha il peso di meno di 100g, è grande pochi centimetri, ha un costo dell’ordine della centinaia di euro, è diversi milioni di volte più veloce e una capacità dell’ordine dei TB (migliaia di miliardi di byte). CURIOSITÀ Il termine algoritmo deriva dal nome del matematico e filosofo arabo Muhammad Algrtimo ’l-Khwarizmi, che sembra essere stato il primo auto- re ad aver espresso il concetto di procedimento nel suo libro di matematica orientale GHf - ghtr adouf, per noi difficilmente pronunciabile. Un quinto usa l’acqua distillata, con i risultati prevedibili in termini di sapidità, un sesto ancora usa un’acqua minerale. Un altro esecutore ancora si imbatte nel problema che, dopo aver buttato la pasta, la temperatura della pentola si innalza ancora e l’acqua rabbocca spegnendo il fuoco, e trascorso il tempo di cottura, se non è saltato ancora in aria, troverà la pasta cruda. Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. Concetti di base dell’informatica 25 1. riempire una pentola con acqua 2. versare nella pentola 1 cucchiaio di sale grosso 3. accendere un fornello e metterci sopra la pentola 4. attendere che l’acqua bolla 5. mettere nella pentola 100 gr di pasta 6. attendere il tempo di cottura indicato sul contenitore 7. spegnere il fornello e scolare la pasta 8. condire la pasta con il sugo pronto Figura 1.9 Un algoritmo per cucinare la pasta, descritto usando un linguaggio naturale, ovvero l’italiano. Ora tocca a te a eseguire la ricetta! Scoprirai che tante altre cose possono accadere. Poiché la ricetta non chiarisce chi è il fortunato che deve mangiare la pasta, puoi sempre valutare di abbandonare la sfida e affidarti alle mani più esperte di una nonna. Una versione più precisa dell’algoritmo è quello presentato nella figura 1.10. Tale esempio è emblematico dell’importanza di soddisfare i seguenti irrinun- ciabili requisiti: l’algoritmo deve essere formulato in un linguaggio perfettamente comprensi- bile all’esecutore le azioni presenti nell’algoritmo devono essere interpretate inequivocabilmen- te dall’esecutore le azioni devono essere in numero finito 1.3.2 Programma e Linguaggio L’esempio riportato nella precedente sezione presenta un semplice algoritmo per la cottura della pasta. Ciò su cui si vuole focalizzare l’attenzione è il rapporto esistente tra algoritmo, programma e linguaggio. A tale scopo è conveniente con- tinuare l’esplorazione della metafora della ricetta della pasta, che ci consente di ragionare su concetti e situazioni ben note. La prima considerazione da fare si riferisce a quello che finora abbiamo chia- mato algoritmo. In effetti la figura 1.9 non è un algoritmo, ma la sua descrizione in un linguaggio. Può sembrare una pignoleria, ma è importante capire bene la differenza tra algoritmo e descrizione dell’algoritmo. L’algoritmo è un procedi- mento per realizzare un compito; in questo caso la cottura di un piatto di pasta, fatto di azioni opportunamente collegate tra loro. Il procedimento riportato nella suddetta figura è invece la descrizione di tale procedimento usando la lingua a noi Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. 26 Capitolo 1 Ingredienti necessari: 1. 2 litri di acqua 2. 2 cucchiai di sale grosso 3. 100 g di pasta 4. 50 g di sugo pronto Procedimento: 1. riempire una pentola d’acqua di dimensione compresa tra uno e due litri 2. versare nella pentola 1 cucchiaio di sale grosso per ogni litro d’acqua 3. accendere un fornello di diametro pari alla pentola e metterci sopra la pentola 4. attendere che l’acqua bolla 5. versare nella pentola 100 g di pasta 6. attendere il tempo di cottura indicato sul contenitore, regolando ogni minuto la fiamma per evitare trabocchi 7. spegnere il fornello e scolare la pasta 8. condire la pasta con il sugo pronto, usando 50 g di condimento per ogni 100 g di pasta Figura 1.10 Un algoritmo per cucinare la pasta, descritto usando un linguaggio naturale, ovvero l’italiano. nota, l’italiano. Poiché tale lingua è scontata per chi la usa da anni (per l’autore ahimè troppi) facciamo fatica a separare l’algoritmo dalla sua descrizione. Proviamo allora a consultare la figura 1.11; in questo caso troviamo una descri- zione in inglese. A parte qualche probabile errore di traduzione, ciò che è descritto in tale figura è il medesimo algoritmo della figura 1.9. A questo punto dovrebbe essere più semplice capire quanto accennato in pre- cedenza: ci troviamo di fronte ad un medesimo algoritmo, quello per cucinare un piatto di pasta, ma descritto in due linguaggi diversi: l’italiano e l’inglese. Intanto è utile introdurre un nuova definizione: Definizione Un programma è la rappresentazione di un algoritmo in un dato linguaggio. Resta da chiedersi il perché dell’impiego di linguaggi diversi per descrivere un medesimo algoritmo; nel caso riportato della ricetta della pasta la risposta è ovvia: è l’unico modo, dal momento che in paesi diversi si parlano lingua diverse, Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. Concetti di base dell’informatica 27 per rendere possibile la sua attuazione a livello mondiale, estesa a tutti i paesi interessati. La motivazione sul piano informatico non è molto diversa: poiché esistono linguaggi di programmazione diversi, ognuno particolarmente indicato a risolve- re problemi in un determinato ambito, durante la fase di progetto dell’algoritmo potrebbe non essere stato ancora definito il linguaggio in cui verrà tradotto l’algo- ritmo. Inoltre è certamente possibile che ci sia la necessità di tradurre l’algoritmo in più linguaggi, soprattutto se esso è un algoritmo di base e quindi di largo impiego. CURIOSITÀ Il primo linguaggio di programmazione della storia, se si esclude quello adope- rato per la programmazione della macchina (meccanica) di Charles Babbage, è il Plankalkül di Konrad Zuse, sviluppato in Svizzera durante la seconda guerra mondiale e pubblicato nel 1946. Plankalkül non venne mai realmente usato per programmare. In questo libro introdurremo un linguaggio di programmazione molto famoso, il C, che ha avuto un’ampia diffusione a partire dagli anni ottanta; il C è famoso per la sua efficienza, legata sostanzialmente alla forte relazione con la componente hardware del calcolatore a tal punto da essere considerato una via di mezzo tra un linguaggio di alto livello e un linguaggo assemblativo. Il C è diventato poi la base dei più moderni linguaggi ad oggetti, come C++ e Java. 1. fill a pot with water 2. pour a spoon of salt in the pot 3. switch on the kitchen range and place the pot on it 4. wait for the water boiling 5. pour 100g of pasta in the pot 6. wait the suggested cooking time 7. switch off the kitchen range and drain off the pasta 8. dress the pasta with a ready to use spice Figura 1.11 Il medesimo algoritmo presentato nella figura 1.9, descritto in lingua Inglese. 1.3.3 Risorse e Processo Successivamente alla traduzione di un algoritmo in un programma, abbiamo la ne- cessità di eseguire quest’ultimo per ottenere i risultati desiderati dall’elaborazione; Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. 28 Capitolo 1 una pentola di adeguate dimensioni un cucchiaio un fornello funzionante e di diametro confrontabile con quello della pentola un cronometro per misurare il tempo di cottura un colapasta un mestolo Figura 1.12 Le risorse necessarie all’esecuzione del programma di figura 1.9. è quindi opportuno comprendere nel dettaglio cosa accade in questa situazione. Innanzitutto abbiamo bisogno di un esecutore; quest’ultimo per quanto finora illustrato non può essere qualsiasi, ma deve essere in grado di comprendere il lin- guaggio in cui è stato scritto il programma. Nella metafora del piatto di spaghetti, se la ricetta (ovvero il programma) è tradotto in linguaggio italiano, l’esecutore deve necessariamente essere un cuoco che è in grado di leggere e comprendere la ricetta in italiano. Il legame tra esecutore e linguaggio è indissolubilmente legato alla comprensione delle azioni di cui si compone il programma. L’esecutore è soltanto una delle cose necessarie a far partire l’esecuzione; nel- la ricetta abbiamo dato per scontato che l’esecutore abbia a disposizione delle risorse di carattere generale. Oltre ai dati di ingresso necessari al programma (per la ricetta gli ingredienti necessari, come gli spaghetti, il sale etc.), da un’a- nalisi più approfondita, si evince che c’e’ anche bisogno di risorse di uso generale, come illustrato nella figura 1.12 Attenzione! Non bisogna trascurare le risorse necessarie a rendere possibile l’e- secuzione di un programma; queste in genere non sono esplicitamente citate in un programma, ma la loro assenza non consentirà di procedere: è quindi sempre utile acquisire consapevolezza di questo problema. Quante volte ci accade di leggere una bella ricetta, e ci accorgiamo solo dopo aver compra- to gli ingredienti e avviato il procedimento di esecuzione, che magari veniva richiesto un forno che raggiungesse certe temperature che non abbiamo? Ov- viamente nell’informatica le risorse non sono fornelli o attrezzi da cucina, bensı̀ sistemi di elaborazione o dispositivi ad essi connessi: potrebbe acca- dere, per fare un esempio semplice, che il programma che vogliamo eseguire richieda una potenza di calcolo non disponibile sul nostro calcolatore, una dimensione minima di memoria, o altre cose del genere. Dal punto di vista terminologico, quando un esecutore avvia l’esecuzione di un programma, si parla di processo. La differenza tra programma e processo è quindi sostanziale: il programma è la descrizione di un procedimento, il processo è invece l’attuazione di tale procedimento che richiede un esecutore che effettua Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. Concetti di base dell’informatica 29 le azioni previste, le risorse necessarie, e i dati di ingresso necessari. Insomma, basta andare in cucina durante l’esecuzione dei nostri spaghetti, che esiste una bella differenza tra una ricetta (programma) e la sua esecuzione (processo). Fase di inizializzazione: verifica che tutte le risorse necessarie siano disponibili inizializza un segnaposto alla prima istruzione del programma Esegui ripetutamente i seguenti passi, fino al raggiungimento della fine del programma 1. leggi l’istruzione del programma associata al segnaposto, e sposta in avanti il segnaposto 2. se l’istruzione ha bisogno di dati, acquisiscili 3. esegui l’istruzione Figura 1.13 L’algoritmo realizzato dall’esecutore per eseguire il programma. A titolo di esempio seguiamo le prime azioni dell’esecutore, in riferimento al programma della ricetta presentato in figura 1.10: 1. Leggo l’istruzione 1 di figura 1.10 2. Acquisisco l’acqua e la pentola 3. Eseguo l’istruzione, ovvero: Riempio la pentola con l’acqua 4. Leggo l’istruzione 2 di figura 1.10 5. Acquisisco il sale grosso 6. Eseguo l’istruzione, ovvero: Verso il sale grosso nella pentola 7. Leggo l’istruzione 3 di figura 1.10 8. Non ho nulla altro da acquisire 9. Eseguo l’istruzione, ovvero: Accendo il fornello e ci metto sopra la pentola 10. Leggo l’istruzione 4 di figura 1.10 11. Nulla altro da acquisire 12. Eseguo l’istruzione, ovvero: Aspetto l’ebollizione dell’acqua 13. E cosı̀ via: ora il procedimento dovrebbe essere chiaro Nel corso del presente capitolo abbiamo finora parlato di un esecutore umano, la cuoca che eseguiva la ricetta degli spaghetti. Ovviamente il nostro interesse è quello di trattare problemi informatici, dove l’esecutore è un elaboratore elettro- nico (calcolatore). La trattazione deve quindi necessariamente completarsi con gli elementi fondamentali dell’architettura di tali sistemi, scopo della seguente sezione. Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. 30 Capitolo 1 CURIOSITÀ Il primo calcolatore elettronico, antesignano dei moderni sistemi, fu progettato da John Atanoff, dell’Università dell’Iowa, ma il merito gli venne attribuito molto più tardi; infatti a causa del progetto non portato completamente a termine, il primato della realizzazione di un calcolatore, fu attribuito all’ENIAC (Electronic Numerical Integrator And Calculator), sviluppato negli anni 50 da J. Prosper Eckert e John W. Manchy, dell’Università di Pennsylvania. 1.4 Macchina di Von Neumann Molti avranno sentito già parlare di John Von Neumann, che ha avuto il merito di proporre uno schema architetturale di un calcolatore elettronico, detto modello di Von Neumann, ancora oggi attuale. I moderni calcolatori, sebbene siano tecnolo- gicamente molto più avanzati del calcolatore costruito con l’importante e decisiva consulenza di Von Neumann, il famoso EDVAC, hanno la medesima organizza- zione interna, che, per tale motivo, ha un’importanza non solo storica, ma anche scientifica e tecnologica. CURIOSITÀ L’ EDVAC utilizzava una rappresentazione binaria dei dati era in grado di ese- guire addizioni, sottrazioni, moltiplicazioni e, mediante programma, divisioni; la capacità dell’EDVAC era di 1.000 registri di memoria, ognuno di 44-bit (in definitiva quindi solo 5.5 Kb). L’ EDVAC era in grado di svolgere un’addizione in poco meno di un millisecondo, e una moltiplicazione in 2.9 millisecondi; un moderno computer portabile effettua tali operazioni in tempi dell’ordine delle decine di nanosecondi. Il sistema aveva 6.000 valvole e 12.000 diodi e richiedeva una potenza di 56 Kw (con questa potenza si alimentano circa 20 appartamenti a pieno carico), con un’occupazione di 45.5 m2 e 7.850 kg. Per farlo funzionare occorrevano 30 persone! Il modello di calcolatore di Von Neumann si basa su tre componenti fondamen- tali, tra loro interconnesse mediante un canale di collegamento detto Bus, come illustra la figura 1.14: la CPU (Central Processing Unit) o unità centrale, a sua volta composta da un’unità di controllo (UC) e da unità logico-aritmetica (ALU), Unità di memoria centrale, usata come memoria di lavoro principale (detta RAM, Random Access Memory), Unità di input/output, preposta alla lettura e scrittura dei dati dall’esterno. Il presente materiale e’ coperto da copyright dal suo autore, Prof. Mario Vento dell’Universita’ di Salerno che lo rende disponibile agli studenti per soli motivi di studio; e’ vietata la riproduzione, la copia e la distribuzione a terzi o un impiego diverso dallo studio. Concetti di base dell’informatica 31 CP U M emoria I/O address bus data bus control bus Figura 1.14 Il modello di Von Neumann: i componenti costitutivi principali e lo schema di interconnessione. 1.4.1 La memoria principale Può essere utile partire dall’analisi del funzionamento della memoria centrale. Que- sta è costituita da un certo numero di celle o registri, ognuna di d bit, dove d è detto parallelismo di memoria; ogni registro è individuato da un indirizzo univoco, espresso in termini binari. Il numero complessivo di registri m è detto dimensione della memoria. Si può semplicemente comprendere che se m è il numero di registri di memoria il numero di bit che costituiscono l’indirizzo è n = log2 m. Infatti con un indirizzo a n bit possiamo avere 2n indirizzi diversi, ognuno associato ad un registro. Si faccia ad esempio riferimento alla figura 1.15 che riporta lo schema di un’u- nità di memoria con parallelismo pari a 8 bit e con 4 bit di indirizzamenti, che ci consente di raggiungere una lunghezza di 16 registri. La capacità, definita come il prodotto tra lunghezza e parallelismo, nell’esempio proposto è pari a 16 B. La memoria comunica con le altre unità del sistema mediante tre registri: il MA, acronimo di memory Address Register (registro indirizzo di memoria

Libro Vento (1) - PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue