domande sulla ricorsione, i suoi limiti e le alternative, come potrei fare per risolvere il problema di indipendenza dei sottoproblemi.
- la ricorsione è una tecnica che permette di richiamare una funzione all’interno della stessa funzione dichiarata.
- I limiti riguardano l’occupazione dello spazio nello stack occupato dalla chiamate ricorsive e dalla complessità algoritmica, che in generale senza effettuare pruning o altri criteri che permettano di ridurre le chiamate ricorsive che sicuramente non portano a un risultato che soddisfi la richiesta, è più costo a livello temporale. Un altro limite riguarda i sottoproblemi gia affrontati, se ho affrontato un sottoproblema di tipologia X in chiamata 1, se si ripresenta tale sottoproblema sempre della tipologia alla chiamata 6 lo dovrò risolvere nuovamente come se fosse un nuovo problema
- come alternative ci sono:
-
ricorrere a criteri di pruning per ridurre al minimo il numero di chiamate ricorsive
-
programmazione dinamica e memoritation
- la memoritation permette di risolvere il problema di indipendenza dei sottoproblemi salvandomi in una struttura dati opportuna - che mi permetta l’accesso diretto al sottoproblema-esimo - il risultato dei vari sottoproblemi
-
paradigma greedy
-
Per ridurre la complessità spaziale, un'alternativa è l'utilizzo della ricorsione tail-call, che consente di evitare l'accumulo di chiamate sullo stack.
- Una funzione ricorsiva è tail-recursive se la chiamata ricorsiva è l’ultima operazione da eseguire, eccezion fatta per return
-
Come implementare una coda a priorità quando il dato immagazzinato è troppo grande?
- (non heap ma tabella di simboli con accesso diretto)
- Si crea il vettore pq->qp per memorizzare a quale indice nello heap della coda a priorità si trova un certo dato.
- La tabella di simboli memorizza i dati e gestisce la corrispondenza dato/indice e indice/dato. Il costo di queste operazioni dipende dall’implementazione della tabella di simboli. Come tabella si può sceglie o vettore/lista oppure tabella di hash.
A partire da un grafo G e da un insieme di vertici T che formano un sottografo completo, come verificare se i vertici di T formano una clique (sottografo completo massimale )
- Per verificare se un insieme di vertici T in un grafo G forma una clique (ovvero un sottografo completo massimale), è necessario verificare che ogni coppia di vertici in T sia connessa da un arco.
- Per fare ciò, si può utilizzare un algoritmo basato sulla verifica di tutte le coppie di vertici in T, ovvero per ogni coppia (u,v) di vertici in T, si controlla se esiste un arco diretto che va da u a v e se esiste un arco diretto che va da v a u.
- Se entrambi gli archi esistono, allora la coppia (u,v) è connessa e si può passare alla coppia successiva.
- Se invece uno o entrambi gli archi non esistono, allora la coppia non è connessa e quindi l'insieme di vertici T non forma una clique.
- L'algoritmo può essere implementato con una complessità di tempo di O(|T|^2), dove |T| è la dimensione dell'insieme di vertici T. Tuttavia, è possibile ottimizzare l'algoritmo utilizzando alcune tecniche di pruning, ad esempio evitando di controllare le coppie di vertici che sono già state verificate o che sono sicuramente non connesse.
cosa è la np completa !!!!!!!!!!
- Problemi P, NP, NP-C e la relazione tra P e NP
- Classi P, NP, NP-C, NP-H
- esempio (hamilton)
- Classi di algoritmi e macchina non deterministica di Turing.
Prim e Kruskal, mst tramite calcolo combinatorio, complessità operazioni sui grafi (visite)!!!!
Colorare un grafo, Problema della colorazione di una mappa (grafo planare) come adattamento del problema di partizione di un grafo
- Un grafo si dice planare se è possibile disegnarlo in modo tale che non ci siano intersezioni tra archi. Quale è il numero minimo di colori per colorare un grafo tale che ogni vertice sia adiacente a vertici di colori diversi dal suo? E’ dimostrato che per i grafi planari il numero minimo di colori è al più 4. Le mappe geografiche sono grafi planari.
Numero di vertici e a quale algoritmo del calcolo combinatorio è possibile associare il numero di questi vertici (grafo completamente connesso)
- Il numero di vertici per un grafo orientato è N(n-1)/2 , altrimenti N(N-1)
- combinazioni
union find e quick find, Weighted Quick Union , Differenza con la quick union, qual è il vantaggio, Complessità!!!!!
-
Union-find è una struttura dati che viene utilizzata per gestire insiemi disgiunti. L'obiettivo principale è quello di unire (union) due insiemi e determinare se due elementi appartengono allo stesso insieme (find). Ci sono diversi algoritmi per implementare questa struttura dati, tra cui Quick Find, Quick Union e Weighted Quick Union.
Quick Find è un algoritmo che utilizza un array per rappresentare gli insiemi e tiene traccia di quale elemento appartiene a quale insieme. L'operazione union richiede di scorrere l'intero array per trovare tutti gli elementi dell'insieme e cambiarne il valore. L'operazione find è invece semplice, poiché richiede solo di verificare se due elementi hanno lo stesso valore nell'array.
Quick Union, invece, utilizza una struttura a albero per rappresentare gli insiemi. Ogni elemento è rappresentato da un nodo e ogni insieme è rappresentato da un albero. L'operazione union richiede di trovare le radici degli alberi degli elementi da unire e farne figli di un nuovo nodo radice. L'operazione find richiede di seguire il percorso dall'elemento fino alla radice per verificare se due elementi appartengono allo stesso insieme.
Weighted Quick Union è un'ottimizzazione di Quick Union che tiene traccia della dimensione di ogni albero e unisce sempre il sottoalbero più piccolo all'albero radice del sottoalbero più grande. Questo aiuta a mantenere un'altezza dell'albero più piccola e quindi un'operazione find più veloce.
Il vantaggio di utilizzare Weighted Quick Union invece di Quick Find o Quick Union è che l'operazione union richiede meno tempo e l'albero risultante è più bilanciato, il che significa che l'operazione find richiede meno tempo. La complessità temporale di Weighted Quick Union è O(N + M log N), dove N è il numero di elementi e M è il numero di operazioni union e find.
In generale, Weighted Quick Union è l'algoritmo union-find più efficiente e viene utilizzato in molte applicazioni in cui è necessario gestire insiemi disgiunti.
Modelli di calcolo combinatorio per il problema delle 8 regine
Componente fortemente connessa, componente connessa, cammino di Hamilton
- Una componente fortemente connessa è un sottografo orientato, quindi un sottoinsieme di archi e un sottoinsieme di vertici che presenta la proprietà di mutua raggiungibilità per tutti i vertici che la compongono. Una componente connessa invece è un sottografo non orientato, quindi un sottoinsieme di archi non orientati e un sottoinsieme di vertici che presenta la proprietà di mutua raggiungibilità per tutti i vertici che la compongono. Un cammino di Hamilton è un cammino che collega un vertice di partenza s a un vertice di destinazione d e che attraversa tutti i vertici che compongono il grafo una e una sola volta.
Horner
Cammino di Hamilton, ciclo di Hamilton, come risolvere il problema del commesso viaggiatore
- Differenza principale tra il cammino di Hamilton e il problema del commesso viaggiatore(sostanzialmente il cammino di Hamilton si calcola su un grafo non pesato, mentre il problema del commesso viaggiatore si applica ad un grafo pesato)
differenza tra Dijstrak e visita in ampiezza
- quando hanno lo stesso effetto
- quando gli archi non hanno peso o lo stesso peso
- Una visita in ampiezza permette, in un grafo orientato e non pesato, di determinare tutti i vertici raggiungibili da un determinato vertice ‘s’ detto ‘sorgente’, calcolando la distanza minima da tra ‘s’ e tutti i i vertici da esso raggiungibili. Dijkstra permette invece, in caso di grafi pesati, di trovare un cammino minimo tra un vertice sorgente e tutti gli altri vertici. Un cammino minimo è quel percorso che collega due vertici e che minimizza la somma dei costi associati all’attraversamento di ciascun arco.