Informatica e Informatica di Base
ALGORITMI
E
LINGUAGGI DI PROGRAMMAZIONE
Francesco Tura
[email protected]
© F. Tura
1
Lo strumento dell’informatico:
ELABORATORE ELETTRONICO
[= calcolatore = computer]


Macchina multifunzionale
Macchina per l’elaborazione dell’informazione
 guidata dal software
© F. Tura
2
Problemi di elaborazione
dell’informazione
problemi di
gestione
dell’informazione
problemi di
manipolazione
dell’informazione
-rappresentazione
-aggiornamento
-reperimento
es. (reperimento): trovare il numero
telefonico di una determinata persona
© F. Tura
es. calcolare il costo totale di un
certo numero di prodotti
3
Problemi di elaborazione dell’informazione
Creazione del software (programmi) necessario
ALGORITMI
Un problema di elaborazione dell’informazione
si risolve elaborando un algoritmo

ALGORITMO  Sequenza di passi da compiere per
ottenere la risoluzione [dati di output]
di un certo problema di elaborazione
dell’informazione a partire da una
determinata situazione iniziale [= dati
iniziali]
© F. Tura
4
Esempio di algoritmo per la risoluzione di un
problema di elaborazione (reperimento)
dell’informazione
 Ricerca di numero telefonico corrispondente a una persona
PASSO 1. Apri l’elenco telefonico alla prima pagina e vai sulla prima
riga
PASSO 2. Leggi il nominativo indicato
PASSO 3. Confronta il nominativo indicato con quello cercato: i
nominativi coincidono? Se sì, vai al passo successivo, se no, passa alla
riga successiva e ritorna al Passo 2
PASSO 4. Leggi il numero di telefono corrispondente al nominativo
indicato -> soluzione del problema
NB: L’esempio riporta – a solo scopo illustrativo – un algoritmo molto poco
efficiente, in quanto non sfrutta il fatto che i nominativi sull’elenco telefonico
compaiono in ordine alfabetico
© F. Tura
5
Formulazioni di un algoritmo
DIAGRAMMA DI FLUSSO <=> formulazione di un
algoritmo in formalismo grafico (ove ai passi dell’algoritmo
corrispondono i nodi del diagramma)
PROGRAMMA <=> formulazione di un algoritmo in un
linguaggio di programmazione (ove ai passi dell’algoritmo
corrispondono le istruzioni del programma)
© F. Tura
6
Fasi della progettazione del software
1. Studio del problema (dati iniziali e dati di output da ottenere)
2. Definizione dell’algoritmo di risoluzione del problema [= analisi
di fattibilità]
3. Formulazione dell’algoritmo in diagramma di flusso
4. Traduzione del diagramma di flusso in linguaggio di
programmazione  creazione di un programma
7
Diagramma di flusso (flow chart)

Formalismo grafico per esprimere un algoritmo

È composto da:
Nodi  figure geometriche contenenti stringhe di
testo
Archi  linee che collegano i nodi dotate di
frecce per indicarne la “direzione” di collegamento
© F. Tura
8
Diagramma di flusso
Nodi
Ciascun nodo del diagramma di flusso contiene
una stringa la quale esprime l’azione che deve
essere eseguita quando durante l’esecuzione
dell’algoritmo, si incontra quel nodo

Le azioni vengono eseguite utilizzando tra
l’altro delle variabili

VARIABILE  nome simbolico che rappresenta un
valore che può variare durante l’esecuzione
dell’algoritmo
© F. Tura
9
Diagramma di flusso
Archi
Gli archi sono i tratti di congiunzione tra i nodi,
e sono dotati di una freccia la quale indica la
direzione di proseguimento dell’algoritmo

© F. Tura
10
Diagramma di flusso
Tipi di nodi
START
STOP
inizio dell’algoritmo
fine dell’algoritmo
assegnazione
© F. Tura
11
Diagramma di flusso
Tipi di nodi
lettura dati in input
scrittura dati in output
S
© F. Tura
N
test booleano (confronto)
12
Diagramma di flusso
Tipi di azioni
Assegnazione
 azione mediante la quale viene assegnato un valore ad una variabile
Il valore assegnato diviene valore corrente della variabile e resta tale finché una
successiva assegnazione non cambi il valore stesso
A  5
© F. Tura
esempio 1: assegnazione alla variabile A
del valore 5
13
Diagramma di flusso
Tipi di azioni: assegnazione
© F. Tura
A  B
esempio 2: assegnazione alla variabile A
del valore corrente della variabile B
A  B+1
esempio 3: assegnazione alla variabile A
del valore corrente della variabile B
incrementato di 1
14
Diagramma di flusso
Tipi di azioni: assegnazione

In generale una assegnazione ha la seguente forma:
VARIABILE  ESPRESSIONE ARITMETICA
A  A+1
© F. Tura
esempio 4: assegnazione il cui risultato è
quello di incrementare il valore corrente
della variabile A
15
Diagramma di flusso
Tipi di azioni
Lettura da input
 azione mediante la quale viene assegnato ad una variabile un valore
specificato dall’esterno
La variabile viene cioè associata ad un dato di input
A
© F. Tura
esempio: alla variabile A viene assegnato il
valore fornito in input
16
Diagramma di flusso
Tipi di azioni
Scrittura in output
 azione mediante la quale viene restituito all’esterno il valore
corrente di una variabile
Il valore della variabile diviene un risultato di output
C
© F. Tura
esempio: il valore corrente della variabile
C viene restituito in output
17
Diagramma di flusso
Tipi di azioni
Test booleano
 azione mediante la quale viene effettuato un confronto (test) di
tipo logico tra due variabili o - più in generale - tra due espressioni
aritmetiche: il risultato può essere vero o falso
S
© F. Tura
N
In caso di risultato affermativo (vero)
del test viene seguita la freccia uscente
dal vertice del rombo marcato da S, in
caso di risultato negativo (falso) viene
seguita la freccia uscente dal vertice del
rombo marcato da N
18
Diagramma di flusso
Tipi di azioni: test booleano

Possono essere effettuati 6 tipi di confronto:
© F. Tura
UGUALE
=
DIVERSO
≠
MINORE
<
MAGGIORE
>
MINORE
O UGUALE
≤
MAGGIORE
O UGUALE
≥
19
Diagramma di flusso
Tipi di azioni: test booleano
S
S
© F. Tura
A≠5
A≥B+3
N
N
esempio 1: il risultato del confronto sarà
vero se il valore corrente della variabile A
è diverso da 5
esempio 2: il risultato del confronto sarà
vero se il valore corrente della variabile A
è maggiore o uguale a quello della
variabile B incrementato di 3
20
Diagramma di flusso
Esempi di algoritmi elementari
START
A
Problema n. 1. Dati 2 numeri,
calcolare la loro somma
B
C A+B
C
STOP
© F. Tura
21
Diagramma di flusso - Esempi di algoritmi elementari
Problema n. 2. Dati N numeri,
calcolare la loro somma
© F. Tura
22
Linguaggi di Programmazione
Passo successivo nella creazione di un programma:
 Traduzione del diagramma di flusso in un linguaggio di
programmazione di alto livello
Programmatore
Linguaggio
di
alto livello
© F. Tura
Computer
Programma
Compilatore o
Interprete
Linguaggio
Macchina
23
Linguaggi di programmazione
Linguaggio di alto livello

È quello in cui l’utente programmatore scrive il programma

Usa termini comprensibili dall’uomo
Esempi: Pascal
Fortran
Basic
C
Prolog
HTML
CODICE SORGENTE  Programma [= serie di istruzioni]
scritto in linguaggio di alto livello
© F. Tura
24
Linguaggi di programmazione
Linguaggio macchina

È quello interpretabile da parte della CPU del computer

È costituito da una serie di cifre binarie (bit) suddivise in
gruppi di 8 cifre (byte)

Varia a seconda del tipo di computer (ovvero della sua CPU)
CODICE OGGETTO  Programma [= serie di istruzioni]
scritto in linguaggio macchina
© F. Tura
25
Programmi Compilatori e Interpreti

Traducono in linguaggio macchina un programma scritto in
linguaggio di alto livello
 traducono il codice sorgente in codice oggetto

Sono specifici per il tipo di macchina su cui operano

A seconda del tipo di linguaggio di alto livello si dividono in:
COMPILATORI
• Traducono il programma intero
 dato un file contenente codice
sorgente, il compilatore crea un altro file
contenente codice oggetto
• Vengono mandati in esecuzione solo
quando il codice sorgente è stato
scritto completamente dal programmatore
© F. Tura
INTERPRETI
• Traducono il programma istruzione
per istruzione, interattivamente
• Vengono mandati in esecuzione prima
di scrivere il programma, per creare
l’ambiente interprete che traduce
immediatamente le varie istruzioni del
programma che ivi verranno scritte
26
dall’utente-programmatore
Programmi Compilatori e Interpreti

L’impiego – per la traduzione del codice – del programma
compilatore piuttosto che del programma interprete dipende dal
linguaggio di alto livello
I programmi che vengono tradotti tramite un programma compilatore
dicono linguaggi compilati
Es. PASCAL
I programmi che vengono tradotti tramite un programma interprete si
dicono linguaggi interpretati
Es. PROLOG
© F. Tura
27
Codice sorgente e codice oggetto
Un file contenente codice oggetto si dice anche
file eseguibile
• Un file contenente codice oggetto è direttamente eseguibile
su comando dato dall’utente e non è leggibile (contiene
cifre binarie)
• Nel caso di software di proprietà, solo i file contenenti
il codice oggetto vengono venduti all’utente, mentre quelli
contenenti il codice sorgente vengono trattenuti dall’autore
e su di essi si applica il diritto d’autore (copyright).
Nel caso di software open source, invece, vengono resi
disponibili all’utente anche i file contenente codice sorgente,
cosicché l’utente è in grado di può modificare il programma
© F. Tura
28
Esercizi
START
Problema n. 1. Dati 2 numeri,
scegliere il maggiore
A
B
DIAGRAMMA DI FLUSSO
S
A≥ B
CA
N
CB
C
STOP
© F. Tura
29
Esercizi
Problema n. 1. Dati 2 numeri,
scegliere il maggiore
program Sceglimaggiore;
var A, B, C: integer;
begin
read(A);
read(B);
if A ≥ B
then C := A
otherwise C := B;
write(C);
end
© F. Tura
PROGRAMMA PASCAL
30
Esercizi
Problema n. 2. Dati N numeri,
calcolare la loro somma
DIAGRAMMA DI FLUSSO
© F. Tura
31
Esercizi
Problema n. 2. Dati N numeri,
calcolare la loro somma
program eseguiSomma;
var I, N, SOMMA, NUOVO: integer;
begin
read(N);
I := 0;
SOMMA := 0;
repeat
read(NUOVO);
SOMMA := SOMMA + NUOVO;
I := I + 1;
until I=N;
write(SOMMA);
end
PROGRAMMA PASCAL
© F. Tura
32