Programmazione

Algoritmo

Un algoritmo è un procedimento che risolve un determinato problema attraverso un numero finito di passi elementari.
Un esempio di algoritmo è la ricetta per fare una torta.

Che cosa è un programma?

Un programma è un insieme di istruzioni che un computer è in grado di comprendere e eseguire.
Un programma traduce un algoritmo in un linguaggio comprensibile da un computer e deve essere scritto in un linguaggio di programmazione attraverso la scrittura del codice sorgente.
Come esistono diverse lingue attraverso cui le persone possono esprimersi, così esistono molti linguaggi di programmazione, per es.

• C
• Python
• Java
• Javascript
• Ruby
• Scala

Codice macchina, la lingua madre di un computer

Nella maggior parte dei computer le singole istruzioni sono immagazzinate come codice macchina ovvero sia come una sequenza di 0 e 1 (vedi Informatica).
A una particolare operazione che il processore è in grado di svolgere viene associato un identificativo numerico unico detto operation code (opcode). In questo modo per esempio l’istruzione corrispondente al comando per sommare insieme due numeri può utilizzare il codice specifico per l’addizione.
I computer più semplici hanno a disposizione un insieme limitato di istruzioni, mentre gli elaboratori più complessi hanno diverse centinaia di codici tra cui scegliere, ciascuno con il suo codice numerico identificativo unico.
Dal momento che la memoria di un computer può immagazzinare numeri, può anche immagazzinare i codici di istruzione. In questo modo interi programmi (che sono semplicemente una lista di istruzioni) possono essere rappresentati come una lista di numeri e possono essere essi stessi manipolati internamente dalla macchina come dati numerici.

Vediamo adesso un esempio di codice macchina costituito da un’istruzione di 32bit (4 byte) per la somma di due numeri dove rs, rt e rd sono i registri corrispondenti agli operandi e al risultato, il campo op è l’operation-code corrispondente alla somma (si tralascia il significato dei campi shamt e _funct).

[  op  | rs  | rt  | rd  |shamt| funct]
 000000 00001 00010 00011 00000 100000

Linguaggio assembly

Anche se è possibile scrivere programmi per computer come sequenze di numeri binari in linguaggio macchina, questo in pratica non è semplice, per cui si è soliti associare a ciascuna operazione di base un breve nome che funge da identificativo dell’operazione stessa e che sia semplice da ricordare, per esempio ADD, SUB, JUMP etc.
L’insieme di questi nomi mnemonici costituisce il linguaggio assembly di un processore.
Il linguaggio assembly è un linguaggio di programmazione di basso-livello, ovvero sia utilizza l’insieme delle istruzioni di un processore senza offrire un livello di astrazione, caratteristica propria dei livelli di alto-livello tipo [Python]((https://www.idrovolante.org/post/programmazione/#linguaggi-di-alto-livello-python) che vedremo in seguito.
La conversione da programmi scritti in linguaggio assembly a programmi che il computer sappia realmente interpretare (linguaggio macchina), viene svolta da un programma che prende il nome di assembler. Di seguito viene riportato un esempio di codice assembly per eseguire la somma di due numeri.

.DATA
prompt_msg1 db 	“Please input the first number: “, 0
prompt_msg2 db 	“Please input the second number: “, 0
sm_msg 		“The sum is “, 0

.CODE
	.STARTUP
	PutStr prompt_msg1	; request first number
	GetInt CX		; CX = first number
	PutStr prompt_msg2	; request first number
	GetInt DX		; DX = second number
	
	push CX		; place first number on stack
	push DX		; place second number on stack
	mov AX, CX		; sum = AX = CX
	add AX, DX		; sum = sum + DX = CX + DX
	PutStr sum_msg	; display “The sum is “
	PutInt AX
	nwln
done:
	.EXIT

La memoria nella macchina a registri

Il modello di macchina a registri deriva dall’architettura di Von Neumann e prevede l’utilizzo di una memoria, la memoria ad accesso casuale, o Random Access Memory (RAM).
Possiamo pensare la memoria come una serie di cassetti impilati uno sull’altro, ciascuno con un’etichetta che lo identifica. Ciascun cassetto può contenere un istruzione da eseguire o un valore (un numero).
Per accedere a una posizione della memoria, ovvero sia al contenuto di un cassetto, un programma utilizza l’indirizzo di memoria, l’identificativo riportato sull’etichetta.
In questo modo vengono memorizzate nella memoria RAM sia le istruzioni che compongono un programma che gli input e gli output del programma.
Il compito dell’Unità di Controllo (che è parte della CPU) è quello di seguire il flusso delle operazioni previsto dal programma, caricando nei registri del processore le istruzioni corrette e i dati presenti in memoria, così che la CPU possa portare a termine tutte le operazioni previste e completare il compito assegnato.

Esempio di programma che esegue la divisione tra due numeri interi, sulla sinistra è riportato l’indirizzo di memoria, sulla destra il contenuto della cella di memoria

000	START: leggi a
001	leggi b
002	BRANCH: if b=0 then goto EXIT
003	d = a/b
004	print d
005	goto EXIT
006	EXIT: exit

L’Unità di controllo si preoccupa di seguire il flusso del programma e di far eseguire alla CPU le istruzioni necessarie, in questo caso se b è diverso da zero la sequenza di indirizzi di memoria che vengono visitati è: 000, 001, 002, 003, 004, 005, 006; nel caso in cui b sia uguale a zero invece la sequenza è: 000, 001, 002, 006.

Linguaggi di alto livello, Python

Python è stato concepito alla fine degli anni ‘80 e la sua implementzione è iniziata nel Dicembre 1989 da Guido van Rossum al CWI (Centrum Wiskunde & Informatica – National Research Institute for Mathematics and Computer Science) in Olanda.
Python permette diversi stili di programmazione, tra cui la programmazione imperativa.

Programmazione imperativa

La programmazione imperativa usa comandi che cambiano lo stato di un programma: in maniera analoga all’imperativo del linguaggio, un programma imperativo è composto da comandi che il computer deve eseguire.
Il codice scritto viene poi tradotto in linguaggio macchina, un linguaggio comprensibile dalla CPU, e lo stato di un programma risulta definito dal contenuto della memoria.
In programmazione imperativa l’ordine dei comandi specifica l’ordine di esecuzione e comandi successivi devono essere eseguiti senza sovrapposizioni.

Interazione utente macchina

La maggior parte degli algoritmi prevede un’interazione tra un utente (persona fisica, altra macchina, bot etc) e la macchina su cui viene eseguito il programma.

Osservata dal punto di vista della macchina questa interazione prevede quattro fasi:
1- Input, la macchina richiede all’utente le informazioni da elaborare;
2- Information storing, la macchina registra le informazioni di input all’interno della memoria;
3- Information processing, la macchina elabora le informazioni;
4- Output, la macchina restituisce all’utente il risultato dell’elaborazione.

Calcolo del prodotto di due numeri

Prendiamo in esame il caso dello sviluppo di un programma per il calcolo del prodotto tra due numeri: l’utente fornirà alla macchina i numeri di cui vuole sapere il prodotto (fase di input); la macchina provvederà a effettuare il calcolo (fase di information storing and processing) e restituirà all’utente il risultato dell’operazione (fase di output).
Il programma che dobbiamo scrivere prevede di determinare un algoritmo che, ricevuti in input due numeri qualsiasi, restituisce a video il risultato del calcolo del loro prodotto.
I valori ricevuti in input dipendono dall’utente e possono variare di volta in volta: per gestire un input variabile si utilizzano le variabili.

Assegnazione di variabili

Le variabili in algebra sono un po’ come i numeri sulle poltroncine di un teatro: indicano un posto preciso ma di volta in volta possano essere occupate da persone diverse. Sono come dei segnaposto che si possono utilizzare per riferirsi a una determinata quantità che nel tempo può variare, per esempio la temperatura registrata in un determinato istante da un termometro, oppure un registro degli ospiti in cui di giorno in giorno si aggiorna il nome chi occupa la camera numero 4…

Un’operazione fondamentale in programmazione è quella dell’assegnazione di variabili.
Pensiamo la memoria del computer come un mobile con moltissimi cassetti in cui possiamo mettere delle informazioni: testo, immagini, suoni e parole, video..
Per identificare un cassetto, possiamo utilizzare un’etichetta – la nostra variabile – così possiamo memorizzare delle informazioni nel cassetto e abbiamo un meccanismo che ci permetterà in seguito di recuperarle con facilità.
Se vogliamo assegnare a un cassetto l’etichetta a e memorizzare al suo interno il numero 5, in Python possiamo scrivere:

a = 5

se successivamente vogliamo riprendere il valore memorizzato in a, sommarci 5 e memorizzare il nuovo risultato in un cassetto con etichetta b, possiamo scrivere

b = a + 7

Il carattere = (uguale) in Python rappresenta l’operatore assegnazione di variabile e è importante capire come Python interpreta questo operatore.
Se consideraiamo il primo esempio, a = 5, Python quado si trova a eseguire questa istruzione, per prima cosa nota l’operatore assegnazione di variabile: a questo punto controlla se in memoria esiste già un cassetto con etichetta a e, se non lo trova, sceglie un cassetto a caso, ci mette un etichetta con su scritto a, lo apre e inserisce al suo interno il numero 5; se invece esiste già un cassetto con etichetta a, allora lo apre, lo vuota e infine ci inserisce il numero 5.
Nel secondo esempio Python per prima cosa sceglie a caso un cassetto della memoria su cui attacca l’etichetta b, poi provvede a mettere nel cassetto a+7, ma cosa succede a questo punto? Il compilatore riconosce correttamente 7 come un numero e il + come operatore di addizione, ma che cosa è a? per prima cosa Python controlla se in memoria c’è un cassetto con etichetta a, lo trova, e a quel punto sostituisce ad a il valore memorizzato nel cassetto, che cosa troviamo nel cassetto con etichetta b?
E se al posto di b=a+7 avessimo scritto b=c+7? a quel punto quando Python va a cercare un cassetto con etichetta c non lo trova e restituisce un messaggio del tipo

NameError: name 'c' is not defined

in pratica ci sta dicendo che in memoria non c’è nessuna variabile (nessun cassetto con etichetta) c.

Per visualizzare il contenuto di un casseto (di una variabile) si può utilizzare il comando print() dove tra parentesi dobbiamo indicare il nome della variabile, con riferimento all’esempio di prima print(b) produrrà il seguente output

12

I un cassetto della memoria si può anche memorizzare del testo, per esempio

indirizzo = "via Garibaldi 72, Prato"

memorizza il testo via Garibaldi 72, Prato in un cassetto con etichetta indirizzo; da notare che un insieme di caratteri che rappresentano del testo, una stringa, devono essere racchiusi da apici singoli ' o doppi (virgolette) ".

Diagramma a blocchi

E’ possibile rappresentare la sequenza delle istruzioni di un programma attraverso un diagramma, il diagramma a blocchi (in ingledse flow-chart).
Poiché un algoritmo è una seguenza di istruzioni che permette di portare a termine un compito in un numero finito di passi, in un diagramma a blocchi troveremo sempre uno o più percorsi che partono dall’inizio del programma (nodo start) e raggiungono la fine del programma (nodo end).

Consideriamo il diagramma a blocchi dell’algoritmo per il calcolo del prodotto tra due numeri che avrà una struttura del tipo:

Diagramma a blocchi dell'algoritmo per il calcolo del prodotto tra due numeri.

Input

In Python per ricevere un input da parte dell’utente si utilizza la funzione input(), che tra parentesi accetta il testo da scrivere a video che accompagna la richiesta, per esempio input("Inserire il primo numero") scrive a video Inserisci il primo numero _ seguito da un cursore lampeggiante che indica all’utente di inserire l’input richiesto dal programma.

Per memorizzare l’input fornito dall’utente si può utilizzare una variabile, per esempio

primoNumero = input("Inserisci il primo numero")

memorizza l’input in un cassetto di memoria con etichetta primoNumero.
E’ importante osservare che Python assume che l’input sia una stringa, ovvero sia una sequenza di simboli, in generale caratteri e cifre, per cui, se sappiamo che l’input deve essere un numero, dovremo convertire la stringa di caratteri in numero. Per far questo possiamo utilizzare la funzione int(), che converte una stringa in un numero intero; se invece vogliamo convertire la stringa in un numero decimale, possiamo utilizzare la funzione float().
In pratica:

primoNumero = input("Inserisci il primo numero")
primoNumero = int(primoNumero)

oppure, in maniera equivalente:

primoNumero = int(input("Inserisci il primo numero"))

Il codice completo dell’algoritmo è il seguente:

a = int(input("Inserisci il primo numero: "))
b = int(input("Inserisci il secondo numero: "))

p = a * b

print("Il prodotto di {0} per {1} è {2}".format(a, b, p))

Attenzione alla funzione di output, print(), che questa volta viene utilizzata per restituire all’utente un testo in cui vogliamo far comparire anche il valore di alcune variabili utilizzate. Per far questo si utilizzano dei segnaposto {0} {1} etc, che saranno sostituiti, in ordine, dal valore delle variabili argomento della funzione format(). Nell’esempio qui sopra a {0} verrà sostituito il valore di a, a {1} il valore di b e così via, in questo modo, se in memoria avessimo avuto a=5 e b=3, in output sarebbe stato visualizzato Il prodotto di 3 per 5 è 15.
Potete vedere il codice in azione su repl.it.

Calcolo del quoziente di due numeri

Determinare l’algoritmo di un programma che, dati due numeri qualsiasi, restituisce a video il loro quoziente.
Nel caso del quoziente dobbiamo tener presente che il denominatore deve essere diverso da zero, altrimenti la divisione è impossibile. Il programma dovrà quindi valutare la condizione “denominatore diverso da zero” e, se questa risulta essere vera, procedere con il calcolo del quoziente, in caso contrario (la condizione è falsa) avvertire l’utente che il calcolo non è possibile.
Per prima cosa consideriamo il diagramma a blocchi dell’algoritmo che stavolta avrà una struttura del tipo:

Diagramma a blocchi dell'algoritmo per il calcolo del quoziente tra due numeri.

if (condizione):
  blocco istruzioni A
else:
  blocco istruzioni B

In pratica viene valutata la condizione espressa traparentesi dopo if e, se questa è vera, si esegue il blocco di istruzioni A, altrimenti else (la condizione è falsa) si esegue il blocco di istruzioni B.
Un blocco di istruzioni è un insieme di istruzioni che vengono eseguite in un particolare contesto – individuato dall’operatore :, nel nostro caso quando la condizione è vera (contesto if(condizione):) oppure nel caso sia falsa (contesto else:).
In Python, tutte le righe di codice che appartengono allo stesso blocco, devono essere indentate (rientrare) di due spazi rispetto all’istruzione (contesto) di riferimento (nel nostro caso if o else).

Nel nostro algoritmo la condizione da valutare il divisore della divisione è diverso da zero?: per far questo possiamo utilizzare l’operatore diverso da, !=, per vedere se nel cassetto di memoria con etichetta b è presente il valore 0.

Il nostro algoritmo può così essere implementato in Python:

# fase di input
a = float(input("Inserire il dividendo: "))
b = float(input("Inserire il divisore: "))

# valutare se il divisore è diverso da zero
if ( b!=0 ):
  # il divisore è diverso da zero
  q = a/b
  print("il quoziente è: ", q)
else:
  # il divisore è uguale a zero
  print("Attenzione, divisione impossibile!")
  print("Il divisore è uguale a zero!")

Potete vedere il codice in azione su repl.it.

Turtle graphics

Quando si programma in Python, si possono estendere le funzioni di base messe a disposizione da Python, utilizzando dei moduli.
In particolare, per fare dei disegni bidimensionali, si può utilizzare il modulo Turtle Graphics.
Turtle graphics mette a disposizione una tartaruga che ha sul piastrone (parte inferiore del corpo) dei pennini colorati: quando la tartaruga si muove, lascia dietro di sé una linea colorata.
Il modulo Turtle ci permette di creare una tartaruga e ci mette a disposizione delle funzioni per spostarla, muoverla in avanti, farla ruotare etc.

Codice base per Turtle Graphics

Lo scheletro di base per un codice in Python with Turtle è questo

import turtle

# fullscreen the canvas
screen = turtle.Screen()
screen.setup(1.0, 1.0)

# code goes here
# ...

# prevent the canvas from closing
screen.mainloop()

Adesso prima cosa da fare è quella di creare una tartaruga e darle un nome, per far questo si utilizza la funzione Turtle() del modulo turtle che può essere chiamata utilizzando l’operatore . (punto), ovvero sia

ruga = turtle.Turtle()

che in pratica si legge, chiamare la funzione Turtle() presente nel modulo turtle (ricordarsi di fare attenzione alle lettere maiuscole e minuscole).

Una volta che abbiamo creato una tartaruga, possiamo iniziare a muoverlo sulla tela (canvas), per esempio utilizzando la funzione forward() per spostarla in avanti e la funzione left() per farla girare a sinistra:

Disegno di un poligono regolare con numero di lati qualsiasi

Scrivere l’algoritmo di un programma che, dati il numero dei lati e la lunghezza del lato di un poligono regolare, disegni a video il poligono.
Per scrivere l’algoritmo possiamo pensare a risolvere un problema più semplice, ovvero sia quello di disegnare con Turtle Graphics un triangolo equilatero di lato qualsiasi.

La prima cosa da osservare è il valore dell’angolo di rotazione. Poiché la rotazione è a sinistra, la tartaruga va ruotata di un angolo pari al supplementare dell’angolo interno del triangolo, in questo caso, essendo il triangolo equilatero, l’angolo interno ha ampiezza 60° e il supplementare ha ampiezza pari a 180°-60°=120°.
Nel caso di un triangolo con un numero qualsiasi n di lati, il valore dell’angolo interno alfa si può calcolare con la formula:

alfa = ( 1 - 2/n ) * 180

beta = 180 - (( 1 - 2/n ) * 180)

Possiamo anche osservare che, nella parte di codice relativa al disegno del triangolo, si ripete tre volte la coppia di istruzioni

t.forward(l)
t.left(120)

Nel caso del disegno di un poligono che ha un numero qualsiasi n di lati, possiamo semplificare il codice utilizzando un ciclo, ovvero sia una struttura Python che permette di ripetere alcune istruzioni. Una di queste strutture è la struttura for, che ha la seguente sintassi

for x in range(10):
  istruzione

in questo caso l’istruzione viene ripetuta tante volte quanto è indicato dall’argomento della funzione range(), ovvero sia dieci volte.

L’algoritmo può così essere modificato nel seguente modo:

Criptare un messaggio

La crittografia (dal greco kryptós, “nascosto”, e graphía, scrittura) si occupa delle “scritture nascoste”, ovvero sia di scritture che non rivelano il messaggio che si vuole comunicare.

L’idea alla base dell’algoritmo è semplice: leggiamo ogni caratere del messaggio orginale partendo dall’ultimo carattere e procediamo indietro verso il primo; ogni carattere letto costituisce un nuovo elemento del messaggio criptato che viene così costruito un passo alla volta, semplicemente aggiungendo un nuovo carattere alla destra di quelli già presenti.
Perché l’algoritmo funzioni per qualsiasi messaggio possiamo ottenre la lunghezza del messaggio e poi iterare (ripetere) l’operazione di base di memorizzazione del carattere appena letto nel nuovo messaggio (quello criptato). Per ripetere l’operazione di base possiamo utilizzare un ciclo, per esempio con il costrutto while, che ripete un blocco di istruzioni finché la condizione che viene testata è verificata.

while (condizione):
  istruzione

L’algoritmo può essere scritto nel seguente modo