Appunti Informatica (Teoria) PDF

APPUNTI Informatica (Teoria)  Sistemi di numerazione Occorre definire la base B da cui discendono varie caratteristiche: - Cifre = {0, 1, 2, 3, …, B – 1} - Peso della cifra i-esima = Bi - Rappresentazione (numeri naturali) su N cifre: 𝑎𝑁−1 𝑎𝑁−2...

APPUNTI Informatica (Teoria)  Sistemi di numerazione Occorre definire la base B da cui discendono varie caratteristiche: - Cifre = {0, 1, 2, 3, …, B – 1} - Peso della cifra i-esima = Bi - Rappresentazione (numeri naturali) su N cifre: 𝑎𝑁−1 𝑎𝑁−2 𝑎𝑁−3 … 𝑎1 𝑎0 𝑁−1 𝐴 = ∑ 𝑎𝑖 ⋅ 𝐵 𝑖 𝑖=0 Sistemi non posizionali (additivi): egiziano, romano, greco. Sistemi posizionali: babilonese (2 cifre, sessagesimale), inuit, selti, maya (ventesimale), indo-arabo. Esempio di ibridi: cinese. Il nostro sistema è quello indo-arabo. Bit e interruttori Sistema binario Base: B = 2 Cifre = {0, 1} BIT = BInary DigiT Esempio: 1012 = 1 ⋅ 22 + 0 ⋅ 21 + 1 ⋅ 20 = 510 Come passare invece da un numero in base 10 a un numero in base 2? Effettuiamo la divisione del numero per 2 e il resto, che può essere 0 o 1 lo teniamo, dividiamo il risultato ancora per 2 e prendiamo il resto, così fino a quando il risultato non fa 0. A questo punto invertiamo l’ordine degli 0 e degli 1 ottenuti e avremo il numero in base 2. Un bit rappresenta una singola cifra, mentre aggregazioni di bit rilevanti prendono il nome di byte = 8 bit. Un’aggregazione di byte forma word (1, 2, 4, 8) utilizzate per le celle di memoria. Dato un numero binario: Per numeri naturali a N bit possiamo avere 2N combinazioni distinte. Somma in binario: 0+0 = 0 0+1 = 1 1+0 = 1 1 + 1 = 0 (𝑐𝑎𝑟𝑟𝑦 1) Quando si effettuano operazioni in colonna bisogna tener conto di queste regole e soprattutto del carry. Sottrazione in binario: 0−0 = 0 0 − 1 = 1 (𝑏𝑜𝑟𝑟𝑜𝑤 = 1) 1−0 = 1 1−1=0 Quando si effettuano operazioni in colonna bisogna tener conto di queste regole e soprattutto del borrow. Overflow Rappresenta una condizione dinamica ed esiste solo come risultato di un’operazione. Indica l’errore che si verifica in un sistema di calcolo automatico quando il risultato di un’operazione non è rappresentabile con la stessa codifica e lo stesso numero di bit degli operandi. Esempio: Se io sto in un byte (quindi con 8 bit) posso rappresentare i numeri da 0 a 255. Se volessi rappresentare un numero maggiore di 255, non bastano più gli 8 bit, ma ne servono altri. Nella somma in binario puro si ha overflow quando si lavora con un numero fisso di bit e si ha carry sul MSB (prima cifra). Sistema ottale Ha base 8 e le sue cifre vanno a 0 a 7. Si rivela utile quando vogliamo scrivere in modo compatto i numeri binari. In questo caso la conversione da base 2 a base 8 si effettua prendendo gruppi di 3 cifre (perché 23=8). La conversione da base 10 a base 8 si effettua come nel sistema binario, solo dividendo per 8. Sistema esadecimale Ha base 16 e le sue cifre vanno da 0 a 1 e poi si utilizzano le lettere da A a F (che sarebbe da 10 a 15). In questo caso la conversione da base 2 a base 16 si effettua prendendo gruppi di 4 cifre (perché 24=8). Rappresentazione dei numeri relativi Ci sono due modi (tipi di codifica) per rappresentare i numeri positivi e negativi: 1) Modulo e segno (M&S) 2) Complemento a 2 (CA2) ATTENZIONE: quando si dà un numero, bisogna SEMPRE specificare la codifica (il calcolatore non la dà per scontata nel momento in cui esegue le operazioni) Modulo e segno Dato un numero di N bit, viene utilizzato il MSB per indicare il segno del numero (0 = +, 1 = −), mentre per il valore assoluto del numero restano N-1 bit Limiti: doppio zero (+0, -0), operazioni complesse, non efficiente, poiché permette di rappresentare i valori compresi nell’intervallo −(2𝑁−1 − 1) < 𝑥 < +(2𝑁−1 − 1). Es: 8 bit [−127, +127]. Complemento a 2 In questa codifica il MSB ha peso negativo, mentre gli altri bit hanno segno positivo. Per convertire un numero decimale in CA2: - Se positivo, si effettua la solita conversione (da binario puro) - Se negativo, si converte il modulo in binario, si complementa ogni bit (gli 0 diventano 1 e gli 1 diventano 0) e si somma 1 sul corrispondente numero di bit. Come possiamo vedere dall’esempio: La codifica CA2 è oggi molto diffusa perché semplifica la realizzazione dei circuiti per eseguire le operazioni aritmetiche ed è possibile applicare le regole binarie a tutti i bit, segno compreso; infatti, possiamo eseguire la somma e la sottrazione senza badare ai segni degli operandi. Al massimo potremmo effettuare la sottrazione immaginando di sommare al minuendo l’opposto del sottraendo (effettuando quindi il cambio di segno come abbiamo visto in precedenza. Quando gli operandi della somma sono con segno discorde non si può mai verificare overflow, mentre quando hanno segno concorde, c’è overflow quando il risultato ha segno discorde. Ma in ogni caso, si trascura sempre il carry sul MSB e il risultato non può essere stampato, visto che necessita di 1 bit. Limiti: in una rappresentazione su N bit possiamo scrivere valori −(2𝑁−1 ) < 𝑥 < +(2𝑁−1 − 1), anche se è comunque uno in più rispetto al modulo e segno, visto che non ha il doppio 0. Rappresentazione dei numeri reali Come rappresentare i numeri con la virgola? Nel sistema decimale si utilizza la rappresentazione posizionale, ad esempio: 0.25 = 2 ⋅ 10−1 + 5 ⋅ 10−2. Per quanto riguarda il sistema binario, i vecchi calcolatori dividevano il numero di bit disponibili in due gruppi: parte intera e parte frazionaria. Utilizzando la notazione scientifica: 3.14 = 0.314 ⋅ 101 , 137 = 0.137 ⋅ 103 , 0.0001 = 0.1 ⋅ 10−3. Quindi un numero N è dato da: 𝑁 = ± 𝑀 ⋅ 10𝐸 (Dove M mantissa ed E = esponente) Nella memoria del calcolatore si memorizzano, in ordine: segno, esponente, mantissa. Formato IEEE-754 (rappresentazioni standard utilizzate dai nostri computer) Con base = 2 e mantissa compresa tra 1 e 2 esclusi: 𝑀 ∈ (1,2), abbiamo due tipi di formato: segno esponente mantissa TOTALE IEEE-754 Singola Precisione (float) 1 bit 8 bit 23 bit 32 bit IEEE-754 Doppia Precisione (double) 1 bit 11 bit 52 bit 64 bit Queste rappresentazioni hanno però i loro limiti. Osserviamo quella a singola precisione (32 bit): Possiamo vedere che non è possibile rappresentare qualunque numero, poiché all’esponente siamo limitati tra -38 e +38. Se si sforano questi valori, il programma restituisce NaN (not a number) se va in overflow, se si va in underflow, il programma approssima a 0. La limitatezza della precisione porta ad avere problemi con le operazioni aritmetiche, infatti, in FP la somma NON è associativa. Questo significa che 𝑥 + (𝑦 + 𝑧) può essere diverso da (𝑥 + 𝑦) + 𝑧. Vediamo un esempio al calcolatore: Rappresentazione di dati non numerici Fino ad ora abbiamo analizzato solo numeri. Ma il mondo non è fatto solo di numeri, quindi è necessario rappresentare tutto il resto: testi, suoni, immagini, video ecc. Il calcolatore, però, è in grado di manipolare solo numeri, quindi per gestire dati non numerici, l’unica possibilità che abbiamo è di creare una corrispondenza tra oggetti e numeri, quindi: - Ad ogni aspetto si assegna un codice univoco - Questo codice binario diventa la rappresentazione dell’oggetto. Come abbiamo visto per i numeri, dati N bit, noi possiamo rappresentare 2N oggetti. Quindi ad esempio se volessi rappresentare 16 colori, sarebbero necessari 4 bit. Di solito i nostri dispositivi producono immagini a 24 bit, quindi, ogni pixel può assumere 224 colori diversi (i famosi 16 milioni di colori), di questi avremo 8 bit per le intensità del rosso, 8 per il verde e 8 per il blu (da cui deriva RGB in inglese). Viceversa, se ho M oggetti, per codificarli tutti dovrò usare un numero di bit N pari a 𝑁 = log 2 𝑀 Questo concetto è applicato nel codice ASCII (American Standard Code for Information Interchange), che originariamente utilizzata 7 bit, ma che adesso ne usa 8 per rappresentare: - 52 caratteri alfabetici (a…z, A…Z); - 10 cifre (0…9) - Segni di interpunzione (,. ; -_! ? \ ecc.) - Caratteri di controllo: caratteri utilizzati per effettuare operazioni sul testo (andare a capo, inserire un tab, nuova pagina, nuova riga ecc.) UNICODE e UTF-8 Il codice ASCII però non bastava, perché ad esempio non aveva le lettere accentate, visto che in lingua inglese non si usano. È stato creato quindi Unicode, in grado di esprimere tutti i caratteri di tutte le lingue del mondo (più di un milione) ed è il codice usato per rappresentare i caratteri in Python. La codifica di Unicode più usata è UTF-8: - 1 byte per caratteri US-ASCII (MSB = 0); - 2 byte per caratteri latini con simboli diacritici, Greco, Cirillico, Armeno, Ebraico, Arabo, Siriano e Maldiviano; - 3 byte per altre lingue di uso comune; - 4 byte per caratteri rarissimi. Un testo però non è fatto solo di caratteri: su Word noi inseriamo un testo, ma forniamo anche altre informazioni: il tipo di carattere, la grandezza, il colore, il grassetto, il corsivo ecc. L’Unicode quindi non basta, ma per fornire queste informazioni bisogna sviluppare un’ulteriore codifica, come ad esempio.doc per i file Word,.pdf per i file finiti ecc. Facciamo quindi distinzione tra due formati di un testo: - Formattato: sono memorizzate sequenze di byte che definiscono l’aspetto del testo; - Non formattato: sono memorizzati solo i caratteri che compongono il testo. Per quanto riguarda i dati multimediali come audio, video ecc, le codifiche sono molto più articolate ma basate sul solito principio di associazione oggetti < −> codice, ma non verranno affrontate in questo corso.  Architettura Per comprendere il processo di processo di programmazione, è necessario conoscere gli elementi costitutivi di un computer, che è formato da componenti fondamentali: - Unità di input/output: interfaccia da/verso l’utente, implicano un cambio di dominio fisico: umano (analogico, asincrono, non elettrico), calcolatore (digitale, sincrono, elettrico); - Unità di elaborazione: contiene i circuiti per l’esecuzione delle istruzioni e il microprocessore; - Memoria: memorizza in modo permanente dati e programmi ed è necessaria per l’elaborazione in termini di efficienza. Il microprocessore (unità di elaborazione) È il circuito che fisicamente esegue tutte le istruzioni e contiene: - Tutti i circuiti per eseguire le operazioni di base su numeri interi, reali e operazioni logiche; - Opportuni circuiti per il coordinamento dell’esecuzione delle istruzioni; - Interfacce per spostare dati da/verso la memoria e verso l’unità I/O; - Parte della memoria, per avere lo stretto necessario per eseguire operazioni (più efficienza). CPU La CPU (Central Processing Unit) è composta da: Unità operativa Registri: elementi di memoria locale usati per conservare temporaneamente dei dati o istruzioni; ogni trasferimento da processore a memoria e viceversa avviene tra registri e memoria RAM. Numero limitato da 8 a 128. Flag: ha valore Vero o Falso e regola il funzionamento delle informazioni, verificando lo stato corrente della macchina; è un registro che contiene un insieme di bit che segnalano determinati stati dell’insieme delle unità di calcolo e vengono utilizzati per implementare alcune condizioni. Flag significativi: - Zero: segnala se il risultato dell’operazione è o no zero; - Segno: indica il segno del risultato dell’operazione precedente; - Overflow: indica se il risultato dell’operazione precedente eccede i limiti della rappresentazione. ALU (Arithmetic Logic Unit): svolge tutti i calcoli (aritmetici, logici, confronti) su numeri interi. FPU (Floating Point Unit): svolge i calcoli su numeri reali Il rapporto dipende dallo specifico processore, ma tipicamente un’operazione FPU è più lenta di 5-50 volte di un’operazione ALU. Unità di controllo Il cuore dell’elaboratore che, in base alle istruzioni nel programma che esegue ed allo stato di tutte le unità, decide l’operazione da eseguire ed emette gli ordini relativi, quindi, non esegue le esegue le operazioni ma le coordina. PC (Program counter): registro che indica sempre l’indirizzo della cella di memoria che contiene la prossima istruzione da eseguire. IR (Instruction Register): registro che memorizza temporaneamente l’operazione corrente da eseguire. Logica di controllo: interpreta il codice macchina in IR per decidere ed emette gli ordini che le varie unità devono eseguire. Come viene eseguita un’istruzione? Avviene in tre fasi: 1) FETCH: IR  M[PC] preleva dalla memoria l’istruzione nella posizione indicata da PC PC  PC + 1 incrementa il valore di PC (al passo successivo conterrà la prossima istruzione da eseguire 2) DECODE: ordini  decode (IR) 3) EXECUTE: attiva i blocchi interessati dall’istruzione). Ogni elaboratore contiene un elemento di temporizzazione detto clock, che genera un riferimento temporale comune per tutti gli elementi costituenti il sistema di elaborazione. Lo esprimiamo con la frequenza e lo misuriamo in Hz, ovvero s-1, in modo da misurare il numero di cicli nell’unità di tempo (il secondo). Un ciclo-macchina è l’intervallo di tempo in cui viene svolta una operazione elementare ed è un multiplo intero del periodo del clock. L’esecuzione di un’istruzione richiede un numero intero di cicli-macchina, variabile a seconda dell’istruzione. Quindi più il processore ha una frequenza maggiore, più ravvicinati saranno i cicli e più velocemente verranno eseguite le operazioni. La prestazione complessiva del programma dipenderà dal mix di istruzioni. La memoria Memorizza i dati e le istruzioni necessarie all’elaboratore per operare. Caratteristiche: - Indirizzamento: la memoria è organizzata in celle (minima unità accessibile direttamente). Ad ogni cella di memoria è associato un indirizzo (numerico) per identificarla univocamente; - Parallelismo: ogni cella di memoria contiene una quantità fissa di bit (word) identica per tutte le celle di una certa unità di memoria, accessibile con un’unica istruzione, è un multiplo del byte, tipicamente la dimensione della cella di memoria coincide con quella dei registri per consistenza e semplicità; - Accesso (sequenziale o casuale) - Struttura gerarchica: ad oggi non esiste una memoria che sia molto capiente, molto veloce, economica e che contenga informazioni non volatili, infatti possiamo avere memorie veloci, che però hanno un costo elevato e sono volatili, e memorie non volatili che costano relativamente poco ma sono relativamente lente. Per rendere il calcolatore efficiente, si posizionano le memorie più veloci e volatili più vicino al processore e le memorie più lente e non volatili lontano. Metrica SRAM (cache) DRAM FLASH (SSD, Disco chiavette) Dimensione MB (1-16) GB (4-16) GB (16-512) TB (>1) Velocità 1-5 ns 50-150 ns Circa 10 ms Circa 10 ms Costo 10-5 $/byte 10-8 $/byte 10-9 $/byte 10-10 $/byte Persistenza Volatile Volatile Non volatile Non volatile Le interconnessioni (bus) Abbiamo illustrato le componenti di un calcolatore, ma come connettere n unità (CPU con memorie e vari controllori di I/O) in modo efficiente? La connessione punto-punto non è pratica, perché il numero di connessioni aumenterebbe con il quadrato del numero di unità da connettere. Viene quindi utilizzata un’unica linea di connessione per connettere tutti i componenti, che sono fisicamente agganciati a questa linea. Vengono chiamati bus, che hanno: - Vantaggi: costi ridotti di produzione, estendibilità (aggiunta di nuovi dispositivi semplificata) standardizzabilità (regole per la comunicazione da parte di dispositivi diversi; - Svantaggi: lentezza, poiché se già il canale contiene un’operazione, per mandarne un’altra bisogna aspettare che si liberi il canale; sovraccarico del processore, che fa da master sul controllo del bus. L’ampiezza di un bus corrisponde al numero di bit di cui è costituito un singolo dato (ogni filo ha un bit); la frequenza corrisponde al numero di dati trasportati al secondo. Se il bus è mal dimensionato, potrebbe essere un collo di bottiglia. Un singolo bus è suddiviso in tre “sotto bus”, detti: - Bus di dati (DBus): girano i dati veri e propri; - Bus degli indirizzi (ABus): indirizzo del dato che mi serve - Bus di controllo (CBus): che operazione deve essere fatta e da chi deve essere fatta Massima memoria interna (fisicamente presente) La dimensione dell’ABus determina il massimo numero di celle di memoria indirizzabili. La dimensione del DBus indica la dimensione di una cella di memoria. 𝑀𝑒𝑚𝑜𝑟𝑖𝑎 𝑚𝑎𝑠𝑠𝑖𝑚𝑎 = 2|𝐴𝐵𝑢𝑠| ⋅ |𝐷𝐵𝑢𝑠| 𝑏𝑖𝑡 Esempio: ABus 20 bit, DBus 16 bit, max mem = 2|20| ⋅ |16| 𝑏𝑖𝑡 = 2 𝑀𝐵 Ovvero un milione di celle di memoria, ognuna da 2 byte. QUADRO GENERALE DELL’ARCHITETTURA DI UN CALCOLATORE