Lezioni, Fondamenti di Informatica

Fondamenti di informatica

Lezione 1

L’informatica, o scienza dell’informazione, nasce molto prima dell’invenzione di ciò che oggi conosciamo come “computer”. Il termine fu coniato nel 1962 dal fisico francese Philippe Dreyfus: INFORMATION + AUTOMATIQUE = “INFORMATIQUE”.

Il concetto moderno di informatica ha origine dopo il rinascimento e si deve a personaggi come Leibniz, Pascal, Loveless, Boole, Frege. I primi lavori accademici si hanno con Alan M. Turing e John von Neumann. L’informatica si configura come scienza del calcolabile; tuttavia, non c’è tuttora unanimità sul fatto di considerarla una scienza a se stante piuttosto che una disciplina evolutiva della matematica.

Nel 1642 il matematico Pascal inventa la macchina addizionatrice (a soli 18 anni). Formata da ruote dentate che rappresentano le unità, le decine, le centinaia e così via. Queste portano sulla circonferenza le cifre da 0 a 9 e sono collegate tra loro mediante ingranaggi. La rotazione completa di una ruota fa avanzare di una unità la ruota alla sua sinistra.

Nel 1832 Charles Babbage dà vita alla prima macchina a programma memorizzato, chiamata “difference engine” (2000 parti meccaniche, ancora oggi funzionante).

Alla fine del 1800, Amedee Manheim inventa la versione moderna del regolo calcolatore, improntato già nel 1600 da William Oughtred.

Nel 1946 all’università della Pennsylvania viene creato l’ENIAC “Electronic Numeric Integrator And Computer”. È il primo esempio di ciò che intendiamo oggi per computer (17468 tubi termoionici equivalenti ad altrettanti transistor). È il primo elaboratore senza parti meccaniche in movimento. È definito computer “la macchina la cui funzionalità di calcolo è programmabile e ridefinibile attraverso un opportuno linguaggio di programmazione”.

Nel 1936 Alan Mathison Turing, matematico e logico britannico considerato il padre dell’informatica moderna, pubblica l’articolo in cui descrive con un modello astratto il funzionamento di una macchina (macchina di Turing) capace di eseguire qualunque algoritmo e di manipolare i dati contenuti su un nastro utilizzando un insieme di regole codificate. La macchina rappresenta un modello teorico e viene usata tuttora nello studio della complessità degli algoritmi. Può essere usata per definire il concetto di algoritmo, ossia un insieme di operazioni effettuabili da una macchina di Turing. Nel 1942 realizza, per il dipartimento delle comunicazioni Inglese, la macchina Colossus, capace di decifrare in modo efficace ed efficiente i codici cifrati nazisti. Egli fu tra i primi a studiare il concetto di intelligenza artificiale, pubblicando nel 1950 il “test di Turing”, un test con il quale è possibile stabilire se una macchina che simula il cervello umano possa o meno essere considerata “intelligente”.

Per algoritmo intendiamo la sequenza delle operazioni necessarie per risolvere un problema in un numero finito di passi. Esiste quindi un algoritmo per eseguire le quattro operazioni elementari.

Turing realizza che ogni tipo di computazione consiste nella manipolazione di simboli secondo un insieme limitato di regole predefinite (Modello del “calcolatore universale”).

Fare eseguire un’operazione ad un calcolatore consiste nel suddividere il problema in problemi più semplici, ognuno dei quali risolvibile con una sequenza di operazioni elementari: si parla di “calcolatore programmabile”.

Il funzionamento della macchina di Turing

• Un insieme di regole definisce il comportamento della macchina su un nastro di “Input-Output”;
• Vi è un nastro (infinito) suddiviso in celle. Ogni cella contiene un solo simbolo oppure è vuota;
• Una testina può spostarsi sul nastro (in entrambe le direzioni), leggendo, scrivendo/sovrascrivendo o cancellando i simboli sul nastro;
• La testina possiede un indicatore che determina lo stato in cui si trova la macchina nel momento in cui legge il simbolo della cella corrente.

A John von Neumann, eminente matematico ed informatico Ungherese, si deve la prima descrizione a blocchi delle componenti essenziali di un calcolatore programmabile (elaboratore). A differenza della calcolatrice, il computer è programmabile e il suo funzionamento non dipende dalla particolare configurazione delle sue parti meccaniche.

L’architettura di von Neumann affida un ruolo centrale all’unità capace di eseguire un programma (ALU – Arithmetic Logic Unit). Sono tuttavia necessari diversi collegamenti per collegare i dati alle varie unità.

Nel 1951 von Neumann crea l’EDVAC, prima macchina digitale programmabile (successore dell’ENIAC). Il modello di von Neumann moderno prevede una sola via di comunicazione dei dati tra le componenti (il “bus” di sistema). Le componenti del computer che consentono l’esecuzione delle funzionalità di un programma sono disposte lungo questo bus.

Grossolanamente, la struttura di un calcolatore può essere scomposta in due blocchi fondamentali: l’hardware e il software. L’hardware è l’insieme dei componenti fisici di cui è composto il calcolatore, ossia la scheda madre (CPU, memorie), unità periferiche, schede di rete, interfacce e altri strumenti. Il software è l’insieme dei componenti logici che implementano le funzionalità di cui il calcolatore è capace, ossia il sistema operativo OS, i programmi applicativi, i programmi e protocolli di rete.

Abstraction Layers

L’Abstraction Layers è la scomposizione (logica) dell’architettura di un calcolatore in livelli di astrazione. Ogni layer è indipendente dai dettagli dell’implementazione degli altri (in particolare, gli applicativi sono indipendenti dai transistor del processore), e eventuali modifiche o aggiornamenti ad un layer, dovrebbero non influenzare gli altri. Nella pratica è tuttavia difficile realizzare una separazione così rigida.

L’architettura dell’Abstraction Layers è organizzata in uno sequenza di strati. Questa schematizzazione “nasconde” i dettagli dell’implementazione:

• OS & Applicazioni: strato che consente l'interazione con l’utente;
• Kernel: “cuore” di ogni sistema operativo, che gestisce i processi eseguiti dalla CPU, la memoria, le operazioni di I/O e i drivers per l’uso dei dispositivi;
• Assembler: trasforma le istruzioni in linguaggio assembly (linguaggio di basso livello) in opcodes, cioè una sequenza binaria di istruzioni comprensibili dalla CPU;
• Firmware: programma di basso livello incluso in un componente hardware e che ne consente l’utilizzo da parte del SO. È “hardware specific”;
• Hardware: microprocessore, bus, memoria, dispositivi I/O, porte, connettori.

Organizzazione di un computer

L’organizzazione di un computer è articolata in diverse componenti:

• Control Unit (CU): controlla l’esecuzione delle operazioni, e la loro sequenza;
• Arithmetic Logic Unit (ALU): effettua le operazioni logiche/matematiche; riceve sequenze di comandi dalla CU;
• Clock: sincronizzazione delle operazioni

Dunque la Central Processing Unit (CPU) è data dall’insieme di ALU, CU, clock e registri. I registri memorizzano operandi e operatori, indirizzi e istruzioni.

Il Bus è un gruppo di collegamenti che trasferisce dati da una componente ad un’altra. Si divide in:

• Data Bus, che sono bidirezionali (lettura/scrittura), e comuni (8/16/32 bit, in genere la stessa lunghezza di una ‘parola’);
• Address Bus, che specificano le locazioni di memoria nella RAM (o altri tipi di memoria eventualmente presenti), e sono monodirezionali. Lo spazio degli indirizzi può essere a 16¹⁶ 32 bit 2 = 64 KB o a 32 bit 2 = 4GB;
• Control Bus, che trasporta i comandi in arrivo dalla CPU e restituisce i segnali di stato dai dispositivi.

La CPU è formata da vari componenti che sono:

• La Main Memory, ossia la memoria centrale (da non confondere con i dischi), detta anche RAM (“Random Access Memory”), presiede alla memorizzazione di tutte le quantità inerenti all’attività del calcolatore. Normalmente la RAM risiede esternamente alla CPU che è in grado di accedervi sia per recuperare che per immagazzinare dei dati.
• L’Instruction Cache, è una memoria più piccola che risiede sullo stesso chip della CPU (molto veloce). Quando al processore servono nuovi dati/istruzioni non deve attendere che vengano recuperate dalla RAM ma le trova già disponibili nella cache.
• La Bus Unit, è una sorta di “autostrada” interna al calcolatore, attraverso la quale i dati viaggiano tra un componente e l’altro. Non si tratta di un’unità ben localizzata, ma piuttosto di un complesso sistema di dispositivi che regolano il traffico si in termini di temporizzazione (master clock) sia in termini di indirizzamento dei dati.
• La Prefetch Unit, è la componente che si occupa di recuperare dati e istruzioni dalla memoria centrale.
• La Decode Unit, si occupa della decodifica delle istruzioni memorizzate nella Instruction Cache. Queste ultime sono memorizzate generalmente in codice Assembly e vengono tradotte da questa unità in codice binario.
• La Control Unit è responsabile, una volta ricevute le istruzioni in codice binario dalla Decode Unit, di attivare tutte le componenti necessarie all’esecuzione delle istruzioni stesse.
• L’Arithmetic Logic Unit è l’unità nella quale vengono effettivamente eseguite le operazioni. È qui che si realizza ciò che immaginiamo sia l’attività fondamentale di un calcolatore: fare conti. Generalmente, questa unità è implementata in due componenti distinte: una dedicata alle operazioni tra numeri interi, l’altra dedicata alle più complicate operazioni tra numeri reali (“floating point unit”).
• I Registri consistono in un insieme, di solito ridotto ad alcune decine, di locazioni di memoria a disposizione della CPU per conservare il codice dell’operazione corrente da eseguire, degli operandi e dell’eventuale operatore sul quale agire. Anche qui, l’effettiva localizzazione di questa componente dipende dalla specifica implementazione.
• La Data Cache è l’unità ad accesso rapido nella quale vengono memorizzati i risultati temporanei delle varie operazioni.

Esempio “Esecuzione di un’operazione” pag 42.

Lezione 2

Un computer è in grado di modificare il suo comportamento (e quindi il tipo di calcoli che è richiesto fare) in funzione di un programma che gli viene sottoposto. Poiché molte operazioni sono riducibili alla manipolazione di simboli, un computer può fare molto di più rispetto alle normali operazioni aritmetiche. La tecnologia corrente permette, in pratica, la realizzazione di un sistema capace di calcolo solo se alla base la rappresentazione è fra stati binari (a due soli valori). Questo perché è costituito da componenti elettronici binari (transistor).

BIT = BINARY DIGIT

In pratica, un programma viene eseguito avendo a disposizione semplicemente una serie di interruttori capaci di essere commutati solamente fra due stati alternativi (ON/OFF convenzionalmente 1/0).

Assumiamo che il digit 0 rappresenti lo stato OFF (ad es. un livello di tensione nullo) e il digit 1 lo stato ON (una tensione positiva).

Il sistema decimale è quello usato dall’essere umano ed è composto da dieci simboli (base 10), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Detti digit: secondo la notazione posizionale, il digit meno significativo (quello più a destra per convenzione) è di ordine 10⁰, quello successivo di ordine 10¹, e così via.

0735D = 7 x 10² + 3 x 10¹ + 5 x 10⁰.

Gli antichi egizi usavano un sistema duodecimale, cioè in base 12 per contare ore e mesi.

Il sistema binario è quello usato dai calcolatori, perché basati internamente su circuiti elettronici (transistor) che possono operare tra due soli stati (on/off). Sono possibili dunque due soli digit (base 2), 0 e 1. Secondo la notazione posizionale, il digit meno significativo è di ordine 2⁰, quello successivo 2¹, e così via.

010110B = 1×2⁴ + 0×2³ + 1×2² + 1×2¹ + 0×2⁰ = 22 (a volte si usa la notazione 0b10110).

Molto usato in informatica è anche il sistema esadecimale, formato da sedici digit (base 16): 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. Secondo la notazione posizionale, il digit meno significativo è di ordine 16⁰, quello successivo 16¹, e così via.

A3EH = 10×16² + 3×16¹ + 14×16⁰ = 2622D (è usata anche la notazione 0xA3EH).

Ogni digit esadecimale (hex digit) è equivalente ad una sequenza di 4 bit. La notazione esadecimale è utilizzata come forma compatta per i bit binari.

Conversione tra basi numeriche

Per la conversione di un numero da base r a base decimale, dato un numero in base r con digit d_n-1d_n-2d_n-3...d₁d₀ il numero decimale equivalente è:

d_n-1 × r^n-1 + d_n-2 × r^n-2 + ... + d₁ × r¹ + d₀ × r⁰.

Per la conversione di un numero da decimale a base r, si divide il numero per la base, si calcolano quoziente e rimanenza e iterativamente, si divide il quoziente per la base (finché il quoziente non è zero). I digit sono rappresentati dalle rimanenze.

Conversione di 261D in esadecimale:

• 261/16: quoziente=16 rimanenza=5;
• 16/16: quoziente=1 rimanenza=0; 261D = 105H
• 1/16: quoziente=0 rimanenza=1

Abbiamo deciso arbitrariamente di riservare 8 bit per la rappresentazione di un numero. Più in generale, per nbits bit avremo:

dove r (la base) e rappresenta la posizione del digit. Storicamente si definisce byte un gruppo di 8 bit. Il numero più grande rappresentabile con 8 bit è 2⁸-1.

Un PC utilizza un numero fissato di bit per rappresentare un dato (un numero, un carattere o altro ancora). Una regione di memoria a bit può rappresentare 2^bit valori distinti. Ad esempio una locazione di 3 bit può contenere le combinazioni 000, 001, 010, 011, 100, 101, 110, 111 cioè 8 entità distinte. Queste “combinazioni” possono essere usate per rappresentare degli interi, come i numeri da 0 a 7 (oppure da 8881 a 8888), i caratteri da ‘A’ a ‘H’, o ancora 8 tipi diversi di frutto.

Una locazione di memoria contiene solamente una sequenza di bit (o pattern binario); è il programmatore a decidere in che modo la sequenza deve essere interpretata. Ad esempio la sequenza binaria 0100 0001B può essere il numero 65 oppure il carattere ASCII ‘A’. È necessario prima decidere in che modo un dato viene rappresentato, prima che una sequenza binaria acquisti un senso. L’interpretazione di un pattern binario viene chiamata codifica o anche “data representation”.

Lezione 3

Gli interi (integers) e i numeri decimali sono rappresentati in modo diverso, e sono processati da componenti diverse dell’ALU. Un intero viene rappresentato da un numero fissato di bit, di solito 8-bit, 16-bit, 32-bit o 64-bit (Unsigned Integers: numeri interi positivi o zero; Signed Integers: numeri interi positivi e negativi e zero).

Per gli interi con segno, esistono diversi schemi di rappresentazione. In tutti, il bit più significativo (sign-bit) rappresenta il segno e si assume 0 per gli interi positivi, 1 per gli interi negativi.

Gli Unsigned Integers possono rappresentare solo valori positivi o nulli e non valori negativi. Il valore di un “insigne integer” è rappresentato dalla “grandezza” della sequenza di bit corrispondente. Ad esempio in una rappresentazione a 16-bit, il bit-pattern 0001 0000 0000 3 12 rappresenta il valore 1x2³ +1x2¹² =4104.

In particolare, un intero senza segno a n bit può rappresentare gli interi da 0 a 2ⁿ-1.

• 8: Minimo 0, Massimo 2⁸-1=255
• 16: Minimo 0, Massimo 2¹⁶-1=65'535
• 32: Minimo 0, Massimo 2³²-1=4'294'967’295
• 64: Minimo 0, Massimo 2⁶⁴-1=18'446'744'073'709'551’615

Gli n-1 bit rimanenti (tolto il bit di segno) rappresentano la grandezza in valore assoluto dell’intero nel modo seguente:

• Per i positivi il valore assoluto è la “grandezza” del pattern di bit;
• Per i negativi il valore assoluto è la “grandezza” del complemento del pattern di bit più uno.

Ogni compilatore, rispettando lo standard, può implementare come preferisce le variabili intere. Quello che è valido tipicamente sulle macchine domestiche, e che assumeremo durante il corso, è:

• char è da 8 bit:
  • (signed) char da -128 a 127;
  • unsigned char da 0 a 255.
• short int è da 16 bit:
  • (signed) short int da -32’768 a 32’767;
  • unsigned short int da 0 a 65’535.
• int è da 32 bit:
  • (signed) int va da -2’147’483’648 a 2’147’483’647;
  • unsigned int va da 0 a 4’294’967’295.
• long int è da 64 bit:
  • (signed) long va da -9’223’372’036’854’775’808 a 9’223’372’036’854’775’807
  • unsigned long va da 0 a 18’446’744’073’709’551’615.

La somma fra numeri espressi in notazione binaria viene eseguita analogamente a quella tra numeri decimali. Dati due soli simboli, 1 e 0 esistono solo quattro somme base:

• 0 + 0 = 0
• 1 + 0 = 1
• 0 + 1 = 1
• 1 + 1 = 0 con riporto di 1

Con il complemento a 2 si ha una sola rappresentazione dello 0 e la sottrazione è trattata come addizione “logica".