Newsgroup: it.comp.programmare
Titolo: Programmazione Dinamica

Ciao a tutti.
Qualcuno di voi per caso ha qualche esercizio/problema svolto con 
l'approccio di Programmazione Dinamica?
In rete non si trova molto... anzi, a parte qualche caso notevole, non 
c'è granché.
Mi son fatto le (vecchie) tracce d'esame del mio prof. ma vorrei 
qualcosa dove poter trovare riscontri sullo svolgimento...
------------
Alexandros

 l'approccio di Programmazione Dinamica?
Guardati il Cormen. C'è un bel po' di roba.
-- 
I know of a particular, very large software producer that explicitly 
assumes that design takes 20% of developers' time, and debugging takes 
80%.
Niklaus Wirth

 
Ehm... forse non hai capito quello che ho scritto.
Sul Cormen, libro che posseggo, ci sono casi notevoli: prodotto 
matriciale, sottosequenza comune più lunga
E poi il tutto non supera i 4-5 paragrafi...


trovi una serie di articoli online, tutorial, dispense di corsi *e* 
libri. Tipo [RB57]. E anche link su algoritmi che utilizzano tali 
tecniche (che sono eccellenti esercizi 'complessi').
Su Amazon pure trovi uno sfracello di libri a riguardo. Io però andrei 
in biblioteca e vedrei su cosa riesci a mettere le mani alla svelta. 
Per quanto [RB57] per esempio mi ispiri molto (le edizioni Dover mi 
garbano alquanto *e* costa poco, per cui potrebbe anche valere la pena 
di comprarlo e tenerselo in casa come reference), potrebbe metterci 
troppo tempo a giungere. Invece quello che trovi nella biblioteca della 
tua università è già li pronto.
Se poi vuoi un elenco di libri su algoritmi che trovo ben fatti, posso 
dartela. Tuttavia non avendoli qui sotto mano, non so dirti facilmente 
quali contengono capitoli su quello che ti interessa. Probabilmente ne 
hanno, ma dovresti controllare su un indice, tipicamente in biblioteca.
----------------------------------------------------------------------
[CLRS01] Cormen, Leiserson, Rivest, Stein, 2001, Introduction to 
Algorithms, Second Edition, The Mit Press, ISBN 0-262-03293-7
[DK398] Donald Knuth, 1998, The Art of Computer Programming v. 3, 
Addison Wesley, ISBN 0-201-89685-0.
[DK4?] Donald Knuth, ?, The Art of Computer Programming v. 4, da 
pubblicare
[RB57] Richard Bellman, 1957, Dynamic Programming, Princeton University 
Press. Dover paperback edition (2003), ISBN 0486428095.
-- 
We will perhaps eventually be writing only small modules which are 
identified by name as they are used to build larger ones, so that 
devices like indentation, rather than delimiters, might become feasible 
for expressing local structure in the source language. (Donald E. 
Knuth)

 Press. Dover paperback edition (2003), ISBN 0486428095.
Noto con piacere che ti dedichi ad ottime letture. Bravo.
------------
Alexandros

 abbozzo di esso per supportare con un riscontro i miei ragionamenti.
Eh, ma tutti quegli esempi *sono* problemi pratici. Qualcuno ha avuto 
tali problemi e sono stati risolti con la programmazione dinamica. Sui 
libri trovi quelli più istruttivi, per dire. Più chiari. Con un 
contesto più facilmente esponibile.
Un altra cosa che potresti fare è prendere alcuni algoritmi tipicamente 
risolti con tecniche greedy e vedere come vengono con tecniche di 
programmazione dinamica.
Una classe di problemi che tipicamente puoi risolvere con 
programmazione dinamica sono grosso modo quelli di scheduling. 
Tipicamente i casi non pesati li riesci a risolvere bene con tecniche 
greedy. Aggiungi i pesi (ovvero non tutti i jobs possibilmente 
sovrapposti hanno uguale 'valore' e vuoi massimizzare non il numero ma 
il valore complessivo).
Che so... sei il gestore di un centro di calcolo. Hai una coda in cui 
puoi mettere dentro i jobs. E diversi centri ricerca che fanno 
richiesta. Tutte le richieste sono note in anticipo. Non tutti i centri 
ricerca pagano lo stesso per unità di tempo spesa in base ad accordi 
esterni. Tu vuoi massimizzare il ricavato. Gli scienziati sono un po' 
rompi palle e ti dicono a che ora vogliono iniziare ad avere 
l'esclusiva della coda e a che ora finiscono. Tu devi dire si o no a 
ciascuna richiesta.
La soluzione non la ho (ma è banale), il problema è tipico e se vuoi 
poi ti do una traccia. Ma non credo che ce ne sia bisogno. Possiamo 
anche riguardare la soluzione qui.
-- 
After more than 30 years of programming we ought to know that the 
design of complex software is inherently difficult.
Niklaus Wirth

Alexandros ha scritto:

Esercizi svolti sono difficili da trovare, io per il mio esame di 
algoritmi II ho studiato su Algorithm Design di Kleinberg, Tardos.
Ti ho linkato il capitolo sulla programmazione dinamica, ci sono un paio 
di esercizi svolti a fine capito, più decine non svolti.
http://www.aw-bc.com/info/kleinberg/chapter.html

 
http://www.aw-bc.com/info/kleinberg/chapter.html
Ti ringrazio.
Ho dato un breve sguardo al capitolo e mi sembra fatto bene.
Ora mi "spulcio" i due problemi svolti... ;)
------------
Alexandros