Algoritmi e Strutture Dati

Ricorsione

lunedì 21 febbraio 2022 13:00 definizione ricorsiva

lmplementazione ricorsiva della funzione fattoriale Si ottiene l’iterazione mediante ripetute invocazioni ricorsive

del metodo. Il processo è finito perché, ogni volta che il

metodo viene invocato, il suo parametro è inferiore di un’unità

rispetto all’invocazione precedente e, quando si raggiunge il

caso base, non vengono più effettuate invocazioni ricorsive.

Ogni riquadro presente nel diagramma corrisponde a

un’invocazione ricorsiva e ogni nuova invocazione

ricorsiva del metodo viene rappresentata da una

freccia rivolta verso il basso, verso una nuova

invocazione. Quando il metodo termina la propria

esecuzione e restituisce un valore, l’evento viene

rappresentato nel diagramma mediante un freccia che

torna verso l’altro e il valore restituito è segnalato

accanto alla freccia

In Java,ogni volta che viene invocato un metodo (ricorsivo oppure no), viene creata una struttura che ne contiene i

dati di attivazione (activation record o activation frame) e memorizza informazioni relative a quella particolare

invocazione di quel metodo.

Quando l’esecuzione del metodo porta a un’invocazione annidata di un altro metodo (o dello stesso metodo),

l’esecuzione del metodo attualmente attivo viene sospesa e nei suoi dati di attivazione viene aggiunta

un’indicazione del punto del codice in cui il controllo del flusso d’esecuzione dovrà riprendere dopo che

l’invocazione annidata sarà terminata. Quindi, vengono creati i nuovi dati di attivazione, per la nuova invocazione

annidata.

Per ogni pollice, dobbiamo posizionare un piccolo segmento con un’etichetta numerica.

Chiamiamo lunghezza maggiore (major tick length) la lunghezza dei segmenti che indicano un numero intero di

pollici, mentre i segmenti più corti che si trovano tra due segmenti lunghi avranno una lunghezza minore (minor

tick length) e saranno posizionati ogni mezzo pollice, ogni quarto di pollice, e così via. Ogni volta che la

dimensione dell’intervallo misurato si dimezza, la lunghezza del segmento corrispondente diminuisce di un’unità

E' un esempio di frattale, cioè di una forma geometrica che ha una struttura auto-ricorsiva a vari livelli di

ingrandimento. Ignorando i segmenti che contengono 0 e 1, vediamo come si possa disegnare la sequenza di

segmenti che si trova tra i due citati.

In generale, una sezione di righello con segmento centrale di lunghezza L ^ 1 è composta da:

• Una sezione con un segmento centrale di lunghezza L - 1

• Un segmento di lunghezza L

• Una sezione con un segmento centrale di lunghezza L - 1

Algoritmi e Strutture Dati Pagina 1

Ogni invocazione di drawinterval dà luogo a due ulteriori invocazioni ricorsive.

La ricerca binaria o ricerca per bisezione (binary search) è utilizzata per individuare in modo efficiente un

valore desiderato in una sequenza ordinata di n elementi memorizzata in un array.

Quando la sequenza non è ordinata (unsorted), per cercare un valore al suo interno normalmente si usa

un ciclo che esamina un elemento dopo l’altro, fin quando non viene trovato rdemento cercato oppure

si esaurisce l’insieme dei dati. Questo algoritmo prende il nome di ricerca lineare {linear search) o ricerca

sequenziale (sequential search) e viene eseguito in un tempo 0(w) (cioè un tempo lineare), perché, nel

caso pesiere, ispeziona ciascun singolo elemento.

L’algoritmo gestisce due parametri, low e high, tali che tutti gli elementi candidati presenti nell’array

abbiano indici compresi tra low e high, compresi. Inizialmente low = 0 e high = « - 1, cioè tutti gli

elementi dell’array sono candidati, perché non abbiamo ancora acquisito informazioni. Poi,

confrontiamo il valore cercato (target, cioè “obiettivo” della ricerca) con il candidato mediano, cioè

quell'elemento il cui indice vale: • Se si arriva alla situazione in cui low > high, la ricerca non ha avuto

successo, perché l'intervallo dei candidati, [low, high], è vuoto.

• Se il valore cercato è uguale al candidato mediano, la ricerca ha

avuto successo e può terminare con esito positivo.

• Se il valore cercato è minore del candidato mediano, possiamo

invocare ricorsivamente la ricerca sulla prima metà della sequenza,

cioè sull’intervallo di indici che va da low a mid - 1.

• Se il valore cercato è maggiore del candidato mediano, possiamo

invocare ricorsivamente la ricerca sulla seconda metà della

sequenza, cioè sull’intervallo di indici che va da mid 4- 1 a high.

Algoritmi e Strutture Dati Pagina 2

Algoritmi e Strutture Dati Pagina 3

giovedì 24 febbraio 2022 11:00 Algoritmi e Strutture Dati Pagina 4 • Quando il numero di valori da sommare è zero

o uno, il problema è banale.

• Con due o più valori, possiamo calcolare

ricorsivamente la somma della prima metà dei

valori, poi la somma della seconda metà, per

sommare, infine, questi due valori insieme.

Per risolvere uno di questi rompicapi, occorre assegnare una diversa cifra numerica (cioè

0, 1,..., 9) a ciascuna lettera presente nell’equazione, in modo da renderla vera.

Durante l’esecuzione dell’algoritmo, usiamo l’insieme U per tenere traccia degli

elementi non contenuti nella sequenza che si sta generando, in modo che un

elemento e non sia ancora stato utilizzato se e solo se e appartiene a U.

Algoritmi e Strutture Dati Pagina 5

Code prioritarie

lunedì 28 febbraio 2022 13:00

La coda è tipo di dato astratto, un contenitore di oggetti che vengono inseriti e rimossi secondo la politica di gestione FIF O (first-in,first-out), cioè il primo entrato sarà il primo a uscire.

Mentre la coda prioritaria o coda con priorità (priority queue) è un contenitore di elementi, ciascuno dei quali ha un livello di priorità: si può inserire qualsiasi elemento, ma è

consentita la rimozione del solo elemento avente la priorità migliore. Quando un elemento viene aggiunto a una coda prioritaria, è l’utente della coda stessa a decidere quale sia la

priorità di quell’elemento, fornendo la chiave (key) da associare'all’elemento stesso all’interno della coda. L’elemento avente la chiave minima sarà, per convenzione, il prossimo a

essere rimosso dalla coda Serve per accoppiare una chiave k e un

valore v all'interno di un unico oggetto.

Deve essere possibile effettuare confronti tra chiavi e i risultati dei confronti non devono essere contraddittori. Perché la regola di confronto, indicata con il simbolo <=,

sia coerente, deve definire una relazione d'ordine totale, cioè deve soddisfare le seguenti proprietà per qualsiasi chiave

Se un insieme (finito) di elementi è dotato di un ordinamento totale definito al proprio interno, allora il

concetto di chiave minima , è ben definito: è quella chiave che rende valida la proprietà

per ogni altra chiave k appartenente all’insieme.

Un comparatore è un oggetto esterno alla classe di cui sono esemplari le chiavi che confronta e mette a disposizione un metod o, avente la firma compare(a, b), che restituisce

un numero intero con significato Algoritmi e Strutture Dati Pagina 6

L’ordinamento è una delle applicazioni delle code prioritarie: ci viene data una sequenza di elementi che possono essere confrontati tra loro secondo una relazione

d’ordine totale e vogliamo sistemarla in modo che gli elementi vi figurino in ordine crescente (o almeno non decrescente, nel caso in cui ci siano elementi duplicati).

L’algoritmo per ordinare una sequenza S usando una coda prioritaria P è costituito dalle due fasi seguenti:

1. Nella prima fase inseriamo gli elementi di S come chiavi in una coda prioritaria P inizialmente vuota, eseguendo n operazioni insert, una per ogni elemento.

2. Nella seconda fase estraiamo gli elementi da P in ordine non decrescente, eseguendo n operazioni removeMin, per memorizzarli di nuovo in S nell’ordine in cui

vengono estratti. Algoritmi e Strutture Dati Pagina 7

1. Nella Fase 1 dello schema pqSort inseriamo tutti gli elementi in una coda prioritaria P

2. nella Fase 2 estraiamo ripetutamente l’elemento minimo da P usando il metodo removeMin.

Algoritmi e Strutture Dati Pagina 8

Heap

giovedì 3 marzo 2022 11:00

Un heap è un albero binario T che memorizza voci nelle proprie posizioni e che soddisfa due ulteriori proprietà:

1. Proprietà relazionale( o proprietà di ordinamento) definita in termini delle modalità di memorizzazione delle chiavi in T

In uno heap T, per ogni posizione p diversa dalla radice, la chiave memorizzata in p è non minore della chiave memorizzata ne l genitore di p

Le chiavi che si trovano lungo un percorso che parte dalla radice e arriva a una qualsiasi foglia di T sono in ordine non decrescente

La chiave minima è sempre memorizzata nella radice di T: questo rende estremamente semplice la localizzazione di una delle voci aventi la

chiave minima nel momento in cui viene invocato il metodo min o il metodo removeMin

2. Proprietà strutturale che riguarda la forma stessa di T

3. Proprietà di completezza di un albero binario: Uno heap T di altezza h è un albero binario completo se i livelli 0,1,2,..., h - 1 di T hanno il

massimo numero possibile di nodi (cioè il livello i ha nodi, per 0 < i < /j - 1) e i nodi del livello h si trovano nelle posizioni più a sinistra di quel

livello

Un heap T contenente n entità ha altezza h = log n

Poiché T è completo, sappiamo che il numero di nodi dei livelli di T che vanno da 0 a /h - 1 è esattamente uguale a

Inoltre, sappiamo che il numero di nodi posti al livello h è almeno 1 e al massimo

1. Prendendo il logaritmo di entrambi i membri della disuguaglianza

2. Prendendo il logaritmo dell’altra disuguaglianza, , e sistemando opportunamente gli addendi, otteniamo

Dato che h è un numero intero, queste due disuguaglianze implicano che

Se eseguiamo operazioni di aggiornamento di uno heap in un tempo proporzionale alla sua altezza, allora tali operazioni richi ederanno un

tempo logaritmico in funzione del numero di posizioni dell’albero

Si memorizza la coppia (k, v) sotto forma di voce in un nuovo nodo dell’albero. Per preservare la proprietà di completezza dell' albero

binario, tale nuovo nodo può essere collocato soltanto nella posizione p subito alla destra del nodo più a destra del livello più basso

dell’albero, oppure nella posizione più a sinistra di un nuovo livello, nel caso in cui l’ultimo livello sia pieno (o lo heap sia vuoto).

L’albero T è ancora completo, ma può violare la proprietà di ordinamento di uno heap, quindi, a meno che la posizione p non sia

la radice di T (cioè che la coda prioritaria fosse vuota prima dell’inserimento), confrontiamo la chiave che si trova nella posizione p

con quella che si trova nel genitore di p, che indichiamo con q.

1. Se , la proprietà di ordinamento dello heap è soddisfatta e l’algoritmo termina.

2. Se, invece, , dobbiamo ripristinare la proprietà di ordinamento, obiettivo che si ottiene scambiando tra loro le voci

che si trovano nelle posizioni p e q. Si ripete la procedura, risalendo in T finché non c’è più alcuna violazione della propr ietà

di ordinamento.

Nel caso peggiore, questa procedura sposta ripetutamente la nuova voce, fino a quando giunge nella radice dello heap T.

Il numero di scambi eseguiti all’interno del metodo insert è uguale all’altezza di T è limitato da

Algoritmi e Strutture Dati Pagina 9

Sappiamo che nella radice r di T è sempre presente una voce avente la chiave minima.

Per garantire che la forma dello heap, dopo l’operazione di rimozione, rispetti la proprietà di completezza di un albero binario,

dobbiamo cancellare la foglia che si trova nell'ultima posizione p di T, definita come la posizione più a destra del livello più profondo

dell’albero. Per fare in modo che la voce presente nell’ultima posizione p rimanga all'interno della coda prioritaria, la copiamo nella

radice r (al posto della voce avente la chiave minima, che deve essere eliminata). A questo punto, il nodo che si trova nell’ultima

posizione può essere rimosso dall’albero.

Anche se ora T è completo, è probabile che violi la proprietà di ordinamento dello heap.

1. Se T ha un solo nodo (la radice) allora la proprietà di ordinamento è banalmente rispettata e T algoritmo termina.

2. Altrimenti, distinguiamo due casi, partendo dalla posizione iniziale p che coincide con la radice di T.

a. Se p non ha figlio destro, chiamiamo c il figlio sinistro di p.

b. Altrimenti (p ha entrambi i figli), chiamiamo c il figlio di p avente chiave minore tra i due.

Se , la proprietà di ordinamento dello heap è soddisfatta e l’algoritmo termina.

Se dobbiamo ripristinare la proprietà di ordinamento dello heap si possono scambiare i nodi memorizzati

in p e in c. È importante osservare che, quando p ha due figli, scegliamo il figlio avente chiave minore tra i due: in

questo modo, non soltanto la chiave di c è minore della chiave di p, ma è anche non maggiore della chiave contenuta

nel fratello di c. Questo garantisce che la proprietà di ordinamento dello heap venga localmente ripristinata quando

la chiave di c viene portata in alto, perché è minore di quella che era in p (e che ora scende) ed è non maggiore di

quella che si trova nella posizione del fratello di c prima della risalita.

Si continua con gli scambi scendendo lungo l’albero, finché non si arriva al punto in cui non ci sono più violazioni

della proprietà di ordinamento.

Nel caso peggiore, un’entità si sposta verso il basso fin quando è possibile il numero di scambi eseguiti all’interno del metodo

removeMin è uguale all’altezza dello heap T

Gli elementi dell’albero sono memorizzati in una lista A basata su array, in modo tale che l’elemento in posizione p venga me morizzato nella

cella di A avente indice uguale al numero fornito dalla funzione di numerazione per livelli associato a p, cioè f(p), definit o in questo modo:

• Se p è la radice, allora f(p) = 0.

• Se p è il figlio sinistro della posizione q, allora f(p) = 2f(q) + 1.

• Se p è il figlio destro della posizione q, allora f(p) = 2f(q) + 2.

Per un albero completo di dimensione n, gli elementi hanno indici consecutivi appartenenti all’intervallo [0, n -1] e l’ultima posizione

dell’albero ha sempre indice n-1 Algoritmi e Strutture Dati Pagina 10

1. Durante la Fase 1, la i-esima operazione insert richiede un tempo O(log i), perché dopo l’esecuzione dell’operazione lo heap contiene i nodi.

Questa fase richiede, quindi, un tempo complessivo O(n log n)

2. Durante la seconda fase del metodo pqSort, la i-esima operazione removeMin viene eseguita in un tempo O(log(n - j + 1)), perché nel

momento in cui inizia l’operazione lo heap contiene n - j + 1 nodi. Sommando per tutti i valori di j, questa fase richiede nuovamente un tempo

O(n log n).

L’intero algoritmo di ordinamento che usa una coda prioritaria realizzata mediante heap viene eseguito in un tempo O(n log n) .

L'algoritmo heap sort ordina una sequenza S di n elementi (occupa spazio O(n)) in un tempo O(n log n), nell'ipotesi che due e lementi di S possano

essere confrontati in un tempo O(1).

Il tempo d’esecuzione O(n log n) di heap sort è significativamente migliore del tempo d’esecuzione degli algoritmi di ordinamento per

selezione e per inserimento.

Si ipotizza che il numero di chiavi, n, sia un numero intero tale che n = , cioè assumiamo che lo heap sia un a lbero binario completo con tutti i

livelli pieni, in modo che la sua altezza sia h = log(n+1) -1. Immaginandola in modo non ricorsivo, la costruzione di uno heap in modalità bottom -up

consiste delle seguenti h + 1 = log(n + 1) fasi:

1. Nella prima fase costruiamo (n+1)/2 heap elementari, ciascuno dei quali memorizza una sola voce.

2. Nella seconda fase componiamo (n + 1)/4 heap, ciascuno dei quali memorizza tre voci, unendo coppie di heap elementari e ag giungendo a

ciascuna coppia una nuova voce, che viene posta inizialmente nella radice e può essere, poi, scambiata con la voce memorizzat a in uno dei suoi

figli, per ripristinare la proprietà di ordinamento dello heap.

3. Nella terza fase, componiamo (n+ 1)/8 heap, ciascuno dei quali memorizza 7 voci, unendo coppie di heap aventi 3 voci ciascuno (costruiti

nella fase precedente) e aggiungendo a ciascuna coppia una nuova voce, che viene posta inizialmente nella radice, ma può darsi che debba

scendere verso il basso per ripristinare la proprietà di ordinamento, come determinato dalla procedura di down -heap

i. Nella generica, i-esima fase, con , componiamo heap, ciascuno dei quali memorizza voci, unendo coppie di heap

aventi voci ciascuno (costruiti nella fase precedente) e aggiungendo a ciascuna coppia una nuova voce che viene posta inizialmente nella

radice, ma può darsi che debba scendere verso il basso per ripristinare la proprietà di ordinamento, come determinato dalla p rocedura di down-

heap.

h +1. Nell’ultima fase, componiamo lo heap conclusivo, che memorizza le n voci, unendo due heap aventi (n -1)/2 voci ciascuno (costruiti nella

fase precedente) e aggiungendo una nuova voce, che viene posta inizialmente nella radice, ma può darsi che debba scendere ver so il basso per

ripristinare la proprietà di ordinamento, come determinato dalla procedura di down-heap

Algoritmi e Strutture Dati Pagina 11

La costruzione bottom-up di uno heap avente n entità richiede un tempo 0(n), nell'ipotesi che due chiavi possano essere

confrontate tra loro in un tempo 0(1).

Algoritmi e Strutture Dati Pagina 12

Merge Sort

lunedì 7 marzo 2022 13:00

Algoritmo teorico ricorsivo basato sull