Algoritmi e Strutture Dati

Ricorsione

Lunedì 21 febbraio 2022 13:00

Definizione ricorsiva

Implementazione 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’alto 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.

Righello e frattale

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à.

È 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.

Ricerca binaria

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 l’elemento 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 O(n), cioè un tempo lineare, perché, nel caso peggiore, 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 = n - 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 + 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 FIFO, 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 metodo, 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 nel 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 richiederanno un tempo logaritmico in funzione del numero di posizioni dell’albero.

Inserimento nello heap

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 proprietà 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 ed è limitato da.

Algoritmi e Strutture Dati Pagina 9

Rimozione del minimo nello heap

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 l’algoritmo termina.
2. Altrimenti, distinguiamo due casi, partendo dalla posizione iniziale p che coincide con la radice di T.
   1. Se p non ha figlio destro, chiamiamo c il figlio sinistro di p.
   2. 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.

Memorizzazione con array

Gli elementi dell’albero sono memorizzati in una lista A basata su array, in modo tale che l’elemento in posizione p venga memorizzato nella cella di A avente indice uguale al numero fornito dalla funzione di numerazione per livelli associato a p, cioè f(p), definito 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

Heap sort

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 elementi 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 albero 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 aggiungendo a ciascuna coppia una nuova voce, che viene posta inizialmente nella radice e può essere, poi, scambiata con la voce memorizzata 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 procedura 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 verso 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 O(n), nell'ipotesi che due chiavi possano essere confrontate tra loro in un tempo O(1).

Algoritmi e Strutture Dati Pagina 12

Merge sort

Lunedì 7 marzo 2022 13:00

Algoritmo teorico ricorsivo basato sull