Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
Algoritmi - Programmazione Dinamica
Forum - Algoritmi - Programmazione Dinamica

Avatar
tuttodiMC (Normal User)
Expert


Messaggi: 326
Iscritto: 29/10/2012

Segnala al moderatore
Postato alle 16:39
Mercoledì, 04/03/2015
Salve a tutti. Pochi giorni fa ho preso parte ad una delle lezioni preparatorie alla selezione regionale delle olimpiadi di informatica, organizzate dalla mia scuola in collaborazione col dipartimento di Informatica dell' università de L'Aquila.

Il professore quel giorno ha spiegato la programmazione dinamica per l'ottimizzazione di algoritmi ricorsivi. Non avendo capito immediatamente l'argomento trattato ho fatto qualche ricerca in internet dove veniva detto che questo tipo di programmazione si basa più sull'approccio bottom-up che sul top-down. Ho provato ad utilizzare questa tecnica di programmazione riuscendo a creare solo una versione quasi istantantea della funzione ricorsiva della successione di fibonacci Fn = F(n-1)+F(n-1).

Vorrei però capire meglio il funzionamento di questa tecnica perchè mi sarebbe molto utile per risolvere alcuni problemi di projecteuler.net. Qualcuno riesce a darmi una spiegazione semplice?


Assembly is the way
PM Quote
Avatar
XBarboX (Member)
Guru


Messaggi: 945
Iscritto: 31/12/2008

Segnala al moderatore
Postato alle 18:42
Mercoledì, 04/03/2015
Ciao!
Ti avverto fin da subito che di programmazione dinamica non me ne intendo gran che.
Tuttavia il concetto che stalla alle base è che se risolvo un sotto-problema conviene salvarlo in modo tale da averlo già risolto per il futuro.

Qui puoi trovare una pagina che avevo scritto tempo fa: http://xbarbox.pierotofy.it/zaino.html
Il problema dello zaino è un ottimo esempio un po' più avanzato di Fibonacci per capire bene la programmazione dinamica.

A proposito di project euler c'è un bellissimo esempio sulla congettura di collatz https://projecteuler.net/problem=14

Questo è un esempio valido per la programmazione dinamica in quanto un sotto problema può tornare utile a un problema di "livello superiore".
Infatti, se definisco collatz(n) come la lunghezza della sequenza di collatz a partire da n, posso definire il problema ricorsivamente in questo modo:

se n pari => collatz(n) = 1 + collatz(n/2)
se n dispari => collatz(n) = 1 + collatz(3*n + 1)
con caso base collatz(1) = 1
    
Per esempio collatz(16) è istantaneo da calcolare se conosco collatz(8) in quanto collatz(16) = 1 + collatz(8).
Quindi un metodo rapido consiste nel salvarti in un vettore tutti i risultati di collatz(i) in posizione i del vettore.

Spero di essere stato chiaro e di aiuto! In bocca al lupo per le olimpiadi! :k:

Ultima modifica effettuata da XBarboX il 04/03/2015 alle 18:43


The old lie: Dulce et decorum est pro patria mori
PM Quote
Avatar
dnha (Member)
Pro


Messaggi: 137
Iscritto: 24/07/2014

Segnala al moderatore
Postato alle 20:41
Mercoledì, 04/03/2015
Testo quotato

Postato originariamente da tuttodiMC:
Pochi giorni fa ho preso parte ad una delle lezioni preparatorie alla selezione regionale delle olimpiadi di informatica [...] Il professore quel giorno ha spiegato la programmazione dinamica per l'ottimizzazione di algoritmi ricorsivi.



E siamo in due :)

Quanto odio gli esercizi del tipo:
Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2.  
  3. int max(int a, int b) {
  4.         if(a > b) return a;
  5.         return b;
  6. }
  7. int f(int a, int b) {
  8.         if (a == b) return b;
  9.         if (a < 0) return -b;
  10.         return max(f(a-1, 2*b), f(a-1, 2*b+1));
  11. }
  12. void main() {
  13.         printf("%d", f(8, 0));
  14. }



:rotfl: :k:

Ultima modifica effettuata da dnha il 04/03/2015 alle 20:41


“La principale differenza tra una cosa che potrebbe rompersi e una cosa che non può in alcun modo rompersi è che quando una cosa che non può in alcun modo rompere si rompe, di solito risulta impossibile da riparare.” [Douglas Adams, Praticamente innocuo]
PM Quote
Avatar
tuttodiMC (Normal User)
Expert


Messaggi: 326
Iscritto: 29/10/2012

Segnala al moderatore
Postato alle 13:30
Giovedì, 05/03/2015
Per quanto riguarda il problema 14 di projecteuler l'ho già debitamente risolto senza utilizzare la programmazione dinamica. Invece devo utilizzarla per risolvere il problema 15,  https://projecteuler.net/problem=15, dato che ho ottenuto ricorsivamente la soluzione al problema verificando l'esempio riportato, tuttavia, la durata dell'esecuzione per la risoluzione del problema vero e proprio è veramente lunga.


Assembly is the way
PM Quote