Teoria Mio (1) - Informazioni e Rappresentazioni PDF

**CAPITOLO 1 (L'INFORMAZIONE E LE SUE RAPPRESENTAZIONI)** **INFORMATICA** informazione + automatica Si occupa del trattamento delle informazioni mediate dei processi automatizzabili attraverso un elaboratore.\ Spazia dall'analisi del problema, alla progettazione della soluzione, fino alla sua impl...

**CAPITOLO 1 (L'INFORMAZIONE E LE SUE RAPPRESENTAZIONI)** **INFORMATICA** informazione + automatica Si occupa del trattamento delle informazioni mediate dei processi automatizzabili attraverso un elaboratore.\ Spazia dall'analisi del problema, alla progettazione della soluzione, fino alla sua implementazione in un formato compreso da un esecutore. **INFORMAZIONI** In generale, un'informazione è qualcosa che viene comunicato in una qualsiasi forma. Ricevere un'informazione, tramite un messaggio, fa diminuire o elimina un'incertezza. Per essere comprensibile essa deve essere rappresentata in un modo specifico. Un'informazione è composta da un **valore**, un **tipo** (l'insieme degli elementi entro cui bisogna scegliere il valore) e un **attributo** (significato associato all'informazione). Ad esempio: Il valore può essere rappresentato in modi diversi. Un **dato** è la rappresentazione di un valore (tramite una codifica). Un dato, da solo, non ha nessun significato, ma esso viene interpretato tramite un\'informazione. Un metadato, poi, è un tipo specifico di dato che descrive un altro dato, riportandone struttura, significato o descrizione. Un metadato può essere descritto da un altro metadato, creando metalivelli.\ \ **CODIFICA** La **codifica** è l'insieme delle regole da adottare per trasformare un'informazione in una sua rappresentazione e viceversa (la decodifica). La stessa informazione può essere codificata in modi diversi (rappresentazioni diverse) a seconda del contesto (1=uno=one=I). Un **codice** è un sistema di simboli che permette la rappresentazione dell'informazione, ed è definito dai seguenti elementi - - - - Se ho N elementi dell'alfabeto e parole codice di lunghezza L, il numero di parole codice differenti è N\^L. Se devo rappresentare M numero di parole, quindi, la lunghezza deve essere scelta in modo che N\^L \>= M. Se si vuole creare ridondanza N\^L \> M, e ci saranno delle parole codice non associate ad alcun valore. Si parla di codifica a lunghezza fissa se tutte le parole codice hanno la stessa lunghezza, altrimenti di codifica a lunghezza variabile. **RAPPRESENTAZIONE ANALOGICA E DIGITALE** Analogica: la rappresentazione varia in analogia con la grandezza reale ed è rappresentata in modo continuo. DIgitale o numerica: è discreta e rappresenta i dati solo secondo dei dati finiti (è quindi un'approssimazione di quella analogica) **SISTEMA BINARIO** La rappresentazione binaria è un tipo di rappresentazione digitale che ha un alfabeto composto da solo due simboli: 0 e 1. Tali due simboli rappresentano le unità minime di rappresentazione e memorizzazione digitale e vengono denominate **bit** da "binary digit". Sebbene questo sistema aumenta la grandezza delle parole codice, semplifica la memorizzazione delle informazioni e la trasmissione dei dati su strumenti fisici. Inoltre, minimizza gli errori perché meno soggetta alle interferenze ambientali o di altri dispositivi. Per questo, i computer usano questo tipo di rappresentazione. 1 e 0 possono rappresentare ad esempio acceso-spento, aperto-chiuso, 5volt-0 volt..... Essi usano parole codice lunghe multipli di 8 (8 bit=1 **byte**, sequenze di bit più lunghe di un byte si dicono **word**). Con otto bit si rappresentano 2\^8 (256) valori diversi. Nel caso in cui un solo byte non fosse sufficiente per rappresentare i K valori dell'informazione, allora si individua il numero b di byte tale che 2 (b\*8) \>= K.  Un computer usa una rappresentazione a lunghezza fissa: questo differenzia i sistemi a 16, 32 o 64 byte. **CONVERGENZA DIGITALE** Negli ultimi anni c'è stata una forte migrazione verso sistemi digitali, con un fenomeno che è stato definito come *convergenza digitale:* - - - Grazie al digitale, che rappresenta ogni mezzo di comunicazione (testo, audio, video, immagini...) con delle semplici sequenze di bit, è possibile combinare diversi codici espressivi. Un **multimedia**, è proprio formato da due o più di questi mezzi di comunicazione. Il *medium* è il mezzo con cui avviene la trasmissione. **DA ANALOGICO A DIGITALE** La trasformazione di testi, audio, immagini, video in oggetti digitale avviene attraverso dispositivi capaci di effettuare la conversione analogico-digitale, detti **ADC** (Analogue to Digital Converter). Questa trasformazione avviene con due processi distinti e effettuati uno dopo l'altro: - - Con campionamento e quantizzazione viene introdotta un'approssimazione della realtà, e effettuare approssimazioni molto precise può arrivare a costare troppo in termini di grandezza e di bit necessari. Per questo è necessario raggiungere un compronesso tra qualità e velocità di trasmissione. **COMPRESSIONE** Per risolvere i problemi connessi alle dimensioni elevate sono stati introdotti nel tempo quelli che si chiamano processi di **compressione**, che riducono lo spazio occupato o mediante la diminuzione del numero di bit necessari per codificare una singola informazione (*compressione entropica*) o la diminuzione del numero di informazioni da memorizzare (*compressione differenziale o semantica*). La compressione può conservare integralmente o no il contenuto della rappresentazione originale secondo due tecniche principali. - - - - - - - - - **CODIFICA DEL TESTO** Il testo è uno degli oggetti digitali più diffuso nel mondo informatico. Molte sono le applicazioni che generano e manipolano i cosiddetti documenti elettronici. Un testo digitale è una stringa di simboli ad ognuno dei quali viene associato un codice binario secondo un prefissato standard.  Alla fine degli anni sessanta l\'ente americano di standardizzazione ANSI (*American National Standards Institute*) decise di fissare un alfabeto che consentisse a tutti i calcolatori, anche di produttori diversi, di poter comunicare tra loro. I simboli dell'alfabeto vennero elencati in una tabella per codificare vari tipi di caratteri: alfabetici, numerici, di punteggiatura, simbolici, e anche alcuni codici da usare come controllo della comunicazione tra una macchina e l\'altra (per esempio, per segnalare l'inizio o la fine di una trasmissione) Il trasferimento di un insieme di informazioni da un calcolatore all\'altro su una rete poteva così essere effettuato attraverso un linguaggio comune, costituito da tale forma di codifica. **ASCII** La tabella fu chiamata **ASCII**, ossia *American Standard Code for Information Interchange.* Il codice ASCII divide i caratteri con un senso logico, ed è stato definito per rendere comoda l'elaborazione di questi caratteri. Ad esempio le lettere minuscole distano da quelle maiuscole esattamente 32 posizioni, o basta controllare se i due bit più significativi sono zero o no per capire se il carattere è di controllo o va stampato. Il suo limite è che è stato concepito solo per la lingua inglese. Inizialmente aveva 7 bit (128 caratteri) per i caratteri e un bit di parità, poi venne esteso a 8 bit (256 caratteri) sotto il nome di extended ASCII, in cui i primi 128 caratteri erano quelli dell'ASCII standard e poi ogni nazione sceglieva i successivi 128 (quindi ne esistono più versioni). Quando internet diventa globalmente diffuso neanche 8 bit bastarono. **UNICODE** Uno standard che si propone di affrontare il problema del multilinguismo è Unicode *(Universal Encoding).* Si basa sulla codifica ASCII, ma va oltre la limitazione dell\'alfabeto latino potendo codificare caratteri scritti in tutte le lingue del mondo. Originariamente si basava su una codifica a 16 bit che dava la possibilità di codificare più di 65 mila caratteri, poi, per rappresentare qualunque carattere, compresi quelli cinesi e tutte le loro varianti, è stato proposto lo standard Unicode (ISO-10646) che utilizza l\'UTF (Unicode Transformation Format) a 8, 16 o 32 bit. ù L'Unicode è un sistema di convenzioni che assegna ad ogni carattere un numero univoco, ma non è una vera e propria codifica. Per la codifica vera e propria si usa proprio l'UTF. L\'UTF-8 si basa su parole di 8 bit (1 byte) per la codifica dei caratteri; ed usa da 1 a 4 byte per carattere: i primi 128 valori, che iniziano col bit 0, utilizzano 1 byte per carattere e corrispondono all\'ASCII, i successivi 1920 (dal 128 al 2047) utilizzano 2 bytes per codificare greco, cirillico, copto, armeno, ebraico, arabo. Per gli altri caratteri si usano 3 o 4 bytes. UTF-16 utilizza parole di almeno 16 bit per codificare i caratteri, viene utilizzato da Java, ed è la rappresentazione interna usata da Windows e Mac OS-X. *NB: 8 o 16 bit sono i bit con cui sono rappresentati i caratteri più frequenti e quelli da cui parte la rappresentazione, che però è flessibile e può arrivare fino a 4 byte.* **CODIFICA DELLE IMMAGINI** Nel mondo reale le immagini sono informazioni continue, caratterizzate da uno spazio e dei colori. Per essere rappresentate da un calcolatore allora deve essere resa discreta. Nel processo di **campionamento** si divide l'immagine in righe orizzontali e verticali, creando dei quadretti che prendono il nome di pixel (picture element). Ovviamente, più la dimensione dei pixel è piccola (e quindi su una stessa immagine grande uguale sono in numero maggiore) minore è l'approssimazione dell'immagine reale. La **risoluzione** è il numero di pixel per pollice (*DPI- Dot Per Inch*). La dimensione dell'immagine viene anche spesso espressa separando il numero di pixel orizzontali e verticali, per esempio 600x800 pixel.  A ogni pixel dell'immagine vengono associati i bit che misurano caratteristiche di colore. Nel processo di **quantizzazione** è necessario quindi stabilire quante sono le sfumature di colore possibili, e quindi in altre parole quanto sono lunghe le stringhe di bit che rappresentano un singolo pixel. La rappresentazione di un\'immagine mediante la codifica dei pixel è chiamata **codifica bitmap o raster**. Le immagini possono essere codificate in bianco e nero, a scala di grigi o a colori. La colorimetria studia i colori e spiega che ogni colore può essere ottenuto tramite la combinazione di tre colori detti primari: rosso, verde. blu. Per la codifica informatica si usa infatti il modello **RGB** *(red, green, blue).* La codifica avviene a 24 bit, assegnando un byte al rosso, uno al verde e uno al blu, con valori più o meno elevati in base a quanto il colore da rappresentare è vicino ad essi. Con questo sistema si possono rappresentare circa 16 milioni di colori diversi. Visto che difficilmente questi colori saranno tutti presenti nella stessa immagine, generalmente si sceglie una palette (chiamata anche **CLUT**, Color Look-Up table) di colori (di 8 bit in genere) per quell'immagine specifica. Tra i formati più comuni: - - - - In diminuzione: - -  **IMMAGINI VETTORIALI** Quando le immagini hanno caratteristiche geometriche ben definite, come nel disegno tecnico con CAD, il disegno può essere scomposto in elementi geometrici di base (punti, linee, archi...), e si preferisce descrivere l'immagine in termini matematici invece che in termini di pixel. Questo tipo di codifica si definisce **vettoriale** e avviene con parametri di posizione (ad esempio coordinate per i punti) e vere e proprie formule matematiche (equazione di una retta ad esempio). Tra i vantaggi vi è il fatto che l'immagine può essere variata di dimensione senza subire distorsioni o sgranarsi (la risoluzione è quindi indipendente dal dispositivo che stiamo usando), e può essere modificata ad alto livello. Non è adatta per visualizzare immagini reali come foto e bisogna avere il programma di generazione dell\'immagine vettoriale per far sì che essa venga visualizzata. Tra i formati grafici più diffusi, vanno ricordati: - - - **IMMAGINI IN MOVIMENTO** Per rappresentare i video si usa un limite dell'occhio umano che il cinema ha sempre sfruttato fin dalla sua nascita: la retina mantiene per alcuni millisecondi l\'immagine che ha appena visto prima che essa svanisca. Quindi se si proiettano un certo numero di immagini al secondo, non ci accorgiamo che sono in sequenza discreta ma sembrano come un filmato continuo Un **video** è quindi una sequenza di immagini disposte in successione temporale. Questa serie di immagini sono dette **frame**, che variano velocemente a intervalli stabiliti (**fps**, **frame-rate**). Il peso del video dipende dalla risoluzione e la codifica a colori di ogni singola immagine, così, ad esempio, un video con frame di 320x240 pixel e 256 colori richiede: Per questo si usano tecniche di compressione. Lo standard MPEG, ad esempio, non conversa tutti i pixel di ogni immagine, ma solo le differenze tra l'immagine corrente e quella successiva (sfruttando il fatto che la differenza tra frame consecutivi è minima) **CODIFICA DEL SUONO** Il suono è un segnale analogico che consiste in delle vibrazioni che formano un\'onda in funzione del tempo. L'altezza di questa onda è detta ampiezza (oggetto della quantizzazione) e la distanza tra due onde è detto periodo (oggetto del campionamento). Quindi anche il suono deve essere campionato e quantizzato per poter essere digitalizzato (anche in questo caso se si sceglie di operare con pochi bit e a intervalli molto grandi, l'audio digitalizzato sarà diverso da quello originale). Di solito si discretizza il valore nell'ordine delle decine di **KHz** (frequenza: numero di oscillazioni che si ripetono in un\'unità di tempo) perché l'orecchio umano percepisce fedelmente il suono originale se il suo campionamento è non inferiore a 30KHz. La frequenza di campionamento dovrebbe essere legata alla frequenza dell'onda iniziale. La regola di **Nyquist** dice che la frequenza di campionamento deve essere almeno il doppio della frequenza massima del segnale analogico iniziale. L'uomo può percepire suoni fino a 20 KHz, quindi, secondo questa regola, un campionamento di 40 KHz è spesso sufficiente.  La quantizzazione invece comporta sicuramente una perdita di qualità, creando quello che si chiama rumore di quantizzazione, che ovviamente dipende dal numero di bit che scegliamo di usare. Anche con gli audio si usano tecniche di compressione, come il formato MP3. **RAPPRESENTAZIONE DEI NUMERI** Nei calcolatori digitali si possono rappresentare solo un numero finito di valori, e ci si deve limitare a rappresentare un intervallo specifico \[min,max\] degli infiniti numeri esistenti. Questo intervallo dipende dal numero di byte usati dal sistema. In questa rappresentazione a precisione finita può capitare che alcune operazioni causino errori se il risultato non appartiene all'insieme dei numeri rappresentabili. Si chiama **overflow** la condizione che si verifica quando il risultato dell'operazione è maggiore del più grande valore rappresentabile (max) o minore del più piccolo (min). Un altro caso notevole si verifica quando il risultato dell'operazione non è compreso nell'insieme dei valori rappresentabili, pur essendo compreso in \[min, max\]. Si parla di **underflow**, se per la precisione della rappresentazione un numero diverso da zero sarebbe approssimato come zero.  Anche l'algebra dei numeri a precisione finita è diversa da quella convenzionale poiché alcune delle proprietà matematiche di base: - - non sempre vengono rispettate, in base all'ordine con cui le operazioni vengono eseguite L'algebra dei numeri a precisione finita deve essere gestita applicando i criteri di **periodicità**: valori non compresi nell'intervallo di numerazione vengono fatti ricadere in esso (con una sorta di effetto pac-man: vedi orologio o periodicità dei gradi). I valori esterni all'intervallo di definizione vengono ricondotti ad esso prendendo il resto della divisione dei valori per il periodo.  Il concetto può essere spiegato con questa sveglia: dove con le sottrazioni si va in senso antiorario e con le addizioni in senso orario Si noti che il numero più grande è susseguito da quello più piccolo e viceversa. Questo fenomeno è noto come **wrap around.** **SISTEMI DI NUMERAZIONE** I sistemi di numerazione sono un insieme di simboli (cifre) e regole che assegnano ad ogni sequenza di cifre uno ed un solo valore numerico. Vengono classificati in sistemi posizionali e non posizionali, in base al modo in cui i valori numerici sono rappresentati e interpretati. - - Una **stringa** è una sequenza di caratteri (cifre/simboli/bit) *'ci-1 ci-2 \... c1 c0'* che rappresentano dei **numeri interi** in formato testuale. Al simbolo *ci* viene associato un diverso peso in base alla sua posizione i-esima occupata nella stringa. Il peso dipende anche dalla base (o radice) di numerazione. Il bit più a destra è quello meno significativo (posizione o peso 0, detto anche LSB da **Least Significant Bit**), mentre quello più a sinistra è quello più significativo ( detto anche MSB da **Most Significant Bit**). In un sistema di numerazione in base *b*, servono *b* simboli per rappresentare i diversi valori delle cifre comprese tra *0* e *b-1*. Ad esempio:  Nei sistemi di numerazione posizionale, non solo è possibile rappresentare numeri interi, ma anche i **numeri reali**, che includono una parte frazionaria. La rappresentazione dei numeri reali segue la stessa logica dei numeri interi per quanto riguarda la posizione delle cifre, con l\'aggiunta di un separatore, come il punto o la virgola, per distinguere la parte intera da quella frazionaria. Sebbene la parte intera venga moltiplicata per la base positiva della sua posizione, la parte frazionaria viene moltiplicata con potenze negative. Ad esempio:  **CAMBIO DI BASE** NB: iniziamo col dire che nel passaggio da una base all'altra alcune proprietà dei numeri si perdono, ad esempio un risultato di una divisione può essere periodico nella base dieci ma non è detto che lo sia in un'altra base. PASSAGGIO DA QUALSIASI BASE ALLA BASE 10 La conversione nella base 10 da qualsiasi base b, avviene calcolando la sommatoria dei prodotti delle cifre per il peso della propria posizione: L\'impiego nella base 2 di un minor numero simboli rispetto al sistema decimale (2 contro 10) implica che lo stesso valore abbia una rappresentazione più lunga in notazione binaria che non in quella decimale CONVERSIONE DA DECIMALE A QUALSIASI ALTRA BASE Preso il numero *d* in base 10 per convertirlo in una base *b* bisogna dividere *d* per *b* scrivendo il resto della divisione, se il quoziente (ovvero il risultato) è strettamente maggiore di 0, il procedimento continua dividendolo ancora una volta per la base e scrivendo il resto, se il quoziente è 0 scriveremo tutte le cifre ottenute come resto in una sequenza inversa.   CONVERSIONE DELLA PARTE FRAZIONARIA Per la conversione della parte frazionaria si procede al contrario moltiplicando per 2 (o per un'altra base visto che questa conversione non è specifica per il binario). Si conserva la parte intera del prodotto e si continua a moltiplicare per 2 solo la parte frazionaria fino a quando non si verifica una delle seguenti condizioni: - - - Se una di queste condizioni si verifica, la conversione binaria sono le cifre intere prese nell'ordine in cui sono state calcolate  CONVERSIONE CON ALTRE BASI Spesso capita di dover rappresentare valori troppo grandi che richiederebbero parole codice in binario lunghissime e difficili da leggere e interpretare. Per questo spesso capita di usare altre due notazioni: quella ottale e quella esadecimale. Quella ottale è usata ad esempio per i permessi UNIX Quella esadecimale è usata ad esempio per i colori RGB  La conversione tra binario e queste due basi (e viceversa) è immediata: una cifra in ottale è rappresentabile esattamente con tre cifre binarie, il cui valore è uguale proprio alla cifra rappresentata, mentre una cifra esadecimale è rappresentata con quattro cifre binarie. Si parte dal bit meno significativo e si raggruppano le cifre a tre a tre (ottale) o a quattro a quattro (esadecimale).  **OPERAZIONI ARITMETICHE BINARIE** Sui numeri binari si applicano operazioni aritmetiche del tutto analoghe ai numeri in base 10. - - - - **RAPPRESENTAZIONE DEI NUMERI RELATIVI** Per i numeri relativi, ovvero tutti i numeri interi, positivi e negativi (incluso lo 0), si utilizzano diverse rappresentazioni, con lo scopo di creare circuiti in grado di fare operazioni aritmetiche efficientemente. SEGNO E MODULO Poiché il segno assume due soli valori ("+" oppure "--"), allora lo si può codificare con un singolo bit, utilizzando il bit più significativo (0 positivo 1 negativo). Quindi, con N bit, N -- 1 di essi vengono attribuiti alla rappresentazione del valore assoluto del numero, e il bit più a sinistra (MSB) alla rappresentazione del segno. Tale rappresentazione permette di codificare i numeri appartenenti all'intervallo  con 2\^(l - 1) valori positivi e altrettanti negativi: per un totale di 2l valori diversi. Ad esempio, Per l=8 sono rappresentabili tutti i numeri relativi appartenenti all'intervallo \[-127,127\].\ \ Il problema di questa rappresentazione è che sono presenti due configurazioni dello zero, lo "0" positivo (00000000) e lo "0" negativo (10000000), quindi le operazioni di somma e sottrazione devono essere corrette nell'attraversamento dello zero. C'è bisogno, inoltre, di algoritmi diversi per effettuare somme e sottrazioni in base al segno degli operandi. Basta provare a sommare uno a tutte le cifre per capire che i numeri non sono sequenziali e l'operazione non è quindi immediata e facile meccanicamente. COMPLEMENTO A 2 Il grande vantaggio è che può essere usato lo stesso algoritmo per la somma e per la sottrazione senza differenza in base al segno degli operandi, e possono essere quindi assegnate allo stesso circuito elettronico. Le configurazioni che hanno il bit più significativo uguale a zero, cioè quelle comprese nell'intervallo \[0, 2\^(l - 1) - 1\], rappresentano se stesse (numeri positivi) codificati in una normale rappresentazione di numeri naturali. Mentre le configurazioni col bit più significativo uguale a uno, cioè quelle rientranti nell'intervallo \[2\^(l - 1), 2\^l - 1\], rappresentano i numeri negativi che si ottengono traslando a sinistra l'intervallo di 2\^l, cioè l'intervallo \[-2\^(l - 1), -1\]  Nella rappresentazione per complemento a 2, i valori rappresentati sono compresi nell'intervallo Quindi, l'intervallo non è simmetrico (c'è un numero in più per la parte positiva perché la parte negativa rappresenta anche lo 0), è c'è una sola rappresentazione dello 0. Ad esempio ad 8 bit i numeri vanno da \[-128,127\] COME SI CALCOLA Il complemento a due x" di un valore negativo x si calcola sottraendo il valore assoluto di x da 2\^l.  Ad esempio  Se si definisce il complemento alla base b di una cifra c come *c' = (b -1) - c* Quindi, il complemento a 2 del valore si ottiene complementando alla base tutte le cifre del valore assoluto del numero x e sommando poi 1 al valore ottenuto. Se si ha una sequenza di l bit che rappresenta un numero intero con segno, con i numeri negativi rappresentati in complemento a 2, allora, per ottenere il numero rappresentato, si procede nel seguente modo: - - - Un'altra interpretazione del complemento a 2 è:  COMPLEMENTO DIMINUITO Il complemento a uno (x') del numero x si differenzia dal complemento a 2 (x") dello stesso numero per una unità *x' = x" -- 1* Quindi, il complemento a 1 di un numero si ottiene semplicemente complementando tutte le cifre del numero. Era usato in passato ma è stato abbandonato perché, come la rappresentazione in segno e modulo, ha una doppia rappresentazione dello 0 ed è simmetrico. RAPPRESENTAZIONE PER ECCESSO I numeri negativi si determinano come somma di se stessi con 2(l -1) dove l è il numero di bit utilizzati.  Il sistema è identico al complemento a due con il bit di segno invertito: In pratica i numeri compresi tra \[-2(l - 1), 2(l - 1)-1\] sono mappati tra \[0, 2(l -1)\]. In tale rappresentazione, il numero binario che rappresenta 2(l -1) sarà associato allo zero, mentre i valori minori di 2(l - 1) ai numeri negativi e quelli maggiori a quelli positivi.  RAPPRESENTAZIONE IN ECCESSO K (OFFSET) CONFRONTO DELLE DIVERSE RAPPRESENTAZIONI  QUALI SI USANO? Le rappresentazioni in complemento a due ed eccesso sono le più efficienti per svolgere operazioni in aritmetica binaria poiché permettono di trattare la sottrazione tra numeri come una somma tra numeri di segno opposto. E' così possibile costruire circuiti che fanno solo addizioni (si sfrutta l\'overflow, quindi c'è bisogno di sistemi a numero di bit finiti).  **RAPPRESENTAZIONE DEI NUMERI REALI** Tale rappresentazione in binario può essere effettuata a virgola fissa o mobile. Nel primo caso si dedica una parte prestabilita delle cifre alla parte intera e le altre alla parte frazionaria (la posizione della virgola è fissata su un bit prestabilito): + XXX.YY. Nel secondo caso si dedica alcune cifre a rappresentare un esponente della base che indica l'ordine di grandezza del numero rappresentato. In virgola mobile si sfrutta la notazione scientifica dei numeri reali: L\'esponente determina l'ampiezza dell\'intervallo di valori preso in considerazione (quanto grande e quanto piccolo può essere il numero), mentre il numero di cifre della mantissa determina la precisione del numero (ossia con quante cifre significative sarà rappresentato).  Questa notazione viene usata per diversi motivi: - - - - La rappresentazione binaria dei numeri reali ha dei limiti poiché deve usare un numero finito di cifre per la mantissa e l'esponente, portando a problemi di approssimazione (si noti che anche in un intervallo piccolo i numeri reali sono di numero infinito). I valori rappresentabili in binario appartengono invece ad un sottoinsieme che contiene un numero finito di valori reali (ognuno dei quali rappresenta un intervallo del continuo). In altri termini, diviso l\'insieme dei numeri reali in intervalli di fissata dimensione, si ha che ogni x appartenente all\'intervallo \[X~i~ ,X~i+1~\[ sarà approssimato a X~i~ o X~i+1~ ​, a seconda di quanto è vicino. Per valutare gli effetti delle approssimazioni e gli errori che ne possono derivare, esiste una disciplina chiamata **calcolo numerico**, che ricerca algoritmi capaci di limitare gli errori legati a queste approssimazioni. In concreto i numeri reali rappresentabili in binario godono della seguente proprietà:  Il valore ε dipende dalla rappresentazione finita (il numero finito di cifre) utilizzata per i numeri reali. Per esempio disponendo di una calcolatrice con aritmetica a quattro cifre decimali, che applica le note regole di arrotondamento sull\'ultima cifra, si ha un errore massimo sull\'ultima cifra di Più in generale se -h è il peso della cifra meno significativa,l'errore massimo che si commette è: I numeri reali rappresentabili sono definiti in un insieme limitato con estremi predefiniti \[-minreal, maxreal\] - minreal o più grandi di maxreal - delle approssimazioni, viene confuso con lo zero. RAPPRESENTAZIONE NORMALIZZATA La rappresentazione in virgola mobile, fissata la base, consente di esprimere lo stesso valore con infinite coppie (mantissa, esponente). Ad esempio: 48 × 10\^2 è uguale a 4800 × 10\^0, ma anche a 4,8 × 10\^3. È allora possibile scegliere, tra le infinite coppie quella che preserva il maggior numero di cifre significative con **la normalizzazione della mantissa**. Nei decimali, per i numeri minori di uno quando la cifra più a sinistra è uno zero, si traslano (shift) verso sinistra le cifre diverse da zero (significative) decrementando l\'esponente di tante cifre quante sono le posizioni scalate. Per i numeri maggiori di uno la normalizzazione avviene spostando la virgola a sinistra e sommando l'esponente di tante cifre quanto sono quelle spostate finché il numero non diventa minore di 1. Il nuovo numero prende il nome di numero normalizzato e la mantissa di mantissa normalizzata. In generale la forma normalizzata della mantissa obbliga che la prima cifra sia diversa da zero e che la parte intera sia un numero minore della base.  N.B: Gli intervalli non hanno tutti la stessa ampiezza: man mano che ci si avvicina alla condizione di overflow gli intervalli si fanno sempre più ampi, mentre intorno alla condizione di underflow non solo si addensano ma diventano sempre più piccoli. E' diverso dire che il numero cambia di 1 su 10\^99 o di uno su 10\^(1). OPERAZIONI IN VIRGOLA MOBILE Con la rappresentazione in virgola mobile le operazioni non solo si complicano ma possono generare errori di approssimazione. Per esempio la somma e la sottrazione richiedono l'allineamento degli esponenti: Mentre per le divisioni e moltiplicazioni servono operazioni separate per mantisse ed esponenti:  CENNI STORICI Nel 1980, i principali costruttori di elaboratori elettronici producevano calcolatori che utilizzavano i numeri reali (Float), ognuno con un proprio formato numerico e con proprie convenzioni di calcolo. Nel 1985 divenne operativo lo standard IEEE 754.   per gli esercizi vedi questo video: [[https://youtu.be/qi2F9JsWrGo?feature=shared]](https://youtu.be/qi2F9JsWrGo?feature=shared) **ALGEBRA DI BOOLE (SECONDO UN PUNTO DI VISTA ASTRATTO)** I circuiti elettronici preposti alla memorizzazione dei bit e alla loro elaborazione sono detti circuiti di commutazione (o logici). Le reti logiche sono formate da quelli che si chiamano *n-poli,* singoli circuiti logici caratterizzati dal fatto che in ingresso e in uscita si possono assumere solo due valori (presenza o assenza di un impulso), e possono quindi essere analizzati a livello logico per capirne il funzionamento senza scendere nei dettagli hardware, analizzando solo le corrispondenze tra segnale in entrata e uscita e sulle funzioni che legano questi segnali. Generalmente quest'analisi logica (o cioè del modo in cui sono collegati gli n-poli e come devono funzionare) viene fatta usando l'algebra di Boole, che fu introdotta da George Boole nel 1854 come strumento per la soluzione matematica in forma algebrica di problemi di logica (essa formalizza ed estende la logica aristotelica, ancora valida fino a quel momento). Il suo uso pratico nelle reti binarie di commutazione si deve in realtà al suo allievo Claude Shannon. L'algebra di Boole permette così di stabilire una corrispondenza biunivoca fra espressioni algebriche e i cicuti di un calcolatore. I principali **operatori logici** introdotti dall'algebra di boole sono: - - - - Si analizza il comportamento di questi operatori su due proposizioni iniziali tramite quelle che si chiamano tabelle di verità. Spesso è anche utile confrontare coppie di valori, per questo si introducono gli **operatori di confronto** (o di relazione), come l'uguale il maggiore o il minore. Questi non sono veri e propri operatori logici ma il loro risultato può essere usato come argomento di operatori logici, visto che restituiscono vero o falso. Ad esempio  Quindi, la verità di un predicato che contiene operatori logici può essere facilmente calcolata a partire dalla verità dei predicati componenti e dalle proprietà degli operatori che li uniscono, e spesso può essere ridotta a una più conveniente con un numero minore di operazioni confrontandone l'equivalenza. **ALGEBRA DI BOOLE (SECONDO UN PUNTO DI VISTA MATEMATICO)** Come tutte le algebre, anche quella di Boole si sviluppa partendo da un insieme di supporto (o di sostegno) *k* su cui sono definite le operazioni che associano a due elementi dell'insieme un altro elemento dell'insieme stesso. Queste due operazioni sono la somma (+) e il prodotto (x). Un **Algebra astratta** è definita quindi come formata dalla terna \. Un'algebra su cui vale la sestupla degli elementi **\** è detta poi **reticolo**, su cui valgono anche le relazioni d'ordinamento che godono della proprietà riflessiva (x ≤ x), antisimmetrica (x ≤ y e y ≤ x =\> x = y) e transitiva (x ≤ y e y ≤ z =\> x ≤ z). L'algebra di Boole è infine descritta come *"un reticolo distributivo, dotato di minimo e massimo assoluti e complementato".* Valgono 14 proprietà (le prime 4 per un reticolo generico e le restanti 3 specifiche per l'algebra di Boole:  Tutti gli assiomi dell'algebra di Boole sono caratterizzati dal **principio di dualità:** da una qualsiasi di queste identità (le proprietà sopra elencate) se ne ricava un'altra valida sostituendo il + con il x e lo 0 con l'1 (e viceversa per entrambi i fatti). Possono essere elencate poi altre caratteristiche dell'algebra di boole a partire da questi postulati. 1. 2.  3. 4.  5. **LE DIVERSE ALGEBRE DI BOOLE** La definizione di AdB come reticolo non specifica quale sia K e come siano definite le operazioni, sono così possibili diversi modelli dell'algebra di Boole. - - - - 1. 2. 3. 4. **CAPITOLO 2 (IL MODELLO DI ESECUTORE)** **PROCESSO E PROCESSORE** Come tutti gli esecutori di ordini anche il computer può compiere solo quei lavori che possono essere specificati mediante operazioni che è in grado di comprendere e mettere in pratica. L\'algoritmo è la descrizione di un compito da portare a termine, e la sua esecuzione da parte di un esecutore si traduce in una successione di azioni che vengono effettuate nel tempo. Si definisce **processo** il lavoro svolto eseguendo l\'algoritmo e **processore** il suo esecutore. Il processo non è altro che l\'elenco delle azioni effettivamente svolte dall'esecutore che sta eseguendo l'algoritmo come si susseguono nel tempo.  **IL MODELLO DI VON-NEUMANN** Per comprendere i motivi che rendono un computer diverso dalle altre macchine si introduce uno schema di riferimento nel quale sono messi in evidenza tre blocchi. Questo è uno schema di principio ed è rappresentativo dei tradizionali computer, esso prende il nome di modello di Von-Neumann, dal primo ricercatore che la propose nel 1945. La *Central Processing Unit* **(CPU)** coordina l'esecuzione delle operazioni fondamentali; La **memoria** contiene sia l'algoritmo/programma che descrive le operazioni da eseguire sia i dati su cui il programma il programma stesso opera; I **dispositivi di input e output** sono le interfacce della CPU nei confronti del mondo esterno, rispettivamente sono le unità che consente l'inserimento di algoritmo e dati in memoria e quella che presenta i risultati dell'attività della CPU. Queste unità fondamentali formano l'hardware, ossia l'insieme di tutti i componenti elettronici, elettrici e meccanici che costituiscono un sistema di elaborazione. Il prototipo di Von-Neumann era basato sul concetto di "programma memorizzato" (**stored procedure**): la macchina memorizza nella propria memoria non solo i dati su cui lavorare ma anche le istruzioni per il suo funzionamento. Da questa caratteristica deriva una grande flessibilità operativa, macchine nate per fare calcoli scientifici possono essere usate per risolvere problemi completamente diversi. **FUNZIONAMENTO INTERNO** Le caratteristiche fondamentali di tale sistema sono: 1. 2. 3. 4. 1\) Anche se internamente molto complesso, nelle sue linee generali il funzionamento di un qualsiasi computer si può ricondurre a questo modello, che alla fine non è dissimile ad uno antropomorfo con un essere umano che risolve dei problemi. Il cervello umano nel modello è la CPU (il "cervello" della macchina), i fogli di carta sono la memoria centrale e una calcolatrice è l'A.L.U. (arithmetic logic unit), ovvero la componente della CPU che effettua tutte le operazioni di calcolo logico e aritmetico, inoltre ci sono i dispositivi di input e output che provvedono alle trasformazioni necessarie a rendere comprensibili le informazioni sia alla CPU che agli utenti esterni al computer, quindi alla trasformazione della rappresentazione delle informazioni dal linguaggio naturale al linguaggio binario e viceversa. Nella maggior parte delle applicazioni pratiche è l'uomo l'utente del computer, ma esistono applicazioni nelle quali il computer scambia informazioni con altri dispositivi, come sensori, che rappresentano le informazioni sotto forma di segnali elettrici. 2\) Dal punto di vista dell'affidabilità gli unici errori commessi dal computer possono essere di motivo hardware che sono facilmente riscontrabili, mentra la velocità di esecuzione si aggira a milioni di istruzioni al secondo svolte dalla CPU. Non vengono commessi errori di concetto o di algoritmo, visto che il computer si limita a eseguire tutte le istruzioni che gli vengono date. 3\) Per memorizzazione si intende il compito della memoria di conservare informazioni per la CPU (la memorizzazione può essere temporanea, permanente o definitiva). La capacità è la misura del numero di informazioni immagazzinabili nella memoria e si misura in numero di byte. 4\) Per quanto riguarda il costo dei computer si può sicuramente considerare che esso è basso se paragonato ai tempi di lavoro necessari affinché esseri umani portino a termine gli stessi compiti. **MEMORIE** La memoria di un calcolatore può essere vista come un insieme di contenitori fisici di informazioni, anche detti locazioni o **registri,** di dimensioni finite o fissate a cui si può far riferimento tramite la posizione occupata nell'insieme ovvero **l'indirizzo** di memoria. La dimensione di un registro si misura in numero di bit. I registri per i singoli bit possono essere fatti in diversi modi: - - - In ogni caso il dispositivo di lettura deve essere in grado di associare allo stato del bit il valore 1 (ad esempio tensione a 5 volt, polo positivo, assenza di buco) o il valore 0 (tensione a 0 volt, polo negativo, presenza di buco). **Operazioni sulla memoria** Le operazioni consentite su un registro sono di **lettura** *(load)* e **scrittura** *(store)***:** - - Quindi, la memoria è un sistema che assolve al compito di conservare il dato, depositandolo in un registro nel caso di operazione di scrittura, e di fornire il dato conservato in un registro, per l'operazione di lettura. Queste operazioni vengono fatte con la CPU che indica preventivamente l'indirizzo della locazione di memoria interessata dall'operazione e la memoria che decodifica tale indirizzo abilitando solo il registro a esso corrispondente, affinché: - - Le operazioni di load e store richiedono **tempi di attuazione** che dipendono dalle tecnologie usate per la costruzione delle memorie e dalle modalità di accesso: - - Le memorie devono mostrare tempi di accesso adeguati alla capacità della CPU, nel senso che non devono introdurre ritardi mentre essa trasferisce dati. Per tale motivo gli sforzi tecnologici sono rivolti alla costruzione di memorie con tempi di accesso il più possibile ridotti, anche se tale parametro contrasta quello del costo delle componenti. **Diversi tipi di memorie** Alcune memorie vengono realizzate in modo tale che sia possibile una sola scrittura iniziale di informazioni. Tali memorie vengono chiamate "sola lettura" oppure **ROM** *(read only memory).* Altre memorie vengono dette RWM (read and write memory), che si dividono in base al modo in cui si accede ai registri: - - Infine si è soliti distinguere le memorie in base alla capacità di conservare le informazioni, anche quando i sistemi che le contengono non sono alimentati. Si dicono **volatili** le memorie che perdono le informazioni in esse registrate quando il sistema viene spento, sono di contro **permanenti** gli altri tipi di memoria. Un esempio di memoria volatili sono le memorie elettroniche mentre un esempio di memorie permanenti sono le memorie di tipo magnetico ottico e tutti i tipi di ROM.. **Memorie di massa** Lo Schema iniziale di Von neumann è stato nel tempo modificato per affiancare alla memoria Centrale (che interagisce direttamente con la cpu) delle unità di memoria ausiliarie, caratterizzate da una elevata capacità, dette **memorie di massa**.  La differenza fondamentale tra la memoria centrale e quella di massa dal punto di vista funzionale risiede nel fatto che: - - Un'altra differenza è la maggiore velocità della memoria centrale nella gestione dei dati rispetto alle memorie di massa. Le memorie di massa hanno tempi di accesso maggiori dovuti alle tecnologie impiegate per realizzarle. Per ovviare alla differenza di velocità si impiegano tecniche che prevedono che la memoria centrale non solo contenga dati ed istruzioni, ma anche aree di accumulo dei dati in transito verso i dispositivi esterni. Tali aree vengono dette **buffer.** Così che la cpu non debba aspettare l'arrivo dei dati ma possa prelevarli dal buffer di input, e una volta finite le operazioni non debba aspettare il dispositivo di output ma possa continuare con la successiva operazione conservando il risultato della vecchia in un buffer di output. Così che possono collaborare dispositivi di velocità diversa senza creare grandi colli di bottiglia. Esistono diverse memorie di massa che si differiscono per composizione, velocità e capacità:  **LA CPU** Il cervello di un elaboratore, la CPU (*Central Processing Unit)* è composto da tre parti fondamentali: l'unità di controllo (**Control Unit (CU)**), l'unità logico-aritmetica (**Arithmetic Logic Unit (ALU)**), e una serie di registri detti "interni" per distinguerli da quelli della memoria centrale e che variano da modello a modello di processore in funzione della sua architettura. **Zoom sui REGISTRI**  **Processori nella realtà** **Control Unit** E' l\'organo che interpreta le singole istruzioni e attiva tutti i meccanismi necessari al loro implementamento. In particolare la CU ha il compito di: - - - Al termine dell\'esecuzione di una istruzione la CU procede al prelievo dalla memoria della successiva istruzione secondo un ordine rigidamente sequenziale: l'esecuzione di una istruzione può avere inizio solo se la precedente è stata portata a termine. Perché l'intero sistema possa avviarsi, la CU deve essere informata del registro che contiene la prima istruzione, in una fase che è detta di boot, e poi esegue ininterrottamente quello che si chiama ciclo del processore fino al suo spegnimento. **Ciclo del processore**   **Arithmetic Logic Unit** Esegue le operazioni aritmetiche, di controllo o bitwise sui dati della memoria centrale o dei registri interni. L'esito dei suoi calcoli viene segnalato da appositi bit in un registro chiamato Status Register che contiene il **Condition Code**. A seconda dei processori L'ALU può essere molto complessa, e quindi nei sistemi moderni essa è affiancata da processori dedicati alle operazioni sui numeri in virgola mobile, detti *coprocessori matematici*. Inoltre, durante le sue elaborazioni la CU può depositare informazioni nei suoi registri interni in quanto sono direttamente individuabili e hanno tempi di accesso inferiori a quelli dei registri della memoria centrale. **I BUS** La CPU comunica con la memoria e con i dispositivi I/O tramite dei canali di comunicazione detti anche **bus**. Il termine bus (che fa riferimento ovviamente a un mezzo pubblico usabile da più persone) indica un canale di comunicazione comune condiviso da più utilizzatori. Un bus è fisicamente costruito da uno o più fili su cui possono transitare uno o più bit contemporaneamente.  A seconda delle informazioni trasportate si hanno: - - - Lo **scambio di informazioni** tra tutti i componenti avvengono secondo le seguenti regole: - - - - Un bus costituito da un solo filo è chiamato **bus seriale** e su di esso i bit transitano uno dietro l'altro, un bus costituito da n fili è chiamato **bus parallelo** perché su di esso transitano n bit alla volta (tipici sono i bus a 8 e 32 fili sui quali si possono trasferire rispettivamente 8 e 32 bit (4 Byte) alla volta). L'address e il data bus sono paralleli e le loro dimensioni caratterizzano i sistemi di calcolo. In particolare, il numero di bit dell'address bus indica la **capacità di indirizzamento** della CPU (cioè la sua capacità di gestire la dimensione della memoria, ad esempio un bus di n bit consente di selezionare un registro da 2\^n disponibili), mentre la dimensione del data bus condiziona la **velocità di scambio delle informazioni** tra i diversi dispositivi (con m fili solo m bit possono viaggiare contemporaneamente). **IL CLOCK** Le attività di tutti i dispositivi vengono sincronizzate tra loro mediante un orologio interno che scandisce i ritmi di lavoro, chiamato **clock**. Il clock è un segnale periodico, di solito un'onda quadrata, caratterizzata da un periodo fissato e una *frequenza* (che indica il numero di cicli di clock che un dispositivo può eseguire in un secondo), ad esempio un clock composto da 10 cicli al secondo ha la frequenza f = 10 Hz e il periodo T= 100ms (la frequenza dei moderni di sistemi spazia dai MHz ai GHz). Quindi, il clock è un segnale che raggiunge tutti i dispositivi per fornire la cadenza temporale con cui eseguire operazioni elementari La velocità di elaborazione di una CPU dipende dalla frequenza del suo clock (più accelerato è il battito del clock maggiore è la velocità di esecuzione). A questa frequenza di clock è legato il numero di operazioni elementari che vengono eseguite nell'unità di tempo. (Ad esempio, se si assume che ad ogni ciclo di clock corrisponde esattamente l'esecuzione di una sola operazione, con un clock a 3 GHz si ha che il processore è in grado di eseguire 3 miliardi di operazioni al secondo. In realtà tale ipotesi non è sempre vera in quanto l'esecuzione di una operazione può richiedere più cicli di clock). **ISTRUZIONI** Lo scopo del modello di Von Neumann è quello di eseguire i comandi memorizzati nella sua memoria centrale. I comandi prendono anche il nome di **istruzioni** perché "istruiscono" la CPU sulle operazioni che deve svolgere. L'insieme delle istruzioni prende il nome di **programma**. Le singole istruzioni sono operazioni semplici come - - - Le istruzioni che un processore è in grado di eseguire sono rappresentate mediante un codice binario definito dal cosiddetto **linguaggio macchina** del processore.  Questo linguaggio è unico per ogni architettura di processore (come x86, ARM, ecc.). Per cui, ogni architettura ha il proprio set di istruzioni binarie che definiscono ciò che il processore può fare. Nella colonna mnemonics le operazioni sono scritte in linguaggio Assembly, che ha una diretta traduzione in binario ma permette di scrivere le operazioni a lettere  Il **repertorio delle istruzioni** varia in base a due "filosofie" distinte per la progettazione dei processori  **Esecuzione di una Istruzione** L'esecuzione di un'istruzione da parte della CU consiste nell'inoltro di una sequenza di abilitazioni di dispositivi (segnali di controllo) il cui effetto corrisponde all\'operazione richiesta. Le prime CU erano realizzate con circuiti detti a **logica cablata**, e cioè ogni singola funzione o istruzione che potevano fare era definita fisicamente nei loro circuiti. I segnali di controllo venivano quindi generati da un apposito circuito hardware e se si voleva dotare il processore di una nuova istruzione, non presente nel suo repertorio, la CU doveva essere sostituita con una che includeva il nuovo circuito. Nelle moderne CU, non ci sono più circuiti cablati per ogni istruzione. Invece, si utilizza una **logica microprogrammata**, cioè ogni istruzione del processore viene eseguita tramite una serie di microistruzioni più semplici, che sono memorizzate nella memoria interna della CU. Ogni istruzione del processore è composta da diverse microistruzioni in sequenza, che insieme permettono alla CU di eseguire l\'istruzione completa. Per fare questo, la CU usa un circuito interno che legge le microistruzioni dalla memoria, una alla volta, seguendo l\'ordine necessario. Il registro IR (Instruction Register) indica la posizione della prima microistruzione da eseguire.  Da notare che internamente la CU è simile a un piccolo modello di Von Neumann. **Firmware e Software** L'insieme dei microprogrammi nella memoria interna della CU è chiamato **firmware**. Aggiungere una nuova istruzione alla CPU significa introdurre un nuovo microprogramma nel firmware, aggiornandolo senza modifiche fisiche alla CU. Il firmware funge da intermediario tra il sistema operativo e i componenti hardware: in sostanza, fornisce al dispositivo le istruzioni operative di base. Il termine "firmware" deriva proprio da questo ruolo di *intermediario tra l'hardware e software*. Inoltre, un firmware viene installato direttamente dal produttore del dispositivo risiedendo stabilmente nell\'hardware per cui è stato scritto, anche se in passato questo non era possibile, oggi può anche essere modificato (aggiornamento firmware) con procedure specifiche. L'insieme di tutte le applicazioni,e quindi tutti i programmi, del computer prende il nome di **software**. In una accezione più ampia il termine software può essere inteso come "tutto quanto può essere preteso dall'hardware": basta infatti inserire in memoria un programma diverso perché il sistema cambi le sue attività. Il computer è quindi un sistema polifunzionale in quanto può eseguire infinite funzioni se viene progettato un programma per ogni applicazione Inoltre, i software si dividono in **software di base**, che servono per tutti gli utenti del sistema e servono per il corretto funzionamento della macchina (vedi sistemi operativi o traduttori dei linguaggi di programmazione **software applicativi,** che risolvono problemi specifici.  Come anticipato tra i software di base c'è il **sistema operativo**, che è un insieme di programmi che gestisce le risorse hardware in modo semplice ed efficiente, permettendo a tutti gli utenti di utilizzarle senza difficoltà. Nei primi computer non esisteva un sistema operativo, quindi il programmatore doveva occuparsi di tutto: gestire i dispositivi di input/output, caricare i programmi in memoria, avviare la CPU e persino indicare quando passare all'istruzione successiva. Con l\'introduzione del sistema operativo, questi compiti sono stati automatizzati. Ad esempio, il passaggio da un'applicazione all'altra avviene automaticamente. La CPU ora può alternare facilmente tra i programmi del sistema operativo e quelli delle applicazioni. Il sistema operativo offre una serie di funzionalità base allo sviluppatore, messe a disposizione tramite moduli software raggruppati in libreria di sistema. Ad esempio il ciclo di vita dei programmi ASM (Assembly) è  Per integrare sistemi con sistemi operativi diversi si sovrappone al SO uno strato software chiamato **middleware**, che maschera l'eterogeneità degli elementi sottostanti. **EVOLUZIONI DEL MODELLO DI VON NEUMANN** Col tempo sono state applicate modifiche al modello di Von Neumann con lo scopo di renderlo più veloce **INTERRUZIONI** Data la natura sequenziale del modello non era possibile sovrapporre operazioni di input e output eseguendo contemporaneamente. Sono stati per questo introdotti sistemi dedicati (**canali**) il cui compito è scaricare la CPU dalla gestione di attività specifiche. Questi sistemi dedicati sono autonomi e possono lavorare contemporaneamente alla CPU. In particolare, per rendere indipendenti questi **processori dedicati** è stato introdotto un segnale hardware detto **segnale di interruzione**. Tramite questo segnale la CPU può attivare uno di questi processori dedicati disinteressandosi delle sue attività: quando un processore conclude il suo compito avanza una richiesta di interruzione alla CPU e aspetta che gli venga rivolta attenzione.  Per consentire alla CU di accorgersi del verificarsi di un'interruzione è stato dotato il CC un bit che diventa uguale a uno quando arriva una richiesta di interruzione. La CU controlla questo bit al termine di ogni istruzione, se è zero continua normalmente, in caso contrario lancia un programma del sistema operativo detto ISR (Interrupt Service Routine) che cerca quale dispositivo ha avanzato la richiesta e nel caso in cui ci siano più richieste contemporaneamente quale servire prima. **CACHE** Per ridurre i tempi di trasferimento dalla memoria centrale ai registri interni della CPU, viene replicata una porzione di memoria e posta tra memoria e CPU stessa. Tale memoria, molto veloce, viene chiamata **cache** e fa da buffer per il prelievo di informazioni dalla memoria centrale. Con operazioni particolari, istruzioni e dati vengono trasferiti dalla memoria centrale nella cache secondo la capacità di quest'ultima. La CU procede nelle tre fasi del suo ciclo al prelievo di istruzioni e operandi dalla cache, se si accorge che il prelievo non può avvenire e mancano dei dati scatta un nuovo travaso dalla memoria centrale. Se la cache è interna alla CPU viene detta di primo livello (L1). Le cache di secondo livello (L2) sono invece esterne e solitamente un pò più lente di quelle di primo livello ma sempre più veloci della memoria centrale. La cache L2 risulta 4 o 5 volte più lenta della cache L1 mentre la RAM lo è addirittura 20 o 30 volte. Si crea così una gerarchie di memorie che offre l'illusione di avere una memoria grande e veloce. In questa gerarchia i livelli più prossimi alla CPU sono quelli più veloci ma più piccoli dato il costo.  **CAPITOLO 3 (ALGORITMI E PROGRAMMI)** L'informatica è lo studio sistematico dei processi che servono al trattamento delle informazioni o più in generale della definizione della soluzione di problemi assegnati. Consiste in: - - - - Se si usa il termine **algoritmo**, che dalla matematica si riferisce alla sequenza precisa di operazioni il cui svolgimento è necessario per la soluzione di un problema assegnato, allora l'informatica diventa lo studio sistematico degli algoritmi. Il **calcolatore** è tra tutti gli esecutori di algoritmi (compreso l'uomo) quello che si mostra più potente degli altri e con una potenza tale da permettere di gestire quantità di informazioni altrimenti non trattabili. Come detto, non tutti i problemi hanno soluzione, ma quelli risolvibili seguono questo schema comune Quindi, gli elementi che concorrono alla soluzione dei problemi sono: - - - - **CALCOLABILITA' DEGLI ALGORITMI** E' importante studiare la **calcolabilità degli algoritmi**. Essa cerca di comprendere quali problemi possono essere trattati tramite un procedimento automatico, e quindi quali problemi sono risolvibili da un calcolatore mediante algoritmi. Non si preoccupa delle risorse necessarie per l'esecuzione, in termini di tempo o di memoria, ma cerca solo di capire se quel problema è teoricamente risolvibile. Lo strumento teorico usato per verificare la calcolabilità e l'esistenza degli algoritmi per un dato problema è la **Macchina di Turing (MdT)**. Prima di descriverne il funzionamento è utile spiegare il concetto di **automa a stati finiti**. Un automa a stati finiti è in generale una macchina che esegue degli algoritmi e che introduce il concetto di **stato** come condizione in cui in un determinato momento può trovarsi la macchina. Un sistema, soggetto a delle sollecitazioni in entrata, risponde in base allo stato che ha in quel momento, magari producendo delle uscite o cambiando il suo stato stesso. Un sistema ha uno stato iniziale e può averne uno finale, a cui si arriva dopo una serie di stati intermedi. Il modello degli automi a stati finiti trova quindi larga applicazione per la capacità di descrivere il comportamento di specifici sistemi.  Un esempio di descrizione grafica e tabellare di un automa a stati finiti è  La macchina di Turing è un particolare automa a stati finiti per il quale sono definiti l'insieme degli ingressi e delle uscite come insiemi di simboli, e un particolare meccanismo di lettura e scrittura delle informazioni. E' un automa con testina di scrittura/lettura su nastro bidirezionale potenzialmente illimitato. Ad ogni istante la macchina si trova in un particolare stato e legge un simbolo sul nastro. La funzione di transizione, in modo deterministico, fa scrivere un simbolo, fa spostare la testina in una direzione o nell\'altra, fa cambiare lo stato. La macchina si compone, quindi, di: - - - In questo sistema, la macchina di Turing che si arresta e trasforma un nastro iniziale t1 in uno finale t2 rappresenta l'algoritmo per l'elaborazione Y=F(X), ove X e Y sono codificati rispettivamente con t1 e t2. Una macchina di Turing la cui parte di controllo è capace di leggere da un nastro anche la descrizione dell'algoritmo si definisce una **macchina universale** capace di simulare il lavoro compiuto da un'altra macchina qualsiasi. Leggere dal nastro la descrizione dell'algoritmo richiede di saper interpretare il linguaggio con il quale esso è stato descritto. La **Macchina di Turing Universale** diventa così anche l'interprete di un linguaggio. Dalla macchina di Turing discendono alcune tesi che restano ancora oggi fondamentali per lo studio degli algoritmi. La **Tesi di Church e Turing** dice che non esiste alcun formalismo che sia più potente della Macchina di Turing e dei formalismi ad essi equivalenti. Ogni algoritmo può essere codificato in termini di Macchina di Turing, e un problema è quindi non risolubile algoritmicamente se nessuna Macchina di Turing è in grado di fornire la soluzione al problema in tempo finito (e viceversa se un problema si può calcolare allora esisterà una macchina di Turing in grado di farlo). Se dunque esistono problemi che la macchina di Turing non può risolvere, si conclude che esistono algoritmi che non possono essere calcolati: si definiscono decidibili quei problemi che possono essere meccanicamente risolvibili da una macchina di Turing, indecidibili tutti gli altri. Si conclude che: - - Più formalmente possiamo dire che la classe delle funzioni calcolabili coincide con quella delle macchina di Turing. La macchina di Turing e la macchina di **von Neumann** sono due modelli di calcolo fondamentali per caratterizzare la modalità di descrizione e di esecuzione degli algoritmi. La macchina di Von Neumann fu modellata dalla Macchina di Turing Universale, la sua memoria è però limitata a differenza del nastro di Turing che ha lunghezza infinita. La macchina di Von Neumann, è quindi un modello di riferimento meno teorico, che prevede anche l'interazione attraverso i suoi dispositivi di input ed output. **TRATTABILITA' DEGLI ALGORITMI** **Calcolabilità** e **Trattabilità** sono due aspetti importanti dello studio degli algoritmi. La prima consente di dimostrare l'esistenza di un algoritmo risolvente un problema assegnato, la seconda studia la eseguibilità di un algoritmo da parte di un sistema informatico. Esistono infatti problemi classificati come risolvibili ma praticamente intrattabili, che pur presentando un algoritmo di soluzione, non consentono di produrre risultati in tempi ragionevoli neppure se eseguiti dal calcolatore più veloce. Il concetto di trattabilità è legato a quello di **complessità computazionale**, che studia i costi intrinseci alla soluzione dei problemi. Inoltre, la complessità consente di individuare i problemi risolvibili che siano trattabili da un elaboratore con costi di risoluzione che crescano in modo ragionevole al crescere della dimensione del problema. Tali problemi vengono detti trattabili. Nello studio degli algoritmi ci sono due tipi di complessità computazionale: - - Queste misurazioni di complessità possono essere **statiche**, se sono basate sulle caratteristiche strutturali (ad esempio il numero di istruzioni) dell'algoritmo e prescindono dai dati di input su cui esso opera, o **dinamiche**, se tengono conto sia delle caratteristiche strutturali dell'algoritmo che dei dati di input su cui esso opera. Un primo fattore che incide sul tempo impiegato dall'algoritmo è la quantità di dati su cui l'algoritmo deve lavorare. Infatti, il tempo di esecuzione è solitamente espresso come una funzione f(n) dove n è la dimensione dei dati di input (si dirà, ad esempio, che un algoritmo ha un tempo di esecuzione n\^2 se il tempo impiegato è pari al quadrato della dimensione dell'input). Però, da sola la dimensione dei dati di input non basta, il tempo di esecuzione dipende anche dalla configurazione dei dati in input e dalla loro difficoltà di interpretazione e calcolo oltre che dalla loro dimensione. Si possono allora fare tre tipi di analisi: - - - Inoltre, è interessante studiare come i tempi crescono al crescere delle dimensioni dei dati. Interessa sapere come l'ordine di grandezza del tempo di esecuzione cresce al limite, ossia per dimensioni dell'input sufficientemente grandi quando la funzione f(n) tende ai suoi asintoti. Lo studio della **complessità asintotica** di un algoritmo permette di fare un\'analisi per ordine di grandezza trascurando le singole operazioni. Dati due algoritmi diversi che risolvono lo stesso problema e presentano due diverse complessità f(n) e g(n), se f(n) è asintoticamente inferiore a g(n) allora esiste una dimensione dell'input oltre il tempo di esecuzione del primo algoritmo è inferiore all'ordine al tempo di esecuzione del secondo. Ad esempio un algoritmo potrebbe avere una complessità asintotica logaritmica o esponenziale.  **DESCRIZIONE DEGLI ALGORITMI** Nella costruzione degli algoritmi è importante specificare in che ordine devono essere eseguite le istruzioni: in **sequenza** secondo un ordine lessicografico occidentale (dall'alto al basso da sinistra a destra); per una **selezione** (fai qualcosa solo se si verifica una condizione); **iterativamente** (ripeti più volte). In tutti gli algoritmi ci sono due classi fondamentali di frasi, quelle che descrivono le singole operazioni, e quelle che descrivono in quale ordine tali operazioni devono essere eseguite, che prendono il nome di **strutture di controllo.** Inoltre, è possibile classificare le istruzioni in **elementari**, se l'esecutore è in grado di comprenderle ed eseguirle, o **non elementari**, quelle non note all'esecutore. Perché un\'istruzione non elementare possa essere eseguita dall\'esecutore a cui è rivolta, deve essere specificata in termini più semplici. Il procedimento che trasforma una istruzione non elementare in un insieme di istruzioni elementari, prende il nome di **raffinamento** o specificazione dell\'istruzione non elementare. Senza questo processo di raffinamento dovremmo scrivere gli algoritmi direttamente in un linguaggio di programmazione, invece la forza dell'analisi del problema e della costruzione di algoritmi è proprio quella di partire da linguaggio naturale e con una serie di operazioni di raffinamento arrivare solo alla fine alla programmazione. **SEQUENZA STATICA E DINAMICA DI ALGORITMI** Le operazioni che compongono un algoritmo devono essere dotate delle seguenti caratteristiche: - - - - Un algoritmo si traduce con una successione di azioni che vengono effettuate nel tempo, questa serie di eventi che avvengono uno dopo l'altro viene detta **sequenza di esecuzione** o **sequenza dinamica**. In un programma, che è la descrizione dell\'algoritmo in un linguaggio di programmazione, la sequenza **statica** delle istruzioni si riferisce all\'ordine in cui le istruzioni sono scritte nel codice sorgente. È detta anche **sequenza lessicografica** perché segue l\'ordine testuale, come se si leggessero le istruzioni da cima a fondo. La sequenza **dinamica** si riferisce all\'ordine effettivo in cui le istruzioni vengono eseguite durante l\'esecuzione del programma. Questa sequenza può differire dalla sequenza statica perché il flusso del programma può essere condizionato da strutture di controllo come **if**, **for**, **while**, funzioni e salti. Quindi, a seconda delle condizioni e dei valori variabili durante l\'esecuzione, il programma può seguire diversi percorsi, e dunque diverse sequenze dinamiche, il cui numero non è noto a priori ma dipende dai dati da elaborare e quale di queste strutture "attivano". Una sequenza statica può portare quindi a una serie di sequenze dinamiche differenti La valutazione sia del tipo che del numero delle sequenze dinamiche è di fondamentale importanza per valutare soluzioni diverse dello stesso problema in modo da poter dire quale di esse presenta un tempo di esecuzione migliore e da poter affermare se una soluzione ha terminazione o meno.