INFORMATICA 1 Corso di Laurea in Fisica a.a. 2007/08

INFORMATICA 1 Corso di Laurea in Fisica

a.a. 2007/08

prof. Paolo Mancarella

1

Dipartimento di Informatica

email: paolo.mancarella@unipi.it

Introduzione al corso Informazioni utili

Informazioni utili

I Ricevimento studenti: MERCOLEDI’ 15-18

I email: paolo.mancarella@unipi.it

I Materiale didattico: questi lucidi pagina web corso:

http://www.di.unipi.it/∼paolo/Informatica1/

Testi consigliati per consultazione:

I

Ceri-Mandrioli-Sbattella Informatica: programmazione McGraw-Hill

I

Kelley-Pohl

C: didattica e programmazione Addison Wesley

I

Crescenzi-Gambosi-Grossi Strutture di dati e algoritmi AddisonWesley

Modalit` a d’esame

Introduzione al corso Programma di massima del corso

Programma di massima del corso

I Concetti di base della programmazione

I Rappresentazione dell’informazione (cenni)

I Architettura degli elaboratori (cenni)

I La programmazione nel linguaggio C

I Cenni di programmazione ricorsiva

I Cenni di complessit` a computazionale

Concetti di base della programmazione Cosa ` e?

Cosa intendiamo per programmazione

I I calcolatori sono macchine in grado di eseguire velocemente e con precisione sequenze di operazioni elementari.

I A differenza di altre macchine automatiche (es. lavatrici, calcolatrici tascabili, registratori di cassa, ecc.) i calcolatori sono programmabili:

la funzione svolta di volta in volta dipende dal particolare programma con cui l’utente istruisce la macchina per la soluzione di un problema.

I Un programma ` e una sequenza di operazioni necessarie per risolvere

un problema, espressa in un linguaggio di programmazione che il

calcolatore ` e in grado di comprendere ed eseguire.

Concetti di base della programmazione Cosa ` e?

Cosa intendiamo per programmazione

I Il procedimento che porta alla definizione dei programmi adatti a risolvere problemi ` e detto programmazione.

I I concetti che stanno alla base della programmazione si possono spiegare e comprendere senza far riferimento al calcolatore.

I La programmazione ` e tuttavia divenuta una vera e propria disciplina

solo con l’avvento dei moderni calcolatori elettronici.

Concetti di base della programmazione Le fasi della programmazione

Le fasi della programmazione

Ad un primo livello di astrazione l’attivit` a della programmazione pu` o essere suddivisa in quattro (macro) fasi principali.

1. Definizione del problema (specifica)

2. Individuazione di un procedimento risolutivo (algoritmo)

3. Codifica dell’algoritmo in un linguaggio di programmazione (codifica)

4. Esecuzione e messa a punto (esecuzione)

Concetti di base della programmazione Le fasi della programmazione

Specifica

I La prima fase della programmazione consiste nel comprendere e definire (specificare) il problema che si vuole risolvere.

I La specifica del problema pu` o essere fatta in maniera pi` u o meno rigorosa, a seconda del formalismo descrittivo utilizzato.

I La specifica di un problema prevede la descrizione dello stato iniziale del problema (dati iniziali, input) e dello stato finale atteso (i risultati, output).

I La caratterizzazione degli stati iniziale e finale dipende dal particolare

problema in esame e dagli oggetti di interesse.

Concetti di base della programmazione Le fasi della programmazione

Esempi di specifica informale

1. Dati due numeri, trovare il maggiore.

2. Dato un elenco telefonico e un nome, trovare il numero di telefono corrispondente.

3. Data la struttura di una rete stradale e le informazioni sui flussi dei veicoli, determinare il percorso pi` u veloce da A a B.

4. Scrivere tutti i numeri pari che non sono la somma di due numeri primi (Congettura di Goldbach).

5. Decidere per ogni programma e per ogni dato in ingresso, se il

programma C termina quando viene eseguito su quel dato.

Concetti di base della programmazione Le fasi della programmazione

Esempi (contd.)

Caratteristiche comuni ai problemi

informazioni in ingresso =⇒ informazioni in uscita

stato iniziale =⇒ stato finale

Concetti di base della programmazione Le fasi della programmazione

Osservazioni sulla formulazione dei problemi:

I la descrizione non fornisce un metodo risolutivo (es. 3 )

I la descrizione del problema ` e talvolta ambigua o imprecisa (es. 2, con Mario Rossi che compare pi` u volte )

I per alcuni problemi non ` e noto un metodo risolutivo (es. 4 )

I esistono problemi per i quali ` e stato dimostrato che non pu` o esistere un metodo risolutivo (es. 5 )





 Noi considereremo solo problemi per i quali

` e noto che esiste un metodo risolutivo.

Concetti di base della programmazione Le fasi della programmazione

Algoritmi

I Una volta specificato il problema, si determina un procedimento risolutivo dello stesso (algoritmo), ovvero un insieme di azioni da intraprendere per ottenere i risultati attesi.

I Il concetto di algoritmo ha origini molto lontane: l’uomo ha utilizzato

spesso algoritmi per risolvere problemi di varia natura. Solo in era

moderna, tuttavia, ci si ` e posti il problema di caratterizzare problemi

e classi di problemi per i quali ` e possibile individuare una soluzione

algoritmica e solo nel secolo scorso ` e stato dimostrato che esistono

problemi per i quali non ` e possibile individuare una soluzione

algoritmica.

Concetti di base della programmazione Le fasi della programmazione

Algoritmi (cont.)

I Utilizziamo algoritmi nella vita quotidiana tutte le volte che, ad esempio, seguiamo le istruzioni per il montaggio di una

apparecchiatura, per la sostituzione della cartuccia di una stampante, per impostare il ciclo di lavaggio di una lavastoviglie, per prelevare contante da uno sportello Bancomat, ecc.







 Un algoritmo ` e una sequenza di passi che, se intrapresa

da un esecutore, permette di ottenere i risultati attesi

a partire dai dati forniti.

Concetti di base della programmazione Le fasi della programmazione

Propriet` a di un algoritmo

La descrizione di un procedimento risolutivo pu` o considerarsi un algoritmo se rispetta alcuni requisiti essenziali, tra i quali:

Finitezza: un algoritmo deve essere composto da una sequenza finita di passi elementari.

Eseguibilit` a: il potenziale esecutore deve essere in grado di eseguire ogni singola azione in tempo finito con le risorse a disposizione

Non-ambiguit` a: l’esecutore deve poter interpretare in modo univoco ogni singola azione.

Tipici procedimenti che non rispettano alcuni dei requisiti precedenti sono:

I

le ricette di cucina: aggiungere sale q.b. - non rispetta 3)

I

le istruzioni per la compilazione della dichiarazione dei redditi (!)

Concetti di base della programmazione Le fasi della programmazione

Codifica

I Questa fase consiste nell’individuare una rappresentazione degli oggetti di interesse del problema ed una descrizione dell’algoritmo in un opportuno linguaggio noto all’esecutore.

I Nel caso in cui si intenda far uso di un elaboratore per l’esecuzione dell’algoritmo, quest’ultimo deve essere tradotto (codificato) in un opportuno linguaggio di programmazione. Il risultato in questo caso ` e un programma eseguibile al calcolatore.

I Quanto pi` u il linguaggio di descrizione dell’algoritmo ` e vicino al

linguaggio di programmazione scelto, tanto pi` u semplice ` e la fase di

traduzione e codifica. Se addirittura il linguaggio di descrizione

coincide con il linguaggio di programmazione, la fase di traduzione ` e

superflua.

Concetti di base della programmazione Le fasi della programmazione

Codifica (cont.)

I linguaggi di programmazione forniscono strumenti linguistici per rappresentare gli algoritmi sottoforma di programmi che possano essere compresi da un calcolatore.

In particolare dobbiamo rappresentare nel linguaggio di programmazione

I l’algoritmo

I le informazioni iniziali

I le informazioni utilizzate dall’algoritmo

I le informazioni finali

=⇒ programma

=⇒ dati in ingresso

=⇒ dati ausiliari

=⇒ dati in uscita

In questo corso impareremo a codificare algoritmi utilizzando il

linguaggio di programmazione denominato C.

Concetti di base della programmazione Le fasi della programmazione

Esecuzione

I La fase conclusiva consiste nell’esecuzione vera e propria del programma.

I Spesso questa fase porta alla luce errori che possono coinvolgere ciascuna delle fasi precedenti, innescando un procedimento di messa a punto tale da richiedere la revisione di una o pi´ u fasi (dalla specifica, alla definizione dell’algoritmo, alla codifica di quest’ultimo).

I Nel caso dei linguaggi di programmazione moderni, vengono forniti strumenti (denominati di solito debugger) che aiutano nella

individuazione degli errori e nella messa a punto dei programmi.

Concetti di base della programmazione Le fasi della programmazione

Esempi

Negli esempi che seguono, utilizziamo un linguaggio pseudo-naturale per la descrizione degli algoritmi.

Tale linguaggio utilizza, tra l’altro, le comuni rappresentazioni simboliche

dei numeri e delle operazioni aritmetiche.

Concetti di base della programmazione Le fasi della programmazione

Problema 1: Calcolo del prodotto di due interi positivi

Specifica

Input: due valori interi positivi A e B Output: il valore di A×B

Algoritmo

Se l’esecutore che scegliamo ` e in grado di effettuare tutte le operazioni di base sui numeri, un semplice algoritmo ` e il seguente:

Passo 1. Acquisisci il primo valore, sia esso A

Passo 2. Acquisisci il secondo valore, sia esso B

Passo 3. Ottieni il risultato dell’operazione A×B

Concetti di base della programmazione Le fasi della programmazione

Problema 1 (cont.)

Codifica

Un esecutore che rispetta le ipotesi precedenti ` e una persona dotata di una calcolatrice tascabile. La codifica dell’algoritmo in questo caso pu` o essere allora la seguente:

Passo 1. Digita in sequenza le cifre decimali del primo valore Passo 2. Digita il tasto ∗

Passo 3. Digita in sequenza le cifre decimali del secondo valore Passo 4. Digita il tasto =

Esecuzione

Concetti di base della programmazione Le fasi della programmazione

Problema 1 (cont.)

I Supponiamo ora che l’esecutore scelto sia in grado di effettuare solo le operazioni elementari di somma, sottrazione, confronto tra numeri.

I E necessario individuare un nuovo procedimento risolutivo che tenga ` conto delle limitate capacit` a dell’esecutore

Algoritmo 2

Passo 1. Acquisisci il primo valore, sia esso A Passo 2. Acquisisci il secondo valore, sia esso B Passo 3. Associa 0 ad un terzo valore, sia esso C Passo 4. Finch´ e B>0 ripeti

Passo 4.1. Somma a C il valore A

Passo 4.2. Sottrai a B il valore 1

Passo 5. Il risultato ` e il valore C

Concetti di base della programmazione Le fasi della programmazione

Problema 1: (cont.)

Un esecutore che rispetta le ipotesi precedenti ` e un bimbo in grado di effettuare le operazioni richieste (somma, sottrazione e confronto) e di riportare i risultati di semplici calcoli su un quaderno.

Codifica

Passo 1. Scrivi il primo numero nel riquadro A Passo 2. Scrivi il secondo numero nel riquadro B Passo 3. Scrivi il valore 0 nel riquadro C

Passo 4. Ripeti i seguenti passi finch´ e il valore nel riquadro B ` e maggiore di 0:

- calcola la somma tra il valore in A e il valore in C - scrivi il risultato ottenuto in C

- calcola la differenza tra il valore in B ed il numero 1 - scrivi il risultato ottenuto in B

Passo 5. Il risultato ` e quanto contenuto nel riquadro C.

Concetti di base della programmazione Il concetto di stato

Il concetto di stato

Gli esempi visti finora consentono di fare le seguenti considerazioni di carattere generale:

I La specifica (astratta) di un problema consiste nella descrizione di uno stato iniziale (che descrive i dati del problema) e di uno stato finale (che descrive i risultati attesi).

I E necessario individuare una ` rappresentazione degli oggetti coinvolti (e dunque dello stato) che sia direttamente manipolabile

dall’esecutore prescelto.

I Un algoritmo ` e una sequenza di passi elementari che, se intrapresi da un esecutore, comportano ripetute modifiche dello stato fino al raggiungimento dello stato finale desiderato.

I Le azioni di base che l’esecutore ` e in grado di effettuare devono

dunque prevedere, tra le altre, azioni che hanno come effetto

Concetti di base della programmazione Il concetto di stato

Un’astrazione dello stato

Introduciamo una possibile astrazione del concetto di stato, di cui faremo spesso uso in seguito.

Stato

Uno stato ` e un insieme di associazioni tra nomi simbolici e valori.

In uno stato, ad ogni nome simbolico ` e associato al pi` u un valore.

Rappresentiamo una associazione tra il nome simbolico x ed il valore val con la notazione







x val 

Concetti di base della programmazione Il concetto di stato

Lo stato: esempi

Stati corretti

I

{nome Antonio, cognome Rossi, eta’ 25}

I

{importo $1650, tasso 10%, interesse $165 }

I

{a 25, b 3, c 50}

Stati non corretti

I

{ nome Antonio, nome Paolo, eta’ 25}

I

{ b 45, a 150, b 10 }

Concetti di base della programmazione Pseudo-linguaggio per la specifica di algoritmi

Pseudo-linguaggio

I Utilizziamo inizialmente uno pseudo-linguaggio con un insieme di costrutti linguistici che costituiscono il nucleo di un qualunque linguaggio di programmazione reale.

I Senza entrare in eccessivi dettagli formali, nel presentare le notazioni utilizzate (sintassi) diamo anche una descrizione informale

(semantica) di ci` o che accade al momento dell’esecuzione in corrispondenza dei vari costrutti.

Il linguaggio contiene costrutti per:

I rappresentare semplici calcoli attraverso le comuni operazioni logico/aritmetiche (espressioni)

I modificare le associazioni nello stato (assegnamento e ingresso)

I controllare l’ordine di esecuzione delle azioni (controllo)

I fornire i risultati (produzione in uscita dello stato finale)

Concetti di base della programmazione Pseudo-linguaggio per la specifica di algoritmi

Espressioni

Espressioni Numeriche

Il linguaggio consente di rappresentare semplici calcoli algebrici, attraverso le usuali espressioni costruite a partire dai valori numerici e dalle operazioni di

somma + sottrazione - prodotto * divisione intera /

resto della divisione intera %.

Il significato di un’espressione ` e il suo valore ottenuto secondo le usuali regole di calcolo.

Esempio:

il valore di 3 ∗ 5 + 6 ` e 21

Concetti di base della programmazione Pseudo-linguaggio per la specifica di algoritmi

Espressioni (cont.)

Oltre ai valori numerici, le espressioni possono contenere nomi simbolici: il calcolo di un’espressione che contiene un nome simbolico x dipende dallo stato, e precisamente dal valore associato al nome x nello stato.

Esempio:

il valore di 3 ∗ (5 + x ) ` e

I 33 in uno stato che contiene l’associazione x 6

I 18 in uno stato che contiene l’associazione x 1

Concetti di base della programmazione Pseudo-linguaggio per la specifica di algoritmi

Espressioni (cont.)

Espressioni Booleane

Il linguaggio consente poi di rappresentare condizioni ovvero espressioni il cui valore ` e un valore di verit` a (true o false).

Le condizioni sono costruite attraverso le usuali operazioni di confronto (==, ! =, <, >, <=, >=) e, come nel caso delle espressioni aritmetiche, il loro valore pu` o dipendere dallo stato.

Esempio: il valore di y==x+1 ` e

I

true in uno stato che contiene le associazioni x 5 e y 6

I

false in uno stato che contiene le associazioni x 5 e y 9 Condizioni pi` u complesse possono essere costruite attraverso operatori logici quali negazione (simbolo !), congiunzione (simbolo

&&) e disgiunzione (simbolo ||).

Concetti di base della programmazione Pseudo-linguaggio per la specifica di algoritmi

Espressioni (cont.)

I Significato di ! - il valore di verit` a di ! P ` e

I

true se il valore di verit` a di P ` e false

I

false se il valore di verit` a di P ` e true

I Significato di && - il valore di verit` a di P && Q ` e

I

true se i valori di verit` a di P e Q sono entrambi true

I

false altrimenti

I Significato di || - il valore di verit` a di P || Q ` e

I

false se i valori di verit` a di P e Q sono entrambi false

I

true altrimenti

Concetti di base della programmazione Pseudo-linguaggio per la specifica di algoritmi

Esempio:

I Il valore di (y >= x) &&(x > 5) ` e

- true in uno stato che contiene le associazioni x 15 e y 30 - false in uno stato che contiene le associazioni x 3 e y 30

I Il valore di (y >= x) || (x > 5) ` e

- true in uno stato che contiene le associazioni x 2 e y 30

- false in uno stato che contiene le associazioni x 3 e y 1

Concetti di base della programmazione Pseudo-linguaggio per la specifica di algoritmi

Modifica dello stato: ASSEGNAMENTO

I L’istruzione che consente di rappresentare modifiche di stato ` e usualmente nota come assegnamento.

I L’assegnamento consente di cambiare un’associazione nello stato, ovvero il valore associato nello stato ad un nome simbolico.

I Useremo per l’assegnamento la seguente notazione



 x = exp;

dove x ` e un nome simbolico e exp una espressione.

I L’esecuzione dell’assegnamento x = exp; consiste nel (i) calcolare il valore, sia esso val, dell’espressione exp (ii) introdurre nello stato l’associazione x val

I Si noti che (ii) comporta la rimozione dallo stato della eventuale

associazione gi` a presente per il nome simbolico x (si parla a questo

proposito di assegnamento distruttivo).

Concetti di base della programmazione Pseudo-linguaggio per la specifica di algoritmi

ASSEGNAMENTO: esempi

Vediamo alcuni esempi, indicando lo stato prima e dopo l’esecuzione degli assegnamenti proposti. Le associazioni modificate nello stato finale sono evidenziate in verde.

Stato iniziale Assegnamento Stato Finale { x 10, y 20} x = 5; { x 5, y 20}

{ x 10, y 20} x = y*2; { x 40, y 20}

{ x 10, y 20} x = x+1; { x 11, y 20}

Si noti come, nel terzo esempio, lo stesso nome simbolico x giochi un duplice ruolo:

- a destra del simbolo = indica un valore (il valore associato ad x nello stato iniziale)

- a sinistra del simbolo = indica l’associazione da modificare nello stato

Concetti di base della programmazione Pseudo-linguaggio per la specifica di algoritmi

Modifica dello stato: INPUT

I La seconda istruzione di modifica dello stato consente di acquisire valori dal mondo esterno al momento dell’esecuzione. La notazione utilizzata ` e





 Input(x);  dove x indica un nome simbolico.

I L’esecuzione consiste nel:

(i) Acquisire un nuovo valore, sia esso val (ii) Introdurre nello stato l’associazione x val

I Come nel caso dell’assegnamento, il punto (ii) comporta la rimozione dallo stato dell’eventuale associazione gi` a presente per il nome simbolico x

I La presenza di tale istruzione permette di descrivere algoritmi generali in cui non tutti i dati sono noti a priori, ma lo saranno solo al

momento dell’esecuzione.

Concetti di base della programmazione Pseudo-linguaggio per la specifica di algoritmi

Istruzioni di controllo: SEQUENZA

I Negli esempi visti in precedenza gli algoritmi sono stati descritti come sequenze di passi elementari del tipo

Passo 1. azione 1 Passo 2. azione 2 . . .

I Abbiamo utilizzato una sorta di numerazione per indicare l’ordine di esecuzione delle varie azioni: prima azione 1 poi azione 2 poi ....

I Nel linguaggio che stiamo introducendo, secondo le convenzioni sintattiche del C, una sequenza di azioni viene rappresentata

mediante un blocco _#

{

istruzione 1 istruzione 2 . . .

istruzione n

Concetti di base della programmazione Pseudo-linguaggio per la specifica di algoritmi

SEQUENZA (cont.)

I Scriveremo dunque {

istruzione 1 istruzione 2 . . .

}

ad indicare che l’ordine di esecuzione dei singoli passi ` e quello testuale del programma.

I Si noti che ogni istruzione viene eseguita a partire dallo stato

risultante dall’esecuzione dell’istruzione che la precede nella sequenza.

I Assegnamento e ingresso sono istruzioni semplici il blocco ` e

un’istruzione composta.

Concetti di base della programmazione Pseudo-linguaggio per la specifica di algoritmi

SEQUENZA: esempi

Stato iniziale Sequenza Stato Finale

{ x 10, y 20} { x = 5; x = x+y; } { x 25, y 20}

{ x 10, y 20} { x = x+1; y = x+1; } { x 11 , y 12 } { x 10, y 20} { x = x+y; y = x+y; } { x 30 , y 50 }

I In tutti gli esempi, lo stato finale si ottiene dall’esecuzione del secondo assegnamento nello stato intermedio risultante dall’esecuzione del primo assegnamento.

I Ad esempio, nel terzo caso:

Stato iniziale Prima istruzione Stato Intermedio { x 10, y 20} x = x+y; { x 30, y 20}

Stato intermedio Seconda istruzione Stato Finale

{ x 30, y 20} y = x+y; { x 30, y 50 }

Concetti di base della programmazione Pseudo-linguaggio per la specifica di algoritmi

Istruzioni di controllo: CONDIZIONALE

I Permette di determinare l’azione da intraprendere a seconda del verificarsi o meno di una condizione. La notazione utilizzata ` e la seguente





 if (condizione) istruzione1 else istruzione2  dove condizione indica una espressione booleana, e istruzione1 istruzione2 sono istruzioni (semplici o composte).

I L’esecuzione del condizionale if (C) S1 else S2 consiste nel (i) Calcolare il valore, sia esso val, dell’espressione booleana C (ii) Eseguire S1 se val ` e true, eseguire S2 se val ` e false.

I Si noti che la presenza dell’istruzione condizionale non ` e in conflitto con il requisito di non ambiguit` a degli algoritmi: l’azione da

intraprendere ` e univocamente determinata dal valore di verit` a della

condizione e dunque non vi ` e facolt` a di scelta da parte dell’esecutore.

Concetti di base della programmazione Pseudo-linguaggio per la specifica di algoritmi

CONDIZIONALE: esempi

Stato iniziale Condizionale Stato Finale if (x > y)

z = x ; else z = y ;

{ x 10, y 20} { x 10, y 20, z 20 }

{ x 10, y 5} { x 10, y 5, z 10 }

Concetti di base della programmazione Pseudo-linguaggio per la specifica di algoritmi

Istruzioni di controllo: RIPETIZIONE

I Consente di ripetere l’esecuzione di una istruzione (o sequenza di istruzioni) fino al verificarsi di una certa condizione (cfr. esempio del calcolo del prodotto tra due numeri).





 while (condizione) Istruzione  dove condizione indica una espressione booleana.

I Terminologia: in while (C) S , la condizione C ` e detta guardia e l’struzione S ` e detta corpo (del ciclo).

I L’esecuzione di while (C) S consiste nel

(i) Calcolare il valore, sia esso val, dell’espressione booleana C (ii) Se val ` e false, terminare l’esecuzione.

(iii) Se val ` e true, eseguire S e ripetere dal punto (i).

Concetti di base della programmazione Pseudo-linguaggio per la specifica di algoritmi

RIPETIZIONE

Esempio: Riformulazione del passo 4 dell’algoritmo per il prodotto (versione 2):

while (b>0) {

c = c+a;

b = b-1;

}

I Intuitivamente, l’esecuzione di

while (guardia) corpo corrisponde all’esecuzione di una sequenza del tipo

{ corpo corpo corpo ... corpo ...}

I In tale sequenza, ogni ripetizione dell’istruzione corpo viene detta iterazione del ciclo.

In generale, non ` e possibile determinare a priori il numero di iterazioni

Concetti di base della programmazione Pseudo-linguaggio per la specifica di algoritmi

RIPETIZIONE

I L’aspetto pi` u critico ` e il fatto che l’esecuzione di un ciclo pu` o essere fonte di non terminazione dell’esecuzione dell’intero algoritmo.

while (3>0) x = 0;

I Un ciclo siffatto provoca la non terminazione dell’esecuzione, dal momento che il valore di verit` a della guardia ` e sempre true e dunque l’esecuzione corrisponde ad una sequenza infinita

x = 0; x = 0; . . . ; x = 0; . . . .

I E compito di chi definisce l’algoritmo assicurare che i cicli presenti ` non diano luogo a non terminazione.

I La pratica programmativa, ed il buon senso, suggeriscono ad esempio di utilizzare cicli in cui:

- il valore di verit` a della guardia dipende dallo stato;

- l’esecuzione del corpo comporta modifiche di associazioni nello stato

dalle quali dipende il valore di verit` a della guardia.

Concetti di base della programmazione Pseudo-linguaggio per la specifica di algoritmi

RIPETIZIONE

I Le indicazioni appena viste non sono tuttavia sufficienti a garantire la terminazione dell’esecuzione. Si consideri ad esempio il ciclo:

while (x>0) x = x+1;

che soddisfa entrambi i requisiti richiesti, ma che pu` o non terminare nel caso in cui venga eseguito a partire da uno stato dove il valore associato al nome x ` e un valore positivo.

I A partire dagli anni ’70 sono stati sviluppati dei metodi formali per la

verifica di correttezza di programmi, che comprendono tecniche per la

dimostrazione formale di propriet` a di terminazione dei cicli.

Concetti di base della programmazione Pseudo-linguaggio per la specifica di algoritmi

Istruzioni di controllo: OUTPUT

I Permette di rendere visibile all’esterno la parte desiderata dello stato.

La notazione utilizzata ` e





 Output(x);  dove x indica un nome simbolico.

I L’esecuzione di questa istruzione consiste nel:

(i) Recuperare il valore, sia esso val, associato nello stato al nome simbolico x.

(ii) Produrre in uscita tale valore.

I Questa operazione non comporta la modifica dello stato. Nei

linguaggi di programmazione reali, l’esecuzione delle operazioni di

uscita produce di solito la visualizzazione di valori su supporti fisici

quali video, stampanti etc.

Concetti di base della programmazione Esempi d’uso dello pseudo-linguaggio

Problema: Calcolo del valore assoluto di un numero

Vediamo alcuni esempi di specifica di algoritmi che utilizzano lo pseudo-linguaggio.

Specifica:

Stato iniziale: { numero A } Stato finale: { risultato |A| } dove A indica un (generico) valore intero.

Algoritmo:

if (numero > 0)

risultato = numero;

else risultato = - numero;

Concetti di base della programmazione Esempi d’uso dello pseudo-linguaggio

Problema: Ordinare due interi positivi

Specifica:

Stato iniziale: { num1 A, num2 B }

Stato finale: { num1 max(A,B), num2 min(A,B) } Algoritmo:

if (num1 < num2) {

temp = num1;

num1 = num2;

num2 = temp;

}

else ;

Concetti di base della programmazione Esempi d’uso dello pseudo-linguaggio

Problema: Ordinare due interi positivi (cont.)

I Si noti l’utilizzo di un nome simbolico aggiuntivo (temp): ` e essenziale per poter effettuare correttamente lo scambio tra i valori associati ai due interi (a causa del carattere distruttivo dell’assegnamento e della sequenzialit` a dell’esecuzione).

I E facile verificare che una sequenza del tipo ` x = y;

y = x;

non consente, in generale, di scambiare i valori associati a x e y.

Esempio:

Stato iniziale Stato Intermedio { x 10, y 20} x = y; { x 20, y 20}

Stato intermedio Stato Finale

Concetti di base della programmazione Esempi d’uso dello pseudo-linguaggio

Problema: Elevamento a potenza

Specifica:

Stato iniziale: { base A, esponente B } con A>0 e B ≥0 Stato finale: { risultato A ^B }

I L’algoritmo si basa sulla seguente, ben nota, definizione di elevamento a potenza.

A ⁰ = 1

A ^B = A × A × . . . × A

| {z }

(se B > 0)

B volte

Concetti di base della programmazione Esempi d’uso dello pseudo-linguaggio

Algoritmo:

risultato = 1;

while (esponente > 0) {

risultato = risultato * base;

esponente = esponente - 1;

}

I Nell’algoritmo, si assume che i valori iniziali di base ed esponente

soddisfino i requisiti della specifica.

Concetti di base della programmazione Esempi d’uso dello pseudo-linguaggio

Input/Output

I Nei problemi visti fino ad ora non ci siamo preoccupati di acquisire i dati iniziali n´ e di produrre in uscita i risultati finali.

Esempio: Ordinare due valori interi acquisiti in input e stampare i valori ordinati.

Algoritmo:

Input(num1);

Input(num2);, if num1 < num2 {

temp = num1;

num1 = num2;

num2 = temp;

} else ;

Output(num1);

Output(num2);

Concetti di base della programmazione Esempi d’uso dello pseudo-linguaggio

Problema: Calcolare quoziente e resto della divisione tra due numeri naturali non nulli.

Specifica:

Stato iniziale: {x A, y B} con A,B > 0 Stato finale: {x A, y B, q Q, r R}

con A = Q · B + R e 0 ≤ R < B Algoritmo:

q = 0;

r = x;

while (r ≥ y) {

q = q + 1;

r = r - y;

}

Concetti di base della programmazione Esempi d’uso dello pseudo-linguaggio

Calcolare il MCD con l’algoritmo di Euclide

I Dati due naturali non nulli si calcola il MCD utilizzando le seguenti propriet` a:

MCD(x , x ) = x

MCD(x , y ) = MCD(x − y , y ) se x > y MCD(x , y ) = MCD(x , y − x ) se y > x

Specifica:

Stato iniziale: {x A, y B} con A,B > 0

Stato finale: {x MCD(A,B)}

Concetti di base della programmazione Esempi d’uso dello pseudo-linguaggio

Calcolare il MCD con l’algoritmo di Euclide (cont.)

Algoritmo:

while (x 6= y) {

if (x > y) x = x - y;

else

y = y - x;

}

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Rappresentazione binaria

I Per informazione intendiamo tutto quello che viene manipolato da un calcolatore:

I

numeri (naturali, interi, reali, . . . )

I

caratteri

I

immagini

I

suoni

I

programmi

I

. . .

I La pi` u piccola unit` a di informazione memorizzabile o elaborabile da un calcolatore, il bit, corrisponde allo stato di un dispositivo fisico che viene interpretato come 1 o 0.

I In un calcolatore tutte le informazioni sono rappresentate in forma binaria, come sequenze di 0 e 1.

I Per motivi tecnologici: distinguere tra due valori di una grandezza

fisica ` e pi` u semplice che non ad esempio tra dieci valori.

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Rappresentazione di numeri naturali

I Un numero naturale ` e un oggetto matematico, che pu` o essere

rappresentato mediante una sequenza di simboli di un alfabeto fissato.

I E importante distinguere tra numero e sua rappresentazione: il ` numerale “234” ` e la rappresentazione del numero 234.

I Si distinguono 2 tipi di rappresentazione:

additiva: ad es. le cifre romane

posizionale: una cifra contribuisce con un valore diverso al numero a seconda della posizione in cui si trova

I Noi consideriamo solo la rappresentazione posizionale.

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Rappresentazione posizionale

I Un numero ` e rappresentato da una sequenza finita di cifre di un certo alfabeto:





 c n−1 c n−2 · · · c ₁ c 0 = N b  c 0 viene detta cifra meno significativa

c n−1 viene detta cifra pi` u significativa

I Il numero b di cifre diverse (dimensione dell’alfabeto) ` e detto base del sistema di numerazione.

I Ad ogni cifra ` e associato un valore compreso tra 0 e b − 1.

Base Alfabeto Sistema

2 0, 1 binario

8 0, . . . , 7 ottale

10 0, . . . , 9 decimale

16 0, . . . , 9, A, . . . , F esadecimale

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

I Il significato di una sequenza di cifre (il numero N che essa rappresenta) dipende dalla base b:

c n−1 · b ⁿ⁻¹ + c n−2 · b ⁿ⁻² + · · · + c 1 · b ¹ + c 0 · b ⁰ =

n−1

X

i =0

c _i · b ⁱ = N

Esempio: Il numerale 101 rappresenta numeri diversi a seconda del sistema usato:

Sistema Base b 101 b Valore ₁₀

decimale 10 (101) 10 101

binario 2 (101) 2 5

ottale 8 (101) ₈ 65

esadecimale 16 (101) 16 257

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Intervallo di rappresentazione

I I numeri rappresentabili in base b con n posizioni (cifre) vanno da 0 a b ⁿ − 1.

3 cifre in base 10 : da 0 a 999 = 10 ³ − 1

8 cifre in base 2 : da 0 a 255 = 2 ⁸ − 1

16 cifre in base 2 : da 0 a 65 535 = 2 ¹⁶ − 1

32 cifre in base 2 : da 0 a 4 294 967 296 = 2 ³² − 1

2 cifre in base 16 : da 0 a 255 = 16 ² − 1

8 cifre in base 16 : da 0 a 4 294 967 296 = 16 ⁸ − 1

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Conversioni di base: da base b a base 10

I Usando direttamente

c _n−1 · b ⁿ⁻¹ + c _n−2 · b ⁿ⁻² + · · · + c ₁ · b ¹ + c ₀ · b ⁰ =

n−1

X

i =0

c _i · b ⁱ = N

esprimendo le cifre e b in base 10 (e facendo i conti in base 10) Esercizio

(domani) Scrivere l’algoritmo di conversione da base b a base 10.

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Conversioni di base: da base 10 a base b

N = c 0 + c 1 · b ¹ + c 2 · b ² + · · · + c k−1 · b ^k−1

= c ₀ + b · (c ₁ + b · (c ₂ + · · · + b · c _k−1 ) · · · )

I Vogliamo determinare le cifre c 0 , c 1 , . . . , c _k−1

I Consideriamo la divisione di N per b:

N = R + b · Q (0 ≤ R < b)

= c ₀ + b · (c ₁ + b · (· · · ))

⇓

R = c 0 ovvero, il resto R della divisione di N per b d` a c 0 (cifra meno significativa)

Q = c ₁ + b · (· · · )

I A partire dal quoziente Q si pu` o iterare il procedimento per ottenere

le cifre successive (fino a che Q diventa 0).

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Conversione da base 10 a base b

i = 0;

while (num ! = 0) { c[i] = num % b;

num = num / b;

i = i+1; }

N.B. Le cifre vengono determinate dalla meno significativa alla pi` u significativa.

Esempio: (25) 10 = (???) 2 = (11001) 2

N : b Q R cifra 25 : 2 12 1 c ₀ 12 : 2 6 0 c ₁ 6 : 2 3 0 c ₂ 3 : 2 1 1 c 3

1 : 2 0 1 c 4

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Rappresentazione di numeri interi

I Dobbiamo rappresentare anche il segno: si usa uno dei bit (quello pi` u significativo)

Rappresentazione tramite modulo e segno

I il bit pi` u significativo rappresenta il segno

I le altre n − 1 cifre rappresentano il valore assoluto

I problemi:

I

doppia rappresentazione per lo zero (00 · · · 00 e 10 · · · 00)

I

le operazioni aritmetiche sono complicate (analisi per casi)

=⇒ invece della rappresentazione tramite modulo e segno si usa una

rappresentazione in complemento alla base

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Rappresentazione in complemento alla base

In quanto segue b indica la base e n indica il numero complessivo di cifre.

I Con base b e n cifre, abbiamo a disposizione b ⁿ configurazioni distinte.

I Utilizziamo met` a delle configurazioni per rappresentare numeri positivi e l’altra met` a per rappresentare numeri negativi.

||X || =

( X se X ≥ 0

b ⁿ − |X | se X < 0

I in questo modo si rappresentano gli interi relativi nell’intervallo [−b ⁿ /2, b ⁿ /2)

I

se X ≥ 0: ||X || ` e compresa in [0, b ⁿ /2)

I

se X < 0: ||X || ` e compresa in [b ⁿ /2, b ⁿ )

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Rappresentazione in complemento alla base

N b = 10 e n = 1 b = 2 e n = 3

−5 5

−4 6 100

−3 7 101

−2 8 110

−1 9 111

0 0 000

1 1 001

2 2 010

3 3 011

4 4

I se b = 2 =⇒ rappresentazione in complemento a 2

I

rappresentazione degli interi relativi nell’intervallo [−2 ⁿ⁻¹ , 2 ⁿ⁻¹ )

I

positivi: la cifra pi` u significativa ` e 0 (rappresentati nella parte inferiore dell’intervallo)

I

negativi: la cifra pi` u significativa ` e 1 (rappresentati nella parte

superiore dell’intervallo)

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Operazione di complementazione

Vogliamo determinare un algoritmo per determinare la rappresentazione in complemento alla base di −X, data quella di X . Indipendentemente dal segno di X , abbiamo:

||X || + || − X || = |X | + b ⁿ − |X | = b ⁿ per cui

|| − X || = b ⁿ − ||X ||

o equivalentemente

|| − X || = b ⁿ − 1 − ||X || + 1

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Operazione di complementazione

I Supponiamo:

||X || =

n−1

X

i =0

c i · b ⁱ

e ricordiamo che la rappresentazione di b ⁿ − 1 ` e

n−1

X

i =0

(b − 1) · b ⁱ

I Otteniamo:

|| − X || = b ⁿ − 1 − ||X || + 1

= (

n−1

X

i =0

(b − 1) · b ⁱ ) − (

n−1

X

i =0

c _i · b ⁱ ) + 1

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Operazione di complementazione

I Sia ora k la prima posizione significativa di ||X ||, ovvero la prima cifra (a partire da destra) diversa da 0. Abbiamo allora:

|| − X || = (

n−1

X

i =0

(b − 1) · b ⁱ ) − (

n−1

X

i =0

c i · b ⁱ ) + 1

= (

n−1

X

i =0

(b − 1) · b ⁱ ) − (

n−1

X

i =k

c _i · b ⁱ ) + 1

= (

n−1

X

i =k+1

((b − 1) − c i ) · b ⁱ ) + ((b − 1) − c k ) · b ^k +

(

k−1

X

i =0

(b − 1) · b ⁱ ) + 1

k−1

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Operazione di complementazione

I Sia ora k la prima posizione significativa di ||X ||, ovvero la prima cifra (a partire da destra) diversa da 0. Abbiamo allora:

|| − X || = (

n−1

X

i =0

(b − 1) · b ⁱ ) − (

n−1

X

i =0

c i · b ⁱ ) + 1

= (

n−1

X

i =0

(b − 1) · b ⁱ ) − (

n−1

X

i =k

c _i · b ⁱ ) + 1

= (

n−1

X

i =k+1

((b − 1) − c i ) · b ⁱ ) + ((b − 1) − c k ) · b ^k + b ^k

I Osserviamo ora che (

k−1

P

i =0

(b − 1) · b ⁱ ) + 1 = b ^k .

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Operazione di complementazione

|| − X || = (

n−1

X

i =k+1

((b − 1) − c i ) · b ⁱ ) + ((b − 1) − c _k ) · b ^k + b ^k

= (

n−1

X

i =k+1

((b − 1) − c i ) · b ⁱ ) + (b − c k ) · b ^k

I L’ultimo addendo ` e 0, poich` e c _i = 0, per ogni i = 0, . . . , k − 1.

I Come possiamo leggere quanto ottenuto?

La rappresentazione di −X si ottiene da quella di X : 1. ricopiando gli zeri meno significativi

2. complementando alla base la prima cifra significativa

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Operazione di complementazione

|| − X || = (

n−1

X

i =k+1

((b − 1) − c i ) · b ⁱ ) + ((b − 1) − c k ) · b ^k + b ^k

= (

n−1

X

i =k+1

((b − 1) − c _i ) · b ⁱ ) + (b − c _k ) · b ^k + (

k−1

X

i =0

c _i · b ⁱ )

I L’ultimo addendo ` e 0, poich` e c _i = 0, per ogni i = 0, . . . , k − 1.

I Come possiamo leggere quanto ottenuto?

La rappresentazione di −X si ottiene da quella di X : 1. ricopiando gli zeri meno significativi

2. complementando alla base la prima cifra significativa

3. complementando alla base meno uno le rimanenti cifre

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Operazione di complementazione

Esempio: b = 3, n = 4, ||X || = 0210 (dunque X = (21) 10 )

|| − X || = 2020

Verifichiamo:

I 2020 = (60) 10

I 3 ⁴ − 60 = 81 − 60 = 21 = | − X |

Nel caso del complemento a 2 abbiamo pi` u semplicemente:

I si lasciano inalterate tutte le cifre fino al primo 1 compreso

I si invertono le rimanenti cifre

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Complemento a 2

Esempio: Rappresentazione di −298 in complemento a 2:

I 298 = 256 + 32 + 8 + 2

I ||298|| = 100101010 = 0100101010

I || − 298|| = 1011010110

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Operazioni su interi relativi in complemento a 2

Somma di due numeri

I si effettua bit a bit

I non ` e necessario preoccuparsi dei segni

I il risultato sar` a corretto (in complemento a 2 se negativo)

I pu` o verificarsi trabocco (overflow) =⇒ il risultato non ` e corretto

Si verifica quando il numero di bit a disposizione non ` e sufficiente per

rappresentare il risultato.

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Operazioni su interi relativi in complemento a 2

Esempio: n = 5, ±9 ± 3, ±9 ± 8

intervallo di rappresentazione: da −2 ⁴ a 2 ⁴ − 1 (da −16 a 15)

rip. 00011 11001 00111 11111

+9 01001 +9 01001 -9 10111 -9 10111

+3 00011 -3 11101 +3 00011 -3 11101

+12 01100 +6 00110 -6 11010 -12 10100

In questi casi non si ha trabocco.

rip. 01000 10000

+9 01001 -9 10111

+8 01000 -8 11000

-15 10001 +15 01111

(e non +17) (e non −17)

Si ha trabocco quando il riporto sul bit di segno ` e diverso dall’ultimo

riporto.

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Operazioni su interi relativi in complemento a 2

Differenza tra due numeri: si somma al primo il complemento del secondo

Esempio: n = 5, intervallo di rappresentazione: da −16 a 15

rip. 11111

+9 01001 -9 10111

0 00000

11001

+9 01001

-3 11101

+6 00110

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Numeri frazionari

I Numeri reali compresi tra 0 e 1: si rappresentano comunemente come N = 0.c −1 c −2 . . . c −n

I Il peso delle cifre dipende, al solito, dalla loro posizione e dalla base prescelta

N _b = c −1 · b ⁻¹ + c −2 · b ⁻² + · · · + c −n · b ⁻ⁿ =

−1

X

i =−n

c _i · b ⁱ

Esempio: Consideriamo b = 10 ed il numero 0.587

0.587 ₁₀ = 5 · 10 ⁻¹ + 8 · 10 ⁻² + 7 · 10 ⁻³

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Numeri frazionari

N _b =

−1

X

i =−n

c _i · b ⁱ (•)

I Nel caso di un numero frazionario in binario, possiamo usare la (•) per convertirlo in base 10

Esempio: Convertiamo in base 10 il numero frazionario binario 0.1011 2

0.1011 2 = 1 · 2 ⁻¹ + 1 · 2 ⁻³ + 1 · 2 ⁻⁴ = 0.6875 10

I La rappresentazione dei numeri frazionari pu` o introdurre

approssimazioni dovute alla limitatezza delle cifre dopo la virgola.

−n

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Conversione di un numero frazionario da base 10 a base 2

I Il metodo pi` u semplice consiste nell’effettuare una sequenza di moltiplicazioni per 2 prendendo ad ogni passo la parte intera del risultato come cifra binaria della rappresentazione

I Esempio: Convertiamo 0.125 in base 2 0.125 × 2 = 0.25 0

0.25 × 2 = 0.5 0 0.5 × 2 = 1.0 1

I In questo caso abbiamo una rappresentazione esatta su 3 cifre (0.125 = 1/8)

0.125 10 = 0.001 2

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Conversione di un numero frazionario da base 10 a base 2

I Esempio: Convertiamo 0.587 10 in base 2 0.587 × 2 = 1.174 1

0.174 × 2 = 0.348 0 0.348 × 2 = 0.696 0 0.696 × 2 = 1.392 1 0.392 × 2 = 0.784 0 0.784 × 2 = 1.568 1 0.568 × 2 = . . .

I Quindi la rappresentazione di 0.587 10 in base 2 ` e:

I

0.1001 2 con 4 cifre (approssimazione accurata entro 2 ⁻⁴ )

I

0.100101 ₂ con 6 cifre (approssimazione accurata entro 2 ⁻⁶ )

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

L’aritmetica reale

I L’insieme dei reali (e dei razionali) ` e infinito =⇒ non ` e possibile rapprentarlo tutto

Rappresentazione in virgola fissa

Si rappresentano separatamente, usando un numero fissato di cifre

• parte intera e,

• parte frazionaria

(si usa una virgola per separare le due parti)

N _b = c _n−1 c _n−2 · · · c ₁ c ₀ , c −1 c −2 · · · c _−m

rappresenta il numero

N = c n−1 · b ⁿ⁻¹ + · · · + c 0 · b ⁰ + c −1 · b ⁻¹ + · · · + c −m · b ^−m

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

L’aritmetica reale

I Limitazioni della rappresentazione:

I

k bit per la parte intera =⇒ (−2 ^k , 2 ^k )

I

m bit per la parte frazionaria =⇒ precisione ≤ 2 ^−m Rappresentazione in virgola mobile (floating point) Utilizza la notazione esponenziale. Si esprime il numero come prodotto di due parti

X = m · b ^e

Esempio:

1150 = 1.15 × 10 ³ ma anche

1150 = 0.115 × 10 ⁴

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Rappresentazione in virgola mobile

Rappresentazione in forma normalizzata in base b X = m · b ^e

I e ` e la caratteristica in base b di X : intero relativo

I m ` e la mantissa in base b di X : numero frazionario tale che 1/b ≤ |m| < 1

I Esempio:

1150 = 0.115 × 10 ⁴

mantissa caratteristica

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Rappresentazione in virgola mobile

I Se la caratteristica ` e rappresentata dalla sequenza di cifre c ₁ c ₂ c ₃ · · ·

allora rappresenta il valore

c 1 · b ⁻¹ + c 2 b ⁻² + · · ·

Esempio: X = (5) 10 = (101) 2 che normalizzato diventa:

m = |m| = (0.101 · · · 0000) ₂

e = (11) 2

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Rappresentazione in virgola mobile

I Fissati:

I

k bit per mantissa

I

h bit per caratteristica

I

1 bit per il segno

l’insieme di reali rappresentabili ` e fissato (e limitato) (0.1) 1/2 ≤ |m| ≤

k

P

i =1

2 ⁻ⁱ (0.11 . . . 1)

|e| ≤ 2 ^h−1 − 1

I Questo fissa anche massimo e minimo (in valore assoluto) numero rappresentabile.

I Assunzione realistica: reali rappresentati con 32 bit:

I

24 bit per la mantissa

I

7 bit per la caratteristica (in complemento)

I

1 bit per il segno della mantissa (0 positivo, 1 negativo)

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Rappresentazione in virgola mobile

Insieme F dei numeri rappresentabili in virgola mobile

I sottoinsieme finito dei numeri razionali rappresentabili (con n bit)

I simmetrico rispetto allo 0

I gli elementi non sono uniformemente distribuiti sull’asse reale

I

densi intorno allo 0

I

radi intorno al massimo rappresentabile m

= 0.10, m

= 0.11, e

= 5 X

= 0.10 × 10

= 10000 X

= 0.11 × 10

= 11000

I molti razionali non appartengono ad F (ed es. 1/3, 1/5, . . . )

I non ` e chiuso rispetto ad addizioni e moltiplicazioni

I per rappresentare un reale X si sceglie l’elemento di F pi` u vicino ad X

I la funzione che associa ad un reale X l’elemento di F pi` u vicino ad X

Rappresentazione dell’informazione (cenni) Rappresentazione informazione

Limitazioni aritmetiche

Dovute al fatto che il numero di bit usati per rappresentare un numero ` e limitato

I perdita di precisione

I arrotondamento: mantissa non sufficiente a rappresentare tutte le cifre significative del numero

I errore di overflow: caratteristica non sufficiente (numero troppo grande)

I errore di underflow: numero troppo piccolo viene rappresentato come 0

Formati standard proposti da IEEE (Institute of Electrical and Electronics Engineers)

I singola precisione: 32 bit

I doppia precisione: 64 bit

I quadrupla precisione: 128 bit

Sistemi di elaborazione Architettura del calcolatore

Architettura di Von Neumann

I L’architettura ` e ancora quella classica sviluppata da Von Neumann nel 1947.

I L’architettura di Von Neumann riflette le funzionalit` a richieste da un elaboratore:

I

memorizzare i dati e i programmi =⇒ memoria principale

I

i dati devono essere elaborati =⇒ unit` a di elaborazione (CPU)

I

comunicazione con l’esterno =⇒ unit` a di ingresso/uscita (periferiche)

I

le componenti del sistema devono scambiarsi informazioni =⇒ bus di

sistema

Sistemi di elaborazione Architettura del calcolatore

Memoria Secondaria Memoria

Principale

Unit `a di Ingresso

Unit `a di Uscita

Bus CPU

Unit `a periferiche

Tra le periferiche evidenziamo la memoria secondaria.

Sistemi di elaborazione Architettura del calcolatore

Memoria centrale (o RAM)

h bit 0 1 2 .. . 2 ^k-1

I ` e una sequenza di celle di memoria (dette parole), tutte della stessa dimensione

I ogni cella ` e costituita da una sequenza di bit

I il numero h di bit di una cella di memoria (dimensione) dipende dall’elaboratore, ed ` e un multiplo di 8: 8, 16, 32, 64

I ogni cella di memoria ` e identificata in modo univoco dal suo indirizzo

I il numero k di bit necessari per l’indirizzo dipende dal numero di celle

di memoria

Sistemi di elaborazione Architettura del calcolatore

Memoria centrale

0 1 2

2

− 1

k

h

.. .

.. . h

972 CPU

registro

registro indirizzi (RI)

dati (RD) bus indirizzi

bus dati

11001010

Operazione di lettura:

1. CPU scrive l’indirizzo della cella di memoria da cui leggere nel registro indirizzi (RI)

2. esegue l’operazione (“apre i circuiti”)

3. il valore della cella indirizzata viene trasferito nel registro dati (RD)

Operazione di scrittura: al contrario

Sistemi di elaborazione Architettura del calcolatore

Memoria centrale

Caratteristiche principali

I ` e una memoria ad accesso casuale, ossia il tempo di accesso ad una cella di memoria ` e indipendente dalla posizione della cella =⇒ viene chiamata RAM (random access memory)

I pu` o essere sia letta che scritta

scrittura distruttiva – lettura non distruttiva

I alta velocit` a di accesso

I ` e volatile (si perde il contenuto quando si spegne il calcolatore) Dimensione della memoria: misurata in byte (1 byte=8 bit)

Kilobyte = 2 ¹⁰ ∼ 10 ³ byte

Megabyte = 2 ²⁰ ∼ 10 ⁶ byte

Gigabyte = 2 ³⁰ ∼ 10 ⁹ byte

Sistemi di elaborazione Architettura del calcolatore

Memoria secondaria

I non volatile

I capacit` a maggiore della memoria centrale (decine di GB)

I tempo di accesso lento rispetto alla memoria centrale

I accesso sequenziale e non casuale

I tipi di memoria secondaria: dischi rigidi, floppy, CDROM, CDRW, DVD, nastri, . . .

Bus di sistema suddiviso in tre parti:

I bus indirizzi: k bit

I bus dati: h bit

I bus comandi: trasferisce i comandi tra le varie unit` a

=⇒ parallelismo (attualmente si arriva a 128 bit)

Sistemi di elaborazione Architettura del calcolatore

CPU (Central Processing Unit)

I coordina le attivit` a di tutte le componenti del calcolatore

I interpreta ed esegue le istruzioni del programma

I 3 componenti principali:

unit` a logico-aritmetica (ALU): effettua i calcoli

unit` a di controllo: coordinamento di tutte le operazioni registri: celle di memoria ad accesso molto veloce

I

registro istruzione corrente (IR): contiene l’istruzione in corso di esecuzione

I

contatore di programma (PC): contiene l’indirizzo della prossima istruzione da eseguire

I

accumulatori: utilizzati dalla ALU per gli operandi ed il risultato

I

registro dei flag: memorizza alcune informazioni sul risultato dell’ultima operazione (carry, zero, segno, overflow, . . . )

I

registro interruzioni: utilizzato per la comunicazione con le periferiche

registro indirizzi (RI) e registro dati (RD) per il trasferimento da e

Sistemi di elaborazione Architettura del calcolatore

CPU

Ciclo dell’unit` a di controllo

I Tutte le attivit` a interne alla CPU sono regolate da un orologio (clock) che genera impulsi regolari ad una certa frequenza (ad es. 800 MHz, 1 GHz, 2 GHz, . . . ).

I Il programma ` e memorizzato in celle di memoria consecutive, sulle quali l’unit` a di controllo lavora eseguendo il ciclo di

prelievo — decodifica — esecuzione while macchina in funzione do

preleva dalla memoria l’istruzione indirizzata da PC e caricala in IR

(aggiorna PC in modo che indirizzi la prossima istruzione) decodifica l’istruzione in IR

esegui l’istruzione

endwhile

Sistemi di elaborazione Architettura del calcolatore

CPU - Ciclo dell’unit` a di controllo

1. fase di prelievo (fetch)

l’unit` a di controllo acquisisce dalla memoria l’istruzione indirizzata da PC e aggiorna PC in modo che indirizzi la prossima istruzione

PC = PC + n

dove n ` e la lunghezza in byte dell’istruzione prelevata 2. fase di decodifica

viene decodificato il tipo di istruzione per determinare quali sono i passi da eseguire per la sua esecuzione

3. fase di esecuzione

vengono attivate le componenti che realizzano l’azione specificata

Sistemi di elaborazione Architettura del calcolatore

Istruzioni

Ogni istruzione ` e costituita da:

01001001 00110011 codice operativo operandi Tipi di istruzione

I

istruzioni di trasferimento dati – da e verso la memoria centrale – ingresso/uscita

I

istruzioni logico/aritmetiche

I

istruzioni di controllo – istruzioni di salto

Le istruzioni dettano il flusso del programma. Vengono eseguite in

sequenza, a meno che non vi sia un’istruzione di controllo che altera

il normale flusso (istruzione di salto).

Sistemi di elaborazione Dal codice sorgente al codice macchina

Dal codice sorgente al codice macchina

I concetti di algoritmo e di programma permettono di astrarre dalla reale struttura del calcolatore, che comprende sequenze di 0 e 1, ovvero un linguaggio macchina.

Livelli di astrazione ai quali possiamo vedere i programmi:

I Linguaggio macchina (o codice binario): livello pi` u basso

I

un programma ` e una sequenza di 0 e 1 (suddivisi in parole) che codificano le istruzioni

I

dipende dal calcolatore

I Linguaggio assemblativo: livello intermedio

I

dipende dal calcolatore e le sue istruzioni sono in corrispondenza 1-1 con le istruzioni in linguaggio macchina

I

istruzioni espresse in forma simbolica =⇒ comprensibile da un umano

I Linguaggi ad alto livello: (e.g. C, Pascal, C++, Java, Fortran, . . . )

I

si basano su costrutti non elementari, comprensibili da un umano

I

istruzioni pi` u complesse di quelle eseguibili da un calcolatore