Seconda Lezione

Introduzione alla programmazione ll

C.1. Contenitori di dati Un algoritmo deve tener traccia degli

ingressi, dei risultati e dei valori intermedi che produce durante il calcolo.

Allo scopo, usa dei contenitori di dati. Un contenitore di dati, detto anche variabile,

è un’astrazione della nozione di area di memoria contenente dei dati.

I dati contenuti hanno un tipo, che caratterizza un insieme di elementi e le operazioni possibili su di essi.

C.1. Contenitori di dati (segue)

Tipo dei contenitori TIPO DI DATO = insieme di elementi

rappresentabili in modo finito, dotato di operazioni primitive su di esso.

ESEMPIO: il tipo degli interi è l’insieme degli interi, sono successioni finite di cifre con

eventuale segno dotato delle seguenti operazioni primitive (e calcolabili):

+, -, *, divisione intera, resto.

pippo: intero

54

NomeNome contenitore e tipo tipo

Contenuto = datodato appartenente al tipo di dati associato al nometipo di dati associato al nome

C.1. Contenitori di dati (segue)

I contenitori di dati utilizzati per i risultati intermedi dipendono dall’algoritmo: quindi, a meno di casi assai elementari, è

necessario avere già un’idea ben delineata dell’algoritmo per determinarli

difficilmente sono TUTTI prevedibili sin dall’inizio; man mano che l’algoritmo prende forma, si possono aggiungere al volo nuovi contenitori

Esempio di outline dell’algoritmo

Contenitori di dati usati da RADICI. Di quali contenitori abbiamo bisogno per

RADICI? Sicuramente di quelli per contenere i dati di

ingresso ed il risultato: 3 contenitori per a,b,c (ingressi) e r1, r2.

Eventuali contenitori per i risultati intermedi (es. delta) ed eventualmente quello finale.

Tutti i contenitori saranno di tipo float.

C.2. Diagrammi di flusso

Diagramma di flusso: è un formalismo visuale per rappresentare in modo semplice e intuitivo un algoritmo.

Un algoritmo compie due tipi fondamentali di operazioni: calcoli primitivi: ottenibili mediante le operazioni

primitive dei tipi di dati (sostanzialmente, valutando espressioni);

azioni: consistono nel modificare il contenuto dei contenitori di memoria, eventualmente eseguendo calcoli primitivi.

Costanti e variabili

I dati nei contenitori possono essere costanti o variabili

I dati costanti sono dati che rimangono inalterati durante l’esecuzione dell’algoritmo da quando ha inizio a quando termina

Es. Variamo leggermente l’ Algoritmo delle RADICI prendendo come equazione di partenza ax2+bx+1=0, ove il termine noto c è determinato a priori. In questo caso dunque il termine noto è una costante

Variabili I dati variabili o semplicemente variabili sono

coppie <nome, valore> Possono essere immaginati come scatole che

hanno come etichetta il nome e come contenuto il valore

Alle variabili deve essere assegnato esplicitamente un valore

Al momento di inizio dell’algoritmo le variabili hanno un valore indeterminato

Es. Nell’Algoritmo delle RADICI sono variabili a,b,c, x1 e x2

Calcoli primitivi Sono valutazioni di espressioni in cui compaiono i

nomi dei contenitori di dati utilizzati e solo operazioni primitive disponibili sui relativi tipi di dati

Il valore dell’espressione è riferito allo STATO di memoria dell’algoritmo, cioè al contenuto attuale dei suoi contenitori di dati

Es.

b * b – 4 * a * c = 0

è un’espressione valutabile perché contiene operazioni primitive disponibili nel tipo float

a : float

2

b : float

4

c : float

2Stato della memoriaStato della memoria

Calcoli primitivi: espressioni booleane

Fra le espressioni valutabili assumono particolare importanza quelle di tipo booleano

Il tipo booleano contiene due valori vero, falso

Esempi di espressioni booleane disponibili nei tipi numerici x<y (x+5)=y ecc.

Azioni Modificano lo stato di memoria, cioè i valori dei

contenitori dei dati Le azioni più semplici sono gli assegnamenti, della

forma: metti ESPRESSIONE in CONTENITORE valuta ESPRESSIONE e metti il risultato in

CONTENITORE, sostituendone il valore precedente Altre azioni sono:

leggi da input scrivi su output

Es.

Metti b * b – 4 * a * c in delta

a : float

2

b : float

4

c : float

2

delta : float

0

Stato della memoriaStato della memoria

Assegnazione L’istruzione di assegnazione è quella particolare

istruzione che permette di definire il valore attuale di una variabile

Il valore rimane inalterato fino a una nuova assegnazione alla variabile

Forma generale: Nome = espressione

L’assegnazione viene eseguita nei seguenti passi: si valuta l’espressione di destra si attribuisce il valore determinato alla variabile

Assegnazione

Regola Ogni volta che una variabile appare a destra

dell’istruzione di assegnazione =, è necessario che un valore sia già stato assegnato a quella variabile

Es. nel caso a=2, b=3, c=a+b, allora si ha c=5 nel caso x=2, x=x+3, allora si ha x=5

Istruzioni

Le istruzioni possono essere divise in 5 categorie Istruzioni operative Istruzioni di controllo Istruzioni di salto Istruzioni di inizio/fine esecuzione Istruzioni di ingresso/uscita

Istruzioni operative

Istruzioni che producono un risultato se eseguite

Ne fanno parte le operazioni aritmetiche e le assegnazioni

Istruzioni di controllo

Istruzioni che controllano il verificarsi di condizioni specificate e che in base al risultato determinano quale istruzione eseguire

Es.

se… allora… altrimenti (if… then… else)

Istruzioni di salto Istruzioni che alterano il normale ordine di

esecuzione delle istruzioni di un algoritmo, specificando esplicitamente quale sia la successiva istruzione da eseguire

Si distinguono istruzioni di salto condizionato o incondizionato

Per quelle condizionate il salto è subordinato al verificarsi di una condizione specificata, per quelle incondizionate il salto è eseguito ogni volta che l’istruzione viene eseguita

Sono sconsigliate nella programmazione strutturata

Istruzioni di inizio/fine

Indicano quale istruzione dell’algoritmo debba essere eseguita inizialmente e quale determini la fine dell’esecuzione

Istruzioni di ingresso/uscita

Istruzioni che indicano una trasmissione di dati o messaggi fra l’algoritmo e tutto ciò che è esterno all’algoritmo

Si dicono di ingresso o lettura quando l’algoritmo riceve dati dall’esterno

Si dicono di uscita o scrittura quando i dati sono comunicati dall’algoritmo all’esterno

Esempio

Nell’Algoritmo delle RADICI Le istruzioni 1,8 sono di inizio/fine Le istruzioni 2,7 sono di ingresso/uscita La istruzione 3 è operativa La istruzione 4 è di salto condizionato Le istruzioni 5,6 sono condizionali

Proposizioni Una proposizione è un costrutto

linguistico del quale si può dire se è vero o falso

Il valore di verità di una proposizione è l’essere vera o falsa della proposizione

Es.“3 è un numero pari” è una proposizione“incrementa x di 10” non è una proposizione

Predicati

È un predicato una proposizione contenente delle variabili e in cui il valore delle variabili determina il valore di verità del predicato

Es.

“x è un numero pari” è un predicato

Predicati

La valutazione di un predicato avviene tramite i seguenti operatori relazionali

= uguale, ≠ diverso > maggiore, ≥ maggiore o uguale < minore, ≤ minore o uguale

Predicati semplici e composti

Un predicato che contiene un solo operatore relazionale è detto predicato semplice

Gli operatori relazionali possono essere combinati con i seguenti operatori logici NOT AND OR

Un predicato che contiene più operatori relazionali combinati tramite uno o più operatori logici è detto composto

Operatori logici NOT: dato un predicato p, NOT p è vero

quando p è falso e viceversa

AND: dati due predicati p e q, p AND q è vero solo quando entrambi p e q sono veri e falso altrimenti

OR: dati due predicati p e q, p OR q è falso solo quando entrambi p e q sono falsi e vero altrimenti

Tavole di verità

p NOT p

V F

F V

Tavole di verità

p q p AND q

V V V

V F F

F V F

F F F

Tavole di verità

p q p OR q

V V V

V F V

F V V

F F F

Vettori Le variabili considerate fino ad adesso

sono dette variabili scalari Una variabile vettore (array) è una

coppia <nome, insieme di valori> Può essere immaginata come una

scatola che ha un nome e che è divisa in tanti comparti ognuno dei quali è numerato e può contenere un valore

Vettori Ogni valore è individuato dal nome della

variabile seguito dal numero del comparto detto indice

La notazione usata è:

A(i) La dimensione di un vettore è il numero

dei suoi elementi

Vettori

Gli indici vanno da 1 (0 in VBA) ad un numero massimo rappresentato dalla dimensione del vettore (dimensione – 1 in VBA)

In fase di dichiarazione di una variabile vettore si specifica la sua dimensione che non è più modificabile successivamente

Matrici

È l’estensione del concetto di vettore Una matrice è un insieme di valori che

sono indicizzati facendo ricorso a due o più indici

La notazione usata è M(i,j)

Per una matrice a 2 dimensioni i è detto indice riga e j indice colonna

Diagrammi di flusso Sono noti anche come Diagrammi a blocchi Costituiscono un linguaggio formale di tipo grafico

per rappresentare gli algoritmi Attraverso il diagramma a blocchi (o flow chart) si

può indicare la logica e l’ordine di esecuzione delle istruzioni

Un particolare simbolo grafico detto blocco elementare è associato ad ogni tipo di istruzione elementare

I blocchi sono collegati tra loro tramite frecce che indicano il susseguirsi delle istruzioni

Diagrammi di flusso

metti x+y in y;metti x-1 in x;

X = 0

- Blocco computazionale (o blocco azione)

- Blocco decisionale (o blocco di controllo)

vero falso

Contengono sequenze diazioni

Contengono una condizione Booleana:• se è vera, si segue la freccia etichettata “vero”• se è false si segue la freccia etichettata “falso”

Diagrammi di flusso Gli altri blocchi elementari sono:

SubLeggi x

End SubScrivi x

Blocco iniziale

Blocco finale

Blocco di lettura

Blocco di scrittura

Strutture di controllo modulari

Un diagramma di flusso si ottiene collegando le frecce uscenti dai blocchi di elaborazione e decisionali

Una buona norma è attenersi a diagrammi con strutture predefinite, con una sola freccia entrante e una uscente

Tali strutture sono dette strutture di controllo e sono alla base della programmazione strutturata

Ciò consente di modularizzare (cioè dividere in parti o moduli) il diagramma; è utile perché spesso i moduli corrispondono a sottoproblemi (sottoprogrammi)

SottoprogrammiCon il blocco

si indica un sottoprogramma di cui è nota la rappresentazione in diagramma a blocchi

A

sottoprogramma

Proprietà dei diagrammi di flusso

Un diagramma a blocchi descrive un algoritmo se: ha un blocco iniziale e uno finale è costituito da un numero finito di blocchi

azione e/o blocchi lettura/scrittura e/o blocchi di controllo

ciascun blocco elementare soddisfa le condizioni di validità

Proprietà dei diagrammi di flusso

Condizioni di validità Ciascun blocco azione, lettura/scrittura ha una

sola freccia entrante e una sola freccia uscente Ciascun blocco di controllo ha una sola freccia

entrante e due uscenti Ciascuna freccia entra in un blocco o si innesta

su un’altra freccia Ciascun blocco è raggiungibile dal blocco iniziale Il blocco finale è raggiungibile da qualsiasi altro

blocco

Esercizio

Scrivere un algoritmo e rappresentarlo tramite un diagramma a blocchi per i seguenti problemi:

attraversare la strada ritirare i soldi al bancomat calcolare l’area del triangolo

Analisi strutturata

È l’analisi volta alla stesura di descrizioni di algoritmi tramite diagrammi a blocchi di tipo strutturato

Un diagramma a blocchi strutturato è più facilmente comprensibile e modificabile

In un diagramma strutturato non apparirà mai una istruzione di salto incondizionato

Analisi strutturata

Teorema di Böhm-JacopiniOgni diagramma a blocchi non strutturato è

sempre trasformabile in un diagramma a blocchi strutturato ad esso equivalente

dove due diagrammi si dicono equivalenti se partendo dagli stessi dati iniziali producono gli stessi risultati

Analisi strutturata

Una descrizione è di tipo strutturato se i blocchi sono collegati tramite gli schemi di flusso corrispondenti alle strutture di controllo principali: schema di sequenza schema di selezione schema di iterazione

Strutture di controllo principali

- Sequenza

- Selezione

- Iterazione

vero falso

vero

falso

Schema di sequenza

Schema di sequenza Due o più schemi di flusso

sono eseguiti in successione

Nota:

lo schema di sequenza è strutturato se e solo se lo sono i blocchi S1 e S2

Sub()

End Sub

S1

S2

Schema di selezione

Schema di selezione Esiste un blocco di

controllo che permette di scegliere quale schema di flusso debba essere eseguito tra due schemi, in funzione del valore di verità del controllo

Sub()

C

S1

End Sub

Sub()

C

S1

End Sub

S2

falso

falso vero

vero