L’idea di programmazione

Corso di Fondamenti di Informatica e Programmazione,

DAMS 2020-21
Felice Cardone
Programmi
Programmi come testi

Ci sono molte varietà di testi:

• romanzi,
• cronache,
• poesie,
• leggi,
• ricette di cucina,
• dimostrazioni matematiche,
• manuali d’uso,
• contratti,
• guide turistiche,
• cataloghi,
Programmi come testi

Ci sono molte varietà di testi:

• romanzi,
• cronache,
• poesie,
• leggi,
• ricette di cucina,
• dimostrazioni matematiche,
• manuali d’uso,
• contratti,
• guide turistiche,
• cataloghi,
• programmi
Programmi come testi

Ogni tipo di testo può essere studiato da molti punti di vista.

E un programma?
Ha una funzionalità
Come un utensile, un programma serve a raggiungere un obiettivo (per esempio
il risultato di un calcolo)

È scritto in un linguaggio (di programmazione)

I programmi sono testi scritti in un linguaggio di programmazione.
Servono a controllare un computer in modo che abbia la funzionalità richiesta

È eseguibile
Un computer esegue un programma

È leggibile
Un programmatore scrive programmi e legge programmi scritti da altri
Linguaggi di programmazione come linguaggi

❝ Per molti anni è stata mia opinione che i linguaggi di

programmazione in particolare, ed i linguaggi meccanici in
generale, mostrino molti fenomeni generalmente ritenuti
caratteristici dei linguaggi naturali
la notazione coreografica e quella musicale sono linguaggi
meccanici, come la notazione per le formule strutturali in
chimica […] alberi di analisi sintattica ed altre notazioni per
la struttura linguistica, disegni meccanici, diagrammi di
cablaggio, schemi a blocchi, diagrammi di controllo della
produzione e schemi di organizzazione nell’industria. Anche
i sistemi di catalogazione, sistemi di contabilità e inventari.
Includerei perfino le notazioni ed i sistemi di disposizione
dei monumenti ed i loro contenuti ❞ (Saul Gorn, 1967)
10 PRINT CHR$(205.5+RND(1)); : GOTO 10

Una monografia
interamente dedicata a
un programma di una
riga scritto in Basic
10 PRINT CHR$(205.5+RND(1)); : GOTO 10

NICK MONTFORT, PATSY BAUDOIN,

JOHN BELL, IAN BOGOST, JEREMY DOUGLASS,

MARK C. MARINO, MICHAEL MATEAS,

CASEY REAS, MARK SAMPLE, NOAH VAWTER

Alcune schermate dell’esecuzione del programma
Alcune schermate dell’esecuzione del programma
Alcune schermate dell’esecuzione del programma
Alcune schermate dell’esecuzione del programma
Alcune schermate dell’esecuzione del programma
Alcune schermate dell’esecuzione del programma
Programmi e algoritmi

Un programma, in generale, è composto da istruzioni che

costituiscono i passi di un algoritmo per la soluzione di un
problema.
Ciascuna istruzione deve potere essere eseguita da un
computer.
I problemi adatti ad essere risolti tramite algoritmi si chiamano
problemi algoritmici.
La descrizione di un problema algoritmico si chiama la sua
specifica.
Resta il problema di capire quando un algoritmo (o il
programma che lo descrive) produce la soluzione del problema
descritto dalla specifica: un problema di correttezza.
L’attività di programmazione: esempi

Vogliamo cercare su un CD un brano che ci interessa, ed eseguirlo.

I comandi sono:

Un programma è una sequenza di comandi, per esempio:

⏯ ⏭ ⏭ ⏭ ⏯
L’attività di programmazione: esempi

Vogliamo programmare i movimenti di un robot in una stanza in modo che vada a

prendere un oggetto che ci interessa.

Un sistema di coordinate definisce le posizioni entro la stanza.

I comandi che il robot può eseguire sono:
↑ (un passo avanti)
↓ (un passo indietro)
→ (un passo a destra)
← (un passo sinistra)
Un programma è una sequenza di comandi, per esempio:
↑↑↑→→↓↓↓
Accade che questo programma sia equivalente a
→→
L’attività di programmazione: esempi

? 🍔

🤖
L’attività di programmazione: esempi

🤖
L’attività di programmazione: esempi

🤖 ↑↑↑→→→→→→
L’attività di programmazione: esempi

→→→→→→↑↑↑
🍔

🤖
Strutture dei dati (promemoria)

Pila Coda Albero

Che cos’è un programma?

Niklaus Wirth, 1969

Algoritmi
Un problema “algoritmico” (dal film Die Hard)

5L 3L

Dati due recipienti, G da 5 litri e p da 3 litri, e una disponibilità illimitata di acqua,

trovare un modo per avere esattamente 4 litri di acqua in G usando solo le seguenti
operazioni:

riempire G
riempire p
vuotare (anche in parte) il contenuto di G in p (G → p)
vuotare (anche in parte) il contenuto di p in G (p → G)
vuotare G
vuotare p
Una soluzione
G = 0, p = 0
Una soluzione
G = 0, p = 0
riempi G

G = 5, p = 0
Una soluzione
G = 0, p = 0
riempi G

G = 5, p = 0
G→p

G = 2, p = 3
Una soluzione
G = 0, p = 0
riempi G

G = 5, p = 0
G→p

G = 2, p = 3
vuota p

G = 2, p = 0
Una soluzione
G = 0, p = 0
riempi G

G = 5, p = 0
G→p

G = 2, p = 3
vuota p

G = 2, p = 0
G→p

G = 0, p = 2
Una soluzione
G = 0, p = 0
riempi G

G = 5, p = 0
G→p

G = 2, p = 3
vuota p

G = 2, p = 0
G→p

G = 0, p = 2
riempi G

G = 5, p = 2
Una soluzione
G = 0, p = 0
riempi G

G = 5, p = 0
G→p

G = 2, p = 3
vuota p

G = 2, p = 0
G→p

G = 0, p = 2
riempi G

G = 5, p = 2
G→p

G = 4, p = 3
Una soluzione
G = 0, p = 0
riempi G

G = 5, p = 0
G→p

G = 2, p = 3
vuota p

G = 2, p = 0
G→p

G = 0, p = 2
riempi G

G = 5, p = 2
G→p

G = 4, p = 3
vuota p

G = 4, p = 0
Una soluzione Altra soluzione
G = 0, p = 0 G = 0, p = 0
riempi G

G = 5, p = 0
G→p

G = 2, p = 3
vuota p

G = 2, p = 0
G→p

G = 0, p = 2
riempi G

G = 5, p = 2
G→p

G = 4, p = 3
vuota p

G = 4, p = 0
Una soluzione Altra soluzione
G = 0, p = 0 G = 0, p = 0
riempi G riempi p
G = 5, p = 0 G = 0, p = 3
G→p

G = 2, p = 3
vuota p

G = 2, p = 0
G→p

G = 0, p = 2
riempi G

G = 5, p = 2
G→p

G = 4, p = 3
vuota p

G = 4, p = 0
Una soluzione Altra soluzione
G = 0, p = 0 G = 0, p = 0
riempi G riempi p
G = 5, p = 0 G = 0, p = 3
G→p p→G
G = 2, p = 3 G = 3, p = 0
vuota p

G = 2, p = 0
G→p

G = 0, p = 2
riempi G

G = 5, p = 2
G→p

G = 4, p = 3
vuota p

G = 4, p = 0
Una soluzione Altra soluzione
G = 0, p = 0 G = 0, p = 0
riempi G riempi p
G = 5, p = 0 G = 0, p = 3
G→p p→G
G = 2, p = 3 G = 3, p = 0
vuota p riempi p
G = 2, p = 0 G = 3, p = 3
G→p

G = 0, p = 2
riempi G

G = 5, p = 2
G→p

G = 4, p = 3
vuota p

G = 4, p = 0
Una soluzione Altra soluzione
G = 0, p = 0 G = 0, p = 0
riempi G riempi p
G = 5, p = 0 G = 0, p = 3
G→p p→G
G = 2, p = 3 G = 3, p = 0
vuota p riempi p
G = 2, p = 0 G = 3, p = 3
G→p p→G
G = 0, p = 2 G = 5, p = 1
riempi G

G = 5, p = 2
G→p

G = 4, p = 3
vuota p

G = 4, p = 0
Una soluzione Altra soluzione
G = 0, p = 0 G = 0, p = 0
riempi G riempi p
G = 5, p = 0 G = 0, p = 3
G→p p→G
G = 2, p = 3 G = 3, p = 0
vuota p riempi p
G = 2, p = 0 G = 3, p = 3
G→p p→G
G = 0, p = 2 G = 5, p = 1
riempi G vuota G
G = 5, p = 2 G = 0, p = 1
G→p

G = 4, p = 3
vuota p

G = 4, p = 0
Una soluzione Altra soluzione
G = 0, p = 0 G = 0, p = 0
riempi G riempi p
G = 5, p = 0 G = 0, p = 3
G→p p→G
G = 2, p = 3 G = 3, p = 0
vuota p riempi p
G = 2, p = 0 G = 3, p = 3
G→p p→G
G = 0, p = 2 G = 5, p = 1
riempi G vuota G
G = 5, p = 2 G = 0, p = 1
G→p p→G

G = 4, p = 3 G = 1, p = 0
vuota p

G = 4, p = 0
Una soluzione Altra soluzione
G = 0, p = 0 G = 0, p = 0
riempi G riempi p
G = 5, p = 0 G = 0, p = 3
G→p p→G
G = 2, p = 3 G = 3, p = 0
vuota p riempi p
G = 2, p = 0 G = 3, p = 3
G→p p→G
G = 0, p = 2 G = 5, p = 1
riempi G vuota G
G = 5, p = 2 G = 0, p = 1
G→p p→G

G = 4, p = 3 G = 1, p = 0
vuota p riempi p
G = 4, p = 0 G = 1, p = 3
Una soluzione Altra soluzione
G = 0, p = 0 G = 0, p = 0
riempi G riempi p
G = 5, p = 0 G = 0, p = 3
G→p p→G
G = 2, p = 3 G = 3, p = 0
vuota p riempi p
G = 2, p = 0 G = 3, p = 3
G→p p→G
G = 0, p = 2 G = 5, p = 1
riempi G vuota G
G = 5, p = 2 G = 0, p = 1
G→p p→G

G = 4, p = 3 G = 1, p = 0
vuota p riempi p
G = 4, p = 0 G = 1, p = 3
p→G

G = 4, p = 0
Alcune domande

(1) Si possono ottenere 4 litri di acqua in G quando:

a) G = 8, p = 3 ?
b) G = 7, p = 3 ?
c) G = 6, p = 3 ?
(risolubilità)
Alcune domande

(1) Si possono ottenere 4 litri di acqua in G quando:

a) G = 8, p = 3 ?
b) G = 7, p = 3 ?
c) G = 6, p = 3 ?
(risolubilità)

(2) Nel caso in cui una soluzione esiste, qual è il numero minimo di operazioni per
ottenerla? (complessità in tempo)
Alcune domande

(1) Si possono ottenere 4 litri di acqua in G quando:

a) G = 8, p = 3 ?
b) G = 7, p = 3 ?
c) G = 6, p = 3 ?
(risolubilità)

(2) Nel caso in cui una soluzione esiste, qual è il numero minimo di operazioni per
ottenerla? (complessità in tempo)

(3) Come cambia la situazione se si hanno a disposizione più recipienti, per esempio
a) G = 5, p = 3, q = 3 ?
b) G = 6, p = 3, q = 3 ? (tradeoff spazio/tempo)
Analisi del comportamento di un “algoritmo”

Immaginiamo il gioco solitario in cui ogni posizione è una fila di pedine bianche (B) e
nere (N). Ogni mossa è fatta in accordo con una delle seguenti regole:

(1) rimpiazzare una pedina bianca ed una nera consecutive con due pedine bianche
consecutive, in simboli BN → BB;
(2) rimpiazzare due pedine bianche consecutive con una pedina nera, in simboli
BB → N;
(3) rimpiazzare una pedina nera ed una bianca consecutive con due pedine bianche
ed una nera consecutive, in simboli NB → BBN.

Domande
1. è possibile, utilizzando mosse di tipo (1), (2) e (3), passare da una posizione BBB ad
una posizione NNN?

2. è possibile, utilizzando mosse di tipo (1), (2) e (3), passare da una posizione BBBB
ad una posizione NNNN?
Analisi del comportamento di un “algoritmo”

Immaginiamo il gioco solitario in cui ogni posizione è una fila di pedine bianche (B) e
nere (N). Ogni mossa è fatta in accordo con una delle seguenti regole:

(1) rimpiazzare una pedina bianca ed una nera consecutive con due pedine bianche
consecutive, in simboli BN → BB;
(2) rimpiazzare due pedine bianche consecutive con una pedina nera, in simboli
BB → N;
(3) rimpiazzare una pedina nera ed una bianca consecutive con due pedine bianche
ed una nera consecutive, in simboli NB → BBN.

Domande
1. è possibile, utilizzando mosse di tipo (1), (2) e (3), passare da una posizione BBB ad
una posizione NNN? NO

2. è possibile, utilizzando mosse di tipo (1), (2) e (3), passare da una posizione BBBB
ad una posizione NNNN? SI
Soluzione

(1) BN → BB
(2) BB → N
(3) NB → BBN

Le sequenze di passi possibili sono le seguenti:

BBB →(2) NB →(3) BBN →(2) NN

BBB →(2) NB →(3) BBN →(1) BBB
BBB →(2) BN →(1) BB

Nessuna di queste può portare BBB in NNN. Ma la seguente derivazione mostra che
c’è una derivazione che porta BBBB in NNNN:

BBBB →(2) NBB →(3) BBNB →(3) BBBBN →(2) NBBN

→(3) BBNBN →(3) BBBBNN
→(2) NBBNN
→(2) NNNN
Programmazione:
un po’ di
terminologia