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 computer è 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 assembler

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.
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 sono come i numeri sulle poltroncine di un teatro: indicano un posto preciso ma di volta in volta possano essere occupate da persone diverse.

Un’operazione fondamentale in programmazione è quella dell’assegnazione di variabili.
Pensiamo la memoria del computer come un mobile con moltissimi cassetti: vogliamo adesso identificare un cassetto e per farlo utilizziamo un’etichetta (la nostra variabile) così da poterci memorizzare delle informazioni e in seguito poterle recuperare.
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

E’ importante notare che nell’esempio precedente 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.

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

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 al 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, una sequenza di caratteri e cifre, per cui, se sappiamo che l’input deve essere un numero, dovremo convertire la stringa di caratteri in numero con la funzione int(), in pratica:

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))

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:

if (condizione):
  blocco istruzioni
elif (condizione alternativa 1):
	blocco istruzioni
..
elif (condizione alternativa n):
	blocco istruzioni
else:
  blocco istruzioni

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

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

# attenzione al denominatore!
if ( b!=0 ):
  q = a/b
  print('il quoziente è: ', q)
else:
  # sono nel caso divisore uguale a zero
  print('attenzione, divisore uguale a zero!')

Potete vedere il codice in azione su repl.it.

Turtle graphics

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