Algoritmi e Programmazione
description
Transcript of Algoritmi e Programmazione
Algoritmi e Programmazione
Giorgio Delzanno
Algoritmi e Programmi
• Algoritmo=Successione di operazioni elementari che possono essere eseguite da un calcolatore
• Programma = Algoritmo codificato nel linguaggio di calcolatore
• Linguaggio macchina = Basato sul set di istruzioni della macchina, rappresentato da sequenze di 0 e 1
• Linguaggio di alto livello = Linguaggio più vicino al linguaggio naturale, rigoroso e non ambiguo
Istruzioni di un calcolatore
• Le istruzioni di un linguaggio macchina servono a gestire registri, memoria, e le capacità logico-matematiche della ALU.
• Istruzione macchina = sequenza di 0,1• Es.: l’operazione ‘loadA ind’ (es. 01 0001) carica
il contenuto della cella di memoria con indirizzo ind nel registro A (loadA=codice dell’istruzione)
Linguaggi di Programmazione
• Invece di codificare algoritmi in linguaggi macchina si utilizzano linguaggi ad alto livello
• Le istruzione dei linguaggi ad alto livello sono facilmente comprensibili ai programmatori.
• Compilatore: (programma che) traduce automaticamente un programma ad alto livello in linguaggio macchina
LP: Un Linguaggio Didattico di Programmazione
• Vedremo il funzionamento delle istruzioni fondamentali di un linguaggio di programmazione
• Utilizzeremo un linguaggio semplificato che chiameremo LP
• Utilizzeremo il linguaggio per programmare il funzionamento di un calcolatore astratto con struttura semplificata
Calcolatore Astratto
Memoria
CPUInput Output
Bus
xy
34
maret..
.
.
.. .
Calcolatore astratto
• CPU: componente di calcolo• Memoria centrale: sequenza di celle di
memorie• Input: sequenza di dati in input (ad es. da un
file, terminale, ecc.)• Output: sequenza di dati in output
Nozione di Variabile
• Come si indirizzano le celle di memoria?• Invece di usare gli indirizzi fisici utilizziamo dei
nomi simbolici (es., x, y, nome,...) che vengono mappati in indirizzi fisici attraverso la fase di compilazione
• Le variabili vanno dichiarate all’inizio del programma (celle diverse, nomi diversi)
• Valore di una variabile = contenuto corrente della cella di memoria associata alla variabile
Nozione di Costante
• Per esprimere direttamente valori prefissati • (cioè che non devono essere modificati dal
programma) si utilizzano le costanti• Una costante è una rappresentazione simbolica di
un numero, stringa, ecc.• Ad esempio, 1, ‘ciao’, 3.14, ecc.• Il set di costanti disponibile dipende dal
linguaggio di programmazione
Espressioni
• Le espressioni servono per rappresentare calcoli a livello simbolico
• Un’espressione può coinvolgere nomi di variabili, costanti, operatori aritmetico-logici, ecc
• Es: 3+4,
x+y-1 (dove x è una variabile),x>0 and y>1
Programma LP
• La sintassi astratta di un programma LP consiste di due blocchi
• Dichiarazione di variabili:– x: intero, y:stringa, z: numero reale, ecc.
• Sequenza di istruzioni racchiusa tra le parole chiave begin …. end e separate dal punto e virgola ‘;’
Esecuzione di un programma
• Qual è significato (semantica) di un programma?Trasformazione da Input iniziale a Output
finale!• Un programma deve essere eseguito per poter calcolare la
trasformazione Input-Output. • L’esecuzione modifica lo stato del programma:
stato iniziale, corrente, e finale: valore iniziale, corrente e finale delle variabili, dell’input e dell’output.
• L’esecuzione dipende dalla semantica operazionale dei singoli costrutti
Lettura e scrittura
• Servono per leggere e scrivere il valore di una variabile dall’input o sull’output (ad es. lettura da tastiera e scrittura su video)
• Assumiamo che input e output siano liste di valori– write(Variabile): aggiunge il valore corrente della
Variabile all’output;– read(Variabile): toglie il primo valore della lista input
e lo assegna alla Variabile.
Esempio 1
• Programma che legge una stringa e la scrive sul video:
var s: stringabegin
read(s);write(s);
end.
Esecuzione del programma 1
• Si utilizza una sola cella di memoria chiamata ‘s’• Inizialmente:
– valore(s)=indefinito; input=‘ciao’, ‘mare’, …; output=vuoto
• Dopo read(s): – valore(s)=‘ciao’, input=‘mare’,….
• Dopo write(s): – valore(s)=‘ciao’,….,output=‘ciao’
• Semantica: trasformazione identica da I-O
Assegnamento
• Si utilizza per assegnare il valore corrente (cioè valutata nello stato corrente del programma) di un’espressione ad una variabile
• L’assegnamento cambia il valore della variabile• Sintassi:
– Variabile := Espressione, se nello stato corrente l’espressione si valuta in val allora ‘valore(Variabile)=val’, dopo l’esecuzione dell’assegnamento
Esempio Valutazione Assegnamento
• Es. x:=x+1• L’espressione x+1 va valutata nello stato corrente.• Il risultato dell’espressione viene assegnato
nuovamente ad x. • Se valore(x)=2 prima dell’esecuzione,
valore(x)=3 dopo l’esecuzione
Esempio 2
• Leggere due numeri, calcolare e stampare la loro sommavar x,y,somma: numero intero;begin
read(x);read(y);somma:=x+y;write(somma);
end.
Istruzione condizionale
• Sintassi:if Condizione then Lista Istruzionielse Lista Istruzioni
• Condizione = espressione Booleana (con valore vero o falso)
• Se la condizione si valuta in vero si esegue ramo then, altrimenti si esegue il ramo else
Diagramma di flusso
IstruzioniIstruzioni
CONDVERO FALSO
Istruzioni
Istruzioni
Esempio 3
• Calcolare e stampare il massimo tra 2 valori letti in input
• Algoritmo informale:leggo(x), leggo(y)se x>y stampo(x) altrimenti stampo(y)
Programma per esempio 3
• var x,y:numero intero;begin
read(x);read(y);if x>y then write(x)else write(y);
end
Istruzione ciclica
• Sintassi while Condizione do Lista Istruzioni end
• Lista Istruzioni viene eseguita fintantochè Condizione si valuta in vero
• Quando Condizione si valuta in falso si passa all’istruzione seguente nel programma
Diagramma di flusso
CONDFALSO
Istruzioni
Istruzioni
Istruzioni
VERO
Esempio 4• Problema: leggere K, e quindi calcolare la somma di K valori letti dall’input• Devo memorizzare K, la somma, e i valori letti V1,V2,…,VK• Poiche uso ogni Vi una sola volta, mi bastano 3 variabili: K, x ed S• x manterrà il valore Vi corrente• Algoritmo informale:
leggo K,inizializzo S con 0 per tutti i valori da V1 a VK, leggo(x)sommo x a S (S=S+x)stampo S
Programma per l’esempio 4• var K, x, somma: numero intero;
beginread(K);somma:=0;while K>0 do
read(x);somma:=somma+x;K:=K-1;
endw;write(somma);
end
Esecuzione del while• Inizialmente: val(x),val(K)=indefiniti,val(somma)=0.• Leggo il valore 3: val(K)=3• Poiché val(K)>0, entro nel ciclo.• Leggo il primo valore in input V1 su cui fare la somma e lo
memorizzo in x.• Calcolo somma=somma+x, e decremento K.• Cioè dopo l’esecuzione delle istruzioni dentro il ciclo
val(x)=3, val(somma)=3, val(K)=2• Proseguo con il ciclo fino a che val(K)=0.• A tal punto esco dal ciclo e scrivo il valore finale di somma
Esempio 5
• Calcolare il massimo comun divisore tra due numeri interi letti da input, utilizzando l’algoritmo di Euclide:– mcd(m,n)=m=n se n=M– mcd(m,n)=mcd(m-n,n) se m>n– mcd(m,n)=mcd(m,n-m) se n>m
Algoritmo di Euclide
• Leggo m and n• (*) Fino a che m diverso da n,
– se m>n allora sottraggo n ad m– se n>m sottraggo m ad n– torno a (*)
• Quando m=n stampo, ad es, n
Programma esempio 5• var m,n: numero intero;
beginread(m);read(n);while not(m=n) do
if m>n then m:=m-n else n:=n-m;
endw;write(n); (Nota: a questo punto n=m!)
end
Strutture dati complesse
• Oltre a variabili di tipo intero, stringa, ecc può essere molto utile utilizzare dati strutturati (ad es. liste, insiemi, ecc)
• Molti linguaggi di programmazione forniscono vari tipi di dato quali – array, – record,– liste
• Vediamo alcuni esempi nel nostro linguaggio LP
Array • Un array rappresenta una sequenza di celle consecutive
contenenti dati omogenei (es. interi)• Una variabile V di tipo array denota la sequenza di celle• Per accedere direttamente alla cella i-esima si utilizza il suo
indice i come segue: V[i]• Sintassi dichiarazione:
– NomeVarArray: array 1..N of Tipo; (N costante)• Nelle espressioni, assegnamenti, ecc si utilizza poi
– NomeVarArray[Exp] dove Exp è un espressione che si valuta in un valore da 1…N
Esempio uso array
• Leggere 3 valori e memorizzarli in un array• var A : array 1..3 of intero; i : intero;
i := 1;while i<4 do
read(A[i]);i:=i+1;
endw;
Esempio 6
• Leggere K=<10 valori e stamparli in ordine inverso
• Dobbiamo leggere V1,…,VK, ,memorizzarli e poi stamparli in ordine VK,…,V1
• Usiamo un array A di N>K posizioni per memorizzare i dati in input
• Dopo aver memorizzato i dati, li scriviamo scorrendo l’array dall’indice K all’indice 1
Programma per esercizio 6• var A : array 1..10 of intero;
i,K : intero;read(K);i := 1;while i=<K do
read(A[i]);i:=i+1;
endw;i:=K;while i>0 do
write(A[i]);i:=i-1;
endw;
Record
• Tipo di dato per gestire dati strutturati di tipo eterogeneo; ogni dato viene chiamato campo del record
• Sintassi:Variabile: record
Campo-1:Tipo1;…Campo-N:TipoN;
end• Per accedere ai campi di un record si utilizza:
Variabile.Campo-i (rappresenta l’i-esimo campo)
Esempio di record
• Dati anagrafici• var Punto:record x,y:numero end;
z:intero;
Punto.x=3;Punto.y=2;z:=Punto.x*Punto.y;
Compilazione
Compilatore e loader
• Un compilatore è un programma che traduce un programma scritto in linguaggio ad alto livello in un programma scritto in linguaggio macchina– Un compilatore produce quindi un programma
eseguibile (.exe in Windows)• Il loader è il programma che carica un programma
in linguaggio macchina in memoria principale (e quindi mappa indirizzi logici in indirizzi fisici)
Come funziona la compilazione
• Un compilatore (che abbia anche la funzione di loader) deve – riconoscere la sintassi del linguaggio ad alto livello – associare uno spazio in memoria principare per poter
gestire le variabili dichiarate nel programma – tradurre i costrutti di alto livello in sequenze di
istruzioni in linguaggio macchina
Compilazione dichiarazioni variabili
• Dato un programma LP P costituito da una parte di dichiarazione di variabili D e da un sequenza di istruzioni L, il compilatore– associa alle variabili in D delle celle di
memoria RAM– associa alle istruzioni in L delle istruzioni in
linguaggio macchina
Dichiarazioni
• Consideriamo le dichiarazionivar x1,x2,....,xn:integer;
• Ad ogni variabile associamo una cella di memoria– x1 RAM[C1]– x2 RAM[C2]– ....
• C1, C2, ... dipende dalla lunghezza del programma
Assegnamento
• L’assegnamento x:=x+1; viene tradotto come segue– Caricare il contenuto della cella di RAM
associata alla variabile x nell’accumulatore– Incrementare il contenuto dell’accumulatore – Spostare il contenuto dell’accumulatore nella
cella di RAM associata ad x
Assegnamento
• Se x RAM[Cx] allora x:=x+1 viene tradotto come
LOAD Cx
INC MOVE Cx
Assegnamento
• L’assegnamento x:=y+1; viene tradotto come segue– Caricare il contenuto della cella di RAM
associata alla variabile y nell’accumulatore– Incrementare il contenuto dell’accumulatore – Spostare il contenuto dell’accumulatore nella
cella di RAM associata ad x
Assegnamento
• Se x RAM[Cx]
• E y RAM[Cy]
• allora x:=y+1 viene tradotto come
LOAD Cy
INC MOVE Cx
Condizionale
• Come si traduce il seguente costrutto?
– if (x=0) then x:=y+1 else x:=x-1
Per compilare if (x=0) then x:=y+1 else x:=x-1dobbiamo• Caricare la cella di RAM associata ad x nell’accumulatore• Se il contenuto dell’accumulatore è zero
– Carichiamo la cella associata ad y nell’accumulatore– Incrementiamo di uno l’accumulatore– Spostiamo il contenuto dell’accumulatore nella cella
associata ad x• Altrimento decrementiamo l’accumulatore e poi spostiamo
il contenuto dell’accumulatore nella cella associata ad x
Condizionale
Codice macchinaDati x –> RAM[Cx] e y RAM[Cy]e if (x=0) then x:=y+1 else x:=x-1
LOAD CxTST LDEC GOTO M
L:LOAD CyINC
M: MOVE Cx
dove L e M sono due etichette
Ciclo
• Come si traduce il seguente costrutto?
while (x>0) doy:=y+1;x:=x-1;
end;
Ciclo annidato
• Come si traduce il seguente costrutto?while (x>0) do
y:=z;while (y>0) doz:=z+x;y:=y-1;end;x:=x-1;
end;