Dal problema all` algoritmo

Dal problema all’ algoritmo
1
Analisi e programmazione
Tramite un elaboratore si possono risolvere problemi di
varia natura. Il problema deve essere formulato in
modo opportuno, perché sia possibile utilizzare un
elaboratore per la sua soluzione.
Per analisi e programmazione si intende l’insieme delle
attività preliminari atte a risolvere problemi utilizzando
un elaboratore, dalla formulazione del problema fino
alla predisposizione dell’elaboratore
Scopo dell’analisi: definire un algoritmo
Scopo della programmazione: tradurre l’algoritmo in
un programma utilizzando un linguaggio di
programmazione
2
Definizione di Algoritmo
Un algoritmo è sequenza finita di azioni elementari che
descrivono la soluzione di un problema in modo
completo
Ogni algoritmo è un insieme finito di azioni e deve
terminare dopo un numero finito di istruzioni.
Completo: deve considerare tutti i casi possibili che si
possono verificare durante l’esecuzione e per ogni caso
può indicare la soluzione da seguire.
3
Programma=algoritmo + dati
Un algoritmo non può essere eseguito direttamente dall’elaboratore
Programma  insieme di istruzioni (o comandi) che traducono
l’algoritmo in un linguaggio comprensibile ed eseguibile da parte di un
elaboratore
Un programma è strutturato in:
- una parte di dichiarazione in cui si dichiarano tutte le variabili
del programma e il loro tipo (intero, reale, stringa, ecc.)
- una parte che descrive l’algoritmo risolutivo utilizzato
Linguaggio di programmazione  linguaggio che permette la
formalizzazione di un algoritmo in un programma traducendolo con un
insieme di istruzioni (codice)
4
Le fasi del procedimento di analisi
e programmazione
Problema
ANALISI
Algoritmo
PROGRAMMAZIONE
Programma
ELABORAZIONE
Dati
Risultati
5
Dati su cui opera un Algoritmo:
Costanti e variabili
I dati su cui opera un algoritmo sono costanti e variabili
Una costante è una locazione (cella) di memoria che
mantiene lo stesso valore per tutta la durata dell'esecuzione
del programma.
Una variabile identifica una locazione (cella) di memoria
destinata a contenere dei dati, che possono essere
modificati nel corso dell'esecuzione di un programma.
Una variabile è caratterizzata da un nome (una sequenza di
caratteri e/o cifre) e da un tipo di variabile numerica,
alfabetica o alfanumerica
(in Visual Basic: integer,
double, string).
Valore
Nome
Rappresentazione di una
variabile
6
Assegnazione
L’istruzione di assegnazione definisce il valore di una
variabile, che resta inalterato fino all’assegnazione
successiva Es. A  5 (a=5)
L’assegnazione si rappresenta con il simbolo “”
nome di variabile  espressione
Es. A  5 si legge “assegna alla variabile A il valore di 5
I nomi delle variabili possono essere scelti in modo
arbitrario, ma è opportuno selezionare nomi significativi
del contenuto della variabile (senza spazi o caratteri
speciali)
7
Assegnazione
Esempi
a = b*c
a  b*c
24
a
6
4
b
c
6
4
b
x = x+3
14
x  x+3
17
x
x
c
Prima dell’assegnazione
Dopo l’assegnazione
Prima dell’assegnazione
Dopo l’assegnazione
8
Le istruzioni
Le Istruzioni operative in un programma possonono essere:
Istruzioni di controllo, che controllano il verificarsi di
condizioni specificate e, in base al risultato del controllo,
determinano il flusso di istruzioni da eseguire
Esistono tre tipi di istruzioni di controllo: sequenza,
selezione (alternativa), ripetizione (ciclo)
Istruzioni di ingresso/uscita, che specificano come debba
essere effettuata una trasmissione di dati tra l’algoritmo
risolutivo e l’ambiente esterno
Istruzioni di inizio/fine esecuzione, che indicano l’inizio/la
fine dell’algoritmo
9
I diagrammi a blocchi (flowchart)
Il linguaggio dei diagrammi a blocchi è un possibile
formalismo per la descrizione di algoritmi; il diagramma a
blocchi, o flowchart, è una rappresentazione grafica
dell’algoritmo
Un diagramma a blocchi definisce il flusso sequenziale di
operazioni da eseguire per realizzare la soluzione del
problema, descritta nell’algoritmo
Ogni istruzione è rappresentata all’interno di un blocco la cui
forma grafica è determinata dal tipo di istruzione (blocco di
elaborazione, di lettura o di scrittura, di scelta, ecc.)
I blocchi sono collegati tra loro da linee di flusso, munite di
frecce, che indicano il susseguirsi di azioni elementari
10
I diagrammi a blocchi
inizio
leggi x
Blocco iniziale
Blocco di lettura (input)
fine
Elaborazione
Blocco di elaborazione
vero
scrivi xX
scrivi
Blocco finale
Condizione
falso
Blocco di controllo
Blocco di scrittura
(output)
Blocchi elementari
11
I diagrammi a blocchi
Un diagramma a blocchi è un insieme di blocchi elementari
composto da:
un blocco iniziale
un blocco finale
un numero finito di blocchi di elaborazione e blocchi di
lettura/scrittura
un numero finito di blocchi di controllo
12
13
Costanti e variabili
Il valore di una variabile deve appartenere all’insieme di
definizione, su cui si opera (numeri interi, reali o stringhe).
Una variabile è caratterizzata dal nome e dal suo valore che
è = 0 in fase di definizione dell’algoritmo, ma assume poi
valori ben precisi durante ogni esecuzione
Esempio: Nell’algoritmo di risoluzione delle equazioni di 2°
grado, a, b, c non corrispondono a nessun valore finché non
si esegue l’algoritmo per trovare le soluzioni di una specifica
equazione:
ad esempio x29x4=0: in fase di esecuzione il valore delle
variabili a,b,c sarà:
a=1, b=9, c=4 e
nell’istruzione =b24ac viene calcolato il valore della variabile
 (discriminante)
14
15
16
Esempio di diagramma a blocchi
inizio
Somma di una
sequenza di N
numeri
N
S=
A
S= S+A
N=N-1
NO
N= 
SI
S
FINE
17
Linguaggio di progetto o pseudocodifica
E un linguaggio formale con regole prive di ambiguità che esprimono i vari tipi di
istruzioni. Es.
inizio
input N (Leggi N)

S
ripeti
input A
S
S+A
N
N-1
finché N=
output S
fine
18
ALGORITMI e PROGRAMMI
Algoritmo
 Un algoritmo non può essere eseguito direttamente
dall’elaboratore
Codifica dell’algoritmo  Programma
 Programma: sequenza ordinata di istruzioni, scritte in un
determinato linguaggio di programmazione, che specificano le
azioni da compiere dall’esecutore (il computer).
Algoritmo
Programma
19
Programma = algoritmo + dati
Un programma è strutturato in:
- una parte dichiarativa in cui si dichiarano tutte le variabili
del programma e il loro tipo (intero, reale, stringa, ecc.)
- una parte che descrive l’algoritmo risolutivo utilizzato
Linguaggio di programmazione  linguaggio che permette
la formalizzazione di un algoritmo in un programma
traducendolo con un insieme di istruzioni (codice)
20
ALGORITMI e PROGRAMMI
PROBLEMA
metodo
risolutivo
ALGORITMO
PROGRAMMA
linguaggio di
programmazione
21
LINGUAGGI: SINTASSI E SEMANTICA
Sintassi: l’insieme delle regole che consentono di scrivere
parole e frasi riconoscibili come appartenenti ad un
determinato linguaggio.
(collegamento ordinato delle parole nel discorso)
Semantica : la disciplina che studia il significato delle
parole e delle frasi.
22
LINGUAGGI a BASSO e ALTO LIVELLO
Linguaggi di Programmazione a basso livello impostano la soluzione di
un problema a partire da “passi elementari”: risolvono il problema con
efficienza ma sono molto vasti per risolvere algoritmi complesssi.
Esempio: Assembly
Linguaggi di Programmazione ad alto livello (di astrazione)


le istruzioni corrispondono ad operazioni più complesse
esempi: Pascal, Basic, C, C++, Java, Visual Basic
ASTRAZIONE: processo di aggregazione di informazioni e dati per
costruire un modello del mondo esterno.
23
Linguaggi di
programmazione
Problema
Algoritmo
Programma
sorgente
Risultati
Dalla
formulazione del
problema alla
sua soluzione
Programma
traduttore
Elaborazione
Programma
oggetto
24
Evoluzione dei Linguaggi
Esistono numerosi linguaggi

differenti per funzionalità e tecnologia
anni ‘60 metà anni ’60
BASIC
COBOL
metà anni ’50
FORTRAN
1968
Pascal
Linguaggi di
Programmazione
Imperativa
1974
C
1991
VB
1990
C++
Linguaggi
Ibridi
1994
Java
2000
Java
Linguaggi
Orientati
agli Oggetti
25
Programma sorgente
Programma sorgente
Istruzioni di
dichiarazione
Descrivono le
variabili utilizzate
dal programma,
definendone tipo e
struttura
Istruzioni di
assegnazione
Consentono di
assegnare alle
variabili un valore
L’algoritmo risolutivo viene
trasformato in un programma
che può contenere:
Istruzioni di
input e output
Richiedono l’ingresso
o l’uscita di una
Strutture
informazione da una
alternativa e
periferica alla
strutture di
ripetizione o cicli memoria centrale e
viceversa
Istruzioni
di controllo
26
Programma
La traduzione da Linguaggio di programmazione a
Linguaggio macchina viene fatta da un
programma traduttore di linguaggio
Due diversi approcci alla traduzione


basata su interprete
basata su compilatore
I linguaggi di programmazione che richiedono un
interprete sono definiti linguaggi interpretati,
mentre quelli che richiedono un compilatore sono
chiamati linguaggi compilati
27
Programma
Linguaggi Interpretati




La traduzione avviene per mezzo di un interprete, che traduce una riga del
programma per volta, ed la esegue immediatamente,
Analogia: gli interpreti simultanei nelle trasmissioni televisive o nei
congressi
Vantaggi: controllo del codice è immediato
Svantaggi: i programmi scritti con linguaggi interpretati, per essere eseguiti,
hanno bisogno dell'interprete (es. Visual Basic, Java)
Linguaggi Compilati




La traduzione avviene per mezzo di un compilatore, che traduce per intero
il programma in un nuovo oggetto
Analogia: i traduttori di libri o riviste
Vantaggi: generano un eseguibile, che può essere eseguito senza bisogno di
altri supporti (es. C)
Svantaggi: correggere gli errori richiede più tempo
28
Linguaggi compilati

C, C++, Fortran
Linguaggi interpretati

Perl, PHP, Visual Basic
Linguaggi interpretati e compilati

Java
29
Compilazione
codice
sorgente
es:primo.c
Compilazione
Compilatore
librerie
esterne
precompilate
es: stdio.h
codice
oggetto
(ling. macchina)
es: primo.obj
Collegamento
codice
eseguibile
es: primo.exe
Linker
30
Ambiente di sviluppo
E’ necessario disporre di vari strumenti
Scrittura del codice del programma

editor di testi (es: Blocco Note o Ubuntu Gedit)
Compilatore e Linker delle librerie
DevC++
 Compilatore g++ da Terminale Linux
g++ programma.cpp –o programma

31
Il Mio primo programma
/* Calcolo area rettangolo */
#include <iostream>
using namespace std;
int main(){
int base=13;
int altezza=5;
int AreaRettangolo;
AreaRettangolo = base*altezza;
cout << "Area rettangolo con base " << base;
cout << " e altezza " << altezza;
cout << " e' uguale a " << AreaRettangolo << endl;
return 0;
}
32
Modifichiamo il primo programma
/* Calcolo area rettangolo */
#include <iostream>
using namespace std;
int main(){
int base=13;
int altezza=5;
int AreaRettangolo;
cout<< "Inserisci base ";
cin>>base;
cout<< "Inserisci altezza ";
cin>>altezza;
AreaRettangolo = base*altezza;
cout << "Area Rettangolo: " << AreaRettangolo << endl;
return 0;
}
33
Struttura di Base di un Programma
#include <iostream.h>
<altre eventuali direttive>
int main(){
<dichiarazioni>
<operazioni>
}
34
Direttive di preprocessore
servono ad “includere” nel programma codice già
scritto (librerie)
 in particolare: #include <iostream>
(in C #include <stdio.h>)
include il codice relativo alle operazioni di lettura e
stampa dei dati da console
 è necessaria un’operazione di collegamento tra le
librerie incluse ed il codice del programma
(linker)

35
Elementi Sintattici di Base
Il codice è composto di istruzioni
 dichiarazioni dei dati (costanti, variabili e loro tipo)
 operazioni sui dati
 In C e C++ tutte le istruzioni si concludono con il punto
e virgola ;
36
Commenti
Testi che forniscono informazioni sul programma
ignorati dal compilatore
Esempi:
1. // primo esercizio
2. /* ----------------------------------Dichiarazioni su più righe
----------------------------------- */
3. // ----------------------------------// Dichiarazioni
// -----------------------------------
37
Tipi di Dato di Base
Parole chiave:
int
float
double
bool
char
string
38
Dichiarazioni di Variabili
Esempi:
int x, y;
string cognome;
bool trovato;
39
Dichiarazioni di Variabili
Esempi:
int x, y;
string cognome;
bool trovato;
40
Dichiarazioni di Costanti
Parole chiave:
const
Esempio:
const int N=10;
const float pigreco = 3.14;
const char segno = ‘X’;
const string corso = “Informatica”;
41
Operatori e Funzioni Predefinite
Principali operatori:
+ - * / %
&& || !
== > >= < <= !=
Principali funzioni predefinite:
abs() pow() sqrt() exp() cos()
atan() log() log10()
42
Istruzioni di Assegnazione
Esempio:
int x,y;
bool z;
x = 3;
x = x+1;
x = pow(y,2);
z = (x>y) && (y <=10); //funzione And
43
Procedure Predefinite di Lettura e Stampa
Lettura da tastiera:
>> operatore di lettura
Stampa su video:
<< operatore di stampa
cin input-stream
cout output-stream
Esempio:
float x;
cout << “Immetti il valore di x: “;
cin >> x;
cout << “Il valore di x e’ :” << x;
44
Strutture di Controllo
Istruzioni Condizionali
Esempio4:
Parole chiave: if ..... else
Esempio1:
int x,y;
if (x>2) cout << x;
Esempio2:
if ((x==3) || (x==5))
{ cout << x;
x = x+1; };
Esempio3:
if ((x==3) || (x==5))
{ cout << x;
x = x+1; };
#include <iostream>
int main(){
int primo, secondo,maggiore, minore;
cout<<"Inserire primo numero";
cin>>primo;
cout<<"Inserire secondo numero";
cin>>secondo;
if (primo<=secondo)
{minore=primo;
maggiore=secondo;
}
else{
minore=secondo;
maggiore=primo;
}
cout<<"Numero minore"<<minore<<endl;
cout<<"Numero
maggiore"<<maggiore<<endl;
return 0;
}
45
Cicli di tipo “FOR”
Parole chiave: for
Esempio1:
#include <iostream>
int main(){
int i,j;
for (i=1; i<=10; i++)
cout << i << endl;
for (i=1; i<=10; i++)
{
for (j=1; j<=10;
j++)
cout << i*j<<"\t";
cout << endl;
}
return 0;
}
46
Cicli di tipo “WHILE”
Parole chiave: while
Esempio1:
int main(){
int i,j;
i=1;
while (i<=10)
{ cout << i << endl;
i=i+1;
}
Esempio2:
i=1;
while (i<=10)
{
j=1;
while (j<=10) {
cout << i*j<<" ";
j=j+1;
}
cout << endl;
i++;
}
47
Sottoprogrammi
Procedure
#include <iostream.h>
using namespace std;
void stampaLogo()
// dichiarazione e definizione della procedura{
cout<<endl;
cout<<"********************************"<<endl;
cout<<"*** Classe II Informatica ***"<<endl;
cout<<"*** Itis Scano - Monserrato***"<<endl;
cout<<"********************************"<<endl;}
int main(){
stampaLogo();
// chiamata della procedura
cout<<endl<<"Programma di prova"<<endl;
stampaLogo();
// chiamata della procedura
system ("PAUSE");
return 0; }
48
Funzioni
#include <iostream.h>
int addizione (int a, int b); // Prototipo della funzione
addizione
int main() {
int z= addizione (5,3);
cout<<"il risultato e': "<<z<<endl;
system("PAUSE");
return 0;
}
int addizione (int a, int b) { // Funzione
int r;
r=a+b;
}
49
Esercizio
#include <iostream.h>
#include <math.h>
int main ()
{int a;
a = pow(2, 3);
// 2 e' la base e 3 e' l'esponente
cout << a<< endl;
system("Pause");
return 0;
}
50
Fine
51
La programmazione
strutturata
È stato dimostrato (Teorema fondamentale della programmazione
strutturata di Jacopini e Böhm) che ogni programma può essere
codificato attenendosi esclusivamente a tre strutture fondamentali:
1. Sequenziale
2. Condizionale o alternativa
3. Iterativa o di ripetizione
v
f
52
Le strutture di controllo
• La sequenza
• Struttura condizionale o alternativa
• Il ciclo con controllo alla fine
• Il ciclo con controllo all'inizio
• Il ciclo con contatore
53
La sequenza
È una struttura di controllo che permette di inserire una successione di
elaborazioni che saranno eseguite una di seguito all'altra.
Sintassi
Le istruzioni vengono scritte una di seguito all'altra, una per riga:
istruzione1
istruzione2
... ….
54
La Struttura alternativa
• È una struttura di controllo che permette di inserire una scelta tra due
possibilità, che porteranno a due elaborazioni distinte (ovvero due distinti
percorsi nel diagramma di flusso).
•Se la condizione risulterà vera, saranno eseguite le istruzioni del ramo VERO, se
invece risulta falsa, saranno eseguite le istruzioni del ramo FALSO.
55
Struttura di controllo iterativa o ciclo
Il ciclo con controllo alla fine
È una struttura di controllo che permette di ripetere un blocco di
istruzioni finché la condizione indicata è falsa. L'uscita dal ciclo si ha
solo quando la condizione diventa vera.
In questo tipo di ciclo il blocco delle istruzioni viene sempre eseguito
almeno una volta.
56
Struttura di controllo iterativa o ciclo
Il ciclo con controllo all'inizio
È una struttura di controllo che permette di ripetere un blocco di istruzioni
fintanto che la condizione indicata risulta vera. L'uscita dal ciclo si ha solo
quando la condizione diventa falsa.
In questo tipo di ciclo il blocco delle istruzioni può non essere mai eseguito, a
seconda della condizione impostata.
57
Strutture di controllo
Mediante i blocchi fondamentali, è possibile costruire delle strutture
tipicamente utilizzate per il controllo del flusso di esecuzione
dell’algoritmo:
• Selezione
• Iterazione o cicli
Selezione
Esprime la scelta tra due possibili azioni
58
Strutture di controllo
Iterazione o cicli
Esprime la ripetizione di una sequenza di istruzioni.
Nel caso piu` generale, e` costituita da:




Inizializzazione: assegnazione dei valori iniziali alle variabili
caratteristiche del ciclo (viene eseguita una sola volta);
Corpo: esecuzione delle istruzioni fondamentali del ciclo che
devono essere eseguite in modo ripetitivo;
Modifica: modifica dei valori delle variabili che controllano
l'esecuzione del ciclo (eseguito ad ogni iterazione);
Controllo: determina se il ciclo deve essere ripetuto o meno.
59
Il ciclo con contatore FOR
I=0
ISTRUZIONI
I=0
I<NUM
È una struttura di controllo che
permette di ripetere un blocco di
istruzioni un numero prestabilito di
volte.
I=I+1
La variabile contatore verrà
inizializzata con il valore minimo
(I=0) e, alla fine di ogni ripetizione
(NEXT), la variabile verrà
incrementata di uno.
ISTRUZIONI
I>NUM
I=I+1
Solo quando la variabile assume un
valore superiore al massimo previsto
si uscirà dal ciclo.
60
Ciclo Enumerativo
Un ciclo è detto enumerativo quando è noto a priori il numero di volte che
deve essere eseguito si usa la tecnica del contatore per controllarne
l’esecuzione: si usa cioè una variabile detta contatore del ciclo che viene
incrementata (o decrementata) fino a raggiungere un valore prefissato
Ciclo Indefinito
Un ciclo è indefinito quando non è noto a priori il numero di volte che deve
essere eseguito Questo accade quando la condizione di fine ciclo dipende
dal valore di una o più variabili contenute nell’interazione.
61
Somma di due valori
forniti dall’utente
62
Note sullo schema di iterazione enumerativa
E’costituito da una sequenza di azioni di assegnazione dette istruzioni
di inizializzazione e una iterazione (ripetizione) di una sequenza di
azioni per un numero specificato di volte
63
Struttura di sequenza
Fra tutti i possibili schemi di flusso ne esistono alcuni che
sono detti schemi fondamentali di composizione
Schema di sequenza: è uno schema elementare o uno schema
di sequenza
inizio
A
fine
64
Struttura di selezione
Schema di selezione: un blocco di controllo subordina
l’esecuzione di due possibili schemi di flusso al verificarsi di
una condizione
Nel primo caso, lo schema S viene eseguito solo se la condizione
C è vera; se C è falsa, non viene eseguita alcuna azione
Nel secondo caso, viene eseguito solo uno dei due schemi Sv o
Sf, in dipendenza del valore di verità della condizione
65
Struttura iterativa o di ripetizione
Il ciclo o loop è uno schema di flusso per descrivere, in modo conciso,
situazioni in cui uno gruppo di operazioni deve essere ripetuto più volte
La condizione di fine ciclo viene
verificata ogni volta che si
esegue il ciclo; se la condizione
assume valore vero (falso), le
istruzioni
vengono
reiterate,
altrimenti si esce dal ciclo
La condizione di fine ciclo può
essere verificata prima o dopo
l’esecuzione dell’iterazione
Le istruzioni di inizializzazione,
assegnano valori iniziali ad
alcune variabili (almeno a quella
che controlla la condizione di fine
Ciclo con controllo in testa
Ciclo con controllo in coda
ciclo)
66
Gli algoritmi iterativi
Problema: Calcolare la somma di tre
interi consecutivi( es. 13+14+15)
Note:
La fase di inizializzazione riguarda la
somma e l’indice del ciclo
Il controllo di fine ciclo viene
effettuato in coda
67
Gli algoritmi iterativi  4
Un ciclo è definito quando è noto a priori il numero di iterazioni:
un ciclo definito è detto anche enumerativo
Un contatore del ciclo tiene memoria di quante iterazioni sono
state effettuate; può essere utilizzato in due modi:
incremento del contatore: il contatore viene inizializzato ad un
valore minimo (ad es. 0) e incrementato ad ogni esecuzione
del ciclo; si esce dal ciclo quando il valore del contatore
eguaglia il numero di iterazioni richieste
decremento del contatore: il contatore viene inizializzato al
numero di iterazioni richiesto e decrementato di uno ad ogni
iterazione; si esce quando il valore del contatore raggiunge 0
68
Gli algoritmi iterativi  5
Un ciclo è indefinito quando non è possibile conoscere a
priori quante volte verrà eseguito
La condizione di fine ciclo controlla il valore di una o più
variabili modificate da istruzioni che fanno parte
dell’iterazione
Comunque, un ciclo deve essere eseguito un numero finito
di volte, cioè si deve verificare la terminazione
dell’esecuzione del ciclo
69
Gli algoritmi iterativi
Problema: Calcolo della media di
un insieme di numeri; non è noto
a priori quanti sono i numeri di
cui deve essere calcolata la media
I numeri vengono letti uno
alla volta fino a che non si
incontra un x = 0, che segnala
la fine dell’insieme
70
Fine
71
Proposizioni e predicati
Una proposizione è un costrutto linguistico del quale si può
asserire o negare la veridicità
Esempi
“Roma è la capitale della Gran Bretagna”
“3 è un numero intero”
falsa
vera
Il valore di verità di una proposizione è il suo essere vera o falsa
Una proposizione è un predicato se il suo valore di verità dipende
dall’istanziazione di alcune variabili
Esempi
“la variabile età è minore di 30”
“la variabile base è maggiore della variabile altezza”
72
Proposizioni e predicati
La valutazione di un predicato è l’operazione che permette di
determinare se il predicato è vero o falso, sostituendo alle variabili
i loro valori attuali
I valori vero e falso sono detti valori logici o booleani
Proposizioni e predicati possono essere espressi concisamente per
mezzo degli operatori relazionali:
= (uguale)
 (diverso)
> (maggiore)
< (minore)
 (maggiore o uguale)
 (minore o uguale)
I predicati che contengono un solo operatore relazionale sono detti
semplici
73
Proposizioni e predicati
Dato un predicato p, il predicato not p, detto opposto o negazione
logica di p, ha i valori di verità opposti rispetto a p
Dati due predicati p e q, la congiunzione logica di p e q, p and q, è
un predicato vero solo quando p e q sono entrambi veri, e falso in
tutti gli altri casi
Dati due predicati p e q, la disgiunzione logica di p e q, p or q, è un
predicato falso solo quando p e q sono entrambi falsi, e vero in
tutti gli altri casi
I predicati nei quali compare almeno uno fra gli operatori logici not,
and, or sono detti composti
La tavola di verità di un predicato composto specifica il valore del
predicato per ognuna delle possibili combinazioni dei suoi
argomenti
74
Proposizioni e predicati
Esempio
Le tavole di verità per i predicati p and q e p or q sono le
seguenti:
p
q
p and q
p or q
falso
falso
falso
falso
falso
vero
falso
vero
vero
falso
falso
vero
vero
vero
vero
vero
75
Proposizioni e predicati
Esempio
not (base > altezza)
è vero solo quando il valore di base è minore o uguale del valore di
altezza
età > 30 and età < 50
è vero solo quando il valore di età è compreso tra 30 e 50
base > altezza or base > 100
è vero quando il valore di base è maggiore del valore di altezza, o
quando il valore di base è maggiore di 100, o quando entrambe le
condizioni sono verificate
76
I vettori
Le variabili, definite come coppie <nome, valore>, sono
scalari
Una coppia <nome, insieme di valori > è una variabile
vettore o array e può essere immaginata come un
contenitore diviso in scomparti; ciascun scomparto può
contenere un valore, detto elemento o componente del
vettore
Ciascuna componente è individuata dal nome del vettore,
seguito dal relativo numero progressivo, racchiuso fra
parentesi tonde: l’indice del vettore
La dimensione di un vettore è il numero dei suoi elementi
I vettori sono particolarmente utili per collezionare dati fra
loro correlati, sui quali devono essere effettuate le stesse
operazioni
77
I vettori
v(1)
v(2)
v(3)
v(4)
Vettore v, costituito dai 4 elementi v(1), v(2), v(3), v(4)
L’utilizzo di variabili vettoriali, in un algoritmo, presuppone la
dichiarazione esplicita della loro dimensione
La dimensione del vettore costituisce un limite invalicabile
per la selezione delle componenti del vettore
Esempio: v(100) asserisce che il vettore v è costituito da 100
elementi; possono essere selezionati v(12), v(57), v(89), ma
non v(121) o v(763), che non esistono
78
I vettori
Esempio: Calcolare il vettore somma di due vettori di uguale
dimensione n
5
7
a(1)
a(2)
6
9
0
a(3)
1
3
a(4)
5
b(1)
b(2)
b(3)
b(4)
11
16
1
8
c(1)
c(2)
c(3)
c(4)
79
I vettori
Esempio: algoritmo per calcolare
il vettore somma di due vettori
Note:
L'utilità dei vettori consiste nell’impiego della tecnica iterativa
in modo da effettuare la stessa
operazione su tutti gli elementi
del vettore
Usando la variabile contatore di
un ciclo come indice degli
elementi di un vettore è
possibile considerarli tutti, uno
alla volta, ed eseguire su di essi
l’operazione desiderata
80
I vettori
Esempio: Algoritmo
per il calcolo del
massimo elemento di
un vettore
vero
81
La pseudocodifica  1
La pseudocodifica è un linguaggio per la descrizione di
algoritmi
La descrizione di un algoritmo mediante pseudocodifica si
compone di due parti...
la dichiarazione delle variabili usate nell’algoritmo
la descrizione delle azioni dell’algoritmo
82
La pseudocodifica  2
Tipo delle variabili
Il tipo di una variabile indica l’insieme dei valori che possono
essere assegnati a quella variabile
Su costanti e variabili di un tipo è possibile effettuare le
operazioni che sono proprie di quel tipo e tutte le operazioni
di confronto (utilizzando gli operatori relazionali)
Sono permessi i seguenti 4 tipi: integer, single, double,
boolean, string
83
La pseudocodifica  3
integer: sono le variabili cui possono essere assegnati numeri interi;
le costanti di tipo integer sono numeri interi, ad es. 1, 3, 150
real: sono le variabili cui possono essere assegnati numeri razionali;
le costanti real possono essere rappresentate in notazione decimale,
con un “.” che separa la parte intera dalla parte decimale (ad es.,
5.17, 12.367, 123., 0.005) o in notazione scientifica
(23.476E+2=2347.6, 456.985E4=0.0456985)
boolean: sono le variabili cui possono essere assegnati i valori
logici; le costanti logiche sono true e false
stringq: sono le variabili cui possono essere assegnate parole (o
stringhe) costituite da q caratteri; le costanti stringq sono
costituite da parole di q caratteri racchiusi tra apici (che non fanno
parte della costante); ad es., ‘FABIO’ è una costante string5,‘+’ è
una costante string1 e ‘124’ string3
84
La pseudocodifica  4
Dichiarazione delle variabili
La dichiarazione delle variabili è un elenco, preceduto dalla
parola var, delle variabili sulle quali l’algoritmo opera
Le variabili sono suddivise per tipo: quelle dello stesso tipo
sono separate l’una dall’altra da una “,”; l’elenco delle variabili
dello stesso tipo è seguito dai “:” e dall’indicazione del tipo; gli
elenchi di variabili di tipo diverso sono separati dal “;”, l’ultimo
elenco è seguito da un “.”
Esempio:
var i, j, a(20): integer;
p, q: real;
nome: string20;
sw: boolean.
85
La pseudocodifica  5
Descrizione delle azioni
Gli schemi di flusso fondamentali sono descritti utilizzando
convenzioni linguistiche: ad ogni schema di composizione
corrisponde una convenzione linguistica
La descrizione di un algoritmo deve soddisfare le seguenti
regole:
a)
b)
c)
d)
e)
La prima azione dell’algoritmo è preceduta dalla parola begin;
L’ultima azione dell’algoritmo è seguita dalla parola end;
L’azione di lettura è rappresentata dalla parola read;
L’azione di scrittura è rappresentata dalla parola write;
Lo schema di sequenza di n flussi S1, S2,…, Sn è rappresentato da
S1;
S2;
…
S n;
86
La pseudocodifica  6
S, Sf, Sv,
sono schemi
f)
Gli schemi di selezione sono rappresentati come:
g)
Gli schemi di iterazione sono rappresentati come:
87
La pseudocodifica  7
Esistono convezioni linguistiche alternative in relazione a
particolari schemi di flusso
Esempio: Ciclo enumerativo
Nel caso che il valore di
“incremento” sia 1, la parte
“step incremento” della frase
for...endfor può essere omessa
88
La pseudocodifica  8
Esempio: Algoritmo per il calcolo del vettore somma di due
vettori di numeri razionali
var a(100), b(100), c(100): real;
i, n: integer.
begin
read n;
for i from 1 to n do
read a(i), b(i);
c(i)  a(i) + b(i);
write c(i)
endfor
end
89
La pseudocodifica  9
Esempio: Algoritmo per il calcolo del massimo elemento di un
vettore di numeri razionali
var max, v(100): real;
i, n: integer.
begin
read n;
for i from 1 to n do
read v(i)
endfor
max  v(1);
for i from 2 to n do
if max < v(i)
then max  v(i)
endif
endfor
write max
end
90
La pseudocodifica  10
Esempio: Algoritmo per il calcolo delle radici di equazioni di
2° grado
var x1, x2, a, b, c, delta: real.
begin
read a, b, c;
delta  b24ac;
if delta < 0
then write “non esistono radici reali”
else if delta = 0
then x1  b/2a;
x2  x1
else x1  (b + delta)/2a;
x2  (b  delta)/2a
endif
write x1, x2
endif
end
91
Introduzione ai linguaggi di
programmazione di alto livello
92
Cenni storici  1
Benché siano macchine in grado di compiere operazioni complesse,
i calcolatori devono essere “guidati” per mezzo di istruzioni
appartenenti ad un linguaggio specifico e limitato, a loro
comprensibile
A livello hardware, i calcolatori riconoscono solo comandi semplici,
del tipo “copia un numero”, “addiziona due numeri”, “confronta due
numeri” : questi comandi definiscono il set di istruzioni della
macchina e i programmi che li utilizzano direttamente sono i
programmi in linguaggio macchina
In linguaggio macchina ogni operazione richiede l’attivazione di
numerose istruzioni base (il linguaggio riflette l’organizzazione della
macchina più che la natura del problema da risolvere); inoltre,
qualunque entità  istruzioni, variabili, dati  è rappresentata da
numeri binari: i programmi sono difficili da scrivere, leggere e
mantenere
93
Cenni storici  2
Negli anni `50, tutti i programmi erano scritti in linguaggio
macchina o in assembly (o assembler)
In assembly ogni istruzione è identificata da una sigla piuttosto
che da un numero e le variabili sono rappresentate da nomi
piuttosto che da numeri
Esempio: carica il numero 8 nel primo registro libero della CPU
0011 1000 
LOAD 8
Codice
istruzione
Linguaggio macchina
Assembly
I programmi scritti in assembly necessitano di un apposito
programma assemblatore per tradurre le istruzioni tipiche del
linguaggio in istruzioni macchina
94
Cenni storici  3
L’assembly definisce una notazione simbolica che è in stretta
relazione con i codici in linguaggio macchina
registro
LOAD R1, MEM1
CMP R1, R2
BEQ RISZERO
STORE R1, MEM1
RISZERO:
LOAD R2, MEM2
Assemblatore
10001000110110101101010101010100
01001001001000000000000000000101
11000000000000000000000000001000
10011000110110101101010101010100
10001001010110101101001000001100
OPCODE
(LOAD)
95
Cenni storici  4
Oggi si utilizza l’assembly solo se esistono vincoli stringenti sui
tempi di esecuzione; viceversa si usano linguaggi più vicini al
linguaggio naturale, i linguaggi di alto livello
I linguaggi di alto livello sono elementi intermedi di una varietà di
linguaggi ai cui estremi si trovano il linguaggio macchina, da un
lato, ed i linguaggi naturali, come l’italiano e l’inglese, dall’altro
I
linguaggi
di
programmazione,
progettati per manipolare informazioni,
differiscono dai linguaggi naturali: sono
infatti meno espressivi ma più precisi
(non ambigui)
96
Scopi e caratteristiche  1
I linguaggi di programmazione di alto livello consentono al
programmatore di trattare oggetti complessi senza doversi
preoccupare dei dettagli della particolare macchina sulla quale il
programma viene eseguito
Richiedono un compilatore o un interprete che sia in grado di
tradurre le istruzioni del linguaggio di alto livello in istruzioni
macchina di basso livello eseguibili dal calcolatore
Un compilatore è un programma “simile” ad un assemblatore, ma
più complesso, infatti…
esiste una corrispondenza biunivoca fra istruzioni in assembler ed
istruzioni macchina
ogni singola istruzione di un linguaggio di alto livello corrisponde a
molte istruzioni in linguaggio macchina: quanto più il linguaggio di
programmazione si discosta dal linguaggio macchina, tanto più il
lavoro di traduzione del compilatore è difficile
97
Scopi e caratteristiche  2
Esempio: In PASCAL, l’assegnazione
e := (a+b)(c+d);
calcola l’espressione e, ottenuta eseguendo una serie di operazioni
aritmetiche sulle variabili a, b, c, e d, salvando opportunamente il
risultato nella posizione di memoria etichettata da e; in linguaggio
assembly la stessa istruzione potrebbe essere riscritta nel modo
seguente:
LOAD a, %r0
LOAD b, %r1
ADD %r0, %r1
LOAD c, %r2
LOAD d, %r3
ADD %r2, %r3
MULT %r1, %r3
STORE %r3, e
98
Scopi e caratteristiche  3
I linguaggi che non dipendono dall’architettura
macchina offrono due vantaggi fondamentali:
i programmatori non devono
architetturali di ogni calcolatore
cimentarsi
con
i
della
dettagli
i programmi risultano più semplici da leggere e da modificare
 portabilità, leggibilità, mantenibilità
99
L’essenza della programmazione di alto livello, ovvero dell’uso di linguaggi di elevata potenza espressiva,
risiede nella capacità di astrazione, cioè nella possibilità di prescindere dai dettagli considerati inessenziali
ai fini della soluzione di un problema, favorendo con ciò la concentrazione sugli elementi fondamentali. Un
linguaggio di programmazione deve fornire all'utente buoni meccanismi per definire autonomamente tutte
le astrazioni di cui ha bisogno: il programmatore, deve disporre di strumenti sufficienti per spiegare al
calcolatore tutte le operazioni che intende effettuare.
Scopi e caratteristiche  4
La funzione svolta da un programma ben strutturato in un linguaggio di programmazione di alto livello può
essere facilmente compresa da un lettore: i simboli e le istruzioni utilizzate si avvicinano più ai simboli ed
alle istruzioni di uso comune che non a quelle interne del calcolatore.
Portabilità: i programmi scritti per un calcolatore possono essere
utilizzati su qualsiasi altro calcolatore, previa ricompilazione
Leggibilità: la relativa similitudine con i linguaggi naturali rende i
programmi più semplici, non solo da scrivere, ma anche da leggere
Mantenibilità: con questo termine si intende far riferimento a
modifiche di tipo correttivo, perfettivo, evolutivo e adattivo; i
programmi scritti in linguaggi di alto livello sono più semplici da
modificare e da correggere
La possibilità di codificare algoritmi in maniera astratta si traduce in
una migliore comprensibilità del codice e quindi in una più facile
analisi di correttezza
100
Scopi e caratteristiche  5
Eventuale svantaggio dell’uso dei linguaggi di alto livello è la
riduzione di efficienza:
È possibile utilizzare istruzioni macchina diverse per scrivere
programmi funzionalmente equivalenti: il programmatore ha un
controllo limitato sulle modalità con cui il compilatore traduce il
codice
Tuttavia… i compilatori attuali ricorrono a trucchi di cui molti
programmatori ignorano l’esistenza
La ragione fondamentale per decretare la superiorità dei
linguaggi di alto livello consiste nel fatto che la maggior parte
dei costi di produzione del software è localizzata nella fase di
manutenzione, per la quale la leggibilità e la portabilità sono
cruciali
101
Un esempio di programma PASCAL
begin
leggi n, ncomp
Problema: Si legga una lista di
valori, la cui lunghezza non è nota a
priori (è un dato in ingresso),
stampando un opportuno messaggio
se un certo valore, anch’esso letto a
runtime,
appartiene
o
non
appartiene alla lista
trovato  FALSE
i1
leggi ncorr
Vero
ncorr = ncomp
Falso
i  i+1
Vero
in
Falso
“trovato un
numero uguale”
trovato  TRUE
Vero
trovato = TRUE
end
Falso
“non trovato
un numero uguale”
102
PROGRAM Search(input,output);
(* Ricerca di un valore desiderato in una lista *)
VAR
n: INTEGER; (* lunghezza della lista *)
ncomp: INTEGER; (* termine di paragone *)
ncorr: INTEGER; (* valore nella lista *)
trovato: BOOLEAN; (* TRUE se si è trovato *)
i: INTEGER; (* contatore dei valori della lista *)
BEGIN
READ(n);
WRITELN(‘Ci sono’, n, ‘valori.’);
READ(ncomp);
WRITELN(‘Ricerca di’, ncomp, ‘.’);
trovato := FALSE; (* non ancora trovato alcun valore *)
FOR i = 1 TO n DO
BEGIN
READ(ncorr);
WRITELN(ncorr);
IF ncorr = ncomp
THEN trovato := TRUE; (* trovato un valore uguale *)
END (* fine ciclo for *)
IF trovato
THEN WRITELN (‘Trovata corrispondenza’)
ELSE WRITELN (‘Non trovata corrispondenza’);
END (* fine programma Search *)
103
Schemi di composizione  3
Schema di iterazione: si itera l’esecuzione di un dato schema
di flusso
Nel primo caso, S può non venire mai eseguito, se la condizione
C è subito falsa; nel secondo caso, S viene eseguito almeno una
volta
Quando lo schema S viene eseguito finché la condizione C si
mantiene vera si parla di iterazione per vero; si ha un’iterazione
per falso quando S viene eseguito finché C è falsa
104
Gli algoritmi iterativi  1
Accade spesso che, per risolvere un
problema, un certo insieme di
operazioni debba essere eseguito un
dato numero di volte
Esempio: Calcolare la somma di tre
interi consecutivi
Note:
La variabile somma è un contenitore
di somme parziali, finché non si
ottiene la somma totale richiesta
La soluzione del problema viene
raggiunta eseguendo azioni simili
per un numero opportuno di volte
105
Proprietà degli algoritmi
Affinché un elenco di istruzioni, possa essere considerato un
algoritmo, devono essere soddisfatti i seguenti requisiti:
Finitezza: ogni algoritmo deve essere finito, cioè composto da un
numero finito di istruzioni, ciascuna delle quali deve essere eseguita
in tempo finito ed un numero finito di volte
Generalità: ogni algoritmo deve fornire la soluzione per una classe
di problemi; deve pertanto essere applicabile a qualsiasi insieme di
dati appartenenti all’insieme di definizione o dominio dell’algoritmo
e deve produrre risultati che appartengono all’insieme di arrivo o
codominio
Non ambiguità: devono essere definiti in modo chiaro i passi
successivi da eseguire; devono essere evitati paradossi,
contraddizioni ed ambiguità; il significato di ogni istruzione deve
essere univoco per chiunque esegua l’algoritmo
Inoltre sono importanti la correttezza e l’efficienza di un algoritmo
106
Sintassi
La condizione è sempre un'espressione di tipo booleano (VERO/FALSO).
Il ramo ELSE (corrispondente all'alternativa falsa) può essere omesso.
Esempio:
If condizione Then
Istruzione1
Istruzione2
………..
Else istruzioni
End If
If valore > 0 Then
Label1.Caption= "Il valore è positivo“
Else
Label1.Caption= "Il valore è minore o uguale
a zero“
End If
107
Il ciclo con controllo alla fine
Do istruzioni
Loop Until condizione
(La condizione è una espressione di tipo booleano).
Esempio: Somma di N numeri
Dim numero, somma As Single
Do
numero = Val(InputBox("Inserisci un numero (zero per finire)", "Inserimento"))
somma = somma + numero
Loop Until numero = 0
Label1.Caption = CStr(somma)
108
Il ciclo con controllo all'inizio
Do While condizione
Istruzioni
Loop
(La condizione è una espressione di tipo booleano).
Esempio: Somma N numeri
Dim numero, somma As Single
Do While numero <> -1
numero = Val (InputBox("Inserisci un numero (-1 per finire)", "Inserimento"))
somma = somma + numero
Loop
Label1.Caption = CStr(somma)
109
Compiti del Programmatore
Analizzare il problema riducendolo in termini astratti, eliminando
ogni componente non indispensabile e formulando un modello del
problema.
Individuare una strategia risolutiva e ricondurla ad un algoritmo.
Codificare l’algoritmo in modo tale da renderlo comprensibile al
calcolatore (programma).
Analizzare il risultato dell’elaborazione evidenziando eventuali errori
nella formulazione del problema, nella strategia risolutiva, nella
codifica dell’algoritmo (debugging, errori di sintassi o logici)
110
Definizione di Algoritmo
Un algoritmo è corretto se perviene alla soluzione
del compito cui è preposto
Un algoritmo è efficiente se perviene alla soluzione
del problema nel modo più veloce possibile e/o
usando la minor quantità di risorse fisiche
(memoria, tempo di esecuzione, ecc.)
Gli algoritmi devono essere formalizzati per mezzo
di un linguaggio di programmazione, dotato di
precise strutture linguistiche (sintassi e semantica)
111
Il ciclo con contatore FOR
For contatore = minimo To massimo
Istruzioni
Next
(La variabile contatore è sempre di tipo numerico intero)
Esempio
Dim cont As Integer
For cont = 1 To 10
Print "Il valore di CONT è: " + CStr(cont)
Picture1.Print "Il valore di CONT è: " + CStr(cont)
‘con PictureBox
Next
112
Cicli
113
maggiore
114
Esempio  Radici di equazioni di 2° grado
Problema: Calcolo delle radici reali dell’equazione di secondo
grado ax2+bx+c=0
Algoritmo:
1)
2)
3)
4)
5)
6)
7)
Acquisire i coefficienti a,b,c
Calcolare  = b24ac
Se <0 non esistono radici reali, eseguire l’istruzione 7)
Se = 0, x1= x2 = b/2a, poi eseguire l'istruzione 6)
Calcolare x1 = (b +)/2a x2 = (b )/2a
Comunicare i valori x1, x2
Fine
115
Esempio  Radici di equazioni di 2° grado
Problema: Calcolo delle radici reali dell’equazione di secondo
grado ax2+bx+c=0
Algoritmo:
1)
2)
3)
4)
5)
6)
7)
Acquisire i coefficienti a,b,c
Calcolare  = b24ac
Se <0 non esistono radici reali, eseguire l’istruzione 7)
Se = 0, x1= x2 = b/2a, poi eseguire l'istruzione 6)
Calcolare x1 = (b +)/2a x2 = (b )/2a
Comunicare i valori x1, x2
Fine
116
I diagrammi a blocchi
inizio
Diagramma a blocchi dell’algoritmo per
il calcolo delle radici dell’equazione di
2° grado ax2 + bx + c = 0
Leggi a,b,c
delta  b2  4ac
Algoritmo (pseudocodifica):
Vero
1. Acquisire i coefficienti a,b,c
2. Calcolare  = b24ac
3. Se <0 non esistono radici reali,
eseguire l’istruzione 7
4. Se = 0, x1= x2 = b / 2a, poi
eseguire l'istruzione 6
5. Calcolare x1 = (b +) / 2a
Calcolare x2 = (b ) / 2a
6. Stampare i valori x1, x2
scrivi
“non ci sono radici reali”
7. Fine
Falso
delta<0
Falso
Vero
delta=0
x1 b/2a
x1 (b+sqrt(delta))/2a
x2 b/2a
x2 (bsqrt(delta))/2a
scrivi
x1 e x2
117
fine