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
Top Related