Teoria Mio (1) 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 dell...

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 - I simboli che sono gli elementi atomici della rappresentazione - L’ alfabeto che rappresenta l’insieme dei simboli possibili: con cardinalità (n) del codice si indica il numero di elementi dell’alfabeto - Le parole codice che rappresentano sequenze possibili di simboli: per lunghezza (L) delle stringhe si intende poi il numero di simboli dell’alfabeto da cui ciascuna parola codice risulta composta - Il linguaggio che definisce le regole per costruire parole codici che abbiano significato per l’utilizzatore del codice 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: - convergenza della codifica: perché tutte le informazioni vengono rappresentate con un solo alfabeto, il codice binario - convergenza tecnologica: perché è il calcolatore elettronico che elabora e trasmette le informazioni - convergenza del mercato: ci sono elementi comuni a tutti che permettono l’integrazione 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: - campionamento: partendo dal segnale analogico si scelgono un sottoinsieme discreto di informazioni. La scelta di questo partizionamento dipende ovviamente dal tipo di informazione su cui stiamo lavorando e sull’utilizzo che ne verrà fatto, per cui è richiesta più o meno precisione. La frequenza di campionamento è il numero di campioni prelevati in un secondo e si misura in Hertz (inverso del periodo). - quantizzazione: si determina un insieme finito di valori rappresentabili e si approssima ogni campione prelevato con il valore discreto rappresentabile più vicino (commettendo un errore di quantizzazione) 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. - Compressione LOSSLESS (reversibile): Non comporta una perdita di informazioni e tramite algoritmi che sfruttano la ridondanza del testo (ad esempio non ripetendo cifre che si ripetono n volte ma usando una codifica per rappresentare questa periodicità) e che consentono di ricostruire tutta l’informazione iniziale partendo da quella compressa. Non sempre si ottengono riduzioni significative. Tra le più famose tecniche di compressione lossless si ricordano: - la Run-length encoding (RLE) che codifica sequenze di valori uguali premettendo un indicatore di ripetizioni al valore codificato - la codifica di Huffman che assegna un numero inferiore di bit alle sequenze più probabili attraverso un vettore di codifica - la compressione Lempel-Ziv-Welch (LZW) che costruisce dinamicamente una tabella di codifica con numero variabile di bit sulla base delle sequenze incontrate  - la codifica differenziale in cui ogni dato è rappresentato come differenza rispetto al dato precedente - Compressione LOSSY (irreversibile): Comporta una perdita di informazione e usa quindi algoritmi che non permettono di tornare all’intero file non compresso (si sfrutta il fatto che alcune frequenze o alcune parti di immagini non possono essere percepite dai sensi umani). Si ottengono riduzioni significative. Tra le più famose tecniche di compressione lossy si ricordano: - La compressione JPEG per le immagini che permette di sopprimere dettagli irrilevanti riducendo il numero di bit necessari per la codifica - La compressione MPEG per i video che codifica parte dei frame come differenze rispetto ai valori previsti in base ad una interpolazione (stima sul valore dei frame in base a quelli circostanti) - La compressione MP3 per l’audio che si basa alle proprietà psicoacustiche dell’udito umano per sopprimere le informazioni inutili 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: - Joint Photographers Expert Group JPEG - Tagged Image File Format TIFF - Portable Graphics Format PNG  - Graphics Interchange Format GIF In diminuzione: - Microsoft Bit Map BMP e Device Independent BitMap DIB - PC Paintbrush PCX 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: - EPS e PDF - Drawing eXchange Format (DXF) - Initial Graphics Exchange Specifications (IGES) 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: - proprietà associativa: a + (b - c) = (a + b) – c - proprietà distributiva: a × (b - c) = a × b – a × c 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. - Nel sistema posizionale, il valore di un numero dipende sia dalle cifre utilizzate sia dalla posizione di queste cifre. La singola cifra acquisisce una certa importanza in relazione alla propria posizione. Alcuni esempi classici sono il sistema decimale (base 10) e binario (base 2). - Nel sistema non posizionale, ogni cifra esprime una quantità svincolata dalla posizione. Un esempio classico di sistema non posizionale è il sistema numerico romano. 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: - la parte frazionaria si annulla  - la parte frazionaria si ripete con periodicità - ci si accontenta di una rappresentazione approssimata con un numero di bit inferiore a quello che andrebbero calcolati (per raggiungere una delle condizioni precedenti) 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. - Somma: gli operandi sono incolonnati allineandoli a destra procedendo dai bit di peso inferiore a quelli di peso superiore, ovvero dal LSB al MSB. Si esegue la somma bit a bit secondo le seguenti regole: 0+0 = 0; 0+1 = 1+0 = 1; 1+1 = 0 con riporto di 1. - Differenza: il sottraendo è incolonnato allineato a destra sotto il minuendo. Si esegue la sottrazione bit a bit procedendo dal bit di peso  minore verso quello di peso maggiore secondo le seguenti regole: 0-0=0; 1-0=1; 1-1=0; 0-1=1 con prestito di 1. - Shift: l’operazione di shift si può fare a destra o a sinistra, scorrere di m bit a sinistra significa aggiungere m bit a 0 in posizione meno significativa, scorrere di m bit a destra significa eliminare gli m bit meno significativi - Moltiplicazione: basata sugli algoritmi di somma e scorrimento. Si incolonna a destra e si riporta la moltiplicazione del moltiplicando per ogni bit del moltiplicatore. Ogni numero risultante va fatto scorrere (shift) di un numero di posizioni verso sinistra pari alla posizione del bit moltiplicatore Si sommano poi tutti i numeri risultanti Le regole base della moltiplicazione tra due bit sono: 0 x 0 = 0; 0 x 1 = 0; 1 x 0 = 0; 1 x 1 = 1. 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: - Si esamina il bit più significativo - Se esso è zero, il numero rappresentato è non negativo e lo si calcola con la normale conversione binario-decimale - Se invece è uno, allora si tratta di un numero negativo, per cui, per ottenerne il valore assoluto, si complementano tutti i bit e si somma 1 al risultato 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: - indipendenza dalla posizione della virgola (“floating point”). - possibilità di normalizzare la mantissa trascurando tutti gli zeri che precedono la prima cifra significativa. - capacità di rappresentare numeri estremamente grandi o piccoli con poche cifre. - la dipendenza del valore rappresentato dalla mantissa e dall’esponente se si adottano specifiche convenzioni per la base e la mantissa. 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 [Xi ,Xi+1[ sarà approssimato a Xi o Xi+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 1/2 x 10-4 Più in generale se -h è il peso della cifra meno significativa,l’errore massimo che si commette è: 1/2 x 10-h I numeri reali rappresentabili sono definiti in un insieme limitato con estremi predefiniti [-minreal, maxreal] - Overflow: condizione che si verifica quando i valori o sono più piccoli di minreal o più grandi di maxreal - Underflow: condizione che si verifica quando un valore, per effetto 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: 100 x 100 + 100 x 10-2 = 100 x 100 + 1 x 100 = 101 x 100 Mentre per le divisioni e moltiplicazioni servono operazioni separate per mantisse ed esponenti: 100 x 100 x 100 x 10-2 = (100 x 100) x 10(0-2) = 10000 x 10-2 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 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: - OR: operatore binario detto disgiunzione logica (il nostro oppure) - AND: operatore binario detto congiunzione logica (il nostro e) - NOT: operatore unario, detto negazione logica - XOR: operatore binario, detto disgiunzione esclusiva 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. negando due volte lo stesso elemento si ottiene l’elemento stesso 2. i numeri neutri sono 0 per la somma e 1 per il prodotto 3. assorbimento del complemento a + ¬a x b = a + b 4. Le due relazioni di DE MORGAN (notare che sono una la duale dell’altra) 5. 0 ed 1 sono l’uno il complemento dell’altro 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. - l’algebra booleana binaria - l’algebra degli insiemi - l’algebra della logica delle proposizioni - l’algebra delle reti 1. Algebra binaria (che nelle slide si chiama algebra dei circuiti): utilizzata per progettare i circuiti logici usati per realizzare delle operazioni sui dati in ingresso a un elaboratore. I circuiti logici sono circuiti elettronici nei quali una grandezza elettrica ai morsetti di ingresso e di uscita può assumere solo due valori, convenzionalmente rappresentati con i due elementi dell’algebra binaria di Boole 0 ed 1 (“basso”, “alto”). Le operazioni sono AND, OR, NOT: ogni circuito numerico può essere visto come una combinazione di queste 3 sole porte logiche. Si può definire la funzione booleana come la legge che associa a ogni combinazione delle variabili indipendenti un valore della variabile dipendente y. Visto che ogni variabile indipendente può assumere due valori, sono possibili 2^n possibili casi, riportati nelle tabelle di verità.  La componente base dei circuiti numerici sono le porte logiche, che permettono le operazione di AND, OR e NOT. 2. Algebra degli insiemi: 3. Algebra della logica delle proposizioni: si lavora sulle proposizioni (frasi che implicano un valore di falsità o verità), siano esse semplici, e cioè che possono assumere solo un valore vero o falso, o composte, che assumono uno di questi valori in base ai connettivi (operatori logici e di confronto) che le compongono. 4. Algebra delle reti: studia i sistemi di interconnessione. 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. Uno schema di funzionamento semplice nelle sue linee generali; 2. La velocità e l’affidabilità nelle esecuzioni di algoritmi; 3. Un’adeguata capacità di memoria; 4. Un costo vantaggioso. 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: - nelle memorie di tipo elettronico sono circuiti detti flip-flop che mostrano un valore di tensione o uguale a 5 Volt o a 0 Volt; - nelle memorie di tipo magnetico è una sorta di calamita polarizzata o positivamente o negativamente; - nelle memorie di tipo ottico è una superficie con o senza un buco in modo da riflettere diversamente il raggio laser che la colpisce. 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): - Load: si preleva l'informazione contenuta nel registro senza però distruggerla - Store: si inserisce una informazione nel registro eliminando quella precedente 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é: - Per una operazione di load copi il dato del registro nel buffer (un’area di transito dei dati dalla CPU alla memoria e viceversa); - Per un’operazione di store copia il dato del buffer nel registro. 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: - Per il load, il tempo di accesso misura il tempo che trascorre tra la selezione del registro di memoria e la disponibilità del suo contenuto nel registro di buffer - Per lo store misura invece il tempo necessario alla selezione del registro e il deposito del contenuto del registro di buffer in esso. 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:  - memoria ad accesso casuale dove il tempo di accesso non dipende dalla posizione anche chiamata R.A.M. (Random Access Memory) - Memoria ad accesso sequenziale dove il tempo di accesso dipende dalla posizione, come avviene nei nastri magnetici 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: - Le informazioni contenute nella memoria centrale possono essere direttamente prelevate dalla CPU, mentre quelle contenute nelle  memorie di massa devono essere prima trasferite nella memoria centrale e successivamente elaborate; - Le informazioni prodotte dalla CPU devono essere depositate nella memoria centrale per poi essere conservate nelle memorie di massa. 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: - prelevare ogni istruzione dalla memoria centrale e decodificarla - prelevare i dati dalla memoria (se servono all’istruzione)  - e infine eseguire l’istruzione. Per esempio se l'istruzione prelevata è di tipo aritmetico e richiede due operandi, la CU predispone dapprima il prelievo dalla memoria di tali operandi, attiva poi l'ALU perchè esegua l'operazione desiderata, ed infine deposita il risultato di nuovo in memoria. 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: - bus dati (data bus): permette ai dati di fluire dalla CPU verso un dato registro di memoria selezionato e viceversa - bus indirizzi (address bus): serve alla CU per comunicare l'indirizzo del dispositivo interessato da un'operazione di lettura o scrittura. In questa ottica anche i dispositivi di I/O sono identificati da un indirizzo come i  registri di memoria, tutti i componenti del sistema (memoria, input, output, memoria di massa, etc.) devono quindi essere dotati della capacità di riconoscere sull’address bus il proprio indirizzo. - bus comandi o di controllo (command o control bus): serve alla CU per indicare ai dispositivi cosa devono fare. Tipici segnali sono read e write mediante i quali la CU indica ai dispositivi se devono leggere un dato dal bus o scriverlo. Lo scambio di informazioni tra tutti i componenti avvengono secondo le seguenti regole: - la CPU è l’unico elemento che fornisce l’indirizzo all’address bus - memorie e dispositivi di input ed output devono ascoltare l’address bus per attivarsi quando su di esso compare il proprio indirizzo identificativo - il dispositivo attivo deve interpretare i segnali del control bus per eseguire i comandi della CU - le memorie prelevano dati dal data bus o immettono dati in esso in funzione del comando impartito dalla CU; i dispositivi di input possono solo immettere dati sul data bus; i dispositivi di output possono solo prelevare dati dal data bus 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 - il trasferimento dei dati da un registro ad un altro (da memoria a memoria o da registri della CPU e viceversa ecc…) - operazioni aritmetiche e logiche eseguite dall’ALU - controllo di condizioni riportate dal registro CC 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: - analisi dettagliata di ciò che serve al trattamento dell’informazione - progetto di una soluzione (si noti che alcuni problemi non hanno soluzione, altri ce l’hanno ma non attuabile in tempi ragionevoli, e altri  ancora ne hanno diverse possibili che vanno studiate per trovare la migliore) - verifica della correttezza e della efficienza della soluzione pensata - manutenzione della soluzione nella fase di funzionamento in esercizio (implica ad esempio la leggibilità del codice) 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: - algoritmo: un testo che descrive un insieme di operazioni eseguendo le quali è possibile risolvere il problema assegnato. Se si indica con istruzione la prescrizione di una singola operazione, allora l'algoritmo è un insieme di istruzioni da svolgere secondo un ordine prefissato. - esecutore: l'uomo o la macchina in grado di risolvere il problema eseguendo l'algoritmo. L’esecutore non solo deve comprendere le singole istruzioni ma deve essere anche capace di eseguirle (una dopo l’altra secondo un ordine rigidamente sequenziale che impone l’inizio  dell’esecuzione di una nuova istruzione solo al termine di quella precedente, oppure più istruzioni contemporaneamente svolgendole in parallelo). - input: le informazioni in ingresso che devono essere fornite affinché avvengano le trasformazioni desiderate - output: i risultati prodotti dall'esecutore del dato algoritmo. 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: - una memoria costituita da un nastro di dimensione infinita diviso in celle; ogni cella contiene un simbolo oppure è vuota; - una testina di lettura/scrittura posizionabile sulle celle del nastro; - un dispositivo di controllo che, per ogni coppia (stato, simbolo letto) determina il cambiamento di stato (sposta la testina) ed esegue un’azione elaborativa (scrive un simbolo). 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: - se per un problema esiste un algoritmo risolutore questo è indipendente dal sistema che lo esegue - l’algoritmo è indipendente dal linguaggio usato per descriverlo, visto che per ogni linguaggio si può sempre definire una macchina di Turing universale che lo implementi. 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:  - quella spaziale: intesa come quantità di memoria necessaria alla rappresentazione dei dati necessari all’algoritmo per risolvere il problema - quella temporale, intesa come il tempo richiesto per produrre una soluzione e cioè della velocità di risposta dell’elaboratore (l’efficienza) 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: - analisi del caso migliore: per calcolare il tempo di esecuzione quando la configurazione dei dati presenta difficoltà minime di trattamento. - analisi del caso peggiore: per calcolare il tempo di esecuzione quando la configurazione dei dati presenta difficoltà massime di trattamento. - analisi del caso medio: per calcolare il tempo di esecuzione quando la configurazione presenta difficoltà medie di trattamento 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: - comprensibilità: Le operazioni devono essere espresse in una forma comprensibile all'esecutore che deve eseguirle. - finitezza: Le operazioni devono avere termine entro un intervallo di tempo finito dall'inizio della loro esecuzione - descrivibilità: Le operazioni devono produrre, se eseguite, degli effetti descrivibili - riproducibilità: Le operazioni devono produrre lo stesso effetto ogni volta che vengono eseguite nelle stesse condizioni iniziali 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.