Preparazione per l'esame di Fondamenti di Informatica

Appunti di Jessica Asietti, non fotocopiare!

LE  OPERAZIONI  IN  VIRGOLA  

Quando   vogliamo   rappresentare   un   numero   nel   calcolatore,   dobbiamo   tener   presente   che   le   celle  

di  memoria  ci  danno  un  vincolo  sul  numero  di  bit  da  utilizzare.  Se,  inoltre,  il  numero  è  composto  

da   una   parte   intera   e   da   una   parte   decimale   allora   è   necessario   capire   quanti   bit   assegnare   alle  

due  parti.    

Il  modo  più  semplice  è  utilizzare  la  rappresentazione  in  virgola  fissa  ovvero  assegnare  a  priori  un  

certo   numero   di   bit   per   la   parte   intera   e   un   altro   tot   di   bit   per   la   parte   decimale,   e   questo   sarà  

uguale  per  tutti  i  numeri.  Inoltre  per  i  numeri  negativi  è  possibile  utilizzare  ancora  il  complemento.    

E’  sostanzialmente  il  metodo  già  discusso  in  precedenza  per  rappresentare  i  numeri  con  la  virgola.  

Facciamo  un  esempio:  rappresentare  i  binario  il  numero  72,6  con  12  bit  di  cui  4  per  i  decimali.  

  Parte  intera  (8  bit):         Parte  decimale  (4  bit):      

  72  :  2  =  36        0       0,6  x  2  =  1,2        1  

à à

  36  :  2  =  18        0       0,2  x  2  =  0,4        0  

à à

  18  :  2  =  9            0       0,4  x  2  =  0,8        0  

à à

  9  :  2  =  4                1       0,8  x  2  =  1,6        1  

à à

  4  :  2  =  2                0       mi  fermo  qui  

à

  2  :  2  =  1                0       (0,6)  =  (1001)  

à 10 2

  1  :  2  =  0                1  

à

  (72)  =  ( 01001000)

10 2  

  (72,6)  =  (0100  1000  1001)  

10 2

  In  complemento  alla  base:  (-­‐72,6)  =  (1011  0111  0111)  

10 2

   Ci   ricordiamo   che   fare   il   complemento   alla   base   significa   invertire   tutti   i   bit   dopo   il   primo   1  

meno  significativo.  

Ma  qual  è  il  vincolo  della  virgola  fissa?    

Sembra   tutto   molto   semplice   e   utile   fino   a   quando   si   parla   di   numeri   come   quello   dell’esempio  

sopra,   ma   ci   si   accorge   subito   che   per   numeri   interi   oppure   numero   minori   di   1   si   ha   un   grosso  

spreco.  infatti:  

in  caso  di  numeri  interi  i  bit  per  la  parte  decimale  sarebbero  tutti  a  

0

• in  caso  di  numeri  <-­‐1  i  bit  della  parte  intera  sarebbero  tutti  a  

0

•

Per  questo  viene  introdotto  il  metodo  della   virgola  mobile.  

Fissata  una  base  

B

,  un  numero  

N

 può  essere  rappresentato  da  una  coppia  di  valori:  

la  mantissa   M ,  che  rappresenta  le  cifre  significative  (cioè  diverse  da  

0

)  del  numero  

• l’esponenziale   E

,  che  indica  la  posizione  della  virgola  

• E

ovvero   N  =  M  x  B .  

Esempi:  

  3 4 -­‐2

  474,35  =  0,47435  x  10  =  0,047435  x  10  =  47435  x  10  

    3 4 -­‐3

  101,011  =  0,101011  x  2  =  0,0101011  x  2  =  101011  x  2  

  Appunti di Jessica Asietti, non fotocopiare!

Si   chiama,   inoltre,   forma   normalizzata   quando   tutte   le   cifre   significative   si   trovano   come   valori  

decimali.  

La  rappresentazione  in  virgola  mobile  

I  numeri  in  virgola  mobile  vengono  rappresentati  da:

un  bit  per  il  segno  

• N  bit  per  l’esponente  (in  

complemento  a  2

)  

• E

N  bit  per  il  valore  assoluto  della  mantissa  

• M

 Come   passare   dall’esponente   in   complemento   a   2   al   numero   che   rappresenta?  

Semplicemente  calcolando  il  suo  valore  prendendo  il  MSB  con  segno  negativo.  

Da   alcuni   esempi   cerchiamo   di   capire   come   risalire   al   numero   dalla   rappresentazione   in   virgola  

mobile.  

  1  010  1010      

  1       à    segno     à    numero  negativo  

1

  010       à    esponente     à    2  =   2

  2

  1010   à    mantissa     à    0,1010  x  2  =  10,10  

1 -­‐1

  (10,10)  =  2  +  2  =  (2,5)  ma  ricordando  il  segno   (-­‐2,5)

2 10 10  

  0  1101  101111  

  0     à    numero  positivo  

3 2 0

  1101     à    -­‐  2  +  2  +  2  =   -­‐3  

-­‐3

  101111   à    0,101111  x  2  =  0,000101111    

-­‐4 -­‐6   -­‐7 -­‐8 -­‐9

  (0,000101111) =  2  +  2 +  2 +  2 +  2  =   (0,09179…)

2   10  

Se  invece  volessimo  fare  il  contrario?  Passaggi  da  seguire.  

a) Guardiamo  il  segno  del  numero  così  da  ottenere  subito  il  bit  di  segno    

b) trasformiamo  il  numero  (in  valore  assoluto)  in  binario        

c) guardiamo  di  quanto  ci  dobbiamo  spostare  perché  appena  dopo  la  virgola  ci  sia  un  

1

.    

se  spostamento  verso  destra  metto  un  

-­‐  

§ se  spostamento  verso  sinistra  metto  un  

+  

§

  e  convertiamo  l’esponente  in  complemento  a  2.  

Esempio:  trasformare  il  numero  (0,3125)  con  N =3  e  N =4.  

10 E M

  0,3125        positivo,  bit  di  segno  a  

1

à

  0,3125  x  2  =  0        0,625  x  2  =  1        0,25  x  2  =  0        0,5  x  2  =  1        (0,0101)    cioè  mantissa  

(1010)

à 2 2  

  0,0101        mi  devo  spostare  a  destra  di  1,  quindi  esponente  -­‐1         (111)  in  complemento  

à à 2

  1  111  1010  

  Appunti di Jessica Asietti, non fotocopiare!

I  formati  della  virgola  mobile  

Lo   standard   IEEE   754   ci   permette   di   rappresentare   i   numeri   reali   in   virgola   mobile   in   due  

precisioni:  

Singola   precisione   con   32   bit:   1   bit   per   il   segno,   8   bit   per   l’esponente   e   23   bit   per   la  

• n-­‐1  

mantissa.   L’esponente   rappresentato   in   eccesso  127   ha   un   range   compreso   tra   -­‐2 =   -­‐128  

n-­‐1

e   2 -­‐1  =  127,  al  di  fuori  di  esso  si  parla  di  overflow.    

Doppia   precisione   con   64   bit:  1  bit  per  il  segno,  11  per  l’esponente  e  52  per  la  mantissa.  In  

• questo  caso  l’esponente  non  è  in  complemento  ma  in  

eccesso  1023.  

Le  operazioni  in  virgola  mobile  

Dividiamo  i  due  casi:  somma  -­‐  sottrazione  e  moltiplicazione  -­‐  divisione:  

moltiplicazione  -­‐  divisione:    

• si  moltiplicano  o  dividono  le  mantisse  

§ si  sommano  o  sottraggono  gli  esponenti  

§

  magari    dopo    l’operazione  potrebbe  essere  necessario  normalizzare  di  nuovo  la  mantissa  e    

  correggere  quindi  l’esponente.  

somma  -­‐  sottrazione:  

• si   rendono   uguali   gli   esponenti   trasformando   il   più   piccolo   come   il   più   grande  

§ spostando  quindi  le  cifre  della  mantissa  di  tante  posizioni  quanta  la  differenza  

si  sommano  o  sottraggono  poi  le  mantisse  

§

  Ovviamente  la  trasformazione  potrebbe  far  perdere  alcune  cifre  meno  significative.  

  Somma:   2 4

  0,6502  x  10  +  0,2347  x  10    

2 4

  0,6502  x  10  =  0,006502  x  10   4 4

  diventa:  (0,006502  +  0,2347)  x  10  =  0,241202  x  10  

  Moltiplicazione:  

1 3

  (0,275  x  10 )  x  (0,00125  x  10 )  

1+3

  (0,275  x  0,00125)  x  10  =  3,4375  

  Appunti di Jessica Asietti, non fotocopiare!

LE  CODIFICHE    

Fino   ad   ora   abbiamo   visto   come   il   calcolatore   memorizza   dei   numeri   ma   noi   abbiamo   bisogno   che  

esso   sia   in   grado   di   memorizzare   anche   le   lettere,   ad   esempio.   Per   questo   motivo   vengono  

inventati  i  codici,  cioè  delle  rappresentazioni  utili  per  far  si  che  il  calcolatore  sappia  gestire  tutti  i  

tipi   di   caratteri.   Prende   il   nome   di   alfabeto   un   insieme   finito   di   simboli   ognuno   dei   quali  

rappresenta  un  carattere  diverso  e  chiamiamo  

stringa  una  sequenza  finita  di  caratteri.  

Ad  esempio:  

{0,1}  è  l’alfabeto  binario  e  

{A,B,…,0,1…}  è  l’alfabeto  alfanumerico.  

Quello   che   è   sicuro   è   che   il   calcolatore   non   è   in   grado   di   sfruttare   alfabeti   troppo   complessi   come  

l’alfanumerico,   perché   le   uniche   operazioni   che   esso   riconosce   sono   “tensione   alta”   e   “tensione  

bassa”…   quindi   utilizzerà   un   alfabeto   binario.   Quindi   ogni   simbolo   del   nostro   alfabeto   “umano”  

corrisponderà   ad   una   stringa   di   simboli   dell’alfabeto   binario   del   calcolatore.   Ma   il   problema   da  

porsi  ora  è:  quanto  deve  essere  lunga  questa  stringa  di  zeri  e  uni?    

Se  il  grande  alfabeto  da  rappresentare  è  composto  da   C  elementi  ( C  come  “cardinalità”)  allora  ogni  

stringa  dell’alfabeto  binario  necessiterà  di  

n

 bit  secondo  la  relazione:    

dove   log C   lo  si  indica  con   M .    

2  

Se:   n  =  M  allora  si  dice  che  il  codice  è   non  ridondante,  cioè  utilizza  il  minor  numero  possibile  di  

• bit  per  rappresentare  tutti  i  simboli  del  codice  

n  >  M  allora  il  codice  è  

ridondante  perché  usa  più  bit  degli  stretti  necessari  

• n  <  M  non  bastano  i  bit  per  rappresentare  il  codice  

•

Se  il  codice  non  è  ridondante  (

n   =   M )  allora  ogni  parola  differirà  per  un  solo  bit,  mentre  se  il  codice  

è  ridondante  ( n  >  M)  ci  saranno  parole  che  “disteranno”  più  bit.  La  distanza  espressa  in  numero  di  

bit  tra  due  parole  del  codice  prende  il  nome  di  

distanza  di  Hamming.  Diciamo  quindi  che:  

un  codice  non  ridondante  ha  distanza  di  Hamming  sempre  unitaria:  

H  =  1

• un  codice  ridondante  ha  distanza  di  Hamming  superiore  a  1:  

H  >  1

•

 Può   sembrare   che   un   codice   ridondante   sia   “meno   efficiente”   di   un   codice   non   ridondante  

perché   sprechi   bit…   in   realtà,   la   distanza   di   Hamming   può   essere   sfruttata   per   rilevare   o,  

addirittura,  correggere  degli  errori  sul  codice.  Si  può  dimostrare  infatti  che:  

un  codice  con  distanza  di  Hamming  

H

 può  rilevare   R  =  H-­‐1  bit  errati  

• -­‐

H 1

un  codice  con  distanza  di  Hamming   H

 può  correggere   C       bit  errati  

≤

• 2

La   parità  è  un  codice  con  distanza  di  Hamming  

H  =  2

.    

Al   codice   non   ridondante   viene   aggiunto   un   bit   che   indicherà   se   nella   stringa   sono   presenti   un  

numero  dispari  o  un  numero  pari  di   1

:  

se  nella  stringa  sono  presenti  un  numero  di  

1

 pari  allora  il  bit  aggiunto  vale  

0

• se  nella  stringa  sono  presenti  un  numero  di  

1

 dispari  allora  il  bit  aggiunto  vale  

1

•

Dato   che   H   =   2   il   controllo   con   la   parità   può   solo   rilevare   degli   errori;   anzi,   può   solo   rilevarli   se  

sono  in  numero  dispari  nella  stessa  parola  del  codice.    

  Appunti di Jessica Asietti, non fotocopiare!

I  codici  di  Hamming  

Dalla   distanza   di   Hamming   nascono   dei   codici   con   la   capacità   non   solo   di   rilevare   ma   anche  

correggere  gli  errori.  Ovviamente  la  distanza  deve  essere  H   >   2  se  no  ricadremmo  nel  caso  della  

parità.    

Ma  come  funzionano  questi  codici?  Nella  parola  di  n   bit  da  trasmettere  vengono  inseriti  k  bit  di  

controllo  in  posizioni  strategiche  chiare  sia  al  trasmettitore  che  al  ricevitore;  questo  vuol  dire  che  il  

messaggio  trasmesso  sarà  composto  da   m  =  n  +  k  bit.  Perché  possa  essere  corretto  un  solo  errore  

deve  valere  la  relazione:    

Se   facciamo   un   esempio:   supponiamo   di   avere   un   codice   di   7   bit   (n   =   7)   e   vogliamo   creare   un  

codice  di  Hamming  con  distanza  3  ( H   =   3

)  dobbiamo  trovare   k

 affinché  la  relazione  scritta  sopra  sia  

valida.  

  4

  7    2  -­‐  4  -­‐  1  =  11        k  =  4  

≤ à

I  codici  ciclici  

Usati   nella   trasmissione   su   linee   rumorose,   questi   codici   non   sono   correttivi   ma   rilevano   solo   la  

presenza   di   errori   e   in   caso   ce   ne   siano   chiedono   al   ritrasmissione.   Il   loro   metodo   si   basa   sulla  

trasmissione  di   polinomi.  

Il   messaggio   M   di   k   bit   viene   convertito   in   un   polinomio   di   grado   k-­‐1   dove   i   bit   del  

• messaggio  originario  rappresentano  i  coefficienti  del  polinomio  

un   altro   polinomio   G   di   grado   r,   chiamato   polinomio   generatore,   ci   aiuta   insieme   a   M   a  

• trovare  un  terzo  polinomio  che  è  quello  utile  per  la  trasmissione.    

Vengono   trasmessi   infatti   i   coefficienti   del   polinomio   T   di   grado   k  ≤  t  ≤  k+r,   polinomio  

• divisibile  per   G .  

Il  ricevitore,  che  conosce   G  e  sa  che  il  polinomio   T  che  riceverà  sarà  divisibile  per   G ,  lo  dividerà  e  se  

il   resto   della   divisione   sarà   nullo   allora   il   messaggio   è   stato   ricevuto   correttamente,   in   caso  

contrario  chiederà  la  ritrasmissione.    

Le  varie  codifiche  per  i  numeri  interi  

Abbiamo  già  detto  che  il  calcolatore  non  è  in  grado  di  leggere  i  numeri  in  base  decimale  e  quindi  è  

necessario  convertirli  in  binario.  In  realtà  esistono  diverse  codifiche  per  poterli  rappresentare:  

il  codice  BCD  (Binary  Coded  Decimal)  trasforma  in  binario  su  4  bit  tutti  i  numeri  tra  0  e  9.  

• Questo   vuol   dire   che   se   volessimo   rappresenta   ad   esempio   il   numero   (24)   troveremmo  

10

(0010  0100)  

BCD

il   codice   ad   eccesso   tre   è   basato   sul   codice   BCD   dove,   però,   la   codifica   del   numero   si  

• ottiene  sommando   3

 alla  codifica  BCD        (4)  =  4  +  3  =  7  =  (0111)  

à 10 EX3

il   codice   2421,   dove   ogni   bit   ha   il   peso   indicato   dal   nome.   La   configurazione   a   tutti   1  

• rappresenta  il  numero   9

       (9)  =  2  +  4  +  2  +  1  =  (1111)  

à 10 2421

Tutti   e   tre   i   codici   si   rappresentano   con   quattro   bit…   ma   con   quattro  

bit  si  potrebbero  rappresentare  fino  a  16  configurazioni!  Questo  vuol  

dire  che  sia  il  BCD,  che  l’eccesso,  che  il  2421  hanno  sei  configurazioni  

inutilizzate.  

  Appunti di Jessica Asietti, non fotocopiare!

Una  particolare  codifica  è  il  codice   Grey  con  la  caratteristica  che  numeri  consecutivi  differiscano  

per  un  solo  bit.  A  differenza  delle  codifiche  viste  fino  ad  ora,  per  il  Grey  non  è  “intuitivo”  assegnare  

una  codifica  ad  un  numero  ma  bisogna  affrontare  diversi  passaggi.  

Vediamo  il  tutto  in  un  esempio:  

  Da  binario  a  Grey  

Si  prende  il  numero  in  binario  e,  partendo  dal  bit  meno  significativo  si  fa  

l’EXOR  a  due  a  due;  per  finire  si  prende  il  bit  più  significativo  così  com’è.  

Da  Grey  a  binario  

Si   parte  dal   bit   più  significativo,   preso   anche   questa   volta  così  com’è,  e  si  fa   una  

reazione  a  catena  di  EXOR  tra  l’EXOR  precedente  e  il  bit  alla  sua  destra.  

 Ci  ricordiamo  che  l’EXOR  vale  

1

 se  i  due  bit  sono  diversi,   0

 se  uguali.  

Codifiche  di  informazioni  alfanumeriche  

Fino   ad   ora   abbiamo   visto   come   rappresentare   in   vari   codici   i   numeri,   ma   il   nostro   alfabeto   è  

composto   da   ben   altro:   26   lettere   (alfabeto   inglese)   e   28   caratteri   vari   tra   punteggiatura   e   simboli  

vari.    

Anche  in  questo  caso  esistono  varie  codifiche  (EBCDIC,  UNICODE,  …)  ma  la  più  usata  sicuramente  

è  la   codifica  ASCII  (American  Standard  Code  for  Information  Interchange).  Di  essa  ne  esistono  due  

versioni:  

la  versione  a   7  bit  (quindi   128  simboli)  dove  l’ottavo  bit  viene  usato  per  la  parità  

• la  versione  a   8

  bit  (quindi   256  simboli)  che  prende  il  nome  di   ASCII  esteso  

•

Appunti di Jessica Asietti, non fotocopiare!

La  codifica  di  immagini  

Un  immagine  è  codificata  come  un  insieme  di  punti,  detti  pixel,  che  a  seconda  della  loro  codifica  

binaria   rappresentano   un   colore.   Ogni   pixel,   infatti,   è   dato   da   24   bit,   8   bit   per   colore:   RGB   (red  

green  blue)  e  più  si  utilizzano  pixel  più  la  nostra  immagine  sarà  dettagliata.  Questo  significa  che  

non  tutte  le  immagini  sono  rappresentate  nello  stesso  modo,  ma  alcune  possono  essere  migliori  di  

altre  in  base  alla   risoluzione  e  al  numeri  di  colori  che  si  utilizzano…  e  ovviamente  più  un’immagine  

è  veritiera  più  occuperà  spazio  in  memoria!  Ad  esempio:  

  Immagine  televisiva:    circa  440  kByte  

  Fotografia:  circa  440  MByte  

Inoltre   un’immagine   può   essere   salvata   in   vari   formati   a   seconda   del   rapporto   qualità/dimensione  

che  ci  sembra  più  indicato,  ad  esempio:  

GIF   (Graphics   Interchange   Format)   permette   di   memorizzare   più   immagini   in   uno   stesso  

• file  creando,  ad  esempio,  una  piccola  animazione  

JPEG   (Joint   Photographers   Expert   Group)   con   metodi   di   compressione   molto   utilizzati   in  

• internet   e   visualizzazione   interlacciata,   cioè   a   righe   alterne   che   vengono   caricate   man  

mano  e  così  acquista  nitidezza  anche  l’immagine  

BMP   (BitMaP)   che   permette   diverse   “qualità”   in   base   al   numero   di   bit   utilizzati   per  

• rappresentare  i  colori  (4,  8,  24  bit)  

Esiste  anche  un  altro  modo  differente  dai  pixel  per  codificare  un  immagine,  si  parla  di  immagini  

vettoriali.  Un’immagine  di  questo  tipo  non  è  rappresentata  con  “puntini”  di  colore  diverso  ma  con  

elementi  come  poligoni,  cerchi  e  linee  e  i  loro  

parametri  (raggio,  lunghezza,  vertici,  …).  

Il   vantaggio   della   codifica   vettoriale   è   l’indipendenza   dalla   risoluzione   e   quindi   un’occupazione  

ridotta   della   memoria   ma   non   tutte   le   immagini   possono   usare   questa   codifica:   una   fotografia,   ad  

esempio,  non  può  essere  divida  in  “oggetti”  principali.    

Discorso   analogo   alla   codifica   di   immagini   è   la   codifica   video.   Un   video   è   infatti   un   susseguirsi  

molto   rapido   di   immagini   e   l’unica   accortezza   è   trovare   un   numero   di   frame   al   secondo   perché  

esso  risulti  “fluido”.  Anche  in  questo  caso  vengono  usate  tecniche  di  compressione  perché  se  no  si  

necessiterebbe  di  troppo  spazio;  una  di  queste  è  la  codifica  

MPEG.    

Altri  dettagli  sui  riassunti  di  Sistemi  di  telecomunicazioni  -­‐  prof.  Favalli.  

  Appunti di Jessica Asietti, non fotocopiare!

ALGEBRA  BOOLEANA  

Una   variabile  booleana,  innanzitutto,  può  assumere  solo  due  valori:  

0

 e   1

.  

Gli  operatori  booleani  sono  quelle  porte  logiche  che  svolgono  operazioni,  appunto,  sulle  variabili  

booleane.  

La  porta  NOT   Semplicemente  inverte  il  valore:  

0 à    1  

1 à    0  

La  porta  AND   In  italiano  potremmo  dire  che  significa  “e”,  in  elettronica  potremmo  dire  che  

sono   interruttori   in   serie.   Questo   vuol   dire   che   vale   1   solo   se   entrambi   gli  

ingressi  valgono  

1 .  

La  porta  OR   In   italiano   potremmo   dire   che   significa   “oppure”,   in   elettronica   potremmo  

dire   che   sono   degli   interruttori   in   parallelo.   Questo   vuol   dire   che   basta   un  

  solo  

1

 perché  l’uscita  sia  a  

1

,  cioè  vale  

0  solo  se  entrambi  gli  ingressi  sono  a  

0 .  

   Nell’algebra   di   Boole   vale   il   teorema   di   dualità:   se   si   scambiano   gli   operatori   logici   e   si  

invertono   tutti   gli   ingressi   allora   si   ottiene   una   funzione   duale   alla   precedente.   Da   qui   nasce   il  

teorema  di  De  Morgan,  fondamentale  nelle  reti  logiche:  

Oltre  ai  tre  operatori  logici  visti  sopra  ne  esistono  altri  due  detti  

operatori  universali:  

la  porta   NAND,  che  vale  quindi  

0

 solo  con  gli  ingressi  a   1

• la  porta   NOR,  che  vale  quindi  

1

solo  con  gli  ingressi  a   0

•

Essi   prendono   il   nome   di   “universali”   perché   è   possibile   realizzare   interi   circuiti   solo   con   una   di  

loro  due.    

Appunti di Jessica Asietti, non fotocopiare!

La  porta  EXOR   Chiamata   anche   OR   esclusivo   può   essere   ricavata   anche   dai   tre  

operatori  logici  principali:      

E’  detta  

funzione  disparità  perché  vale   1

 solo  quando  un  numero  dispari  di  ingressi  vale  

1

.  

Esiste  anche  la  sua  complementare,  la  

XNOR,  che  invece  rappresenta  la  funzione  parità.  

  Appunti di Jessica Asietti, non fotocopiare!

LE  MEMORIE  

La  RAM  

RAM,  acronimo  di  Random  Access  Memory,  è  appunto  una  memoria  ad  accesso  casuale,  ovvero  non  in  un  

determinato  ordine,  ma  permette  di  raggiungere  qualsiasi  indirizzo  di  memoria  con  lo  stesso  dispendio  di  

tempo.  Ha  lo  svantaggio  di  essere  una  memoria  volatile  ovvero,  appena  manca  la  corrente,  essa  si  cancella.    

Ne  esistono  vari  tipi:  

SRAM:  (Static  RAM)  sono  particolari  RAM  che  riescono  a  mantenere  le  informazioni  per  un  tempo  

• infinito,   molto   veloci   e   con   poco   consumo.   Sono   molto   costose   e   a   bassa   capienza,   per   questo  

solitamente  vengono  utilizzate  per  le  memorie  cache.    

DRAM:   (Dynamic   RAM)   sono   particolari   RAM   formate   da   un   transistor   separato   da   un  

• condensatore.  Essendo  che  il  condensatore  tende  a  scaricarsi  si  rischia  di  perdere  le  informazioni  

memorizzate  per  questo  è  necessario  svolgere  un  refresh  ogni  pochi  millisecondi  e,  nel  momento  

del  refresh,  la  memoria  è  inagibile  (ovvero  non  si  può  accedervi)  e  questo  è  un  enorme  svantaggio!  

Sono   memorie   asincrone,   cioè   l’accesso   alla   scrittura   e   lettura   non   è   comandato   da   un   clock   e,  

quando  un  dato  viene  letto  viene  anche  perso  (lettura  distruttiva).  Non  sono  memorie  molto  veloci  

ma  sono  ad  alta  capacità,  per  questo  vengono  usate  spesso  come  memoria  principale  del  sistema.  

SDRAM   e   SSRAM:   sono   memorie   sincrone,   comandate   da   un   clock,   quindi   basta   specificare  

• l’indirizzo   di   partenza   e   una   lunghezza   e   loro   procedono   in   maniera   sequenziale;   risulta  

un’operazione  veloce  perché  non  c’è  bisogno  di  compiere  istruzioni  strane,  ci  pensa  il  clock.    

La  ROM  

ROM,   Read   Only   Memory,   sono   appunto   memorie   di   sola   lettura,   cioè   non   più   modificabili   dopo   la   loro  

scrittura   da   parte   del   programmatore.   Solitamente   contengono   programmi   come   quello   per   avviare   il  

calcolatore.  A  differenza  della  RAM  sono  memorie  non  volatili  ovvero  mantengono  le  informazioni  anche  se  

vengono  disalimentate.  Anche  di  ROM  ne  esistono  vari  tipi:  

PROM:  (Programmable  ROM)  la  prima  scrittura  viene  fatta  dall’utente  e  non  dal  programmatore,  

• ma,  comunque,  una  volta  scritta  per  la  prima  volta  non  può  più  essere  modificata.  

EPROM:   (Erasable   Programmable   ROM)   come   la   PROM   anche   essa   può   essere   scritta   dall’utente  

• ma  la  differenza  è  che  si  può  cancellare  esponendola  a  raggi  ultravioletti  così  da  poterla  riscrivere  

(anche   se   per   un   numero   limitato   di   volte).   Per   poterla   cancellare,   la   EPROM,   ha   una   piccola  

finestrella   sulla   sua   superficie   che   lascia   intravedere   il   chip,   se   esso   viene   posizionato   sotto   una  

lampada  a  UV  (ne  esistevano  di  apposite  come  la  Eprom  Eraser)  per  un  massimo  di  45  minuti,  tutti  i  

bit  della  memoria  passavano  al  valore  alto  facendola  diventare  riscrivibile.  Oramai  le  EPROM  non  

vengono   quasi   più   usate.   Ne   esiste   anche   una   versione   cancellabile   tramite   segnali   elettrici,   la  

EEPROM.  

FLASH:   sostitute   delle   EPROM,   esse   sono   memorie   non   volatili   che   è   possibile   usare   anche   come  

• memorie   di   lettura-­‐scrittura.   Il   loro   vantaggio   è   la   cancellazione,   anche   parziale,   tramite   impulsi  

elettrici;   in   pratica   si   usa   il   cosiddetto   “effetto   tunnel”   cioè   tutti   i   contatti   source   vengono   portati   a  

tensione   positiva   mentre   i   gate   ad   una   tensione   negativa.   Si   chiamano   FLASH   perché   sono   molto  

veloci,   infatti   la   loro   scrittura   viene   fatta   bit   a   bit   mentre   la   cancellazione   è   fatta   ad   aree   e   sono  

utilizzate  in  cellulari  e  fotocamere  oltre  che  nei  recenti  computer  portatili.  

Sia   le   RAM   che   le   ROM   sono   memorie  a  semiconduttore  cioè   i   loro   circuiti   integrati   hanno   una   base   in  

silicio.    

  Appunti di Jessica Asietti, non fotocopiare!

Le  memorie  a  supporto  magnetico  

Bistabili:  sono  memorie  a  supporto  magnetico,  infatti  sono  costituiti  da  areole  ferromagnetiche  sopra  un  

supporto  di  plastica,  lette  da  una  testina  elettromagnetica  (di  lettura  e  scrittura).    

  spire  per  leggere  e  scrivere  

  testina  

areole  

supporto  

Si   chiamano   bistabili   perché   possono   essere   stabili   in   due   stati   (0   e   1)   determinati   dal   senso   di  

magnetizzazione   della   testina   ovvero   magnetizzando   le   areole   grazie   alla   corrente   positiva   o   negativa  

inserita  nelle  spire.  Anche  per  quanto  riguarda  la   lettura,  essa  si  effettua  grazie  alla  tensione  mandata  nelle  

spire  che  permette  il  passaggio  delle  areole  sotto  la  testina.    

Esistono  due  categorie  di  bistabili:  gli  asincroni  (che  modificano  il  loro  stato  tramite  segnali  d’ingresso)  e  i  

sincroni  (  sensibili  al  segnale  di  clock,  come  i   flip-­‐flop).    

Hard   disk:   o   disco   rigido,   è   un   dispositivo   di   memoria   di   massa   di   tipo   ferromagnetico   in   quanto   per  

funzionare   utilizza   dischi   magnetizzati   sui   quali   vengono   archiviate   le   informazioni.   E’   formato   da   “piatti”   di  

alluminio  rivestiti  capaci  di  ruotare  velocemente  e  da  due  testine  per  ogni  disco  (lontane  pochi  micron  dal  

disco)  che  ne  permettono  la  scrittura  e  la  lettura.    

  testina  in  movimento  

  tracce  

  settore  

Esistono   anche   hard   disk   a   testine   fisse   che   per   essendo   molto   più   veloci   sono   anche   più   costosi   e   non  

permettono  la  sostituzione  dei  dischi.  

Alcuni  parametri:     velocità  rotazione   max  15000  giri  al  minuto  

  velocità  spostamento  braccio   30  millisecondi    

  velocità   t rasferimento   max  60  Megabyte  al  secondo  

  capacità  memorizzazione   20  Gigabyte  -­‐  Terabyte  

Speciali   memorie   sono   i   RAID   (Redundant   Array   of   indipendent   Disks)   che   sono   un   insieme   di   dischi   rigidi   a  

basso  costo  collegati  tra  di  loro.  Esse  sono  usate  per  proteggere  i  dati  in  caso  di  malfunzionamento  di  uno  

dei  dischi  rigidi,  infatti  salvano  dati  ridondanti  in  piccoli  blocchi  così  da  essere  sicuri  non  perderli.    

Floppy   disk:   anch’esso   è   un   supporto   di   memorizzazione   grazie   alla   magnetizzazione   di   un   sottile   disco  

protetto  da  un  involucro  di  plastica.  Necessitano  di  un  lettore  apposito  e,  una  volta  scritti,  non  possono  più  

essere  cancellati.  Oramai  sono  caduti  in  disuso  anche  perché  avevano  il  grosso  svantaggio  di  essere  fermi,  

non  rotanti  come  negli  HD  e  per  questo  l’accesso  alle  informazioni  risultava  molto  lento.    

  Appunti di Jessica Asietti, non fotocopiare!

Nastri:   formati   da   una   striscia   sottile   in   plastica   rivestita   di   un   materiale   magnetizzante,   anche   i   nastri  

servono  per  memorizzare  dati.  Ogni  striscia  è  formata  da  9  piste  parallele  ed  ognuna  ha  una  propria  testina  

che  consente  appunto  di  memorizzare  le  informazioni  anche  con  il  bit  di  parità  (cioè  ogni  pista  memorizza  

un  bit  così  da  poter  memorizzare  nello  stesso  momento  un  byte  con  il  proprio  bit  di  parità).  

  testine  

nastro  e  tendinastro  

bobina  

Le   informazioni   sono   memorizzate   in   blocchi,   cioè   ogni   informazione   è   divisa   una   dall’altra   grazie   a   zone  

non  magnetizzate;  ogni  blocco  è  chiamato  record.  Il  loro  svantaggio  è  che  sono  molto  lenti  perché  il  loro  

accesso   è   sequenziale,   ovvero   prima   di   trovare   l’informazione   che   si   cerca   il   nastro   deve   essere   letto   ma  

hanno   anche   l’enorme   vantaggio   di   essere   molto   capacitivi   e   per   questo   sono   adatti   soprattutto   per   i  

backup  (possono  contenere  da  100  GB  a  1  TB).    

Dischi   ottici:   derivati   dai   CD,   vengono   usati   per   riproduzioni   audio,   e   sono   formati   da   dischi   con  

deformazioni   permanenti   (cioè   buchi)   fatte   durante   la   fase   di   scrittura   grazie   a   un   raggio   di   luce   che   ne  

colpisce  la  superficie  (formata  da  una  sola  traccia  avvolta  a  spirale).  Hanno  il  difetto,  come  le  ROM,  di  non  

poter  essere  cancellati  (sola  lettura).  I  dischi  ottici  sono  anche  conosciuti  come  WORM  ovvero  Write  Once  

Read  Many,  proprio  per  il  fatto  di  essere  scritti  una  volta  sola  ma  con  la  possibilità  di  essere  letti  più  volte.    

CD-­‐RW:   ovvero   riscrivibili,   sfruttano   la   tecnologia   del   “phase-­‐change”   per   poter   scrivere   o   cancellare   le  

informazioni:  

se   la   superficie   viene   colpita   con   un   laser   da   8mW   l’informazione   viene   scritta   (lo   spazio,   detto  

• spot,  diventa  amorfo)  

se  la  superficie  viene  colpita  da  un  laser  di  18mW  l’informazione  viene  cancellata  (spot  cristallino).  

•

I   DVD  differiscono  dai  CD  per  la  loro  struttura:  

  policaarbonato  

  semi-­‐riflettetente  (memoria  di  circa  4  GB)  

  policarbonato  

  completamente  riflettente  (memoria  di  circa  5  GB)  

Tipi  di  accesso  e  convenienza  

Non  tutte  le  memorie  hanno  lo  stesso  tipo  di  accesso:  

accesso   casuale  tipico  della  memoria  centrale,  grazie  all’indirizzo  è  possibile  trovare  subito  il  dato  

• con  un  dispendio  di  tempo  fisso  

accesso   sequenziale   tipico   dei   nastri,   i   dati   vengono   sempre   letti   uno   dopo   l’altro   quindi,   per  

• trovare   l’informazione   che   si   vuole   è   necessario   aspettare   che   il   nastro   venga   letto   tutto   fino   al  

punto  in  cui  è  presente  l’informazione  

accesso  diretto  tipico   dei   dischi,   il   dato   viene   trovato   subito   ma   il   tempo   varia   a   seconda   di   dove   si  

• trova  nel  disco  (non  c’è  un  tempo  fisso,  dipende  da  quanto  la  testina  deve  cercare)  

Ordine  di  convenienza:  le  memorie  a  semiconduttore  sono  le  più  veloci  ma  hanno  un  costo  elevato,  i  dischi  

sono   meno   costosi   ma   anche   più   lenti   e   infine   i   nastri   sono   molto   lenti   ma   poco   costosi   (e   con   gran  

capacità).   Appunti di Jessica Asietti, non fotocopiare!

I  canali  che  portano  le  informazioni:  i  BUS  

I  BUS  sono  dei  canali  che  permettono  il  passaggio  delle  informazioni.  Ne  esiste  più  di  un  tipo:  

BUS  dati:  i  segnali  che  passano  al  suo  interno  sono  proprio  le  informazioni  che  vengono  trasferite  

• da  un’unità  alla  sua  destinazione  scritta  nel  suo  pacchetto.  i  conduttori  del  bus  dati  possono  essere  

8,  16  oppure  32  a  seconda  della  lunghezza  delle  parole  del  sistema.  

BUS   indirizzi:  si  occupa  di  trasferire  gli  indirizzi  dalla  CPU  alla  periferica  interessata.  Anche  in  questo  

• caso   i   conduttori   possono   essere   da   un   minimo   di   10   ad   un   massimo   di   32,   a   seconda  

dell’indirizzamento.  

BUS   di   controllo:   si   occupa   appunto   di   controllare   che   tutto   funzioni,   sia   la   qualità   del  

• trasferimento  che  la  validità  di  indirizzi  e  dati.  Il  BUS  di  controllo  varia  da  calcolatore  a  calcolatore  

ma,  in  generale,  tutti  svolgono  la  stessa  funzione.    

BUS   di   servizio:  è  un  BUS  ausiliario,  usato  solo  quando  serve  ad  esempio  un  “reset”  o  per  segnalare  

• il  clock.  

BUS  di  alimentazione:  al  suo  interno  non  passano  segnali  ma  l’alimentazione  delle  periferiche  (5  o  

• 12  V  e  la  massa).  

Nei  BUS  è  molto  importante  il  numero  di  conduttori  (linee)  che  li  formano;  infatti,  più  un  BUS  ha  conduttori  

a  disposizione,  più  potrà  trasferire  dati  nello  stesso  momento  (nel  caso  del  BUS  dati)  o  indirizzare  maggior  

quantità  di  memoria  (nel  caso  del  BUS  di  indirizzi).    

Appunti di Jessica Asietti, non fotocopiare!

LA  GESTIONE  DELLA  MEMORIA  

    Le   memorie   sono   una   risorsa   fondamentale   per   il  

CPU     buon   funzionamento   d i   un   elaboratore,   infatti,   per  

  esempio   ogni   programma   per   poter   essere  

memoria  cache   eseguito   deve   risiedere   nella   memoria   centrale  

c t come   anche   i   dati   coinvolti   nell’istruzione.   Il  

o e problema  sta  nel  trovare  delle  memorie  che  siano  

memoria  centrale   s m il   più  possibile   grandi   (in   modo   che   molti   processi  

t p possano   “convivere”   nello   stesso   momento)   ma  

o   o   anche   veloci   (per   non   avere   dispendio   di   tempo).  

dischi  magnetici   Un   ulteriore   problema   è   come   organizzare   la  

  memoria   in   quanto   essa   è   suddivisa   in   celle   tutte  

nastri     uguali  che  possono  contenere  indirizzi  utilizzati  per  

  svolgere   le   istruzioni,   questo   viene   fatto   grazie   al  

  principio  di  località  degli  accessi.  

Esso  consiste  appunto  nell’organizzare  al  meglio  la  memoria  cercando  di  limitare  anche  le  memorizzazioni  

di  dati  tutti  uguali  a  breve  distanza  di  tempo.  Esistono  due  tipi  di  principi  di  località:  

temporale:   alta   probabilità   che   la   stessa   cella   venga   utilizzata   a   distanza   di   poco   tempo   (quindi   per  

• convenienza   il   dato   viene   tenuto   così   da   non   doverlo   ricopiare   ma   basta   riaccedere   a   quello   già  

memorizzato)  

sequenziale:   alta   probabilità   che   oltre   ad   una   cella   vengano   richieste   quelle   vicine   (lettura  

• sequenziale,  consecutiva)  

In   pratica   la   memoria   viene   organizzata   in   maniera   virtuale   cioè   le   informazioni   non   vengono   ricopiate  

fisicamente  nella  memoria  centrale  ma  vengono  pescate  da  una  piccola  parte  ricavata  da  una  memoria  di  

massa.   Il   problema   è   il   loro   indirizzo   che   arriva   alla   memoria   centrale   come   virtuale   e   deve   essere  

trasformato   nell’indirizzo   fisico   dove   effettivamente   si   trova   il   dato   nella   memoria   di   massa;   questo  

problema  è  risolto  dalla   MMU   ( Memory  Management  Unit).  I  compiti  della  MMU  sono:  

tradurre  l’indirizzo  da  virtuale  a  fisico    

• controllare  che  effettivamente  l’indirizzo  fisico  esista,  ci  sia  un  corrispondente  reale  nella  memoria  

• di  massa  

Ovviamente   la   MMU   necessita   dei   suoi   tempi   e   quindi,   il   fatto   di   avere   una   memoria   virtuale,   ha   lo  

svantaggio  di  far  perdere  velocità  al  calcolatore.    

Esistono  due  modi  per  creare  una   memoria  virtuale:  

con   il   metodo   della   paginazione   (gestito   dall’hardware),   ovvero   dividendo   la   memoria   in   tante  

• pagine   di   ugual   dimensione   che   corrisponde   alla   dimensione   minima   di   informazione   trasferita  

dalla  memoria  di  massa  a  quella  centrale    

con   il   metodo   della   segmentazione   (gestito   dall’utente)   che   divide   il   programma   in   pezzi  

• indipendenti  

Memoria  paginata  

L’idea  è  quella  di  dividere  la  memoria  virtuale  in  pagine  tutte  della  stessa  dimensione  (circa  4  Kilobyte)  così  

da   trasferire   informazioni   presenti   nella   memoria   di   massa   nelle   pagine   tramite   operazioni   di   swapping.  

Anche  la  memoria  fisica  viene  divisa  nelle  stesse  pagine  e  ogni  programma,  ad  esempio,  può  occupare  più  

pagine  anche  non  di  seguito.    

Esiste   una   tabella   che   relazione   le   pagine   fisiche   con   le   pagine   virtuali   così   da   tenere   sotto   controllo  

v dove  si  trovano  i  dati.  Ogni  riga  è  formata:     pagina   presente/non  presente   indirizzo  fisico  

  Appunti di Jessica Asietti, non fotocopiare!

Nel   caso   la   pagina   non   sia   presente   nella   memoria   virtuale   è   necessario   caricarla   dalla   memoria   di  

massa   ma   questo   vuol   dire   trovare   una   parte   di   memoria   virtuale   vuota   dove   inserirla.   Se   non   è  

presente   nessuna   pagina   vuota   viene   eliminato   il   contenuto   della   pagina   che   non   viene   usata   da   più  

tempo  ( LRU,  Least  Recently  Used).  

Svantaggi:   innanzitutto   il   problema   che   se   la   memoria   è   divisa   in   molte   pagine   anche   la   tabella   sarà  

v molto   estesa   e   quindi   complicata,   e   in   secondo   luogo   che   magari   un   programma   necessita   di   poco  

spazio  superiore  alla  dimensione  di  una  pagina  quindi  dovrà  utilizzarne  almeno  due  di  cui  una  rimarrà  

mezza  vuota  (molto  spazio  inutilizzato).    

  pag1   pag2   pag3   pag4   pag5   …  

Memoria  segmentata  

La   memoria   non   è   più   suddivisa   in   pagine   di   dimensione   standard   ma   in   segmenti   di   lunghezza   variabile.  

Esiste  comunque  anche  in  questo  caso  una  tabella  per  tener  sotto  controllo  l’organizzazione:  

segmento   presente/non  presente   indirizzo   lunghezza  segmento    

Anche  in  questo  caso  se  il  segmento  non  è  presente  è  necessario  importarlo  dalla  memoria  di  massa  e,  se  

questo   necessita   di   cancellare   un   vecchio   segmento   inutilizzato,   il   nuovo   occuperà   una   certa   quantità   della  

lunghezza  del  vecchio  segmento,  non  necessariamente  la  stessa,  lasciando  memoria  inutilizzata.    

Dopo   un   certo   numero   di   operazioni   di   swapping   (cioè   che   la   memoria   virtuale   viene   riempita   o  

v svuotata)  la  memoria  risulta  piena  di  buchi  dovuti  ai  vari  spostamenti  ed  è  necessario  eliminarli.  Si  usa  

quindi  fare  ogni  tanto  una   compattazione.  

1   2   3   4   5   6    

1   2   v   3   4   v   5   6    

1   2   3   4   5   6   vuoto     compattazione  

Segmentazione  paginata  

E’   una   soluzione   intermedia   tra   la   paginazione   e   la   segmentazione:   ogni   programma   viene   diviso   in  

segmenti   (dimensione   variabile)   a   loro   volta   suddivisi   in   pagine   (della   stessa   dimensione)   così   da   cercare   di  

limitare   lo   spazio   avanzato   nell’ultima   pagina.   Anche   in   questo   caso   servirà   una   tabella   identificativa   ma  

con  due  livelli:  uno  per  identificare  il  segmento,  e  uno  per  identificare  la  pagina  dentro  il  segmento.    

Gerarchia  di  memoria  

Essendo  che  le  memorie  sono  difficili  da  gestire  bisogna  cercare  di  sfruttare  il  loro  spazio  nel  migliore  dei  

modi  anche  per  sfruttare  al  meglio  il  tempo:  

le  informazioni  a  disposizione  del  calcolatore  sono  memorizzate  sui   nastri  (grandi,  economici,  lenti)  

• le  informazioni  utilizzate  quotidianamente  sono  memorizzate  sui   dischi  (più  veloci  e  piccoli)  

• le   informazioni   usate   quotidianamente   dai   programmi   sono   memorizzate   nelle   memorie   a  

• semiconduttore  (lente  ma  con  grande  capacità)  

le   informazioni   usate   in   quel   momento   sono   memorizzate   in   altre   memorie   a   semiconduttore  

• piccole  ma  molto  veloci  

La  memoria  cache  

La   memoria   cache   è   una   memoria   veloce   completamente   gestita   dall’hardware   (quindi   il   software   non   si  

accorge   della   sua   esistenza)   creata   per   aiutare   la   memoria   principale   nella   gestione   dei   dati   usati   più   di  

recente  e  che  quindi  potrebbero  essere  richiesti  di  nuovo  in  un  futuro  prossimo.  Grazie  ad  essa  è  possibile  

Appunti di Jessica Asietti, non fotocopiare!

velocizzare   gli   accessi   alla   memoria   principale   riducendo,   però,   il   traffico   sui   BUS   e   quindi   limitando   dei  

possibili  bottleneck.    

La  sua  velocità  è  data  dalla  tecnologia   SRAM  ( Static  Random  Access  Memory),  più  costosa  della  DRAM,  ma  

che   non   necessita   refresh,   dove   i   dati   possono   rimanere   per   un   tempo   teoricamente   infinito   a   basso  

consumo  e  con  tempi  di  lettura,  appunto,  molto  veloci.  

Come  funziona  quindi  la  cache?  

Se   il   processore   ha   bisogno   di   un   dato   o   un’istruzione,   prima   di   ricercarla   nella   memoria   centrale,   controlla  

che  non  sia  presente  già  nella  cache  così  da  averla  disponibile  in  poco  tempo  data  la  sua  velocità.  Solo  se  

non  è  presente  nella  cache,  allora,  domanda  alla  memoria  centrale.    

  Appunti di Jessica Asietti, non fotocopiare!

STRUTTURE  INFORMATIVE  

I  dati,  all’interno  di  un  calcolatore,  possono  essere  strutturati  in  modi  differenti.  In  realtà,  la  prima  

differenza  sostanziale  sta  nell’organizzazione  in  strutture  astratte  o  strutture  concrete:  

si   parla   di   strutture  astratte   per   quelle   rappresentazioni,   appunto,   astratte   dei   vari   legami  

• tra  componenti.  Ne  sono  esempi  le  matrici,  le  tabelle,  le  pile,  gli  alberi  e  così  via  

si   parla   di   strutture   concrete   per   indicare   come   realmente   sono   organizzati   i   dati  

• all’interno  della  memoria,  quindi  ci  si  riferisce  ai  vettori  di  memoria  o  ai  file.  

Iniziamo  dalle  strutture  astratte.  

La  lista    

Sono   caratterizzate   da   un   insieme   ordinato   di   elementi   dove   ogni   elemento   ha   un   suo   precedente  

e   un   suo   successivo   ben   identificato   (tranne,   ovviamente,   il   primo   e   l’ultimo   elemento).   In  

un’organizzazione  di  questo  tipo,  quindi,  per  poter  arrivare  all’elemento   X

 è  necessario  passare  da  

tutti  gli  elementi  che  lo  precedono  nella  lista.    

Solitamente   su   una   lista   è   possibile   svolgere   molte   operazioni:   cancellazione   di   un   elemento,  

modifica,  concatenazione  di  più  liste,  ecc.    

Se  gli  elementi  della  lista  sono  lettere  dell’alfabeto  allora  si  parla  di  

stringa.  

La  coda    

Molto  simile  alla  lista  con  la  particolarità  che:  

si  possono  inserire  elementi  solo  dopo  l’ultimo  elemento  della  coda  (fondo)  

• si  possono  eliminar  elementi  solo  dal  primo  elemento  della  coda  (testa)  

•

NB.  Detta  così  significa  che  la  coda  viene  vista  da  destra  verso  sinistra,  cioè  con  una  politica  FIFO,  

First  Input  First  Output.    

La  pila   TOS:  Top  of  the  Stack  

Struttura   lineare   dove   sia   l’inserimento   che   l’estrazione   dei   dati  

avvengono   dalla   stessa   parte   e   quindi   con   una   politica   LIFO,   Last  

Input  First  Output.   Questo   significa  che   il  primo  elemento  inserito  

sarà  poi  l’ultimo  a  venir  estratto.  

Gli  array  

L’array  è  una  struttura  a  lunghezza  finita  dove  ad  ogni  elemento  è  associata  una  n-­‐upla  di  numeri  

interi   chiamati   indici:   se   esiste   un   solo   indice   si   parla   di   vettore   mentre   se   gli   indici   sono   due   si  

parla   di   matrice.   Quindi,   a   differenza   della   lista   dove   per   arrivare   ad   un   elemento   è   necessario  

percorrere   tutti   gli   elementi   precedenti,   per   accedere   ad   un   elemento   dell’array   basta   conoscere   i  

suoi  indici.     Appunti di Jessica Asietti, non fotocopiare!

La  tabella  

Possiamo  dire  che  la  tabella  assomiglia  molto  ad  un  array  con  la  differenza  che,  per  accedere  ad  

un  elemento,  non  vengono  richiesti  i  suoi  indici  bensì  una  

chiave.  

Questo  viene  usato  quando  non  c’è  un  legame  “matematico”  tra  le  varie  

colonne,   cioè   quando   ogni   colonna   contiene   dati   completamente  

scollegati   dalle   altre.   Nell’esempio   affianco,   infatti,   non   c’è   nessuna  

caratteristica   “matematica”   che   lega   le   varie   colonne   e   quindi   è   più  

sensato  usare  delle  chiavi,  piuttosto  che  gli  indici,  per  differenziarle.    

Possiamo  dire  quindi,  che  la  tabella  assomiglia  ad  un  insieme  di  vettori  verticali  dove  la  colonna  è  

una  sola  (e  di  indice  la  sua  chiave)  mentre  la  riga  avrà  un  indice  come  accadeva  per  gli  array.    

Come  per  gli  array  anche  in  questo  caso,  però,  si  parla  di   struttura  statica  perché  solitamente  non  

cambia  più  di  dimensione  una  volta  realizzata.    

I  grafi  

Un  grafo  è  una  figura  costituita  da  due  elementi  principali:  

nodi  (o  vertici)  che  sono  i  punti  raggiungibili  del  grafo  

• archi  (o  lati)  che  sono  i  collegamenti  che  congiungono  due  nodi  

•

quindi  se  vediamo  un  nodo  come  un  dato  e  un  arco  come  la  relazione  tra  due  dati,  allora  si  nota  

subito  che  un  grafo  è  una  struttura  informativa  astratta.  

Definizioni:  

Nodi  adiacenti:  

nodi  per  cui  esiste  un  arco  che  gli  unisce.  

• Cammino:   successione   di   nodi   adiacenti.   Si   parla   di   cammino   semplice   se   il   nodo   di  

• partenza  non  è  il  nodi  di  arrivo,  mentre  di   ciclo  (o  circuito)  se  il  nodo  di  partenza  è  anche  la  

destinazione  finale.  

Grafo   connesso:  un  grafo  si  dice  connesso  se,  scelta  a  caso  una  coppia  di  nodi,  è  sempre  

• possibile  congiungerli.  Quindi  se  ogni  nodo  è,  in  qualche  modo,  legato  a  tutti  gli  altri  nodi  

del  grafo.  

Grafo   orientato:   si   pala   di   grafo   orientato   se   gli   archi   hanno   un   orientamento   e,   cioè,  

• possono  essere  percorsi  solo  in  un  determinato  verso.    

Gli  alberi   Un  albero  è  un  grafo  connesso  in  cui,  però,  non  esistono  cicli  e,  scelto  un  

nodo   qualsiasi   come   radice,   è   possibile   ordinare   i   suoi   nodi   in   livelli.  

Addirittura   si   parla   di   albero  ordinato  se  in  ciascun  livello  conta   l’ordine  

in  cui  compaiono  i  nodi.    

Per  un  albero  costituito  da  

N

 nodi:  

esistono   N-­‐1  archi  

• ogni  coppia  di  nodi  è  connessa  da  

un  solo  percorso  semplice    

• se  si  rimuove  un  arco  qualsiasi  non  si  avrà  più  un  albero  connesso  bensì  due  alberi  distinti  

•

  Appunti di Jessica Asietti, non fotocopiare!

  Definizioni:  

Foglia:   nodo   che  non  appare  mai   in   nessun   percorso  

• tra  la  radice  e  un  altro  nodo.  

Sottoalbero:   albero   denotato   prendendo   un   nodo  

• sottostante  alla  radice  come  nuova  radice.  

Grado:  

numero  di  sottoalberi  del  nodo.  

•

Come  per  le  liste  si  passava  da  un  elemento  all’altro,  in  questo  caso  si  parla  di  visitare  un  albero  

quando   gli   elementi   (nodi)   vengono   esaminati   ad   uno   ad   uno   in   ordine   appropriato.   Il   metodo   più  

semplice   sarebbe   quello   di,   ad   ogni   visita   ad   un   nodo,   ripartire   dalla   radice   ma   questo   metodo  

risulta  inefficiente.  Per  questo  esistono  due  altri  modi  per  visitare  un  albero:  

ordine  anticipato:  

si  parte  dalla  radice  e  si  esaminano  in  ordine  tutti  i  sottoalberi  

• ordine   differito:   la   radice   viene   visitata   per   ultima,   quindi   si   parte   dalle   foglie   di   livello  

• maggiore  e  si  sale  visitando  i  sottoalberi  “al  contrario”    

E’  più  facile  capire  i  tipi  di  visita  con  un  disegno:  

Ordine  anticipato:   D  B  A  C  F  E  H  L  I  G  

Ordine  differito:     A  C  B  F  L  H  I  G  E  D  

Un  altro  tipo  di  albero  è  l’albero  binario:  

formato   da   una   radice   e   due   sottoalberi,   uno   destro   e   uno   sinistro,  

mantiene  la  sua  identità  anche  con  la  mancanza  di   un  sottoalbero,   cosa  

non   possibile   in  un   normale   albero   e   per   questo   un   albero   binario   non   è  

un  tipo  particolare  di  albero  bensì  un  tipo  distinto.    

Anche  gli  alberi  binari,  però,  possono  essere  visitati  in  ordine  anticipato  

oppure  differito;  e  anche  in  un  terzo  modo:   visita  in  ordine  simmetrico.  

Questo   terzo   modo   consiste   nel   visitare   prima   il   sottoalbero   sinistro,   poi   la   radice   e   poi   il  

sottoalbero  destro.  In  un  esempio:   Se  vediamo  

D

 come  radice:  

  G  D  H  I  

Se  vediamo  

F  come  radice:   L  F  M  N  

Quindi  in  generale:     G  D  H  I  B  E  -­‐  A  -­‐  C  L  F  M  N  

Ma  perché  utilizzare  gli  alberi  binari?  Perché  qualsiasi  albero  ordinato  può  essere  trasformato  in  

un  albero  binario  ed  essi  hanno  una  struttura  molto  semplice  da  rappresentare  in  memoria.    

E  come  trasformare  un  albero  ordinato  in  un  albero  binario?    

1. La  radice  dell’albero  ordinato  

S

 coincide  con  la  radice  dell’albero  binario  

T  

2. ogni  nodo  di   T  ha  come  figlio  sinistro  il  primo  figlio  del  nodo  corrispondente  in  

S

3. ogni  nodo  di   T  ha  come  figlio  destro  il  fratello  del  nodo  corrispondente  in  

S

  Appunti di Jessica Asietti, non fotocopiare!

Quindi,  nell’esempio:  

1. D  rimane  la  radice  

2. il  figlio  sinistro  rimane   A

3. il  figlio  destro  diventa  

F  

4. A  non  avrà  figlio  sinistro  

5. A  avrà   C  come  figlio  destro  

e  così  via  fino  a  trovare  le  “parentele”  per  ogni  

nodo.    

Con   l’albero   si   chiudono   tutte   le   strutture   astratte   di   dati.   Vediamo   ora   le   strutture   concrete  

ovvero   quelle   strutture   che   veramente   rappresentano   la   memoria   del   calcolatore   per   le   quali   le  

strutture  astratte  sono  solo  una  semplificazione.    

Le  strutture  concrete  sono  tre:  la  struttura  sequenziale,  la  catena  e  il  plesso.  

La  struttura  sequenziale   La  struttura  sequenziale,  come  dice  la  parola  

stessa,   è   formata   da   un   insieme   di   elementi  

adiacenti   tra   di   loro   che   possono   richiedere  

una   o   più   celle.   Solitamente   ogni   elemento  

utilizza  lo  stesso  numero  di  celle,  cioè  hanno  

tutti  la  stessa  lunghezza,  ma  questo  non  è  per  

forza  vero.    

I   parametri   necessari   in   una   struttura  

sequenziale  sono:  

i   indirizzo  primo  elemento  

• b

m   numero  di  elementi  

• d   numero  di  celle  per  elemento  

•

Quindi:  

indirizzo  (X )  =  i  

1 b

indirizzo  (X )  =  i  +  i*d     cioè  l’indirizzo  del  primo  elemento  più  un  certo  numero  di  celle  per  

i b

        raggiungere  l’i-­‐esimo  elemento.  

  i

  sarà   comunque   un   numero   compreso   tra   1   e   m   ed   m   non   è   più   modificabile   dopo   la  

creazione.   Questo   vuol   dire   che   la   struttura   sequenziale   è   una   struttura   rigida   e   per   questo   è  

necessario  sapere  a  priori  quanti  dati  verranno  inseriti!  

Abbiamo   detto   che   non   è   per   forza   vero   che   tutti   gli   elementi   utilizzano   lo   stesso   numero   di   celle.  

In  questo  caso  ci  sono  solo  due  possibili  soluzioni  per  trattare  la  nuova  struttura:  

normalizzo   tutti   gli   elementi   alla   stessa   lunghezza   basandomi   sull’elemento   che   richiede  

• più  celle  di  memoria  

lascio   ad   ognuno   la   sua   lunghezza   ma   devo   essere   in   grado   di   fornire   abbastanza  

• informazioni  per  calcolare  tutti  gli  indirizzi  senza  troppi  problemi…  e  questo  non  è  per  nulla  

semplice!   Appunti di Jessica Asietti, non fotocopiare!

Inoltre   le   strutture   sequenziali   non   sono   per   niente   flessibili,   infatti   se   volessi   inserire   un   nuovo  

elemento  in  una  certa  posizione  dovrei  cancellare  tutti  gli  elementi  presenti  da  quella  posizione  in  

avanti.  Stesso  discorso  per  cancellare  un  elemento.  

La  catena  (o  lista)    

A   differenza   della   struttura   sequenziale   che   risultava   non   flessibile,   la   catena   permette  

l’inserimento  o  la  cancellazione  di  un  elemento  anche  se  esso  si  trova  in  mezzo  alla  lista.    

Ogni  elemento  è  formato  da  due  parti:  il   dato  che  è  il  vero  contenuto  (diciamo  l’elemento  astratto  

da  rappresentare)  e  il  puntatore  cioè  l’indirizzo  all’elemento  successivo  nella  catena.  Quindi,  per  

poter   raggiungere   un   determinato   elemento   si   partirà   dal   primo   puntatore   e   si   percorrerà   tutta   la  

lista   (grazie   a   tutti   i   puntatori)   fino   ad   arrivare   all’elemento   desiderato.   L’ultimo   elemento   della  

lista  avrà  puntatore  nullo.  

Esistono  vari  tipi  di  lista:  

lista   bidirezionale:   ogni   elemento   è   formato   da   tre   “celle”;   il   dato   e   due   puntatori,   uno  

• all’elemento  successivo  e  uno  all’elemento  precedente  

lista  circolare  (o  ciclica):  il  puntatore  dell’ultimo  elemento  non  è  nullo  bensì  punta  al  primo  

• elemento  della  lista  

lista  multipla:   ogni   elemento   ha   tre   celle;   il   dato,   il   puntatore   all’elemento   successivo   e   un  

• altro  puntatore  ad  un’altra  lista.  

  Ma   come   si   comportano   i   puntatori   quando   si  

inserisce/cancella  un  elemento  della  lista?  

Supponiamo  di  voler   inserire   un   elemento   K

 tra  due  

elementi  

H   e   H .  

i i+1

Il  puntatore  di  

H  sarà  l’indirizzo  di   K

• i

il  puntatore  di  

K

 sarà  l’indirizzo  di   H  

• i+1

  Se  invece  volessimo   cancellare   l’elemento  H  il  

i

puntatore  di  

H  sarà  l’indirizzo  di   H  

i-­‐1 i+1

Come  per  le  strutture  sequenziali  abbiamo  considerato  il  caso  in  cui  tutti  gli  elementi  richiedano  lo  

stesso   spazio   nella   memoria.   In   realtà   potrebbero   avere   occupazioni   diverse   e   allora   ogni  

elemento  non  sarebbe  più  formato  da  due  campi  ma  da  tre,  uno  in  cui  si  memorizza  appunto  la  

sua  lunghezza.  

Ricapitolando:  la  catena  risulta  più  vantaggiosa  rispetto  alla  struttura  sequenziale  soprattutto  per  

la   gestione   degli   elementi,   il   loro   inserimento   e   la   loro   cancellazione.   Ovviamente,   però,   lo  

svantaggio   è   la   richiesta   di   spazio   per   memorizzare   i   puntatori;   se,   addirittura,   il   dato   vero   e  

proprio   è   molto   piccolo   si   rischia   che   la   maggior   parte   della   memoria   sia   dovuta   proprio   agli  

indirizzi!    

  Appunti di Jessica Asietti, non fotocopiare!

Il  plesso  di  Ross    

Il  plesso  è  un  insieme  di  elementi  disposti  nella  

memoria   in   maniera   arbitraria   purché   non   si  

sovrappongano,   dove   ogni   elemento   contiene  

un   dato,   dei   puntatori   e   delle   informazioni  

(come   la   lunghezza   dell’elemento   e   quanti  

puntatori  sono  presenti).    

Queste  informazioni  prendono  il  nome  di  

formato  e  rappresentano  il  primo  byte  di  ogni  elemento:  

la  parte  più  significativa  del  byte,  chiamata  

nybble,  indica  la  lunghezza  del  dato  

• la  parte  meno  significativa  quanti  puntatori  sono  presenti.  Ogni  puntatore  è  rappresentato  

• da   due  byte.    

Abbiamo  visto  allora  tutti  e  tre  i  modi  in  cui  possono  essere  rappresentate  concretamente  delle  

strutture   astratte,   ma   esiste   una   struttura   concreta   più   indicata   piuttosto   che   un’altra   per   una  

determinata  struttura  astratta?  La  risposta  è,  ovviamente,  sì.  

Una   lista   può   essere   inserita   in   memoria   sia   tramite   struttura   sequenziale   che   tramite  

• struttura   concatenata,   la   scelta   di   una   piuttosto   che   l’altra   dipende   dalle   operazioni   che  

vengono  richieste  sui  dati.  Se  i  dati  devono  solo  essere  letti  e,  al  massimo,  modificati  può  

bastare  una  struttura  sequenziale  ma,  in  caso  si  renda  necessaria  una  cancellazione  o  un  

inserimento  successivo,  essa  non  basta  più  e  deve  essere  usata  una  catena.    

La   coda  solitamente  è  rappresentata  da  una  catena  circolare  dove  l’ultimo  elemento  tiene,  

• come   da   definizione,   l’indirizzo   della   testa   della   coda   e   un   puntatore   aggiorna  

periodicamente  l’indirizzo  del  fondo  della  coda.  

La   pila,   a   differenza   della   coda,   ha   un   elemento   di   testa   fisso   e   per   questo   può   essere  

• utilizzata   una   semplice   struttura   sequenziale   in   cui   viene   aggiornato   solo   il   puntatore  

sull’ultimo  elemento  dopo  un  inserimento  o  una  cancellazione.  

Per   le   matrici   si   usa   una   struttura   sequenziale   dove   gli   elementi   vengono   accodati   o   per  

• colonne   o   per  righe.   Se   si   parla   di   memorizzazione   per   righe   l’indirizzo   di   un   elemento   sarà  

quindi  dato  da:    

  indirizzo(A )  =  indirizzo(A )  +  (i-­‐1)*m*l  +  (j-­‐1)*l  

ij 11

  dove:   m  sono  il  numero  di  colonne  e   l

 la  dimensione  di  ogni  elemento  (quante  celle).  

Sempre   parlando   delle   matrici,   se   in   una   matrice   sono   presenti   molti   elementi   nulli   (e   la  

• matrice  prende  il  nome  di  matrice   sparsa)  allora  è  utile  organizzare  in  una  tavola  solo  gli  

elementi   diversi   da   zero   e   i   loro   indici.   Questo   può   essere   fatto,   ad   esempio,   con   una  

catena  circolare  dove  ogni  elemento  ha  una  cella  dati,  due  celle  per  i  suoi  indici,  e  due  celle  

per  i  puntatori  alla  colonna  e  riga  successive.    

  In    realtà    le    tavole    sono    memorizzate,    però,    in      strutture      sequenziali    e  la    ricerca  di    un  

  elemento  può  essere  fatta  mediante  metodi  diversi.