1. (a) Cos’è l’algoritmo “dividi et impera”? Spiegare l'approccio generale degli algoritmi divide et impera. (6 punti)
(b) Utilizzare l'approccio divide et impera per progettare un algoritmo per trovare l'elemento minimo in un array di n elementi. Analizza la complessità temporale del tuo algoritmo. (10 punti)
2. (a) Spiegare il concetto di tecniche di hashing e di risoluzione delle collisioni. (6 punti)
(b) Consideriamo una tabella hash di dimensione m e un insieme di n elementi da sottoporre ad hashing. Supponiamo che gli elementi siano distribuiti uniformemente tra gli m slot. Qual è la probabilità di una collisione quando n =m/2? Analizza il numero medio di confronti richiesti per inserire correttamente tutti gli elementi nella tabella hash utilizzando il sondaggio lineare. (10 punti)
3. (a) Descrivere il concetto di programmazione dinamica e spiegare come differisce dall'approccio divide et impera. (6 punti)
(b) Utilizzare la programmazione dinamica per risolvere il problema del taglio delle barre, dove una barra di lunghezza n può essere tagliata in barre più piccole e ciascuna barra di lunghezza i ha un prezzo p[i]. L'obiettivo è trovare il ricavo massimo che si può ottenere tagliando la canna in pezzi più piccoli. Analizza la complessità temporale e spaziale del tuo algoritmo. (10 punti)
4. (a) Spiegare il concetto di NP-completezza e il suo significato nell'analisi degli algoritmi. (6 punti)
(b) Dimostrare che il seguente problema è NP-completo:dato un insieme di n elementi con i rispettivi pesi e valori, determinare se esiste un sottoinsieme di questi elementi il cui peso totale è inferiore o uguale a un dato limite e il cui totale il valore è massimizzato. (10 punti)
5. (a) Spiegare il concetto di analisi ammortizzata degli algoritmi. Perché viene utilizzato e quali sono i suoi vantaggi? (6 punti)
(b) Eseguire un'analisi ammortizzata della struttura dei dati dello stack, dove le operazioni push e pop sono le uniche operazioni consentite. Determinare la complessità temporale media di ciascuna operazione. (10 punti)
6. (a) Descrivere l'algoritmo di Kruskal per trovare l'albero di copertura minimo di un grafo pesato non orientato. (6 punti)
(b) Applica l'algoritmo di Kruskal al grafo seguente e trova l'albero di copertura minimo:
```
(1)---2---(3)
/ |
/ |
5/4
-----------
(4)---6---(5)
```
Calcolare il peso totale dell'albero di copertura minimo. (10 punti)
7. (a) Spiegare il concetto di una sorta topologica di grafo aciclico diretto (DAG). (6 punti)
(b) Eseguire un ordinamento topologico sul seguente DAG:
```
(1) -> (2) -> (3)
\/
-> (4)
```
Fornire l'ordine dei vertici nell'ordinamento topologico. (10 punti)
8. (a) Descrivere il concetto di alberi binari di ricerca (BST). Spiegare come vengono utilizzati i BST per operazioni di ricerca e inserimento efficienti. (6 punti)
(b) Inserisci i seguenti elementi in un BST inizialmente vuoto:20, 10, 30, 5, 15, 25, 35. Disegna il BST risultante e analizza la complessità temporale della ricerca di un elemento in questo BST. (10 punti)
Ricordarsi di dimostrare una chiara comprensione dei concetti, fornire spiegazioni corrette e analizzare le complessità temporali e spaziali degli algoritmi quando richiesto.
Programmazione © www.354353.com