Lezione1-Algoritmi+strutturedati= programmihomes.di.unimi.it/anisetti/Teaching/15-16/Unit7.pdf ·...

Lezione 1 - Algoritmi + strutture dati =

programmi

Corso — Programmazione

Programmazione e progettazione — Strutture dati e

sottoprogrammi

Marco Anisetti

e-mail: [email protected]

web: http://homes.di.unimi.it/anisetti/

Università degli Studi di Milano — Dipartimento di informatica

http://homes.di.unimi.it/anisetti/

Scrivere programmi

• Descrivere cioè algoritmi con un linguaggio per cui

l'esecutore è il calcolatore.

• Se si parte dal problema da risolvere serve l'abilità di

descrivere la soluzione pensando in termini di algoritmi

(Algorithmic Thinking)

• Per scrivere un programma abbiamo bisogno di

Descrivere i datiDefinire le istruzioni che operano sui dati (istruzioni datedall'algoritmo e codificate in un linguaggio)

• Flusso

Partenza dai dati inizialiAlgoritmo (dati + istruzioni)Otteniamo dei dati finali (soluzione alla nostra istanza diproblema)

Algorithmic Thinking(1)

• Un programmatore deve sviluppare l'abilità di capire,

eseguire, valutare e creare algoritmi

• Capire ed eseguire: Attitudine a seguire sequenze precise

di istruzioni senza perdere la pazienza e con estrema

diligenza e perseveranza. A volte è veramente tedioso

seguire step-by-step un algoritmo complesso, ma non

bisogna arrendersi

• Valutare: Determinare se un algoritmo risolve il problema

per cui è nato

• Creare Dato un problema trovare una soluzione

algoritmica al problema

• Tutto questo deve essere fatto sapendo quel è l'esecutore

• Gli algoritmi trattati nel corso sono quelli eseguibili da un

calcolatore

Algorithmic Thinking(2)

• Problem-solver vs Programmer

• Disaccoppiare il linguaggio di programmazione

dall'algoritmo

• Uno strumento agevole per farlo è come abbiamo già

intuito il flow chart

• I flow chart introducono un certo carico di lavoro dovuto al

disegno e alla difficoltà della modifica se non si utilizzano

strumenti elettronici

• Se fosse possibile programmare usando i flow chart

servirebbe uno strumento che li converta nel relativo

codice macchina per permetterne l'esecuzione

Descrivere i dati

• Per il momento non ci siamo preoccupati se non in

maniera superficiale della descrizione dei dati

• Abbiamo parlato genericamente di variabili e del fatto che

occupino una locazione di memoria di dimensione

dipendente dal tipo

• Abbiamo visto che il tipo determina le istruzioni che

possono essere eseguite su di esso

• I dati di un problema devono essere descritti con lo stesso

rigore e precisione con la quale si determina l'algoritmo

per risolvere un problema

• I dati possono essere semplici o strutturati ed organizzati

in dati complessi

Algoritmi + strutture dati = programmi

• Nel momento in cui si passa da algoritmo a programma le

strutture dati devono essere esplicitate

• I problemi affrontati sono talmente semplici che bastano

variabili semplici assimilabili a incognite matematiche

• Sembra che l'algoritmo dipenda soprattutto dal set di

istruzioni che lo compongono

• In realtà conta moltissimo anche la struttura dati su cui

agisce

• Lo stesso problema si può risolvere con algoritmi differenti

Lo stesso algoritmo può avere delle incarnazioni differentise la struttura su cui si appoggia è differenteUna struttura dati adeguata può aiutare a risolvere ilproblema e a scrivere il programma relativo, piùagevolmente (embrione della programmazione ad oggetti)

Istruzioni e strutture dati(1)

• Un programma per funzionare deve essere caricato in

memoria e da li può essere eseguito dall'elaboratore

• Questo ci suggerisce che anche le istruzioni di un

programma risiederanno in memoria assieme alle

strutture dati dello stesso programma

• Per le competenze che abbiamo raggiunto fino ad ora

possiamo dire che la memoria allocata per il programma

in esecuzione viene divisa tra codice e dati

• In realtà esistono differenti strategie per la gestione della

memoria

• Un programma in esecuzione (processo) potrebbe aver un

bisogno crescente di memoria dati (dati dinamici)

• Il segmento dati deve poter crescere, il segmento codice

non cresce

Segmentazione della memoria(1)

• E' importante per un programmatore comprendere cosa

succede al programma che scrive nel momento in cui

viene eseguito

• Per prima cosa quando viene eseguito il programma è

stato trasformato in un codice macchina direttamente

interpretabile dall'elaboratore

• In generale i riferimenti ad indirizzi di memoria locali al

processo (variabili) sono espressi in forma relativa

(dipende dal traduttore usato per passare al linguaggio

macchina)

• La gestione della memoria e del caricamento delprogramma in memoria è a carico del Sistema Operativo(definisce l'indirizzo di base)

Approfondimenti nel corso di Sistemi Operativi

Segmentazione della memoria(2)

• Per le nostre competenze attuali possiamo dire:

• Segmento codice: Contiene il codice del programma (ed

in alcuni casi le costanti). Normalmente viene condiviso

fra tutti i processi che eseguono lo stesso programma.

Viene marcato in sola lettura per evitare sovrascritture

accidentali (o maliziose)

• Il segmento dei dati: Contiene le variabili (a volte

diviso in due parti, variabili inizializzate e non inizializzate)

Lezione 2 - Tipi da dato elementare



sottoprogrammi

Marco Anisetti





Modificatori di tipo Costante

• Costante è intuitivamente un valore che non cambia per il

lasso di tempo in cui viene usato

• Costante è differente da letterale

• Un letterale è un carattere che viene inserito in unaespressione

Esempio x + 5 x variabile 5 letterale

• Una costante in programmazione è un modificatore di tipo

che indica che una variabile non potrà mai cambiare valore

Variabili e costanti

• Sia variabili che costanti potrebbero in alcuni linguaggi di

programmazione richiedere una loro ′′dichiarazione′′

• Se esiste l'obbligo della dichiarazione questa permette di

definire sia variabili che costanti e deve necessariamente

indicarne un tipo (almeno per le variabili)

• La dichiarazione deve avvenire prima dell'utilizzo della

variabile o costante

• La costante deve essere solitamente inizializzata con il

suo valore nel momento che viene dichiarata

• A volte come nel caso del Pascal la costante non richiede il

tipo perchè è immediatamente deducibile dalla sua

inizializzazione

Tipi di dato

• In generale un linguaggio di programmazione permette il

trattamento di diversi tipi di dato

• Un tipo di dato è determinato dal range di valori che può

assumere un oggetto di quel tipo e da delle operazioni che

si possono effettuare su tale tipo

• I tipi più comunemente presenti nei linguaggi di

programmazione sono catalogabili in tipi semplici, tipi

strutturati e tipi puntatore

Tipi di dato semplice(1)

I tipi semplici solitamente annoverano:

• Numeri interi: indica il campo dei numeri interi,

ovviamente ristretto dai valori MAXINT e MININT. Gli

operatori definiti sono solitamente quelli di +, -, *, div e

mod

• Numeri reali: I numeri reali formano un continuo, mentre

nei calcolatori il tipo reale può contenere un numero finito

di valori ciascuno per rappresentare un intervallo del

continuo. Questa approssimazione implica un errore che è

campo d'indagine per il calcolo numerico. I processi che

utilizzano il tipo reale sono detti numerici.

Tipi di dato semplice(2)

• Carattere: indica il campo finito ed ordinato di simboli

(caratteri). Richiede una standardizzazione per associare

un codice ad un carattere es ASCII. Esistono i codici sia

dei caratteri di stampa che dei caratteri di controllo (es.

carriage return, line feed)

• Booleani: assumono due valori logici True o False, sono

definiti degli operatori come AND OR NOT ecc. Tutti gli

operatori di relazione solitamente ritornano un valore

booleano. Di solito vengono descritte delle tabelle di

verità per valutare i risultati degli operatori. Le

espressioni basate su booleani e operatori possono essere

valutate con tecniche short-circuit

Tipi di dato: numeri reali(1)

• Virgola fissa, si stabiliscono a priori le cifre per la parte

decimale e per quella intera

• Virgola mobile, rappresentazione matematica

esponenziale dei numeri mediante mantissa m ed

esponente e: x = m ∗ Be, dove B è la base dellarappresentazione è può essere 10, 16 o 2 a seconda

dell'elaboratore (standard IEEE 754)

• La precisione di una aritmetica in virgola mobile può

essere definita come ε ovvero il più piccolo numeropositivo tale che 1 6= (1 + ε) (se precisione di n cifredecimali ε = 10−n ), ed è fonte di errori che unprogrammatore deve considerare

Tipi di dato: numeri reali(2)

• Alcune proprietà delle operazioni vengono meno proprio

per questa imprecisione

[ESEMPIO associatività]

Consideriamo un'aritmetica a 4 cifre, x = 9. 900, y = 1. 000,z = −0. 999(x + y) + z = 10. 90 + (−0. 999) = 9. 910x + (y + z) = 9. 900 + 0. 001 = 9. 901

Approssimazione nei reali: esempio(1)

• Soluzione di una equazione di secondo grado (problema

della cancellazione)

ax2 + bx + c = 0

• Si risolve matematicamente come noto con

d ← sqrt((b ∗ b)− 4 ∗ a ∗ c)x2 ← −(b+ d)/(2 ∗ a); x1 ← (d − b)/(2 ∗ a)

• Con una aritmetica a 4 cifre e con i seguenti numeri

a = 1. 000 ,b = −200. 0, c = 1. 000 si avrebbe:d = sqrt(40000− 4. 000) = 200. 0x1 = 400. 0/2. 000 = 200. 0x2 = 0. 000/2. 000 = 0

• Ma le soluzioni corrette alla quarta cifra sono x1 = 200. 0 ex2 = 0. 005

• Non sempre si possono applicare metodi risolutivi della

matematica quando si ha a che fare calcolatori numerici

Approssimazione nei reali: esempio(2)

• Si può superare questo limite in questo caso usando un

algoritmo differente che sfrutta la relazione x1 ∗ x2 = c/a

• Quindi si può calcolare una soluzione (con valore

maggiore) e poi applicare questa relazione per ricavare

l'altra

[esempio]

d ← sqrt((b ∗ b)− 4 ∗ a ∗ c)if b ≥ 0 then x1 = −(b+ d)/(2 ∗ a)else x1 = (d − b)/(2 ∗ a)endif

x2 = c/(x1 ∗ a)end

Tipi puntatore

• Puntatore o riferimento: si riferisce all'indirizzo di

memoria dove una determinato oggetto (di un tipo

conosciuto) risiede. Vengono usati per questioni di

efficienza e per gestire tipi dinamici che possono crescere

o decrescere a run-time

• Di solito il controllo del tipo è molto stringente sui

puntatori per evitare che essi vengano interpretati come

altri tipi.

• Le operazioni che si fanno sui puntatori sono di solito

allocazione, riferimento, assegnamento, controllo di

uguaglianza, deallocazione

• Esempio: se x contiene l'indirizzo di una variabile intera

y, allora si dice che x punta alla variabile intera y e si

indica con un operatore di riferimento a seconda del

linguaggio (∗x liguaggio C)

Ricapitolando

• L'associazione tra operatori e tipi viene difinita nei manuali

dei linguaggi

• In questa fase ci interessano considerazioni più generiche

• Rappresentazione dei dati in forma interpretabile dalla

macchina

• I tipi semplici fittano in una locazione della macchina

• I tipi strutturati derivano dai tipi base e sfruttano

sequenze contigue di locazioni della macchina

• La rappresentazione di tipi che formano un continuo come

i reali è discretizzata introducendo delle approssimazioni

• Tipi puntatore contengono indirizzi di memoria e si

riferiscono sempre ad un tipo semplice o strutturato

• Costanti sono un modificatore di tipo

• La tipizzazione aiuta il programmatore nella codifica

Lezione 3 - Flow Chart con RAPTOR



sottoprogrammi

Marco Anisetti





Flow chart con RAPTOR

• Si tratta di un ambiente grafico che permette il disegno

dei flow chart e la loro esecuzione automatica

• Si seguono le regole per la definizione del flow chart già

viste

• Esistono dei formalismi aggiuntivi per determinare deiblocchi che eseguono i seguenti compiti:

Input: un trapezio con una freccia entranteOutput: un trapezio con una freccia uscenteCall: un trapezio con una doppia freccia uscente,determina la chiamata di una funzionalità di libreria

• E' possibile rappresentare tutti i costrutti basilari della

programmazione strutturata

Flow chart con RAPTOR

RAPTOR: le variabili(1)

• Le variabili hanno un ruolo importante in ogni tipo di

programma

• RAPTOR gestisce le variabili in modo che queste siano

non specificate fino a che non vengono assegnate

• RAPTOR non prevede una fase dichiarativa per le variabili

• Una variabile si vede cambiare o settare il proprio valorein tre modi:

Un valore inserito da una istruzione di inputIl valore assegnato relativamente al calcolo di unaequazioneValore di ritorno ottenuto da una chiamata a unafunzionalità di libreria o chiamata a procedura

• Una variabile è identificata dal suo nome (identificatore)

che serve seguire delle regole semplici come

l'impossibilità che inizi per un numero, che contenga spazi

o caratteri non strettamente alfanumerici

RAPTOR: le variabili(2)

• Alloca virtualmente la memoria per la variabile indicata

del relativo identificatore nel momento in cui la trova per

la prima volta.

• La variabile esiste fino al termine del programma

• Quando la variabile viene creata allora si determina anche

il tipo

• Esistono solamente due tipi base in RAPTOR il tipo numero

e il tipo testuale

• Le variabili non possono cambiare tipo durante

l'esecuzione del programma

Le costanti

• Sono degli identificatori che si rifanno ad una zona di

memoria che non è modificabile dopo che è stato definito

il suo contenuto la prima volta

• In RAPTOR esistono delle costanti di sistema definite per

facilitare il calcolo di espressioni matematiche es pi = π ede

• In generale un linguaggio di programmazione permette di

definire delle costanti che rimangono tali per la durata del

programma

RAPTOR: Statements o istruzioni(1)

• Trattandosi di flow chart i tipi di istruzioni sono codificati

nel costrutto grafico utilizzato

• In RAPTOR esistono costrutti per istruzioni di tipo: Input,

Assignment, Call, and Output

• Input Statement: Permette di specificare un testo da

usare come prompt e il nome della variabile dove verrà

salvato l'input

• Assignment Statement: Generalmente serve per

effettuare un calcolo e salvare il risultato in una variabile.

In generale la parte destra potrebbe contenere

espressioni di varia complessità

Le espressioni matematiche(1)

• Definite utilizzando un linguaggio e una notazione

(prefissa, infissa, postfissa)

• E' composta da operatori e operandi

• Gli operandi possono essere delle costanti (numeri) delle

funzioni (es funzioni matematiche predefinite) o delle

variabili

• RAPTOR adotta la notazione infissa e quindi le normali

regole di precedenza tra operatori

• Nel dettaglio le precedenze in Raptor sono:

1. Le funzioni2. Ogni cosa nelle parentesi3. Esponenziali4. Moltiplicazioni e divisioni da sinistra a destra5. Somme e sottrazioni da sinistra a destra

Le espressioni matematiche(2)

• Ogni linguaggio di programmazione definisce delle

funzioni aggiuntive agli operatori matematici elementari

come ad esempio operatori per il calcolo del modulo della

divisione (mod) della radice quadrata (sqrt) del valore

assoluto (abs) ecc.

• Tali possono richiedere una rappresentazione in termini di

funzione con la notazione < nome funzione > (< parametri

funzione >)

• Le espressioni matematiche sono espressioni che

coinvolgono oggetti di tipo numerico

• In generale un linguaggio potrebbe permettere

espressioni che contengano oggetti di altro tipo

Le espressioni generiche

• Una espressione è una combinazione di oggetti che

avviene attraverso degli operatori che sono definiti per

quegli oggetti

• In RAPTOR esistono solo due tipi di dati i numeri e il testo

• Esiste un operatore che è definito sul testo che è

l'operatore ``+'' che permette di concatenare testo

• Tale operatore è definito anche per la coppia < numero >< testo > ed agisce convertendo il numero in testo (senzaassegnare questa conversione) e concatenando.

Altri esempi di operatori ridefiniti sono il * tra < numero > < stringa > in python

(ripete la stringa per < numero > di volte)

Ricapitolando

• RAPTOR permette di programmare usando i costrutti dei

flow chart

• Come tutti i linguaggi di programmazione ha delle

caratteristiche associate alla gestione di variabili e tipi

• La forma grafica identifica la tipologia di istruzione

• L'istruzione scritta all'interno della forma è pilotata

• Le espressioni matematiche vengono gestite in modo

classico

• Alcuni operatori hanno delle specificità tipo l'operatore

``+''

Lezione 4 - Utilizzo di RAPTOR



sottoprogrammi

Marco Anisetti





Ricapitolando

• Abbiamo visto come si può usare RAPTOR per scrivere uno

dei programmi visti fino ad ora a lezione

• RAPTOR permette di valutare un flow chart in modo

automatico

• Ha delle limitazioni dovute a delle semplificazioni

• Aiuta a pensare in termini di algoritmo ed evidenzia il

controllo di flusso

Lezione 5 - Relazioni di ricorrenza e tipi di

dato strutturato (parte I)



sottoprogrammi

Marco Anisetti





Programmi basati su relazioni di

ricorrenza(1)

• La ricorrenza prende spunto dal concetto matematico di

induzione

• La ricorrenza può avere due forme nella programmazione,

le ripetizioni (ciclo) e la ricorsione

• Vedremo prevalentemente programmi che si basano su

ripetizioni semplici nella forma pre-condizionata while

cond do I

• Le ripetizioni hanno senso se terminano ovvero se I

modifica almeno una variabile che compare in cond

rendendola non più soddisfatta

• Il ciclo sopra può diventare logicamente il seguente: V←v0; while p(V) do V ← f(V)

• Dove p è un predicato (booleano) e f una funzione

• All'inizio della ripetizione V deve avere un valore ben

determinato V0

Programmi basati su relazioni di

ricorrenza(2)

• Esempio: Calcolo fattoriale f (n) = 1 ∗ 2∗3∗ · · · ∗n = n! (n ≥ 0)

• E' calcolabile usando una relazione di ricorrenza

• f (n) = n ∗ f (n− 1) per n > 0

• Avendo come condizione iniziale f (0) = 1

Tipi di dato strutturato: array(1)

• Vettori o array: struttura che contiene dati omogenei(dello stesso tipo), aventi uno stesso identificatore.

L'accesso agli elementi del vettore avviene attraverso indiciche definiscono le posizioni nel vettore (accesso diretto)Si tratta di una struttura sequenziale (memorizzata in unastruttura di memoria contigua)Si tratta di una struttura statica, ovvero la sua dimensionedeve essere definita a priori e non può essere modificatadurante l'esecuzione del programmaSequenzialità e staticità sono legati chiaramente da comeviene allocato lo spazio per un vettore in memoria


• La gestione di un array avviene tramite tre diverse

informazioni: L'indirizzo di base IB dato dalla variabile

definita come array stessa, il numero di elementi N, la

dimensione del singolo elemento D

• Queste informazioni assieme al fatto che si tratta di una

struttura dati contigua permette l'accesso diretto tipico

degli array

• Esempio: se volessi accedere all'elemento J di un array

allora dovrei recuperare il dato che si trova in

IB+D ∗ (J − 1)

• Può avvenire o meno il controllo dello sforamento della

dimensione dell'array

• Generalmente non sono accettati array di dimensione

dinamica non nota in fase di compilazione


• Inizializzazione e caricamento sono due fasi simili in cui un

vettore viene riempito dei dati che servono al programma

• L'inizializzazione avviene solitamente in fase di

dichiarazione, si tratta del primo caricamento di dati nel

vettore

• Il caricamento è una operazione che prevede l'inserzione

di dati in un vettore in modo completo (simile

all'inizializzazione) o parziale

• Solitamente la notazione per l'array prevede l'uso delle

parentesi [] per racchiudere l'indice o la dimensione se sista valutando la fase dichiarativa

Array in RAPTOR

• RAPTOR non prevedendo la fase dichiarativa considera un

array ogni identificatore seguito da ``[< numero >]''

• Nel momento in cui viene utilizzato per la prima volta ad

esempio il vettore v[n], raptor provvede ad inserire anchei valori per v[(n− 1). . 1] ovvero alloca lo spazio per glielementi del vettore inferiori a n

Caricamento di un array

• Il caricamento dei dati in un array avviene attraverso un

ciclo che ad ogni iterazione inserisce un valore e sposta

l'indice al prossimo elemento

Problema

• Calcolo del peso di un aeroplano e del suo bilanciamento

(esempio tratto dal manuale di RAPTOR)

• Per ogni elemento che costituisce un aereo:

Moltiplicane il suo peso per il suo ``moment arm'' perottenere il momento dell'elementoCalcolare il momento totale sommando tutti i momentidegli elementiCalcolare il peso complessivo sommando i pesi di ognielemento

• Ottenere il centro di gravità dividendo il momento totale

per il peso totale

• Se considerassi solo 3 elementi potrei anche risolvere il

problema usando 6 variabili distinte

Soluzione

Soluzione usando gli array

Utilità di un array

• Gli array sono utilizzati spesso in associazione a cicli

• Sono indispensabili per risolvere problemi in cui abbiamo

aggregazioni di dati da elaborare scandendoli in vario

modo

• Permettono di aggregare variabili dello stesso tipo e che si

possono correlare tra loro distinguendole in base ad indici

• Esistono diverse operazioni che ha senso studiare sugli

array e che possono tornare utili per la scrittura di un

programma

Array: esempio

• Dato un array V di 10 elementi contenente interi,

restituire a video un array A con gli elementi invertiti

(ultimo al primo posto etc)

• Analisi: La richiesta equivale a scorrere il vettore in senso

opposto dall'ultimo elemento al primo dato che devo solo

stamparli a video

[Pseudcodice]

integer v[10]={2,3,6,1,8,3,9,2,5,9}

i← 10

while (i>0) do

stampa(a[i])

i← i-1

endwhile

Lezione 6 - Relazioni di ricorrenza e tipi di

dato strutturato (parte II)



sottoprogrammi

Marco Anisetti





Operazioni semplici sugli array: Ricerca(1)

• Ricerca: Esistono due casi da valutare: 1) vettore in cuicercare non ordinato, 2) vettore in cui cercare ordinato.

Nel caso di array non ordinato è necessario scorrere tuttol'array (es. scrivere l'algoritmo usando raptor)Per la ricerca in un array ordinato è interessante provare apensare ad un algoritmo efficiente che eviti di scorreretutto o in gran parte l'array

Operazioni semplici sugli array: Ricerca(2)

• Ricerca in un array ordinato fermandomi quando non

viene più rispettato l'ordine

• Utilizzando il metodo dicotomico o la ricerca binaria.Si controlla l'elemento mediano del vettore ordinatoconfrontandolo con quello che cerco (consideriamoordinamento crescente) e a questo punto ci son 3 casi

Elemento è uguale, allora l'ho trovatoElemento è minore rispetto a quello che cerco, allora possoescludere che si trovi nella prima metà (sottosequenzasinistra) del vettore, quindi continuo con la seconda metà(sottosequenza destra)Elemento è maggiore rispetto a quello che cerco, alloraposso escludere che si trovi nella seconda metà(sottosequenza destra) del vettore, quindi continuo con laprima metà (sottosequenza sinistra)

Operazioni semplici sugli array:

Ordinamento(1)

• Ordinamento: algoritmo di Selezione e algoritmo

bouble-sort

• Algoritmo di selezione: L'idea è quella di cercare e

scambiare, ovvero la prima volta cerco l'elemento più

piccolo e lo metto alla prima posizione e poi continuo con

il secondo più piccolo ecc.

Operazioni semplici sugli array:

Ordinamento(2)

• Bouble sort:Si scorre tutto il vettore scambiando gli

adiacenti a due a due se non sono in ordine. Si ripete la

scansione fino a che non se ne effettua una che non

sposta nulla

• Il nome dell'algoritmo deriva proprio da questo

movimento a salire degli elementi che viene visto come

bolle in un liquido.

Operazioni semplici sugli array: merge(1)

• Dati due vettori ordinati V di N elementi e W di M elementi

si definisce Merge dei due il vettore ordinato X di al

massimo M +N elementi ottenuto dalla fusione di V e W

• Se esistono elementi condivisi non possono comparire più

di una volta in X (elementi non ripetuti). Esistono anche

Merge con ripetizione

Operazioni semplici sugli array: merge(2)

• L'algoritmo di Merge senza ripetizione si può descrivere

come:

1. Inizializzo gli indici di scorrimento I(per V),J(per W),K (perX) dei vettori

2. Assicurandosi che I e J siano validi

se V [I] < W[J] allora X [K ] prende valore V [I] ed incremento Ie K altrimenti se V [I] > W[J] si carica W[J] e si incrementa J eK, altrimenti se sono uguali carico a scelta e incremento tutti

e 3 gli indici

3. A questo punto tutto V o W è stato ricopiato in X, copio irestanti elementi alla fine di X

Matrici

• Le matrici sono degli array multidimensionali

• Dal punto di vista degli array visti fino ad ora si tratta di

vettori che hanno come elementi altri vettori

• Per individuare un elemento di una matrice sono necessari

due indici

• Solitamente il primo indice identifica le righe mentre il

secondo le colonne

• In RAPTOR come in Pascal una matrice è definita come

M[i,j] con i e j indici per righe e colonne

Matrici: esempio

• Scrivere il programma che data una matrice ritorna gli

elementi della diagonale principale

• Analisi: gli elementi richiesti sono quelli che stanno nelle

posizioni dove i due indici sono uguali

[Pseudcodice]

integer v[10,10]

i← 1

j← 1

while (i<=10 and j<=10) do

stampa(v[i,j])

i← i+1

j← j+1

endwhile

• Si può scrivere in maniera più compatta?

Tipi di dato strutturato: record(1)

• La natura dei dati di un problema può essere troppo

complessa per essere descritta con variabili semplici o

array

• Ad esempio una transazione bancaria racchiudono conto

corrente, tipo di operazione ed importo

• Volendo con 3 variabili semplici si potrebbe risolvere il

problema senza però che esse riferiscano espressamente

alla stessa transazione

• Non si tratta di descrivere un oggetto ma di trovare un

modo più opportuno per descrivere una classe di oggetti

con caratteristiche comuni (attributi)

• Esempio attributi di un'auto possono essere Marca, Tipo,

Colore, Numero di telaio. Essi sono comuni alla classe

Automobile, ogni automobile è caratterizzata da dei

precisi valori per questi attributi

Tipi di dato strutturato: record(2)

• Un Record è una struttura dati complessa che cattura

questo concetto. E' composto da un insieme finito di

elementi (campi) di qualsiasi tipo che sono però

logicamente connessi

• I campi corrispondono agli attributi: ogni campo contiene

un valore per un attributo

• Ogni record è individuato dal suo identificatore, mentre

ogni suo campo è individuato dall'identificatore del record

e dall' identificatore del campo stesso

• Si può vedere analogamente all'array come un rettangolo

suddiviso ma in blocchi che possono essere anche di

dimensioni differenti, con gli attributi al posto degli indici

e i campi sotto gli attributi fuori dal rettangolo

Record: esempio

• Consideriamo un array di strutture di tipo anagrafico

comprendenti nome e cognome. Scrivere un programma

che dato in ingresso il cognome trova tutti i nomi relativi e

li stampa a video assieme al cognome

[Pseudcodice]

type anagrafica = record

nome:stringa

cognome:stringa

end

anagrafica an [10]

i← 1

leggi(nom)

while (i<=10) do

if (an[i].nome==nom) then stampa (nom, an[i].cognome)

i← i+1

endwhile

Record varianti

• Genericamente i record sono delle struttura dati fissate in

fase di dichiarazione similmente a quelli che avviene per

gli array

• In alcuni casi si nota la necessità di avere record varianti

in cui i cambi del record dipendono dal valore di altri capi

dello stesso record

• Ad esempio consideriamo una anagrafica di pazienti nella

quale vogliamo indicare la malattia e gli esami da fare in

relazione alla malattia

• Ogni malattia ha i suoi esami specifici, si potrebbe

considerare una struttura nella quale tutti gli esami

vengono definiti ma solo alcuni vengono flaggati come

validi

• In questo caso avrei spreco di spazio che può essere

considerevole.

• La dimensione occupata dal record è comunque la

massima dimensione tra le varianti

Record varianti: esempio(1)

• Realizzare un tipo di dato adeguato per conservere

informazioni sui libri di una biblioteca. I campi di interesse

sono: autore, titolo, anno, collocazione.

• Collocazione può essere o il numero di uno scaffale e del

ripiano o il nome e cognome della parsona che l'ha preso

a prestito

• Analisi: esiste una parte fissa che è costituita da autore,

titolo anno e una parte variante che determina la

collocazione che può essere di due tipi. Consideriamo

scaffale e ripiano come un record posizione e nome e

cognome come un altro record anagrafica

Record varianti: esempio(2)

[Pseudcodice]

type posizione = record

scaffale:integer

ripiano:integer

end

type libro = record

autore:stringa

titolo:stringa

anno:integer

union{

cliente: anagrafica

collocazione: posizione

} end

• Non c'è alcun controllo sulla rappresentazione adottata

Controlli sui tipi

• I tipi associati a delle variabili si estendono alleespressioni (type system del linguaggio)

Operatori aritmeticiOverload: significati differenti a seconda del contestoCoercion: promozioni automatiche a tipi differenti perrisolvere conflittiPolimorfismo: una funzione polimorfica ha un tipoparametrico o generico

• A seconda del linguaggio il tipo di una variabile può esserefisso o meno

Valore dinamico ma tipo fisso (binding statico)Tipo associato run-time (binding dinamico)

• Equivalenza tra tipi• Controllo statico o dinamico

Errore sul tipo avviene quando una funzione (operatore) siaspetta un tipo come argomento e ne trova un altroControlli sul codice prima che venga tradottoControlli sui tipi run-time (controllo sforamento indici di unarray)

Dati strutturati in memoria

• Dediamo un esempio di come dovrebbero essere allocate

le variabili strutturate in memoria

Ricapitolando

• L'importanza di poter derivare delle relazioni di ricorrenza

• Relazione tra tipo di dato strutturato array e i cicli

Cicli che scorrono indici, alcuni linguaggi hanno definito uncostrutto ad hoc (compatto) per questo genere di cicli (esfor)

• Operazioni base di ricerca merge e ordinamento su array

• Definizione di array multidimensionali (matrici)

• Definizione di tipo strutturato record

• Controlli sui tipi

• Occupazione di memoria

Lezione 7 - Strutture dati su memoria di

massa



sottoprogrammi

Marco Anisetti





Dati strutturati in memoria di massa

• Le variabili strutturate viste fino ad ora sono definite a

partire dal tipo di struttura sequenziale e dal tipo di dato

dei componenti

• File: Una successione di elementi

• Simile ad un array ma non è possibile accedere ad un

singolo elemento attraverso un indice ed il numero di

elementi non deve per forza essere stabilito a priori

• E' una struttura che ben si adatta alla natura sequenziale

della memoria di massa o a dispositivi di output tipo

stampanti

• I file risiedono tipicamente su memoria di massa

I file(1)

• Un file potrebbe in maniera astratta essere un semplice

tipo non legato alla sua memorizzazione

• Le specificità di tale tipo sono:

La lunghezza è libera non deve essere dichiarataHa una natura intrinseca sequenziale (scorrere per leggere,scrivere alla fine o in testa o dopo aver scorso)

• Può essere associato al concetto di flusso (dispositivo

logico associato a dispositivi di I/O)

• Esistono due tipi di flussi: flusso binario, flusso di caratteri

• Con questa visione un file è mappato su qualsiasi

dispositivo di I/0 il mapping avviene tramite l'operazione

di apertura

I file(2)

• L'operazione di apertura di un file richiede il nome del file

e la modalità di apertura

• La modalità può essere di sola lettura, lettura e scrittura

sola scrittura ed in alcuni casi append

• La apertura ritorna un riferimento o un puntatore ad una

struttura file (in C) o ad un buffer

• Ogni operazione sul file viene fatta attraverso questo

riferimento/puntatore

• La struttura file contiene informazioni aggiuntive tipo la

posizione corrente nel file, eventuali errori, indicatore di

terminazione del file ecc.

I file(3)

• Le operazioni possibili su un file sono la lettura e la

scrittura, ed eventualmente il posizionamento

• Esistono alcuni file standard che sono aperti e passati al

programma dal sistema operativo e servono per

permettere l'interazione del programma con il mondo

esterno (standard input, standard output, e standard

error)

• Una volta terminato l'utilizzo un file viene normalmente

chiuso passando il puntatore o riferimento

• Le operazioni sui file si interfacciano con la gestione dei

file del Sistema Operativo

File utilità

• Servono per interfacciarsi con dispositivi mappabili su un

flusso

• Possono essere utili per salvare lo stato di elaborazioni

successive

• Vengono usati come repository permanente di

informazioni (es le configurazioni di un programma)

• Possono essere di varia natura e contenere informazioni

quali immagini, video ecc.

File di record

• E' possibile salvare in un file una serie di record ottenendo

una struttura simile ad una tabella

• Generalmente questi file sono considerati ad

accesso casuale ovvero non obbligatoriamente

sequenziale

• Posso ricercare un record utilizzando la sua posizione nel

file (ad esempio il 13 record nel file)

• Il supporto che mappa il file deve permetterlo

• Si usano istruzioni di spostamento nel file per posizionarsi

sul record da leggere

• La dimensione del record deve essere fissa per ogni

elemento per permettere di spostarsi con n*dimensione

Conclusioni

• Oggi si pensa a strutture più complesse ed astratte per

immagazzinare dati (database)

• Tali strutture superano il problema della sequenzialità dei

file e permettono rapidi accessi e ricerche

• Richiedono delle interfaccie specifiche ed un linguaggio di

interrogazione (e.g. SQL)

• Memorizzano comunque il dato in strutture file ma

associano la gestione

Lezione 8 - Sottoprogrammi



sottoprogrammi

Marco Anisetti





Sottoprogrammi e astrazione

• Il concetto di astrazione è un elemento fondamentale per

risolvere i problemi

• E' assodato che il cervello umano non riesce a

parallelizzare il pensiero in modo indefinito

• La soluzione di un problema passa quindi

obbligatoriamente da delle astrazioni che limitano il

numero di problemi che vengono gestiti

contemporaneamente dal nostro cervello (sottoproblemi).

• Questo approccio è alla base della progettazione Top Down

e dell'organizzazione procedurale dei programmi

• L'astrazione procedurale equivale al raggruppamento di

più problemi dettagliati in un unico macro-problema

• Un esempio analogo all'approccio modulare

Esempio: calcolo delle radici(1)

Calcolo delle soluzioni reali di ax2 + bx + c = 0Prima approssimazione della soluzione, approccio modulare

Esempio: calcolo delle radici(2)

Versione più dettagliano il modulo del calcolo delle radici

Sottoprogrammi

• Nella risoluzione dei problemi e nella stesura deiprogrammi si possono presentare i seguenti casi:

Ripetere identicamente più volte la stessa sequenza diistruzioniRipetere la stessa sequenza di istruzioni su variabili chepossono avere valori o identificatori diversi da quelli assuntila volta precedenteCopiare o inserire in un programma un altro programmagià realizzatoUtilizzare un programma di libreria

• Un termine generico per definire il raggruppamento

procedurale è quello di sottoprogramma

• A tale raggruppamento viene assegnato un nome univoco

per il programma chiamato

identificatore del sottoprogramma

• Alcuni termini più specifici derivano da come questo

sottoprogramma si relaziona con il programma principale

Sottoprogrammi: classificazione

• Macro: un insieme di istruzioni al quale viene assegnato

un nome. Il nome della macro viene rimpiazzato

dall'insieme delle istruzioni relative prima di passare il

sorgente al traduttore che lo codifica in un linguaggio

comprensibile alla macchina (sottoprogramma improprio)

• Procedura: un insieme di istruzioni alle quale viene dato

un nome e che definiscono un' unità di esecuzione a sé

stante. Una procedura comunica con il programma che

l'ha chiamata attraverso dei parametri passati tra ``()''

dopo il suo nome, generalmente una procedura non

restituisce un valore di output (terminologia ALGOL)

• Funzione: una procedura che restituisce uno o più valori

in output. Simile alle funzioni matematiche da cui prende

il nome

Struttura a livelli

• I sottoproblemi risolti da un sottoprogramma generico

possono a loro volta essere suddivisi in

sotto-sottoproblemi

• Si arriva ad una gerarchia a livelli dove vengono riassunte

le relazioni tra sottoprogrammi e dove la radice comune è

costituita dal programma principale detto Main

[Sottoprogramma]

Un problema di tipo procedurale caratterizzato da un

algoritmo A che opera su dati D per produrre risultati R si può

partizionare in n sottoproblemi procedurali a differenti livelli

ove l'i-esimo è caratterizzato da un algoritmo Ai che opera su

dati Di ⊂ (D0 + R0 + · · ·+ Ri−1) con D0 ∈ D e R0 insieme vuoto

Procedura e funzioni in pseudocodice(1)

• Consideriamo il seguente pseudocodice

[Sequenziale]

t ← r mod q;r ← q;q← t;

[Procedurale]

Procedure Pbegint ← r mod q;r ← q;q← t;end

• Da notare l'uso esplicito della definizione del blocco che

appartiene alla procedura tramite keyword begin end

(altri linguaggi usano le {})• I blocchi begin end possono essere usati anche in

associazione ad altri costrutti in dipendenza dal linguaggio

Procedura e funzioni in pseudocodice(2)

• La procedura è individuata da una intestazione (P) e da

un corpo (racchiuso tra begin end)

• L'intestazione contiene l'identificativo della procedura (P)

ed eventuali parametri

• E' evidente che P è una procedura, se fosse una funzione

andrebbe indicato cosa torna e ci dovrebbe essere una

istruzione nel corpo che indica il valore da ritornare

(possiamo chiamarla return(<cosa>)) oppure si

assegna il valore al nome della funzione• Altre cose fondamentali da indicare sono i tipi deiparametri passati e dell'eventuale output

Esempio: Function F(x:real):real begin f ←x*x+sqrt(x);endCi indica come si deve chiamare che prende in ingresso unreale e ritorna un realeNel suo corpo vediamo che viene usata una funzionamatematica predefinita dal linguaggio che è sqrt(< var >)

Passaggio di parametri

• Passaggio per valore: Viene passata una copia del valore

della variabile utilizzata al momento della chiamata.

• Passaggio per indirizzo o riferimento: Viene passato un

riferimento alla variabile del chiamante, che quindi non

viene duplicata nel sottoprogramma ma può essere usata

e modificata dal chiamato agendo sulla variabile del

chiamante.

• Output di una funzione: Si tratta di un valore che viene

ritornato esplicitamente dal sottoprogramma (che in

questo caso è in sostanza una funzione).

• La definizione formale di funzione prevederebbe il ritorno

di un solo parametro, tale regola è man mano scomparsa

nella programmazione odierna

• I parametri vengono definiti nel momento in cui la

procedura viene creata (parametri formali) e devono

essere inclusi nel momento in cui la procedura viene

chiamata (parametri attuali)

Importanza dei sottoprogrammi

• Fornisce uno strumento potente per scomporre il

problema in sottoproblemi più gestibili

• Non serve solo per abbreviare il lavoro di codifica ma in

modo essenziale per articolare, suddividere e strutturare

un programma in componenti fra loro coerenti

• La struttura è determinante per la comprensibilità delprogramma

L' abbiamo visto a livello di costruttiConcetto analogo se ci spostiamo a livello di programma

• Migliora la leggibilità e la verificabilità del codice

• L'estrazione di una parte di programma in un

sottoprogramma permette di mettere in risalto le variabili

da essa influenzate e di porre in risalto le condizioni da

soddisfare per l'ottenimento del risultato intermedio

• Mettono in evidenza i campi di influenza delle variabili

contenute

Concetto di scope

• Un qualsiasi oggetto (variabile, costante, procedura,

funzione) che è significativo soltanto in una determinata

parte di un programma è detto locale

• Al contrario se è sempre significativo è detto globale

• Le procedure e le funzioni costituiscono degli

ambiti di esecuzione separati dal resto del programma e

che dialogano con esso tramite l'interfaccia definita dalla

loro intestazione (o attraverso delle variabili globali)

• Le macro non sono un abito di esecuzione

• Per questo motivo non definiscono un ambito locale

• Gli oggetti dichiarati all'interno del corpo di una procedura

o funzione sono locali a quella

• Località o globalità è genericamente detta visibilità

• Si dice scope di una variabile il suo ambito di visibilità

• Anche blocchi begin end possono definire uno scope

Funzione: esempio(1)

• Esempio di due funzioni con passaggi di parametri

differenti

[Passaggio per valore]

procedure swap(x,y: integer)integer zbeginz=x;x=y;y=z;

enda=10;b=5;swap(a,b);

[Passaggio per indirizzo]

procedure swap(var x,y: integer)integer zbeginz=x;x=y;y=z;

enda=10;b=5;swap(a,b);

Funzione: esempio(2)

• Consideriamo al chiamata della swap di prima con i

parametri passati per riferimento

• Cosa succede se la chamata è swap(i,A[i])?

• Se i=2 e A[i] =99 allora il corpo che eseguirebbez=x;x=y;y=z; esegue:

z=2; i=99; A[2]=z;

Call and return(1)

• Essendo ambiti di esecuzione separati le procedure o

funzioni vengono effettivamente chiamate dal programma

che ne fa uso e questa operazione scatena una serie di

eventi

• Come cosa fondamentale un salto all'esecuzione di codice

della procedura/funzione, la sospensione dell'esecuzione

del chiamante e il relativa salto indietro quando termina

Call and return(2)

• Esiste una struttura di supporto per memorizzare

l'indirizzo di ritorno dopo la chiamata, i parametri passati

e utilizzati da procedure o funzioni

• Tale struttura è un segmento di memoria del processo

chiamata stack

• E' una struttura dati astratta che agisce come una pila

LIFO (Last In First Out)

• Per primo viene inserito l'indirizzo di ritorno (l'indirizzo

dell'istruzione successiva alla chiamata)

• In seguito i parametri

• Poi le eventuali dichiarazioni locali alla procedura o

funzione

Memoria del processo

• Con la gestione dei sottoprogrammi la struttura della

memoria si arricchisce di un segmento stack

Record di attivazione(1)

• La visibilità della procedura o funzione è determinata dallo

stack

• L'insieme di oggetti che vengono caricati nello stack ad

ogni chiamata si chiama record di attivazione

• Ogni esecuzione di sottoprogramma ha il suo record di

attivazione

• Anche il programma principale main ha un record di

attivazione nello stack


[Esempio in linguaggio C]

void Prima(int a){int b;

}void Seconda(float c){}int main(){int num=100;Prima(10);Seconda(num);

}

Risoluzione macro

Macro espansione a compile time

Controllo dei parametri attraverso un

metodo grafico(1)

• Serve per permettere agli studenti alle prime armi di

controllare i valori delle variabili passate e la loro validità

• Ad ogni variabile viene associato ad un rettangolo che

rappresenta l'area di memoria nella quale viene scritto il

valore della variabile. L'identificatore della variabile viene

scritto all'esterno.

• Bisogna tener presente i seguenti casi:

• Variabili ridichiarate: ad ogni redichiarazione si

costruisce un rettangolo dove l'identificatore è quello della

variabile ridichiarata con a pedice il nome del

sottoprogramma dove avviene la ridichiarazione. Il

rettangolo si cancella quando si esce dal sottoprogramma


metodo grafico(2)

• Parametro trasmesso per valore: all'atto della

chiamata si crea un nuovo rettangolo con identificatore

uguale al nome del parametro formale e valore uguale al

valore del parametro attuale corrispondente. Al rientro il

parametro viene cancellato

• Parametro passato per indirizzo o riferimento:

quando avviene la chiamata il rettangolo esiste già, serve

solo indicare esternamente l'identificatore del parametro

formale che corrisponde all'attuale già esistente. In

questo caso l'area di memoria risulta avere due nomi.

L'identificatore del parametro formale viene cancellato

all'uscita dal sottoprogramma


metodo grafico(3)

Lezione 9 - Chiamate a sottoprogrammi

con RAPTOR



sottoprogrammi

Marco Anisetti





RAPTOR: Statements(2)

• Procedure call Statement: Una procedura è un insieme di

istruzioni che servono per eseguire un compito al quale

insieme viene affidato un nome. Tale nome serve per

richiamare la procedura. La chiamata di una procedura

sospende l'esecuzione del programma per preoccuparsi

dell'esecuzione della procedura, che una volta terminata

restituisce il controllo al programma. Le procedure

possono avere associati dei parametri che vengono

passati come ingressi al codice che esegue la procedura

• Si tratta di chiamate a funzionalità di libreria interne a

RAPTOR. Alcune di queste funzioni permettono di aprire

finestre grafiche, disegnare linee ecc

• Output Statement: Scrive in output sulla finestra

MasterConsole quanto indicato nello statement

RAPTOR: commenti

• Come per ogni linguaggio di programmazione è possibile

inserire dei commenti per spiegare le scelte

implementative

• In Raptor per inserire un commento basta cliccare sul

tasto destro sopra un elemento del flow chart e scegliere

l'opzione comment

• Intestazione del programma: Commenti su chi ha

scritto il programma quando e una descrizione generale di

cosa fa (commento al simbolo start)

• Descrizione delle sezione: Commenti alle sezioni più

significative del programma, servono per far comprendere

la struttura del programma stesso

• Descrizione logica: Commenti a istruzioni

particolarmente significative e di non semplice lettura

RAPTOR: Strutture di controllo(1)

• Sono le tipiche strutture di controllo del flow chart, ovvero

selezione ed iterazione

• Selection Control: Serve per definire delle selezioni

basati su una decisione. La decisione avviene nel

momento in cui si valuta la condizione

• La valutazione della condizione equivale alla valutazione di

un predicato booleano e segue tutte le regole dell'algebra

di Bool. Essendo in sostanza analoga alla valutazione di

una espressione ha rilevanza l'ordine con il quale viene

valutata. Le espressioni matematiche vengono valutate

con le precedenze già descritte mentre per il resto:

1. Operatori (=! = / =<<=>>=) da sinistra a destra2. Operatore not da sinistra a destra3. Operatore and da sinistra a destra4. Operatore xor da sinistra a destra5. Operatore or da sinistra a destra

RAPTOR: Strutture di controllo(2)

• Loop control: Rappresenta ogni tipo di costrutto iterativo

tramite una selezione ed un ritorno del ciclo (ellisse con

loop). E' possibile definire sia cicli post-condizionati che

pre-condizionati

• Per costruire cicli pre o post condizionati serve aggiungere

prima o dopo la selezione gli statement richiesti.

• E' possibile aggiungere sia prima che dopo la condizione

ottenendo cicli misti (equivalente di goto)

• La selezione deve essere impostata in logica booleana in

modo da seguire i cammini predefiniti che non sono

modificabili

Procedure call in RAPTOR

• In RAPTOR la procedure call può essere utilizzata per

implementare macro procedure o funzioni

• Esistono numerose procedure di sistema per il disegno,

tra queste alcune sono delle procedure tipo (Open Graph

Window (X Size, Y Size)) altre delle macro tipo (Close

Graph Window), ad altre per l'interfaccia con l'utente

• Alcune procedure sono definite bloccanti, in quanto

includono delle istruzioni che attendono il verificarsi di un

determinato evento

• Esistono delle funzioni di interfaccia tipo (GetMouseX) che

ritornano dei valori al chiamante ( x ← GetMouseX)

RAPTOR: subcharts e procedure

• In RAPTOR il termine procedure comprende

sottoprogrammi che siano comparabili a procedure e

funzioni dato che il passaggio di parametri è concesso così

come il ritorno di valori

• Per il momento abbiamo visto la chiamata a delle

procedure di libreria presenti in RAPTOR

• In seguito proveremo a definirne di nostre partendo con la

definizione di subcharts

• I subcharts sono dei diagrammi di flusso che vengono

richiamati dal diagramma di flusso principale (chiamato

main) per essere eseguiti

• I subcharts equivalgono alle macro, non avendo parametri

di ingresso e non ritornando nulla

RAPTOR: subcharts(1)

• Per creare un subchart occorre cliccare con il tasto destro

del mouse sulla tab del flow chart main

• Tra le voci appare Add subchart

• Nel dialog box viene richiesto il nome del subcharts. Tale

nome deve essere ovviamente univoco all'interno del

programma

• I subcharts condividono lo stesso scope delle variabili del

flow chart main, ed è proprio per questo motivo che

equivalgono a delle macro

RAPTOR prevede diversi livelli di profilo per i programmatori che lo utilizzano. Se

si passa al livello intermedio, nello stesso menu apparirà anche l'opzione ``Add

procedure''

Subcharts: esempio

RAPTOR: subcharts(2)

• I subcharts sono molto utili per dividere il programma in

sottoprogrammi che possono essere richiamati più volte

• Come le macro hanno il vantaggio di evitare il duplicarsi di

codice

• Nell'esempio di prima il subcharts viene richiamato 4 volte

separatamente

• Lo stesso programma scritto senza subcharts sarebbe più

difficile da leggere debuggare e sviluppare

RAPTOR: procedure(1)

• Nell'esempio del Draw Bulls Eye si può notare che ogni

chiamata viene preceduta da degli assegnamenti per le

variabili x e y che vengono poi usati dal subchart

richiamato in seguito

• Questo è tipico dell'uso dei subchart e delle macro in

genere per generare comportamenti differenti a partire

della stessa base di codice

• L'equivalente si potrebbe ottenere passando x e y ad una

procedura che esegue la macro Draw Bulls Eye

• In Raptor è possibile definire delle procedure in maniera

molto simile ai subcharts segliendo l'opzione add

procedure nel menu di tasto destro sul tab main

• La procedura è molto più flessibile perchè è possibile

chiamarla con differenti valori iniziali ad ogni chiamata

senza dover settare le variabili prima della chiamata

RAPTOR: procedure(2)

• Questa flessibilità si ottiene attraverso il passaggio di

parametri

• I parametri sono delle variabili che prendono valore nel

momento della chiamata (parametri di ingresso) oppure

cambiano valore nel momento che la procedura termina

(parametri di uscita)

• Quando si definisce una procedura in Raptor si indicano se

i parametri sono da considerarsi di ingresso o di uscita o

sia di ingresso che di uscita

Passaggio di parametri in RAPTOR

• Parametri di ingresso (input): i valori vengono

inizializzati nel momento della chiamata e i valori dei

parametri attuali vengono passati ai formali (passaggio

per valore)

• Parametri di uscita (output): il loro valore viene

ricopiato nella relativa variabile del programma chiamante

(copy-out della call-by-value-result)

• Parametri di ingresso e uscita (input/output):

vengono trattati come parametri di input all'ingresso e

output all'uscita della procedura (simile al passaggio per

riferimento o al call-by-value-result)

• I parametri vengono definiti nel momento in cui si crea

una procedura ma possono anche essere modificati a

posteriori con il click del tasto destro sulla tab della

procedura

Procedure: esempio

RAPTOR: scope delle variabili

• La procedure di RAPTOR esattamente come tutte le

procedure in generale hanno un loro spazio di

dichiarazione delle variabili che vivono fino a quando la

procedura non termina

• Le variabili usate in una procedure di RAPTOR non sono

visibili al di fuori della procedura stessa

• In RAPTOR le variabili definite (utilizzate) in una

procedure o nel flow chart main hanno visibilità solo in

quella procedura o nel main a meno che non vengano

passate esplicitamente come parametri

• Non esistono variabili globali

Riassumento

• Variabili:

Esistono solo due tipi semplici, numero e stringaLe variabili non vengono dichiarate esplicitamente maimplicitamente quando vengono usate in un assegnamentoOgni variabile ha una sua visibilità che equivale al flowchart nella quale è usata (il subchart ha la visibilità del flowchart da cui è chiamato)

• Sottoprogrammi: macro (subchart), procedure efunzioni (procedure)

Le procedure possono ricevere parametriHanno una ambito di definizione delle variabili disgiunto dalflow chart chiamanteL'unico punto di contatto sono i parametri che vengonopassati o ritornatiI parametri possono essere definiti come di input di outputo di input/output

Lezione 10 - Ricorsività



sottoprogrammi

Marco Anisetti





Ricorsività

• Un oggetto ricorsivo è definito totalmente o parzialmente

in base a se stesso

• Il concetto di ricorsione nella programmazione èstrettamente collegato a quello di induzione o ricorrenzain matematica. Molti concetti matematici sono definiti inmodo induttivo o tramite ricorrenze. L'esempio canonicodi un concetto matematico definito in modo induttivo èquello di numero naturale

Base: 0 è un numero naturale;Passo: se n è un numero naturale, allora anche ilsuccessore di n, S(n) (cioè n + 1), è un numero naturale

Ricorsività: esempi

• Fattoriale: n! è definito come n ∗ (n− 1)!

• M.C.D.(A,B): se A > B M.C.D.(B,A), se B = 0 A, se A > B

M.C.D.(B,A MOD B)

• Numero di Fibonacci di un numero naturale n è: F (n) sen = 0 0, se n = 1 1, se n > 1 F (n− 1) + F (n− 2)

Ricorsività: divide et impera

• La ricorsione sta alla base di una tecnica molto potente di

programmazione, chiamata divide et impera

• Essa consiste nello scomporre (divide) un problema in

sotto problemi dello stesso tipo, più semplici da risolvere

(impera). Questa tecnica è la chiave per la progettazione

di molti algoritmi importanti, ed è un ingrediente

fondamentale della programmazione dinamica

• Virtualmente tutti i linguaggi di programmazione in uso al

giorno d'oggi permettono la specificazione diretta di

funzioni e procedure ricorsive, utilizzando lo stack per

tener traccia delle loro chiamate annidate

• Si può dimostrare che ogni sottoprogramma ricorsivo può

essere trasformato in un sottoprogramma iterativo

mediante l'utilizzo esplicito di uno stack

Nucleo della ricorsività

• Il potere della ricorsività sta nella possibilità di definire un

insieme anche infinito di oggetti con un numero finito di

comandi

• Si usano algoritmi ricorsivi quando il problema da

risolvere, la funzione da valutare o la struttura dati da

usare sono intrinsecamente ricorsivi

• Un linguaggio permette la ricorsione se permette ad un

sottoprogramma di richiamare se stesso

• Un sottoprogramma ricorsivo S può essere espresso come

una combinazione C di istruzioni Ii non contenenti

riferimenti a S e una chiamata ad S S = C[Ii,S]

• Se il sottoprogramma S contiene un riferimento esplicito a

se stesso allora si parla di ricorsività diretta

• Se il sottoprogramma S contiene un riferimento ad una

procedura Q che contiene il riferimento a S allora si parla

di ricorsività indiretta

Ricorsività: problemi(1)

• Un sottoprogramma ricorsivo crea dei problemi legati alla

terminazione e alla instanziazione

• Il problema della terminazione è comune a tutti gli

algoritmi, nel caso della ricorsione il caso terminale

quando raggiunto fa concludere la procedura o funzione

senza ulteriori chiamate ricorsive

• Nel caso del fattoriale il caso terminale è 0! = 1

• La chiamata ricorsiva viene generalmente fatta precedere

dalla condizione di terminazione B

1. B è vera finchè il caso terminale non è stato raggiuntoallora: S if B then C[Ii,S] oppure S C[Ii, if B thenS]

2. B è falsa finchè il caso terminale non è stato raggiuntoallora: S if B then nothing else C[Ii,S] oppure S = C[Ii, if Bthen nothing else S]

Ricorsività: problemi(2)

• Quando si chiama un sottoprogramma vengono allocate le

aree di memoria per variabili costanti locali e parametri

passati (record di attivazione)

• Questa area di memoria viene deallocata nel momento

del'uscita dal sottoprogramma

• Nel caso della ricorsione dato che il sottoprogramma si

richiama ricorsivamente prima di uscire allora ne esistono

più istanze analoghe in memoria (solitamente stessi

identificatori ma valori potenzialmente diversi) un record

di attivazione per chiamata

• Questo conflitto si risolve considerando come attiva solo

l'ultima instanza allocata (scope)

• Esiste anche un problema di spazio in memoria per

garantire la sopravvivenza della ricorsione

Record di attivazione: ricorsione(1)

[Esempio in linguaggio C]

void Prima(int a){int b;Prima(a-1); }

void Seconda(float c){}int main(){int num=100;Prima(10);Seconda(num);

}

Record di attivazione: ricorsione(2)

[Nota] Cosa succede se un parametro è passato per indirizzo?

Iterazione e ricorsione

Calcolo del fattoriale con tecnica iterativa e ricorsiva

[Fattoriale iterativo]

int fattoriale (int n) {int i, f;f = 1;

for (i = 1; i <= n; i++) {f = f * i;

} return f;}

[Ricorsiva]

int fattoriale (int n) {if (n == 0) return 1;else return (n * fattoriale(n - 1));

}

Ricorsione multipla

• Si ha ricorsione multipla quando un’attivazione di funzione

causa più di una attivazione ricorsiva della stessa funzione

• n-esimo numero di Fibonacci

[Fibonacci ricorsivo]

int F(n){

if (n==0) return 0;

if (n==1) return 1;

if (n>1) return F(n-2) + F(n-1);

}

Torre di Hanoi e ricorsione(1)

• Problema visto nelle precedenti lezioni, caratterizzato

dalla sua intrattabilità

• Soluzione naturale ricorsiva: consideriamo i paletti dasinistra verso destra come P1, P2 e P3 e i dischi da 1 il piùpiccolo a n il più grande

Sposta i primi n− 1 dischi da P1 a P2 usando P3 comeappoggioSposta il disco n da P1 a P3

Sposta n− 1 dischi da P2 a P3

Torre di Hanoi e ricorsione(2)

• Considero il numero di dischi n il numero del palo sorgente

s il numero del palo destinazione d e il palo di appoggio a

• Partendo da un certo numero di dischi e scegliendo

sorgente e destinazione possiamo scrivere la seguente

funzione ricorsiva

[Hanoi ricorsivo]

void hanoi(n, s, d, a) {

if (n == 1)

muoviDisco(s, d);

else {

hanoi(n-1, s, a, d);

muoviDisco(s, d);

hanoi(n-1, a, d, s);

}

}

Iterazione o ricorsione

• Come facciamo ad accorgerci se una ricorsione è corretta

o ben definita?

• Se ad ogni volta che applico la ricorsione sono

significativamente più vicino al caso base

• Si dice che a definizione non è circolare ma converge

• Solitamente le soluzioni ricorsive sono più eleganti, sono

più vicine alla definizione del problema

• Non è detto che siano più efficienti

• L'utilizzo di algoritmi ricorsivi costituisce l'opzione più

naturale ed intuitiva per operare su strutture definite in

modo ricorsivo (esempio alberi)

Lezione 11 - Strutture dati dinamiche



sottoprogrammi

Marco Anisetti





Strutture dati vs programmazione

strutturata

• Assegnamento ↔ Tipo di dato elementare

• Sequenza ↔ Record (una serie di asseganmenti)

• Selezione ↔ Record variante

• Iterazione ↔ Array

• Ricorsione ↔ Strutture dati dinamiche

Strutture dati dinamiche e tipo

puntatore(1)

• Le strutture dati viste fino ad ora hanno diverse

caratteristiche: sono statiche e sequenziali

• Statiche perchè la loro dimensione è definita a priori e non

può variare

• Sequenziale perchè la successione logica ricalca quella

fisica in memoria

• Esistono strutture dati che diversamente da array estrutture sono dinamiche e concatenate

Non è necessario definire le dimensioni a priori la strutturapuò crescere all'interno del programmaNon è pensabile allocare a priori lo spazio in fase didichiarazione, quindi si usa un tipo di memorizzazione dettoconcatenato

Strutture dati dinamiche e tipo

puntatore(2)

• Alla struttura logica concatenata non fa riscontro una

struttura fisica, ovvero gli elementi consecutivi dal punto

di vista logico possono non esserlo dal punto di vista fisico

• L'elemento J-esimo può essere in qualsiasi area di

memoria, l'importante è che l'elemento (J-1) esimo abbia

informazione di dove si trova l'elemento J-esimo

• Questa informazione è chiamata anche puntatore per via

del fatto che si tratta di un indirizzo di memoria che viene

usato per puntare alla cella di memoria dove si trova il

dato

• Da cui il tipo di dato puntatore

• il tipo puntatore è definito anche dal

tipo di oggetto che punta

• Una variabile di tipo puntatore conterrà al suo interno un

indirizzo

Lista semplice(1)

• Una struttura di questo tipo non permette un

accesso diretto all'elemento ma serve scandire la struttura

per arrivare seguendo i puntatori all'elemento da

selezionare

• Le strutture dinamiche possono introdurre delle perdite di

efficienza per il reperimento di un dato ma hanno il

grande vantaggio per inserimenti e eliminazioni

• Essendo ogni elemento di una struttura dinamica

composto da due campi, l'informazione da memorizzare

ed il puntatore al prossimo elemento, si può affermare

che gli elementi sono di tipo Record, ad esempio due

campi uno denominato Inf e uno Pun

Lista semplice(2)

• Il campo informazione (Inf ) può contenere di tutto, il

campo puntatore Pun deve contenere un indirizzo di

memoria dove reperire il successivo elemento

• La lista è una delle strutture dinamiche basilari

Lista semplice(3)

• L'indirizzo del primo elemento si trova in un puntatore P0esterno alla struttura della lista (Puntatore di testa),

l'ultimo elemento della lista ha un puntatore che non

punta a nulla (0 o null)

• Ogni elemento della lista è individuato dal puntatore che

lo punta

• Esiste un formalismo per dire che ci stiamo riferendo al

dato a cui il puntatore si riferisce al posto dell'indirizzo che

il puntatore contiene

• Consideriamo un puntatore pun (a tutti gli effetti una

variabile) contenente un indirizzo se mi riferisco a pun sto

riferendomi all'indirizzo contenuto che sarà un numero

plausibilmente. Se voglio indicare che mi sto riferendo al

dato (cella di memoria) puntato da pun allora posso usare

il formalismo simile al pascal pun̂ o similmente al c ∗pun

Lista semplice(4)

• Considerando l'esempio di prima posso accedere aglielementi della lista in questo modo:

P0̂.Inf: campo informazione del primo elementoP0̂.Pun: campo puntatore del primo elemento, ovverol'indirizzo del secondoP0̂.Pun̂.Inf: campo informazione del secondo elementoP0̂.Pun̂.Pun: campo puntatore del secondo elemento,ovvero l'indirizzo del terzo

• Le operazioni base che si possono fare su una lista sono

ricerca inserzione e cancellazione

Lista semplice(5)

• Ricerca: Si tratta di una operazione di scansione

completa della lista in ricerca del valore, la lista va

potenzialmente scandita completamente

• Inserzione: Si tratta di una operazione semplice dato

che l'elemento viene inserito logicamente in un punto

della lista ma non fisicamente. Se devo inserire Z tra X e

Y quello che devo fare è aggiornare i puntatori per far si

che Z sia successore di X e abbia come successore Y. Si

possono considerare dei casi particolari, inserzione in

testa, inserzione in coda, inserzione in mezzo

• Cancellazione: Si tratta di una operazione che prevede

lo sganciamento di un elemento dalla lista e la

de-allocazione (o meno a seconda del linguaggio) della

memoria usata per esso

Strutture dati dinamiche

• Esistono molte strutture dati dinamiche che si possono

generare a partire dalle liste quali le liste bidirezionali,

alberi ecc.

• Tra le strutture dati dinamiche interessanti c'è la pila o

stack

• La pila è una struttura caratterizzata da una gestione LIFO

(Last In First Out) L'ultimo elemento inserito è il primo a

essere estratto

Strutture dati dinamiche: stack

• Le operazioni su uno stack sono: Push e Pop

Push: inserisco un nuovo elemento nella pilaPop: estraggo l'elemento affiorante dalla pila

• Considerando lo stack come struttura svincolata dal suoimpiego nell'informatica, essa potrebbe essere realizzatacome una lista semplice o un array

Come lista: si considerano solo inserimenti e cancellazioniin testa. Può essere pesante in termini di occupazione datala presenza del puntatoreCome vettore: dato che si inserisce ed estrae da una solaparte risulta indicato anche l'utilizzo di array. Si effettuatenendo in memoria l'indice del TOP

Strutture dati dinamiche: coda

• E' una struttura dati caratterizzata da una gestione di tipo

FIFO (First In First Out)

• In una coda è possibile un inserimento in fondo alla coda

o una estrazione dalla testa della coda

• Le code vengono gestite generalmente attraverso liste

semplici (inserzioni in fondo, cancellazioni in testa)

• E' altamente sconsigliabile utilizzare un vettore per

implementare una struttura tipo coda perché dovendo

agire su testa e fine della coda diventa di difficile gestione

Strutture dati dinamiche:

Implementazione

• Puntatore: il linguaggio deve prevedere la possibilità di

indicare un riferimento ad una determinata zona di

memoria dove risiede un certo dato

• Allocazione di memoria: il linguaggio deve permettere

di allocare dinamicamente la memoria per nuove strutture

dati• Le funzionalità di base sono generalmente fornite al livellodel sistema operativo che gestisce la memoria associata alprogramma in esecuzione (processo)

Allocazione della memoria: la dimensione dipende daltipo (new, malloc ecc.), viene ritornato generalmente unpuntatore o riferimento alla memoria allocataDe-allocazione della memoria: la memoria vieneliberata e ritorna disponibile per altre allocazioni (free), puòessere liberata esplicitamente o implicitamente a secondadel linguaggio di programmazione

Strutture dati dinamiche: la memoria

• Verranno trattate in dettaglio nel corso di Sistemi

Operativi

• Stack: zona di memoria statiche che serve a gestire le

chiamate a funzione , il passaggio di parametri e

l'allocazione di variabili locali alla funzione

• Heap: lotto dinamico di memoria che viene allocato al

processo ed evolve con esso.

• Esistono tecniche di programmazione evoluta ai limiti

della legalità (legalità in ambito di programmazione) che

dipendono dal compilatore e che permettono di allocare

dinamicamente spazio nello stack, violando la

caratteristica staticità (possibilità di predeterminarne la

dimensione) dello stack stesso.

Strutture dati dinamiche evolute

• Lista multipla: ogni elemento è composto da 3 parti,

informazione, puntatore al prossimo, puntatore ad una

sottolista

• Si parla di lista padre e sottoliste, può avere più livelli

formando una gerarchia di elementi

• Le operazioni fondamentali sono: ricerca, inserzione e

cancellazione

• Inserzione e cancellazione possono essere effettuate a

livello di lista padre o a livello di sottolista

Strutture dati astratte

• Albero: Struttura dati astratta gerarchica molto usata, gli

elementi che la compongono si chiamano nodi mentre le

linee che connettono tali elementi archi.

• Un albero è un insieme di uno o più nodi tale che: i) un

nodo è designato come radice, ii) i restanti nodi se

esistono, possono essere suddivisi in insiemi disgiunti

ognuno dei quali è a sua volta un albero detto sotto

albero. I nodi che non hanno successori vengono detti

foglie dell'albero.

• Ogni nodo ha uno ed un solo padre. Si possono valutare

diversi livelli nella struttura ad albero.

• Grafi: Generalizzazione degli alberi aventi meno

restrizioni. Il grafo è un insieme di nodi connessi tra di

loro, si considerano orientati o meno a seconda che esista

un verso sugli archi

• Come memorizzare un albero o un grafo? si può usare

una lista multipla

Memoria del processo

• Con la gestione dinamica della memoria aggiungiamo il

segmento heap alla memoria del processo

Lezione 12 - Programmazione strutturata

con RAPTOR



sottoprogrammi

Marco Anisetti





Lezione1-Algoritmi+strutturedati= programmihomes.di.unimi.it/anisetti/Teaching/15-16/Unit7.pdf ·...

Documents

Transcript of Lezione1-Algoritmi+strutturedati= programmihomes.di.unimi.it/anisetti/Teaching/15-16/Unit7.pdf ·...