Programmazione dinamica

Question 1

Quali sono le differenze rispetto alla ricorsione?

Answer 1

La programmazione dinamica è destinati a problemi di ottimizzazione che hanno una struttura ottima, segue un approccio bottom-up, prima di risolvere un problema controlla se è già stato fatto.
C’è anche la memoization che è top-down.

Question 2

Quali sono i passi per arrivare a una soluzione ottima?

Answer 2

Verifica di applicabilità + soluzione ricorsiva per il valore + ricostruzione bottom-up iterativa della soluzione

Question 3

Quando si ha una struttura ottima?

Answer 3

Quando la struttura può essere divisa in sottostrutture anche esse ottime nel senso che sono ottime le soluzioni ai sottoproblemi

Question 4

Come si calcola in generale la complessità?

Answer 4

Theta(num di sottoproblemi * costo di ricombinazione)

Question 5

Come funziona la memoization?

Answer 5

Attraverso il look up controlla se la soluzione esiste già e per questo deve memorizzare le sol ai sottoproblemi

Question 6

unsigned long fib (int n, unsigned link *knownF);

Question 7

Che caratteristiche ha il P. Greedy?

Answer 7

Non sempre trova una soluzione ottima ma è meno complesso.

Question 8

Come funziona il P. Greedy?

Answer 8

A ogni passo sceglie una soluzione localmente ottima che non rivaluta più. La scelta viene fatta in base all’appetibilità

Question 9

Codici Huffamn: lunghezza

Answer 9

• fissa: n°bit = parte intera di log_2(card(S)) dove card(S) è il numero di tutti i bit che bisogna codificare
• variabile: più difficile, meno memoria, frequenze diverse

Question 10

Codici di Huffman: vincolo

Answer 10

nessun codice è prefisso di un altro codice