Programmi Programmi

(1)

Programmi Programmi

Corso di Programmazione Corso di Programmazione CdS: CdS: Informatica e Tecnologie Informatica e Tecnologie per la Produzione di Software per la Produzione di Software Nicola Fanizzi Nicola Fanizzi

fanizzi@di.uniba.it

(2)

2 2

Comunicazione Comunicazione

dell’algoritmo all’elaboratore dell’algoritmo all’elaboratore

 Linguaggi non ambigui e sequenziali Linguaggi non ambigui e sequenziali

 Comprensibili alla macchina Comprensibili alla macchina

 Requisiti per la descrizione Requisiti per la descrizione

 Univoca Univoca



Non dà adito ad interpretazioni errate Non dà adito ad interpretazioni errate

 Completa Completa



Prevede tutte le azioni necessarie Prevede tutte le azioni necessarie

 Ripetibile Ripetibile



Garantisce un buon risultato se eseguita da più Garantisce un buon risultato se eseguita da più esecutori con medesime caratteristiche

esecutori con medesime caratteristiche

(3)

3 3

Programmazione Programmazione

 Descrizione del procedimento di soluzione Descrizione del procedimento di soluzione di un problema ad un esecutore meccanico di un problema ad un esecutore meccanico

 Poiché l’esecutore è meccanico, Poiché l’esecutore è meccanico, consiste nel

consiste nel

 Ricondurre il problema da risolvere a problemi Ricondurre il problema da risolvere a problemi primitivi

primitivi



Eseguibili come insieme di azioni primitive Eseguibili come insieme di azioni primitive

 Organizzare ed utilizzare le “risorse” Organizzare ed utilizzare le “risorse”

dell’elaboratore

(4)

4 4

Programmazione Programmazione

 Trasformazione della descrizione di un Trasformazione della descrizione di un algoritmo in un

algoritmo in un messaggio messaggio

 Insieme di istruzioni codificate in un Insieme di istruzioni codificate in un

linguaggio interpretabile da un esecutore linguaggio interpretabile da un esecutore

 Passa attraverso un’astrazione Passa attraverso un’astrazione

 Sia Sia delle delle operazioni operazioni che il procedimento che il procedimento prevede

prevede

 Sia Sia degli degli oggetti oggetti su cui il procedimento deve su cui il procedimento deve operare

operare

(5)

5 5

Programmazione Programmazione

 Metodologie Metodologie

 Astrazione Astrazione



Oggetti Oggetti



Azioni Azioni

 Tecniche Tecniche

 Strumenti Strumenti

 Linguaggi Linguaggi

 Ambienti Ambienti

(6)

6 6

Programma Programma

 Traduzione della procedura di soluzione Traduzione della procedura di soluzione in un linguaggio comprensibile alla

in un linguaggio comprensibile alla macchina

macchina

con indicazioni sui dati di ingresso e uscita con indicazioni sui dati di ingresso e uscita

 Comunica al calcolatore istruzioni Comunica al calcolatore istruzioni operative

operative

 Quali dati di ingresso deve trattare Quali dati di ingresso deve trattare

 Come deve operare su questi dati Come deve operare su questi dati

 Quali dati deve dare come risultato Quali dati deve dare come risultato

(7)

7 7

Programma Programma

 Procedura eseguibile su calcolatore, che Procedura eseguibile su calcolatore, che

rappresenta una soluzione ad un problema rappresenta una soluzione ad un problema

 Risultato di un lavoro di analisi e progetto che Risultato di un lavoro di analisi e progetto che inizia dalla formulazione del problema

inizia dalla formulazione del problema

 Corrisponde alla tripla Corrisponde alla tripla

(Dati, Algoritmo, Risultati) (Dati, Algoritmo, Risultati)



[Wirth] Algoritmi + Strutture Dati = Programmi [Wirth] Algoritmi + Strutture Dati = Programmi

(8)

8 8

Programma Programma

 Traduzione di un metodo di soluzione Traduzione di un metodo di soluzione

eseguibile in un linguaggio comprensibile eseguibile in un linguaggio comprensibile

alla macchina alla macchina

 Descrive come vanno elaborati insiemi di Descrive come vanno elaborati insiemi di valori che rappresentano le entità del

valori che rappresentano le entità del problema

problema

 Usa rappresentazioni simboliche per Usa rappresentazioni simboliche per estendere l’applicabilità del metodo di estendere l’applicabilità del metodo di

soluzione a valori diversi soluzione a valori diversi



Uso di variabili Uso di variabili

(9)

9 9

Dati Dati

 Entità su cui lavora il programma Entità su cui lavora il programma

 Costanti Costanti

 Variabili Variabili

 Rappresentati come sequenze di bit Rappresentati come sequenze di bit

 Nei linguaggi ad alto livello il programmatore Nei linguaggi ad alto livello il programmatore può ignorare i dettagli della rappresentazione può ignorare i dettagli della rappresentazione



Tipo di dato Tipo di dato

(10)

10 10

Istruzioni Istruzioni

 Operative Operative

 Lavorano su rappresentazioni delle entità del Lavorano su rappresentazioni delle entità del problema

problema

 Dichiarative Dichiarative

 Consentono di definire come interpretare e Consentono di definire come interpretare e

rappresentare tali entità in termini di variabili rappresentare tali entità in termini di variabili

nel programma nel programma



Totale caratterizzazione mediante la definizione di: Totale caratterizzazione mediante la definizione di:

 Un nome Un nome

 Un tipo Un tipo

(11)

11 11

Istruzioni Dichiarative Istruzioni Dichiarative

 Definiscono le aree di memoria in cui sono Definiscono le aree di memoria in cui sono

conservati i dati cui fa riferimento un algoritmo conservati i dati cui fa riferimento un algoritmo



Predispongono le posizioni di memoria da utilizzare Predispongono le posizioni di memoria da utilizzare



Associano un nome a ciascuna di esse Associano un nome a ciascuna di esse



Identificatore Identificatore



Determinano il tipo di dati che vi possono essere Determinano il tipo di dati che vi possono essere memorizzati

memorizzati



Insieme dei valori permessi Insieme dei valori permessi



Insieme delle operazioni applicabili Insieme delle operazioni applicabili

(12)

12 12

Tipi di Istruzioni Tipi di Istruzioni

 Un linguaggio di programmazione dispone di: Un linguaggio di programmazione dispone di:



Istruzioni di ingresso Istruzioni di ingresso



Permettono all’esecutore di conoscere informazioni fornite Permettono all’esecutore di conoscere informazioni fornite dall’esterno

dall’esterno



Istruzioni di uscita Istruzioni di uscita



Permettono all’esecutore di notificare all’utente i risultati Permettono all’esecutore di notificare all’utente i risultati ottenuti dall’elaborazione

ottenuti dall’elaborazione



Istruzioni operative Istruzioni operative



Permettono di effettuare calcoli o, comunque, operazioni Permettono di effettuare calcoli o, comunque, operazioni sulle entità astratte rappresentanti gli elementi del problema sulle entità astratte rappresentanti gli elementi del problema



Strutture di controllo Strutture di controllo

(13)

13 13

Istruzioni di Istruzioni di Ingresso/Uscita Ingresso/Uscita

 Livello di descrizione dell’algoritmo Livello di descrizione dell’algoritmo

 Necessità di indicare i dati su cui operare Necessità di indicare i dati su cui operare

 Livello di programma Livello di programma

 Necessità di comunicare i dati e i risultati Necessità di comunicare i dati e i risultati



Istruzioni di lettura e scrittura Istruzioni di lettura e scrittura

(14)

14 14

Istruzioni di Uscita Istruzioni di Uscita

 Consentono di notificare all’utente il valore di Consentono di notificare all’utente il valore di una variabile del programma

una variabile del programma



Visualizzazione, stampa, … Visualizzazione, stampa, …

 Attivano un’operazione di scrittura Attivano un’operazione di scrittura



Copiatura su un supporto esterno Copiatura su un supporto esterno



carta, nastri e dischi magnetici, display, … carta, nastri e dischi magnetici, display, …

del contenuto di un’area di memoria denotata dal del contenuto di un’area di memoria denotata dal nome della variabile che compare nell’istruzione di nome della variabile che compare nell’istruzione di scrittura

scrittura

 Esempio: Esempio: write y write y

(15)

15 15

Istruzioni Dichiarative Istruzioni Dichiarative

Variabili Variabili

 Forniscono una lista contenente i nomi Forniscono una lista contenente i nomi

scelti per le variabili e i tipi corrispondenti scelti per le variabili e i tipi corrispondenti

 Convenzione: indicare Convenzione: indicare tutte tutte le variabili le variabili

 Necessarie nei linguaggi di Necessarie nei linguaggi di programmazione

programmazione

 Nel programma si fa riferimento agli indirizzi Nel programma si fa riferimento agli indirizzi

delle aree di memoria in cui sono conservati i

dati dati

(16)

16 16

Variabile Variabile

 Nome simbolico per denotare un’area di Nome simbolico per denotare un’area di memoria e, tramite essa, il valore

memoria e, tramite essa, il valore contenuto

contenuto

 Contiene una rappresentazione di un oggetto Contiene una rappresentazione di un oggetto su cui l’algoritmo opera

su cui l’algoritmo opera

 Memorizzazione di un valore Memorizzazione di un valore



Istruzioni di ingresso Istruzioni di ingresso



Istruzioni di assegnamento Istruzioni di assegnamento

(17)

17 17

Variabile I 2 Variabile I 2

 Caratterizzata da Caratterizzata da

 Un nome Un nome



Identificatore Identificatore

 Un valore Un valore

 Un tipo Un tipo



Attributo che specifica l’insieme di valori che la Attributo che specifica l’insieme di valori che la variabile può assumere

variabile può assumere

(18)

18 18

Variabile / 3 Variabile / 3

 Rappresenta una Rappresenta una locazione locazione di memoria del di memoria del computer, contraddistinta da uno specifico computer, contraddistinta da uno specifico

indirizzo

indirizzo , che contiene il , che contiene il valore valore su cui su cui applicare le istruzioni del programma

applicare le istruzioni del programma

 Un identificatore denota una coppia Un identificatore denota una coppia



Posizione di memoria Posizione di memoria



Quantità in essa contenuta Quantità in essa contenuta



Una limitazione nel rappresentare dati di tipo numerico o Una limitazione nel rappresentare dati di tipo numerico o

alfanumerico viene dalle dimensioni limitate della memoria

(19)

19 19

Tipo Tipo

 Attributo di una variabile che ne specifica ed Attributo di una variabile che ne specifica ed individua:

individua:



L’insieme dei valori che la var. può assumere L’insieme dei valori che la var. può assumere



L’insieme di operazioni effettuabili sulla var. L’insieme di operazioni effettuabili sulla var.



Il modo con cui ci si può riferire alla var. Il modo con cui ci si può riferire alla var.

 Per parlarne in termini formali è utile introdurre Per parlarne in termini formali è utile introdurre il concetto di

il concetto di algebra di dati algebra di dati



Esempio: Esempio:

Stipendio: numero intero non negativo

(20)

20 20

Algebra di Dati Algebra di Dati

 Famiglia di insiemi Famiglia di insiemi



Insiemi di dati Insiemi di dati

 Famiglia di operatori sui dati Famiglia di operatori sui dati



Operatori Operatori

 Repertorio di simboli per indicare l’insieme dei Repertorio di simboli per indicare l’insieme dei dati dati



Nomi Nomi

 Repertorio di simboli per indicare gli operatori Repertorio di simboli per indicare gli operatori

 Repertorio di simboli per indicare elementi Repertorio di simboli per indicare elementi singoli degli insiemi di dati

singoli degli insiemi di dati

(21)

21 21

Algebra di Dati Algebra di Dati

Esempio Esempio

 Famiglia di insiemi Famiglia di insiemi



Numeri interi Numeri interi



Valori logici Valori logici

 Famiglia di operatori Famiglia di operatori



Operatori aritmetici Operatori aritmetici



Somma, sottrazione, moltiplicazione, divisione, modulo Somma, sottrazione, moltiplicazione, divisione, modulo



Operatori per i valori logici Operatori per i valori logici



Negazione, congiunzione, disgiunzione, ... Negazione, congiunzione, disgiunzione, ...



Operatori di confronto fra interi Operatori di confronto fra interi



Maggiore (stretto), minore (stretto), uguale, diverso Maggiore (stretto), minore (stretto), uguale, diverso

(22)

22 22

Algebra di Dati Algebra di Dati

Esempio Esempio

 Nomi Nomi

int int , boolean , boolean per gli insiemi di dati per gli insiemi di dati

+, + , – – , , ·, · , / / per gli operatori aritmetici per gli operatori aritmetici

!, ! , && && , , || || per gli operatori logici per gli operatori logici

<, < , = = , , >, > , ≤ ≤ , , ≠ ≠ , , ≥ ≥ per i confronti fra interi per i confronti fra interi

 Costanti Costanti



Ogni intero è indicato da una sequenza di cifre Ogni intero è indicato da una sequenza di cifre decimali, eventualmente precedute da

decimali, eventualmente precedute da + + o o – –



Interpretata secondo la notazione decimale Interpretata secondo la notazione decimale



I valori logici sono di solito indicati dalle costanti I valori logici sono di solito indicati dalle costanti

true true e e false false

(23)

23 23

Algebra di Dati Algebra di Dati

 Ogni linguaggio di programmazione Ogni linguaggio di programmazione propone

propone

 Dati Dati

 Operatori Operatori



Funzioni che Funzioni che

 Prendono come argomenti dei dati Prendono come argomenti dei dati

 Restituiscono dati come risultati Restituiscono dati come risultati



Argomenti e risultati sono dati di tipo prestabilito Argomenti e risultati sono dati di tipo prestabilito all’atto della definizione dell’operatore

all’atto della definizione dell’operatore

(24)

24 24

Algebra di Dati Algebra di Dati

 Caratteristiche dipendenti da Caratteristiche dipendenti da



la famiglia di insiemi la famiglia di insiemi



la famiglia di operatori la famiglia di operatori



Possono essere combinati per ottenere espressioni Possono essere combinati per ottenere espressioni

 Dunque: Dunque:



Un dato indica un valore che una variabile può Un dato indica un valore che una variabile può assumere

assumere



Un tipo di dato è un modello matematico Un tipo di dato è un modello matematico che sta ad che sta ad indicare una collezione di valori sui quali sono

indicare una collezione di valori sui quali sono ammesse certe operazioni

ammesse certe operazioni

(25)

25 25

Tipo Tipo

 Tripla Tripla

T = <D, C, O>

 Dominio Dominio

 Costanti Costanti

 Operatori Operatori



Funzioni Funzioni



Predicati Predicati

(26)

26 26

Tipo Tipo

Esempio Esempio

 Tipo dei complessi Tipo dei complessi



Dominio Dominio



Sottoinsieme dei numeri complessi Sottoinsieme dei numeri complessi



Costanti Costanti



Parte reale Parte reale



Parte immaginaria Parte immaginaria



Operazioni Operazioni



Addizione Addizione + : complesso + : complesso × × complesso complesso → → complesso complesso



Non ci interessiamo della rappresentazione interna Non ci interessiamo della rappresentazione interna dei valori e delle operazioni

dei valori e delle operazioni

(27)

27 27

Dichiarazione di Tipo Dichiarazione di Tipo

Utilità Utilità

 Definizione del dominio di applicazione del Definizione del dominio di applicazione del programma

programma

 Comprensione del funzionamento di un Comprensione del funzionamento di un algoritmo

algoritmo

 Verifica della correttezza del programma Verifica della correttezza del programma



Compilatore Compilatore



Programmatore Programmatore

 Definizione dello spazio di memoria necessario Definizione dello spazio di memoria necessario

 Rappresentazione interna Rappresentazione interna



Esempio: 18 Esempio: 18 e 18.0 e 18.0

(28)

28 28

Definizione di Tipo Definizione di Tipo

Meccanismi Linguistici Meccanismi Linguistici

 Istruzioni e costrutti linguistici necessari Istruzioni e costrutti linguistici necessari per informare l’esecutore su

per informare l’esecutore su

 dominio della variabile dominio della variabile

 insieme di operazioni effettuabili su di essa insieme di operazioni effettuabili su di essa

 modo attraverso cui ci si può riferire ad essa modo attraverso cui ci si può riferire ad essa

 Esempio: Indicazione esplicita dei valori Esempio: Indicazione esplicita dei valori permessi per ogni variabile

permessi per ogni variabile

 Costanti di tipo Costanti di tipo

(29)

29 29

Definizione di Tipo Definizione di Tipo

nei Ling. di Programmazione nei Ling. di Programmazione

 I moderni linguaggi di programmazione I moderni linguaggi di programmazione mettono a disposizione

mettono a disposizione

 Un insieme di tipi di uso più comune Un insieme di tipi di uso più comune



Tipi predefiniti Tipi predefiniti

 Gli strumenti per poter costruire qualunque Gli strumenti per poter costruire qualunque tipo di dati

tipo di dati

(30)

30 30

Tipi Standard Tipi Standard

 Tipi più comuni di variabili Tipi più comuni di variabili



Interi Interi



Reali Reali



Logici Logici



Caratteri Caratteri

 Valori rappresentabili limitati Valori rappresentabili limitati



Dimensioni della memoria che dovrà ospitarne le Dimensioni della memoria che dovrà ospitarne le variabili

variabili



Tipo numerico Tipo numerico



Tipo alfanumerico Tipo alfanumerico

(31)

31 31

Tipo degli Interi Tipo degli Interi

 Valori nell’insieme dei numeri interi Valori nell’insieme dei numeri interi

 Stringa di cifre, Stringa di cifre,

eventualmente preceduta dal segno eventualmente preceduta dal segno



Positivi Positivi



Negativi Negativi

 Operazioni basilari Operazioni basilari

 somma, prodotto, differenza, quoziente, resto, somma, prodotto, differenza, quoziente, resto, elevamento a potenza

elevamento a potenza

(32)

32 32

Tipo degli Interi Tipo degli Interi

 Non sono in numero infinito nell’aritmetica dei Non sono in numero infinito nell’aritmetica dei calcolatori

calcolatori



Per ogni macchina esistono Per ogni macchina esistono



il più grande intero il più grande intero



il più piccolo intero il più piccolo intero

rappresentabile in una locazione di memoria rappresentabile in una locazione di memoria

 Alcune proprietà dell’aritmetica non restano Alcune proprietà dell’aritmetica non restano valide in generale

valide in generale



Risultato di un’operazione non rappresentabile Risultato di un’operazione non rappresentabile



Overflow Overflow



Legge associativa Legge associativa

(33)

33 33

Tipo degli Interi Tipo degli Interi

Valori Negativi Valori Negativi

 Rappresentare il segno nel primo bit Rappresentare il segno nel primo bit



2 rappresentazioni per lo zero 2 rappresentazioni per lo zero



Differente gestione per somma e sottrazione Differente gestione per somma e sottrazione



La somma di opposti non dà zero La somma di opposti non dà zero

 Associare alle rappresentazioni disponibili un Associare alle rappresentazioni disponibili un intervallo di altrettanti valori progressivi a

intervallo di altrettanti valori progressivi a cavallo dello zero

cavallo dello zero



Differente gestione per somma e sottrazione Differente gestione per somma e sottrazione



La somma di opposti non dà zero La somma di opposti non dà zero

(34)

34 34

Tipo degli Interi Tipo degli Interi

complemento a 2 complemento a 2

 Cambiare tutti gli 0 in 1 e viceversa Cambiare tutti gli 0 in 1 e viceversa

 Aggiungere 1 Aggiungere 1



Esempio: Esempio: 4 4

₁₀₁₀

= 0100 = 0100

₂₂

0100

0100 → 1011 + 1 = 1100 → 1011 + 1 = 1100 ≡ ≡ –4 –4

 Valori rappresentabili con Valori rappresentabili con n n bit: bit: 2 2

ⁿⁿ



Da Da –2 –2

^n-1^n-1

a a +2 +2

^n-1^n-1

– 1 – 1

 I valori negativi iniziano sempre per 1 I valori negativi iniziano sempre per 1

 Allineamento automatico per la somma Allineamento automatico per la somma

(35)

35 35

Tipo degli Interi Tipo degli Interi

 Overflow nell’addizione Overflow nell’addizione

 Esempi corretti Esempi corretti

+3 +3 0011 0011 –8 –8 1000 1000 – – 6 6 1010 1010 +7 +7 0111 0111 –3 – 3 1101 1101 –1 –1 1111 1111

 Esempio con overflow Esempio con overflow

+2 +2 0010 0010 +7 +7 0111 0111

– – 7 7 1001 1001 ≠ ≠ +9 !!! +9 !!!

(36)

36 36

Tipo dei Reali Tipo dei Reali

 Valori nell’insieme dei numeri reali Valori nell’insieme dei numeri reali

 Parte intera Parte intera

 Parte decimale Parte decimale



Differenza tra il numero e la sua parte intera Differenza tra il numero e la sua parte intera



< 1 < 1



Sequenza potenzialmente infinita di cifre Sequenza potenzialmente infinita di cifre

 In alcuni casi esiste un’ultima cifra diversa da In alcuni casi esiste un’ultima cifra diversa da

zero, seguita da una successione infinita di zeri

(37)

37 37

Tipo dei Reali Tipo dei Reali

 Non formano un continuo nell’aritmetica Non formano un continuo nell’aritmetica dei calcolatori

dei calcolatori

 Ciascuno rappresenta un intervallo del Ciascuno rappresenta un intervallo del continuo

continuo



Insieme di infiniti valori reali Insieme di infiniti valori reali

 Ad ogni numero reale è associata una Ad ogni numero reale è associata una rappresentazione

rappresentazione



Intervallo in cui ricade Intervallo in cui ricade

 Forma un sottoinsieme dei numeri reali Forma un sottoinsieme dei numeri reali

(38)

38 38

Tipo dei Reali Tipo dei Reali

 Rappresentazione ottenuta per Rappresentazione ottenuta per troncamento o arrotondamento troncamento o arrotondamento

 Possibili errori di precisione anche consistenti Possibili errori di precisione anche consistenti

 Esiste un valore massimo Esiste un valore massimo

 Overflow Overflow



Rappresentazione indefinita per tutti i valori Rappresentazione indefinita per tutti i valori maggiori

maggiori

(39)

39 39

Tipo dei Reali Tipo dei Reali

Rappr. in Virgola Fissa Rappr. in Virgola Fissa

 z = n,m z = n,m



N N bit per la parte intera bit per la parte intera n n



M M bit per la parte decimale bit per la parte decimale m m

 Naturalmente allineati per addizione e Naturalmente allineati per addizione e sottrazione

sottrazione

 Cattiva gestione della memoria Cattiva gestione della memoria



Possibile spreco di memoria Possibile spreco di memoria



Aumento delle probabilità di trabocco Aumento delle probabilità di trabocco



Parte intera Parte intera



Parte decimale Parte decimale

(40)

40 40

Tipo dei Reali Tipo dei Reali

Rappr. in Virgola Mobile Rappr. in Virgola Mobile

 z = z = ± m · b ± m · b

^e^e

→ → | | ± ± | | m m | | e e | | ( ( b b fissata) fissata)



1 bit per il segno 1 bit per il segno



N N bit per il valore assoluto della mantissa bit per il valore assoluto della mantissa m m



Cifre più significative non nulle Cifre più significative non nulle



Numero reale (1/b Numero reale (1/b ≤ m < 1) ≤ m < 1)



M M bit per l’esponente bit per l’esponente e e



Ordine di grandezza della prima cifra significativa Ordine di grandezza della prima cifra significativa



Riferito alla base Riferito alla base b b (= 2) (= 2)



Numero intero Numero intero



Rappresentazione corrispondente Rappresentazione corrispondente

(41)

41 41

Tipo dei Reali Tipo dei Reali

Rappr. in Virgola Mobile / 2 Rappr. in Virgola Mobile / 2

 Ottimizzazione della gestione della memoria Ottimizzazione della gestione della memoria



Cifre significative Cifre significative

 Allineamento manuale per addizione e Allineamento manuale per addizione e sottrazione

sottrazione



Riportare i valori allo stesso esponente Riportare i valori allo stesso esponente

 Comoda per la moltiplicazione Comoda per la moltiplicazione



Prodotto delle mantisse Prodotto delle mantisse



Somma degli esponenti Somma degli esponenti

(42)

42 42

Reali in Virgola Mobile Reali in Virgola Mobile

Esempio Esempio

π π = = 3,14159265… 3,14159265…

= = +0,314159265… +0,314159265… · · 10 10 ¹ ¹

 Rappresentazione con 5 cifre significative Rappresentazione con 5 cifre significative

 Troncamento Troncamento 3,1415

3,1415 → → | + | 31415 | +1 | | + | 31415 | +1 |

 Arrotondamento Arrotondamento 3,1416

3,1416 → → | + | 31416 | +1 | | + | 31416 | +1 |

(43)

43 43

Reali in Virgola Mobile Reali in Virgola Mobile

Esempio Esempio

 Rappresentazione con 4 cifre significative Rappresentazione con 4 cifre significative

211.5 211.5 = +0.2115 = +0.2115 · 10 · 10

³³

→ → | + | 2115 | +3 | | + | 2115 | +3 | 37.592

37.592 = +0.37592 = +0.37592 · 10 · 10

²²

→ → | + | 3759 | +2 | | + | 3759 | +2 |

 Allineamento per la somma Allineamento per la somma

| + | 2115 | +3 |

| + | 3759 | +2 |

| + | 3759 | +2 | → → | + | 03759 | +3 | | + | 03759 | +3 |

| + | 2490 | +3 |

| + | 2490 | +3 | = +249.0 = +249.0

(44)

44 44

Reali in Virgola Mobile Reali in Virgola Mobile

Esempio Esempio

 Rappresentazione con 2 cifre significative Rappresentazione con 2 cifre significative

 Con arrotondamento Con arrotondamento

1,36 1,36 = + 0.136 = + 0.136 · 10 · 10

¹¹

→ → | + | 14 | +1 | | + | 14 | +1 | – – 1,34 1,34 = – 0.134 = – 0.134 · 10 · 10

¹¹

→ → | – | 13 | +1 | | – | 13 | +1 |

 Errore di approssimazione nella Errore di approssimazione nella sottrazione

sottrazione

1,36 – 1,34 = 0,02 1,36 – 1,34 = 0,02

| + | 14 | +1 |

| – | 13 | +1 |

| + | 01 | +1 |

| + | 01 | +1 | = 0,1 = 0,1 !!! !!!

(45)

45 45

Tipo dei Reali Tipo dei Reali

Proprietà Proprietà

 Commutatività di somma e prodotto Commutatività di somma e prodotto

x + y = y + x

x + y = y + x x x · y = y · x · y = y · x x x ≥ y ≥ y ≥ ≥ 0 0 ⇒ ⇒ (x – y) + y = x (x – y) + y = x

 Simmetria rispetto allo zero Simmetria rispetto allo zero

x – y = x + (–y) = –(y – x) x – y = x + (–y) = –(y – x) (–x)

(–x) · y = x · · y = x · (–y) = –(x (–y) = –(x · · y) y) (–x)

(–x) ÷ y = x ÷ ÷ y = x ÷ (–y) = –(x (–y) = –(x ÷ ÷ y) y)

 Monotonia Monotonia

0 0 ≤ ≤ x x ≤ a ≤ a 0 0 ≤ ≤ y y ≤ ≤ b b x + y

x + y ≤ ≤ a + b a + b x – b x – b ≤ ≤ a – y a – y

x x · · y y ≤ ≤ a a · · b b x x ÷ ÷ b b ≤ ≤ a a ÷ ÷ y y

(46)

46 46

Tipo dei Reali Tipo dei Reali

Proprietà Mancanti Proprietà Mancanti

 Associativa Associativa

 Può accadere che Può accadere che (x + y) + z (x + y) + z ≠ ≠ x + (y + z) x + (y + z)

 Distributiva Distributiva

 Può accadere che Può accadere che x x · · (y + z) (y + z) ≠ ≠ (x (x · · y) + (x y) + (x · · z) z)

(47)

47 47

Tipo dei Valori Logici Tipo dei Valori Logici

 Rappresentano valori di verità Rappresentano valori di verità

 Falso, Vero Falso, Vero



Falso < Vero Falso < Vero

 Usati tipicamente nelle condizioni Usati tipicamente nelle condizioni

 Ottenibili come risultato di confronti Ottenibili come risultato di confronti

(48)

48 48

Tipo dei Valori Logici Tipo dei Valori Logici

Operatori Operatori

 Per priorità decrescente: Per priorità decrescente:

 not not

 and and

 or or

 Sottoinsieme completo Sottoinsieme completo

 Può simulare tutti gli altri operatori logici Può simulare tutti gli altri operatori logici

V V

F V

V

V F

F F

V

V F

V V

F

F F

V F

F

x or y x and y

not x y

x

(49)

49 49

Tipo dei Caratteri Tipo dei Caratteri

 Insieme finito ed ordinato di simboli Insieme finito ed ordinato di simboli



Lettere dell’alfabeto Lettere dell’alfabeto



Cifre decimali Cifre decimali



Punteggiatura Punteggiatura



Simboli speciali Simboli speciali



Spaziatura ( Spaziatura ( blank blank ), Ritorno carrello, A capo, Separatore di ), Ritorno carrello, A capo, Separatore di linea (EOL), …

linea (EOL), …

 Costanti di tipo Carattere racchiuse tra apici Costanti di tipo Carattere racchiuse tra apici



Esempi: Esempi: ‘a’ ‘a’ ‘8’ ‘8’ ‘?’ ‘?’ ‘@’ ‘@’

(50)

50 50

Tipo dei Caratteri Tipo dei Caratteri

Rappresentazione Rappresentazione

 Corrispondenza biunivoca tra l’insieme dei Corrispondenza biunivoca tra l’insieme dei caratteri e un sottoinsieme degli interi

caratteri e un sottoinsieme degli interi



Standard Standard ASCII ASCII

(American Standard Code (American Standard Code for Information Interchange) for Information Interchange)

7 bit

7 bit → → ² ²

⁷⁷

= 128 simboli = 128 simboli



UNICODE UNICODE

16 bit

16 bit → → ² ²

¹⁶¹⁶

> 65000 simboli > 65000 simboli

(51)

51 51

Tipo dei Caratteri Tipo dei Caratteri

Proprietà Proprietà

 Funzioni di trasferimento Funzioni di trasferimento



ord(c) ord(c)



numero d’ordine del simbolo numero d’ordine del simbolo c nella tavola di codifica c nella tavola di codifica



chr(i) chr(i)



Simbolo il cui numero d’ordine è Simbolo il cui numero d’ordine è i i

 Proprietà Proprietà



ord(chr(i))=i ord(chr(i))=i chr(ord(c))=c chr(ord(c))=c



c c

₁₁

< c < c

₂₂

⇔ ⇔ ord( ord( c c

₁₁

) < ord( ) < ord( c c

₂₂

) )

 Relazione d’ordine totale Relazione d’ordine totale



Coerente con i sottoinsiemi delle lettere e delle cifre Coerente con i sottoinsiemi delle lettere e delle cifre



ord(‘A’) ord(‘A’) ≤ ≤ ord(‘B’) ord(‘B’) ≤ ≤ … … ≤ ≤ ord(‘Z’) ord(‘Z’)



ord(‘a’) ord(‘a’) ≤ ≤ ord(‘b’) ord(‘b’) ≤ ≤ … … ≤ ≤ ord(‘z’) ord(‘z’)



ord(‘0’) ord(‘0’) ≤ ≤ ord(‘1’) ord(‘1’) ≤ ≤ … … ≤ ≤ ord(‘9’) ord(‘9’)

(52)

52 52

Tipo dei Caratteri Tipo dei Caratteri

Note Note

 Alcuni caratteri non sono stampabili Alcuni caratteri non sono stampabili

 Esempio: Esempio: campanello ( campanello ( bell bell ) )

 NB: caratteri delle cifre diversi dalle cifre NB: caratteri delle cifre diversi dalle cifre

 Hanno come rappresentazione interna un Hanno come rappresentazione interna un valore diverso dalla cifra che rappresentano valore diverso dalla cifra che rappresentano

 Relazione d’ordine totale Relazione d’ordine totale

 Proprietà riflessiva, antisimmetrica, transitiva Proprietà riflessiva, antisimmetrica, transitiva

 ∀ ∀ x, y: x x, y: x ≤ ≤ y y ∨ ∨ y y ≤ ≤ x x

(53)

53 53

Istruzioni di Ingresso Istruzioni di Ingresso

 Permettono di acquisire informazioni Permettono di acquisire informazioni

dall’esterno, inserendole in opportune variabili dall’esterno, inserendole in opportune variabili

del programma del programma

 Attivano un’operazione di lettura Attivano un’operazione di lettura



Assegnazione del valore letto su un supporto di Assegnazione del valore letto su un supporto di memorizzazione esterno

memorizzazione esterno



schede, nastri e dischi magnetici, … schede, nastri e dischi magnetici, …

ad un’area di memoria individuata dal nome che ad un’area di memoria individuata dal nome che compare nell’istruzione di lettura

compare nell’istruzione di lettura

 Esempio: Esempio: read x read x

(54)

54 54

Assegnazione Assegnazione

di valori a variabili di valori a variabili

 Avviene in 2 stadi Avviene in 2 stadi



Produzione di un nuovo valore Produzione di un nuovo valore



Assegnamento di quel valore alla variabile Assegnamento di quel valore alla variabile

 L’operazione di assegnazione viene indicata con L’operazione di assegnazione viene indicata con

← ← := :=

= =

a seconda dei diversi linguaggi di a seconda dei diversi linguaggi di

programmazione programmazione



Confusione fra uguaglianza e assegnazione Confusione fra uguaglianza e assegnazione

(55)

55 55

Assegnazione Assegnazione

 Per produrre il valore si possono usare Per produrre il valore si possono usare

espressioni (aritmetiche o logiche) il cui risultato espressioni (aritmetiche o logiche) il cui risultato

è un singolo valore è un singolo valore

 Il valore prodotto dall’espressione a destra viene Il valore prodotto dall’espressione a destra viene memorizzato nell’area di memoria riservata alla memorizzato nell’area di memoria riservata alla

variabile a sinistra variabile a sinistra



La memorizzazione del valore ottenuto nella locazione La memorizzazione del valore ottenuto nella locazione di memoria riservata alla variabile implicata

di memoria riservata alla variabile implicata nell’assegnamento rimpiazza qualunque valore nell’assegnamento rimpiazza qualunque valore contenuto in precedenza

contenuto in precedenza

(56)

56 56

Legami degli Identificatori Legami degli Identificatori

 Identificatore – Posizione di memoria Identificatore – Posizione di memoria

 Statico Statico

 Identificatore – Valore Identificatore – Valore

 Dinamico nel programma Dinamico nel programma

Identificatore Identificatore

Posizione Posizione di Memoria

di Memoria Valore Valore

denota staticamente

denota

dinamicamente

contiene

(57)

57 57

Legami degli Identificatori Legami degli Identificatori

 La dinamicità del legame identificatore- La dinamicità del legame identificatore- valore consente di scrivere senza

valore consente di scrivere senza

contraddizioni assegnazioni del tipo contraddizioni assegnazioni del tipo

x x ← ← x + 1 x + 1

 Alla posizione di memoria identificata da x Alla posizione di memoria identificata da x

assegna il valore ottenuto calcolando la somma assegna il valore ottenuto calcolando la somma

del valore già memorizzato e

del valore già memorizzato e 1 1

(58)

58 58

Assegnazione Assegnazione

Computo dei Valori Computo dei Valori

 Le operazioni di assegnazione possono Le operazioni di assegnazione possono implicare calcoli complessi

implicare calcoli complessi

 Espressioni aritmetiche Espressioni aritmetiche

 Espressioni logiche e predicati Espressioni logiche e predicati

(59)

59 59

Espressioni Aritmetiche Espressioni Aritmetiche

 Formate da associazioni di variabili e costanti Formate da associazioni di variabili e costanti secondo regole opportune e attraverso

secondo regole opportune e attraverso

l’applicazione di definiti operatori numerici l’applicazione di definiti operatori numerici

Potenza

“

**, ˆ, …

Divisione

“ /, ÷, DIV,

…

Prodotto

“

*, ·, …

Differenza

“ -, …

Somma Numerico

+

Operazione Tipo di valore cui dà luogo

Simbolo

(60)

60 60

Espressioni Logiche o Espressioni Logiche o

Predicati Predicati

 Usate in: Usate in:



Assegnazioni fatte Assegnazioni fatte ad una variabile ad una variabile logica

logica



Strutture di Strutture di controllo che controllo che comportano la comportano la verifica di

verifica di condizioni condizioni

Minore o uguale

“

≤

Maggioranza

“

>

Maggiore o uguale

“

≥

Minoranza

“

<

Diversità

“

≠

Uguaglianza

“

=

Connettivi logici

Logico NOT, AND,

OR

Operazione Tipo di

valore cui

dà luogo

Simbolo

(61)

61 61

Costanti Costanti

 Dati il cui valore viene definito Dati il cui valore viene definito

inizialmente e non varia per tutta inizialmente e non varia per tutta

l’esecuzione del programma l’esecuzione del programma

 Accessibili solo in lettura Accessibili solo in lettura

 Garanzia nell’uso Garanzia nell’uso

 Impossibile eseguire assegnazioni sugli Impossibile eseguire assegnazioni sugli identificatori corrispondenti

identificatori corrispondenti

(62)

62 62

Strutture di Controllo Strutture di Controllo

 Obbligatorie Obbligatorie

 Sequenza Sequenza

 Selezione binaria Selezione binaria

 Una Iterazione illimitata Una Iterazione illimitata

 Opzionali Opzionali

 Selezione multipla Selezione multipla

 L’altra iterazione illimitata L’altra iterazione illimitata

 Iterazione limitata Iterazione limitata

(63)

63 63

Tipi di Dati Tipi di Dati

Tassonomia Pascal-like Tassonomia Pascal-like

Enumerativi Enumerativi

INTERI

INTERI LOGICILOGICI CARATTERICARATTERI Predefiniti

Predefiniti SottocampoSottocampo Scalari

Scalari REALIREALI Semplici

Semplici PuntatorePuntatore

VETTORI

VETTORI SCHEDESCHEDE INSIEMIINSIEMI ARCHIVIARCHIVI Strutturati

Strutturati Tipi di Dati

Tipi di Dati

(64)

64 64

Tipi di Dati Tipi di Dati

Tassonomia in Java Tassonomia in Java

Tipi Tipi Primitivi

Primitivi Riferimento Riferimento

Logici

Logici Numerici Numerici Array Array Classi Classi Interfacce Interfacce

Interi

Interi Reali Reali

Caratteri

Caratteri Singola precisione Singola precisione Lunghi/Corti

Lunghi/Corti Doppia precisione Doppia precisione Con/senza segno

Con/senza segno

(65)

65 65

Definizione di Tipo Definizione di Tipo

 Fornisce, tramite le istruzioni dichiarative: Fornisce, tramite le istruzioni dichiarative:

 L’indicazione di tutti i valori che caratterizzano L’indicazione di tutti i valori che caratterizzano il tipo

il tipo

 L’eventuale strutturazione di insiemi di valori L’eventuale strutturazione di insiemi di valori

 Esempio: Esempio: tipo t : T tipo t : T

 t t è il nome che indica il tipo è il nome che indica il tipo

 T T ne è la descrizione ne è la descrizione

(66)

66 66

Tipi Semplici Tipi Semplici

 I cui elementi sono singoli valori I cui elementi sono singoli valori

 primitivi (forniti dal linguaggio) primitivi (forniti dal linguaggio)

 definiti dall'utente definiti dall'utente

(67)

67 67

Tipi Scalari Tipi Scalari

 Corrispondenza uno-a-uno fra i valori e un Corrispondenza uno-a-uno fra i valori e un intervallo di interi

intervallo di interi



Ordinali Ordinali dei relativi valori dei relativi valori

 Operazioni consentite: Operazioni consentite:



Confronto Confronto



Assegnamento Assegnamento



Funzioni predecessore-successore Funzioni predecessore-successore pred(X)

pred(X)

succ(Y)

(68)

68 68

Tipi Scalari Tipi Scalari

 Sono tipi scalari quelli usati più di Sono tipi scalari quelli usati più di frequente

frequente

 Solitamente Solitamente predefiniti predefiniti in ogni linguaggio in ogni linguaggio



Interi, Logici, Caratteri Interi, Logici, Caratteri

 Altri sono definibili dal programmatore Altri sono definibili dal programmatore

 Enumerativi (il più spontaneo) Enumerativi (il più spontaneo)



Elenco dei valori Elenco dei valori

 Sottocampo di un tipo scalare Sottocampo di un tipo scalare



Valori estremi (min/max) Valori estremi (min/max)

(69)

69 69

Tipi Scalari Tipi Scalari

Enumerativi Enumerativi

 Definiti elencando l’insieme dei valori che ad essi Definiti elencando l’insieme dei valori che ad essi competono

competono

tipo T : (v

₁₁

, v , v

₂₂

, …, v , …, v

_n_n

) )

 Gli insiemi di valori scalari sono definiti ed Gli insiemi di valori scalari sono definiti ed ordinati

ordinati

Per ogni tipo

Per ogni tipo T T deve valere: deve valere:



I valori sono distinti ( I valori sono distinti ( ∀ i ∀ i ≠ ≠ j: v j: v

_i_i

≠ v ≠ v

_j_j

) )



L’ordine dipende dall’elencazione (i < j: v L’ordine dipende dall’elencazione (i < j: v

_i_i

< v < v

_j_j

) )



Gli unici valori del tipo sono quelli elencati Gli unici valori del tipo sono quelli elencati (solo v

(solo v

_i_i

, , i = 1…n appartiene al tipo i = 1…n appartiene al tipo T T ) )

(70)

70 70

Tipi Scalari Tipi Scalari

Sottocampo Sottocampo

 Basati su un tipo scalare preesistente Basati su un tipo scalare preesistente

 Tipo Tipo Ospite (in senso attivo) Ospite (in senso attivo)

 Definiti specificando Definiti specificando

 Il più piccolo Il più piccolo

 Il più grande Il più grande

valore dell’intervallo dei valori valore dell’intervallo dei valori

rappresentati dal sottocampo rappresentati dal sottocampo

 tipo T : [v tipo T : [v

_min_min

… v … v

_max_max

] ]

(71)

71 71

Tipi Scalari Tipi Scalari

Esempio Esempio

 Enumerativo Enumerativo

tipo giorno:(lun,mar,mer,gio,ven,sab,dom) tipo giorno:(lun,mar,mer,gio,ven,sab,dom) x: giorno

x: giorno x x ← gio ← gio

se x < sab allora … se x < sab allora … write pred(x)

write pred(x) write succ(x) write succ(x)

 Sottocampo Sottocampo

tipo feriale : [lun … sab]

(72)

72 72

Dati Strutturati Dati Strutturati

 Insiemi di valori correlati Insiemi di valori correlati

 Indicati collettivamente da un unico nome Indicati collettivamente da un unico nome

 Si presuppone che tra essi esista una struttura Si presuppone che tra essi esista una struttura legata

legata



all’organizzazione all’organizzazione



al tipo di valori che compongono l’insieme al tipo di valori che compongono l’insieme



alle operazioni per estrarre i dati dall’insieme alle operazioni per estrarre i dati dall’insieme

 È fondamentale il modo in cui vengono È fondamentale il modo in cui vengono individuati i dati componenti

individuati i dati componenti

(73)

73 73

Variabili Strutturate Variabili Strutturate

 I cui valori sono aggregazioni di componenti I cui valori sono aggregazioni di componenti



La dichiarazione prevede l’indicazione di La dichiarazione prevede l’indicazione di



Nome Nome



Tipo di struttura Tipo di struttura

 I linguaggi di programmazione offrono I linguaggi di programmazione offrono costruttori per le strutture più comuni costruttori per le strutture più comuni



Operatori già definiti Operatori già definiti



Alcuni linguaggi consentono operazioni su intere variabili Alcuni linguaggi consentono operazioni su intere variabili strutturate

strutturate

 Strutture più complesse definibili attraverso il Strutture più complesse definibili attraverso il costrutto di tipo

costrutto di tipo

(74)

74 74

Struttura di Dati Struttura di Dati

 Agglomerato (significativo) in cui sono riuniti Agglomerato (significativo) in cui sono riuniti dati da elaborare

dati da elaborare



Particolare tipo di dato Particolare tipo di dato



Caratterizzato più Caratterizzato più dall’organizzazione imposta agli elementi dall’organizzazione imposta agli elementi componenti che dal tipo degli elementi stessi

componenti che dal tipo degli elementi stessi

 Consiste di Consiste di



Un modo sistematico di organizzare i dati Un modo sistematico di organizzare i dati



Un insieme di operatori per Un insieme di operatori per



Manipolare elementi della struttura Manipolare elementi della struttura



Aggregare elementi per costruire altre strutture Aggregare elementi per costruire altre strutture

(75)

75 75

Strutture di dati Strutture di dati

Esempi Esempi

 Tabelle Tabelle

 Orario delle Lezioni Orario delle Lezioni

 Orario Ferroviario Orario Ferroviario

 Matrici Matrici

 Date Date

 Schede Schede

 Patente e altri documenti di riconoscimento Patente e altri documenti di riconoscimento

 Schede di biblioteca Schede di biblioteca

(76)

76 76

Strutture di Dati Strutture di Dati

 I moderni linguaggi di programmazione I moderni linguaggi di programmazione mettono a disposizione

mettono a disposizione

 Un insieme di strutture di uso più comune Un insieme di strutture di uso più comune (predefinite)

(predefinite)



Sufficiente l’indicazione di Sufficiente l’indicazione di

 Dimensione Dimensione

 Tipo delle componenti Tipo delle componenti

 Gli strumenti per poter costruire qualunque Gli strumenti per poter costruire qualunque tipo di struttura

tipo di struttura



Costruttori di tipo Costruttori di tipo

(77)

77 77

Strutture di Dati Strutture di Dati

Dimensioni di

Dimensioni di Classificazione Classificazione

 Disposizione dei dati Disposizione dei dati componenti

componenti



Lineari Lineari



Dati disposti in Dati disposti in sequenza

sequenza

 Primo elemento, Primo elemento, secondo elemento, secondo elemento,

… …



Non lineari Non lineari



Non è individuata una Non è individuata una sequenza

sequenza

 Numero di dati Numero di dati componenti

componenti



A dimensione fissa A dimensione fissa



Il numero di elementi Il numero di elementi della struttura rimane della struttura rimane

costante nel tempo costante nel tempo



A dimensione variabile A dimensione variabile



Il numero di elementi Il numero di elementi

può variare nel tempo

(78)

78 78

Strutturare i Dati Strutturare i Dati

 Applicazioni Applicazioni

 Vettore/Matrice Vettore/Matrice

 Prodotto Cartesiano Prodotto Cartesiano

 Record Record

 Insieme Potenza Insieme Potenza

 Set Set

 Sequenze Sequenze

 File File

(79)

79 79

Vettore Vettore

 Tabella monodimensionale Tabella monodimensionale

 Struttura lineare Struttura lineare

 A dimensione fissa A dimensione fissa

 Sequenza di elementi dello stesso tipo Sequenza di elementi dello stesso tipo

 Operazioni consentite: Operazioni consentite:



Lettura (selezione) Lettura (selezione)

 Reperimento del valore di un elemento Reperimento del valore di un elemento



Scrittura (sostituzione) Scrittura (sostituzione)

 Sostituzione del valore di un elemento con un Sostituzione del valore di un elemento con un nuovo valore

nuovo valore

(80)

80 80

Vettore Vettore

 Numero fissato di componenti Numero fissato di componenti



Tutte dello stesso tipo Tutte dello stesso tipo



Tipo Tipo base base



Ciascuna esplicitamente denotata ed indirizzata Ciascuna esplicitamente denotata ed indirizzata tramite un selettore (

tramite un selettore ( indice) indice)



Non si è legati ad uno specifico tipo di indice Non si è legati ad uno specifico tipo di indice

 Definito da: Definito da:



Tipo degli elementi Tipo degli elementi



Numero degli indici Numero degli indici



Tipo degli indici Tipo degli indici

(81)

81 81

Vettore Vettore

vettore (

vettore ( tipo_indice tipo_indice ) di ) di tipo_base tipo_base

 Accesso a qualunque componente Accesso a qualunque componente

 Specificandone la posizione Specificandone la posizione



Nome della variabile vettore seguito dall’indice Nome della variabile vettore seguito dall’indice

 In un tempo indipendente dal valore In un tempo indipendente dal valore dell’indice

dell’indice

