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à logicomatematiche 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: 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 Bus CPU x y t 3 4 mare .. . Memoria .. Input .. Output 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: stringa begin 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 somma var x,y,somma: numero intero; begin read(x); read(y); somma:=x+y; write(somma); end. Istruzione condizionale • Sintassi: if Condizione then Lista Istruzioni else 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 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 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; begin read(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; begin read(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;