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
Nome contenitore e tipo
Contenuto = dato appartenente al
tipo 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.
a : float
b : float
c : float
2
4
2
Stato della memoria
b*b–4*a*c=0
è un’espressione valutabile perché contiene operazioni
primitive disponibili nel tipo float
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:



Altre azioni sono:



metti ESPRESSIONE in CONTENITORE
valuta ESPRESSIONE e metti il risultato
CONTENITORE, sostituendone il valore precedente
leggi da input
scrivi su output
Es.
Stato della memoria
a : float
b : float
c : float
delta : float
2
4
2
0
Metti b * b – 4 * a * c in delta
in
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
- Blocco computazionale
(o blocco azione)
metti x+y in y;
metti x-1 in x;
Contengono sequenze di
azioni
- Blocco decisionale
(o blocco di controllo)
vero
X=0
falso
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:
Sub
Blocco iniziale
End Sub
Blocco finale
Leggi
x
Blocco di lettura
Scrivi
x
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)
Sottoprogrammi
Con il blocco
A
sottoprogramma
si indica un sottoprogramma di cui è nota
la rappresentazione in diagramma a
blocchi
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-Jacopini
Ogni 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
- Iterazione
falso
vero
- Selezione
vero
falso
Schema di sequenza

Schema di sequenza

Due o più schemi di flusso
sono eseguiti in successione
Sub()
S1

Nota:
lo schema di sequenza è
strutturato se e solo se lo
sono i blocchi S1 e S2
S2
End Sub
Schema di selezione
Sub()

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
falso
C
vero
S1
End Sub
Sub()
falso
C
S2
vero
S1
End Sub
Scarica

Teoria_della_Programmazione_2