1. Definizione del problema (specifica) (stato iniziale/finale) 2. Individuazione di un procedimento risolutivo (algoritmo) 3. Codifica dell’algoritmo in un linguaggio di

(1)

Algoritmi

(2)

Le fasi della programmazione

Ad un primo livello di astrazione l’attività della

programmazione può essere suddivisa in quattro (macro) fasi principali.

1. Definizione del problema (specifica) (stato iniziale/finale) 2. Individuazione di un procedimento risolutivo (algoritmo) 3. Codifica dell’algoritmo in un linguaggio di

programmazione (codifica)

4. Esecuzione e messa a punto (esecuzione)

(3)

Proprietà di un algoritmo

La descrizione di un procedimento risolutivo può considerarsi un algoritmo se rispetta alcuni requisiti essenziali, tra i quali:

Finitezza: un algoritmo deve essere composto da una sequenza finita di passi elementari.

Eseguibilità: il potenziale esecutore deve essere in

grado di eseguire ogni singola azione in tempo finito con le risorse a disposizione

Non-ambiguità: l’esecutore deve poter interpretare in

modo univoco ogni singola azione.

(4)

Pseudo-linguaggio

•Utilizziamo inizialmente uno pseudo-linguaggio con un insieme di costrutti linguistici che costituiscono il nucleo di un qualunque linguaggio di programmazione reale.

• Senza entrare in eccessivi dettagli formali, nel presentare le notazioni utilizzate (sintassi) diamo anche una

descrizione informale (semantica) di ciò che accade al momento dell’esecuzione in corrispondenza dei vari costrutti.

Il linguaggio contiene costrutti per:

• rappresentare semplici calcoli attraverso le comuni operazioni logico/aritmetiche (espressioni)

• modificare le associazioni nello stato (assegnamento e ingresso)

• controllare l’ordine di esecuzione delle azioni (controllo)

• fornire i risultati (produzione in uscita dello stato finale)

(5)

Espressioni Numeriche

Il linguaggio consente di rappresentare semplici calcoli

algebrici, attraverso le usuali espressioni costruite a partire dai valori numerici e dalle operazioni di

somma + sottrazione - prodotto * divisione /

resto della divisione intera %.

Il significato di un’espressione è il suo valore ottenuto secondo le usuali regole di calcolo.

Esempio:

il valore di 3 * 5 + 6 è 21

il valore di 3 * (5 + 6) è 33

(6)

Oltre ai valori numerici, le espressioni possono contenere nomi simbolici: il calcolo di un’espressione che contiene un nome simbolico x dipende dallo stato, e precisamente dal valore associato al nome x nello stato.

Esempio:

il valore di 3 * (5 + x) è

• 33 in uno stato che contiene l’associazione x ↔ 6

• 18 in uno stato che contiene l’associazione x ↔ 1

(7)

Espressioni Booleane

Il linguaggio consente poi di rappresentare condizioni ovvero espressioni il cui valore è un valore di verità (true o false).

Le condizioni sono costruite attraverso le usuali operazioni di confronto (==, ! =, <, >, <=, >=) e, come nel caso delle

espressioni aritmetiche, il loro valore può dipendere dallo stato.

Esempio: il valore di y==x+1 è

• true in uno stato che contiene le associazioni x

↔

5 e y

↔

6

• false in uno stato che contiene le associazioni x

↔

5 e y

↔

9 Condizioni più complesse possono essere costruite attraverso operatori logici quali negazione (simbolo !), congiunzione

(simbolo &&) e disgiunzione (simbolo ||).

(8)

•Significato di ! - il valore di verità di ! P è true se il valore di verità di P è false false se il valore di verità di P è true

• Significato di && - il valore di verità di P && Q è

true se i valori di verità di P e Q sono entrambi true false altrimenti

• Significato di || - il valore di verità di P || Q è

false se i valori di verit`a di P e Q sono entrambi false true altrimenti

(9)

Esempio:

• Il valore di (y >= x) &&(x > 5) è

- true in uno stato che contiene le associazioni x↔ 15 e y ↔ 30

- false in uno stato che contiene le associazioni x ↔ 3 e y ↔ 30

• Il valore di (y >= x) || (x > 5) è

- true in uno stato che contiene le associazioni x ↔ 2 e y ↔ 30

- false in uno stato che contiene le associazioni x ↔ 3 e

y↔ 1

(10)

Modifica dello stato: ASSEGNAMENTO

! L’istruzione che consente di rappresentare modifiche di stato è usualmente nota come assegnamento.

! L’assegnamento consente di cambiare un’associazione nello stato, ovvero il valore associato nello stato ad un nome

simbolico.

! Useremo per l’assegnamento la seguente notazione:

x = exp;

dove x è un nome simbolico e exp una espressione.

! L’esecuzione dell’assegnamento x = exp; consiste nel (i) calcolare il valore, sia esso val, dell’espressione exp (ii) introdurre nello stato l’associazione x ↔ val

! Si noti che (ii) comporta la rimozione dallo stato della

eventuale associazione già presente per il nome simbolico x (si parla a questo proposito di assegnamento distruttivo).

(11)

Vediamo alcuni esempi, indicando lo stato prima e dopo l’esecuzione degli assegnamenti proposti. Le associazioni modificate nello stato finale sono evidenziate in verde.

Stato iniziale Assegnamento Stato Finale

x

↔

^{10 y}

↔

20 x = 5; x

↔

^{5, y}

↔

²⁰

x

↔

^{10, y}

↔

20 x = y*2; x

↔

^{40, y}

↔

²⁰

x

↔

10, y

↔

20 x = x+1; x

↔

11, y

↔

20 Si noti come, nel terzo esempio, lo stesso nome simbolico x giochi un duplice ruolo:

- a destra del simbolo = indica un valore (il valore associato ad x nello stato iniziale)

- a sinistra del simbolo = indica l’associazione da modificare nello stato a seguito dell’assegnamento.

E input e output??

(12)

Istruzioni di controllo: SEQUENZA

! Negli esempi visti in precedenza gli algoritmi sono stati descritti come sequenze di passi elementari del tipo

Passo 1. azione 1 Passo 2. azione 2 . . .

! Abbiamo utilizzato una sorta di numerazione per indicare l’ordine di esecuzione delle varie azioni:

prima azione 1 poi azione 2 poi ....

! Nel linguaggio che stiamo introducendo, secondo le

convenzioni sintattiche del C, una sequenza di azioni viene rappresentata mediante un blocco

(13)

! Scriveremo dunque {istruzione 1

istruzione 2 . . .

}

ad indicare che l’ordine di esecuzione dei singoli passi è quello testuale del programma.

! Si noti che ogni istruzione viene eseguita a partire

dallo stato risultante dall’esecuzione dell’istruzione che la precede nella sequenza.

! Assegnamento e ingresso sono istruzioni semplici il blocco è un’istruzione composta.

(14)

Istruzioni di controllo: CONDIZIONALE

! Permette di determinare l’azione da intraprendere a seconda del verificarsi o meno di una condizione. La notazione

utilizzata è la seguente

if (condizione) istruzione1 else istruzione2

dove condizione indica una espressione booleana, e istruzione1 istruzione2 sono istruzioni (semplici o composte).

! L’esecuzione del condizionale if (C) S1 else S2 consiste nel (i) Calcolare il valore, sia esso val, dell’espressione booleana C (ii) Eseguire S1 se val è true, eseguire S2 se val è false.

! Si noti che la presenza dell’istruzione condizionale non è in conflitto con il requisito di non ambiguità degli algoritmi:

l’azione da intraprendere è univocamente determinata dal valore di verità della condizione e dunque non vi è facoltà di scelta da parte dell’esecutore.

(15)

Flusso di esecuzione

condizione Istruzioni2

Flusso di esecuzione Istruzioni1

Falsa

Vera

(16)

Istruzioni di controllo: RIPETIZIONE

! Consente di ripetere l’esecuzione di una istruzione (o sequenza di istruzioni) fino al verificarsi di una certa condizione .

while (condizione) Istruzione

dove condizione indica una espressione booleana.

! Terminologia: in while (C) S , la condizione C è

detta guardia e l’struzione S è detta corpo (del ciclo).

! L’esecuzione di while (C) S consiste nel

(i) Calcolare il valore, sia esso val, dell’espressione booleana C

(ii) Se val è false, terminare l’esecuzione.

(iii) Se val è true, eseguire S e ripetere dal punto (i).

(17)

While

 Eseguire un’attivita’ purche’ una condizione rimanga vera:

While (condizione) (azione)

 Es.: while (ci sono biglietti) (vendi un

biglietto)

(18)

Semantica del ciclo while

• All’esecuzione viene valutata l’espressione booleana, se è vera vengono eseguite le

istruzioni che seguono. Si valuta poi di

nuovo l’espressione booleana; se l’espressione è falsa si procede con l’esecuzione del

programma

• ATTENZIONE!! Se le istruzioni non alterano

il valore dell’espressione booleana il ciclo non

terminerà mai

(19)

Flusso di esecuzione

condizione

Flusso di esecuzione Istruzioni1

Falsa

Vera

FLUSSO CICLO

WHILE

(20)

Fasi del ciclo

 Inizializzazione: stato iniziale, che verra’

modificato dall’azione

 Controllo della condizione di terminazione:

confronto tra stato corrente e condizione, terminazione se uguali

 Modifica dello stato: per andare verso la

condizione di terminazione

(21)

Esempio di pseudocodice

Procedure Saluti Conta =3;

While (Conta > 0)

{stampa il messaggio “Saluti”;

Conta= Conta - 1;}

Nome del pezzo (procedura) di pseudocodice  possiamo

chiamare questo pezzo per

nome all’interno di un altra procedura

Inizializzazione: Conta  ³

Condizione di terminazione: conta <0 o conta ==0

Modifica stato: Conta  ^{Conta -1}

(22)

Attenzione alla condizione di Terminazione

numero = 1;

while (numero != 6)

numero = numero +2;

• Condizione di terminazione:numero == 6

• Non verra’ mai raggiunta!

(23)

•Due considerazioni molto importanti:

(1) la condizione del ciclo deve essere inizializzata: se la

condizione non e' inizializzata, il ciclo potrebbe usare valori errati o addirittura indefiniti;

(2) il valore della condizione deve mutare durante il ciclo: se il valore della condizione non cambia durante il ciclo, non ci sara' alcuna possibilita' di uscita dal ciclo, che continuera'

indefinitamente

(24)

Problema: Calcolo del valore assoluto di un numero

Vediamo alcuni esempi di specifica di algoritmi che utilizzano lo Pseudo-linguaggio.

Specifica:

Stato iniziale: numero

↔

A Stato finale: risultato

↔

|A| dove A indica un (generico) valore intero.

Algoritmo:

if (numero > 0)

risultato = numero;

else risultato = - numero;

(25)

Problema: Ordinare due interi positivi Specifica:

Stato iniziale: num1

↔

A, num2

↔

B

Stato finale: num1

↔

max(A,B), num2

↔

min(A,B) Algoritmo:

if (num1 < num2) { temp = num1;

num1 = num2;

num2 = temp;

} else ;

(26)

Problema: Elevamento a potenza Specifica:

Stato iniziale: base↔A, esponente↔B } con A>0 e B >=0 o analogamente !(B<0) Stato finale: risultato↔A^B

! L’algoritmo si basa sulla seguente, ben nota, definizione di elevamento a potenza.

A⁰ = 1

A^B = A × A × . . . × A (se B > 0)

(27)

Algoritmo:

risultato = 1;

while (esponente > 0)

{ risultato = risultato * base;

esponente = esponente - 1;

}

! Nell’algoritmo, si assume che i valori iniziali di base ed esponente soddisfino i requisiti della specifica.

(28)

Programmi e grafi

• Se associamo ad ogni istruzione un vertice di un grafo e colleghiamo ogni istruzione alla

istruzione che la segue con un arco orientato otteniamo il grafo di flusso associato al

programma

• Le istruzioni di salto condizionato sono caratterizzate da due archi in uscita che verranno percorsi in alternativa in funzione

del verificarsi o meno della condizione di salto

(29)

Istruzioni in sequenza

Salto

Condizione

Salto

condizionato

(30)

La programmazione strutturata

• Negli anni ’60 fu dimostrato che qualsiasi grafo di flusso poteva essere trasformato in un grafo strutturato equivalente (dal

punto di vista del risultato) composto solo da sequenze di istruzioni combinate con le due strutture fondamentali la scelta (if -

else) e il ciclo (while)

(31)

Linguaggi di terza generazione



Insieme di primitive ad alto livello, ognuna traducibile in una sequenza di primitive in linguaggio macchina



Es.: pesolordo = pesocarico + pesoveicolo



Due load, una add, una store



Programma traduttore (compilatore): traduce il programma in linguaggio macchina



Interprete: traduce ogni primitiva ed esegue

subito le primitive corrispondenti del l.m., senza memorizzare la traduzione



Programmi scritti in un ling. di terza generaz.

sono trasportabili da una macchina all’altra,

basta cambiare compilatore

(32)

3232

Paradigmi di programmazione -1 Paradigmi di programmazione -1

• Possiamo aggregare i numerosi linguaggi di programmazione esistenti sulla base del modello modello

astratto di programmazione

astratto di programmazione che sottintendono e che è necessario adottare per utilizzarli

Linguaggi di Linguaggi di programmazione programmazione Imperativi

Imperativi

Paralleli Paralleli

Procedurali Procedurali (C, Pascal)

(C, Pascal) Ad oggettiAd oggetti (C++, Java) (C++, Java)

Dichiarativi Dichiarativi

Funzionali Funzionali

(Lisp)

(Lisp) LogiciLogici (Prolog) (Prolog)

(33)

3333

Paradigmi di programmazione -2 Paradigmi di programmazione -2

• Linguaggi imperativiLinguaggi imperativi

 Il modello computazionale è basato sul cambiamento di stato cambiamento di stato della memoria

della memoria della macchina

 È centrale il concetto di assegnazione di un valoreassegnazione di un valore ad una (variabile) locazione di memoria

 Il compito del programmatore è costruire una sequenza di assegnazioni che producano lo stato finale (in modo tale che questo rappresenti la soluzione del problema)

• Linguaggi dichiarativiLinguaggi dichiarativi

 Il modello computazionale è basato sui concetti di funzione e funzione e relazione

relazione

 Il programmatore non ragiona in termini di assegnazioni di valori, ma di relazioni tra entità e di valori di una funzione

(34)

Compilatore

• Il compilatore riceve in ingresso un programma specificato ad alto livello e restituisce lo stesso programma in

linguaggio macchina

• La funzione calcolata dai due programmi

deve essere la stessa

(35)

Compilatore

• Il programma originale (codice sorgente) è un file di testo

• Il compilatore procede attraverso le fasi di

front end e di back end per poter restituire lo

stesso programma in linguaggio macchina

(36)

Due parti: analisi e sintesi

Analisi (front end): prende un programma e lo divide in parti su cui impone una struttura grammaticale; crea una

rappresentazione intermedia del programma sorgente; segnala possibili errori; mette informazioni sul programma in una

tavola dei simboli, da passare alla sintesi

Sintesi (back end): costruisce il programma oggetto dalla rappresentazione intermedia e dalla tavola dei simboli

Sequenza di fasi: ogni fase trasforma una rappresentazione del programma sorgente in un’altra

Fasi principali: analisi lessicale, analisi sintattica, analisi

semantica, generazione del codice intermedio, ottimizzazionee del codice, generazione del codice

(37)

3737

Il compilatore

Il compilatore − − 1 1

• Compilatore Compilatore

 Analisi lessicale  token (parole)

 Analisi sintattica  albero sintattico

 Analisi semantica  tabella dei simboli

(38)

3838

Il compilatore

Il compilatore − − 2 2

• L’analizzatore lessicale analizzatore lessicale trasforma il programma sorgente da stringa di caratteri a stringa di tokenstringa di token

• Un token è un simbolo che esprime la natura di un elemento token del linguaggio

 Punteggiatura ed operatori vengono trasformati direttamente in token

 Per parole riservate, nomi di variabili e costanti, l’analizzatore deve determinare il token appropriato, esaminando sia la stringa di caratteri, sia il contesto

 Ogni identificatore viene inserito nella tabella dei simboli tabella dei simboli ed i suoi attributi vengono aggiornati nella fase di analisi semanticaanalisi semantica

(39)

3939

Il compilatore

Il compilatore − − 3 3

• L’output del’analisi lessicale è un insieme di coppie, il cui primo elemento identifica la classe del token ed il secondo punta alla posizione del token e dei suoi attributi nella tabella dei simboli

 Alcuni token non richiedono attributi e dunque avranno puntatori nulli (ad es., operatori e parole riservate del linguaggio)

(40)

4040

Il compilatore

Il compilatore − − 4 4

(41)

4141

Il compilatore

Il compilatore − − 5 5

• L’analizzatore sintattico analizzatore sintattico (o parser) permette la costruzione parser dell’albero di derivazione del particolare programma basato sulla grammatica del linguaggio

(42)

4242

Il compilatore

Il compilatore − − 6 6

• L’analizzatore semantico, infine, usa l’albero di derivazione analizzatore semantico per generare una rappresentazione intermedia e completare la tabella di simboli

 Un altro ruolo svolto dall’analizzatore semantico è la scoperta di errori dipendenti dal contesto (tipi di dati che non corrispondono, variabili non dichiarate, etc.)

(43)

4343

Il compilatore

Il compilatore − − 7 7

• Il generatore di codice generatore di codice traduce la rappresentazione intermedia in linguaggio assembler o linguaggio macchina

• Prima della generazione di codice:

 Allocazione della memoria

 Allocazione dei registri

• L’ottimizzatore del codice ottimizzatore del codice intermedio effettua trasformazioni atte a migliorare l’efficienza del codice eseguibile finale

(44)

4444

Il compilatore

Il compilatore − − 8 8

Traduzione da algoritmo a codice C e da C ad Assembler Traduzione da algoritmo a codice C e da C ad Assembler

(45)

4545

Il compilatore

Il compilatore − − 9 9

Interazione fra compilatore, SO e hardware Interazione fra compilatore, SO e hardware

(46)

4646

Compilatore e linker

Compilatore e linker − − 1 1

• I compilatori consentono tipicamente la compilazione separata di parti di programmi (moduli)moduli

• I diversi moduli possono essere progettati, costruiti e messi a punto separatamente, e archiviati in opportune librerielibrerie

• Nel momento in cui un programma deve essere eseguito, un programma apposito, detto linker, si occupa di collegare linker opportunamente fra loro i moduli oggetto

• Il risultato dell’esecuzione del linker è un unico modulo, detto modulo eseguibile, pronto per il caricamento in modulo eseguibile memoria e l’esecuzione

(47)

4747

Compilatore e linker

Compilatore e linker − − 2 2

Il ruolo del linker Il ruolo del linker

(48)

4848

Compilatore e linker

Compilatore e linker − − 3 3

Da sorgente ad eseguibile Da sorgente ad eseguibile

(49)

Debugger

• Anche quando tutti gli errori sintattici sono stati corretti, non è detto che il programma funzioni!

– Errori “runtime” che interrompono il programma o portano a cicli infiniti

– Errori che portano il programma a fornire

risultati errati

(50)

Debugger

• Un errore in un programma è chiamato

“bug”

• Il de-bugger serve a eliminare questi errori analizzando:

– Il valore delle variabili passo a passo

– Interrompendo l’esecuzione al verificarsi di

alcuni eventi

(51)

Dal codice all'eseguibile

CODICE

SORGENTE COMPILATORE MODULO

OGGETTO LINKER PROGRAMMA

ESEGUIBILE LIBRERIE

CORREZIONE DEBUGGER

(52)

Linguaggi compilati

• Fino ad ora abbiamo visto il meccanismo di funzionamento dei linguaggi compilati:

un compilatore non esegue il programma che riceve in ingresso, ma lo traduce in linguaggio macchina (memorizzando su file il codice oggetto pronto per

l'esecuzione diretta da parte del

processore).

(53)

Linguaggi interpretati

• Un linguaggio interpretato è invece un linguaggio di programmazione i cui programmi vengono eseguiti da un interprete.

• Un programma interpretato, in esecuzione, richiede più memoria ed è meno veloce. Durante l'esecuzione, l'interprete deve infatti analizzare le istruzioni a

partire dal livello sintattico, identificare le azioni da eseguire, trasformarle in linguaggio macchina ed eseguirle; mentre le istruzioni del codice compilato, già in linguaggio macchina, vengono caricate e

istantaneamente eseguite dal processore.

(54)

Linguaggi interpretati

• In compenso, l'interpretazione di un programma può essere più rapida del ciclo compilazione/esecuzione.

Questa differenza può costituire un vantaggio durante lo sviluppo di un programma.

• Inoltre, la maggior parte degli interpreti consentono all'utente di agire sul programma in esecuzione

sospendendolo, ispezionando o modificando i contenuti delle sue variabili, e così via, in modo spesso più

flessibile e potente di quanto si possa ottenere, per il

codice compilato, da un debugger.

(55)

5555

L’arte della programmazione L’arte della programmazione

Analisi Analisi

Programmazione Programmazione

• La soluzione di un problema tramite un programma è un procedimento che non si esaurisce nello scrivere codice in un dato linguaggio di programmazione, ma comprende una fase di progetto, che precede, e di verifica, che segue, la scrittura del codice

 Definizione del problema

 Algoritmo per la soluzione del problema

 Codifica

 Debugging

 Validazione

 Documentazione

 Manutenzione