[informatici]Programmazione dinamica Rompicapo

[Rulez]

Ho un problema di programmazione dinamica di cui non riesco a venirne a capo!

=================================================
PROBLEMA: ci sono n oggetti da ordinare usando le relazioni "<" e "=". Per esempio con "a, b, c", i possibili ordinamenti sono:
a=b=c , a<b=c , a=b<c,
a<b<c, a<c<b, a=c<b,
b<a=c, b<a<c, b<c<a,
b=c<a, c<a=b, c<a<b,
c<b<a

Determinare un algoritmo che calcoli, in funzione di n, il numero di possibili ordinamenti diversi. L'algoritmo deve lavorare in tempo O(n^2) e in spazio O(n).
=================================================

Situazione .. allora il prof. ci ha consigliato di intraprendere la strada della programmazione dinamica.. che ricordo essere costituita dai 3 passi:
1)Caratterizzazione della struttura di una soluzione ottina
2)Definizione RICORSIVA del valore della soluzione
3)Calcolo del VALORE della soluzione secondo uno schema botton-up
E considerare che l'algoritmo deve restituire solamente il numero di combinazioni .. e non stamparle!!

Il problema è proprio che non riusciamo ne a capire come può essere "strutturata" una soluzione ottima.. e soprattutto a dare una definizione di valore Ricorsivo (es. non riesco a definire un valore come TOT+min{altri valori collegati}) ..

Il prof aveva accennato a provare a partire da 2 variabili ed aggiungere la terza per vedere come cambiava...


Con 2 variabili abbiamo le combinazioni: a=b, a<b, b<a .. sono 3!!

>aggiungiamo ad "a=b" la variabile c.. otteniamo a=b=c, a=b<c, c<a=b... sono 3 di questo sottoproblema..

>aggiungiamo ad "a<b" la variabile c e otteniamo a<b=c, c=a<b, a<b<c, c<a<b... sono 4!!

>aggiungiamo ad "b<a" la variabile c e otteniamo b<a=c, c=b<a, c<b<a, b<a<c .. e sono ancora 4!!

TOTALE: 3+4+4=11!! mancano all'appello a<c<b e b<c<a!! Quelle con il c in mezzo!! :doh:

Allora qui passa per la mente che "ovviamente" il numero di combinazioni che si generano a partire da una formula di dimensione minore "dipende dal numero di uguali" che ha! DOH!! Oltretutto non so nemmeno quante sono le combinazioni con 4 variabili perchè sono troppe da provare!!


Però non ne vengo a capo!!
In effetti non è tanto semplice.. però magari qualche cervellone mi trova la soluzione!! :D

[FuckAuthority]

che palle di cosa :asd:
mi viene male solo a pensarci, io non ti aiuto di certo :rotfl:
ma in che linguaggio devi farlo?

[Rulez]

Guarda.. devi trovare l'algoritmo.. puoi scriverlo in pseudocodice come in fortran è uguale :asd: .. anzi puoi anche fare a meno di scrivere l'algoritmo .. basta che mi spieghi come trovare la soluzione :asd: ..ah che non sia esaustiva .. ho il vincolo della complessità O(n^2) :asd:

[FuckAuthority]

fortran :rotfl:
no sorry son appena arrivato a casa dopo 8 ore di java ne ho i coglioni pieni ora vado a suonare :asd:

[Radical]

ma è un obbrobrio :asd:

[Rulez]

Vabbè aspetto diablo, poi lascio perdere :asd:

[Milton]

se per n=4 sono 57 ti ho trovato la funzione ricorsiva :asd:

[Rulez]

dimmela allora :asd:

[Milton]

oh eccomi, ero a cena poi mi son scordato :asd:

cmq no, prima di andare a cena ho visto che per n=4 è diverso da 54, almeno mi sembra, ho giusto buttato giu al volo l'albero e mi pareva maggiore.

Però ti lascio un paio di idee: se vedi l'albero, per ogni n, il numero dei rami è legato al numero delle uguaglianze, o meglio per ogni n hai nel sotto albero di sinistra ( quello generato dalla prima uguaglianza ) l'intero sviluppo dei rami per l'albero a livello n-1, mentre gli altri due sotto alberi ( quelli generati dalle due > < ) hanno uno sviluppo dei rami che è tra loro speculare e naturalmente sono quelli che crescono piu velocemente.
Io non c'ho provato però credo che gia da qua si potrebbe tirar fuori piu di qualcosa.

Poi all'inizio avevo visto che cmq tutti i termini di pure disuguaglianza ( espressioni senza = ) crescono come il fattoriale di n ( n! ), quindi sarebbe da trovare ricorsivamente quello che è il resto, cioè le espressioni con uguaglianze e sommarle, anche qua non ho provato, o meglio avevo buttato giu al volo ma era sbagliata, però mi sembra percorribile ( ed anche duale allo sviluppo dell'albero )

Altrimenti si potrebbe analizzare come stringa ( alfabeti, grammatiche, ecc. ) però questa mi è venuta ora e sono troppo stanco anche per ragionarci sopra, quindi la lascio cosi :asd:

[Diablo81]

Vabbè aspetto diablo, poi lascio perdere :asd:

Guarda rulez gli ho dato una letta, ma non ho capito una cosa: devi stampare il risultato (a=b=c bla bla) o solo calcolare il numero di combinazioni tra i simboli?

Detto questo non è detto che io sappia fare una cosa del genere, anzi a dirti la verità in questi "giochini" del cazzo sono sempre stato una sega :asd: . A parte gli scherzi, rispondimi che vedo se riesco a buttarti giù un'ipotesi di piano di esecuzione.

[Rulez]

oh eccomi, ero a cena poi mi son scordato :asd:

cmq no, prima di andare a cena ho visto che per n=4 è diverso da 54, almeno mi sembra, ho giusto buttato giu al volo l'albero e mi pareva maggiore.

Però ti lascio un paio di idee: se vedi l'albero, per ogni n, il numero dei rami è legato al numero delle uguaglianze, o meglio per ogni n hai nel sotto albero di sinistra ( quello generato dalla prima uguaglianza ) l'intero sviluppo dei rami per l'albero a livello n-1, mentre gli altri due sotto alberi ( quelli generati dalle due > < ) hanno uno sviluppo dei rami che è tra loro speculare e naturalmente sono quelli che crescono piu velocemente.
Io non c'ho provato però credo che gia da qua si potrebbe tirar fuori piu di qualcosa.

Poi all'inizio avevo visto che cmq tutti i termini di pure disuguaglianza ( espressioni senza = ) crescono come il fattoriale di n ( n! ), quindi sarebbe da trovare ricorsivamente quello che è il resto, cioè le espressioni con uguaglianze e sommarle, anche qua non ho provato, o meglio avevo buttato giu al volo ma era sbagliata, però mi sembra percorribile ( ed anche duale allo sviluppo dell'albero )

Altrimenti si potrebbe analizzare come stringa ( alfabeti, grammatiche, ecc. ) però questa mi è venuta ora e sono troppo stanco anche per ragionarci sopra, quindi la lascio cosi :asd:

Sono tutte idee che mi erano già venute "circa" ma non mi hanno portato alla soluzione..


Guarda rulez gli ho dato una letta, ma non ho capito una cosa: devi stampare il risultato (a=b=c bla bla) o solo calcolare il numero di combinazioni tra i simboli?

Detto questo non è detto che io sappia fare una cosa del genere, anzi a dirti la verità in questi "giochini" del cazzo sono sempre stato una sega :asd: . A parte gli scherzi, rispondimi che vedo se riesco a buttarti giù un'ipotesi di piano di esecuzione.

Solo il numero! E' un fatto fondamentale che non ti chiede di stamparle!!

[Diablo81]

Allora occhio e croce ho trovato due metodi, uno con complessità n^2 e l'altro n log n. Il primo è puramente matematico: ti calcoli le combinazioni su n e poi le combinazioni tra le combinazioni su n e sugli n-1 simboli (di = e <).

L'altro metodo è più "euristico" e parla di grafi, ma ora non te lo posso descrivere perché è un pò più lungo e dovrei farti un paio di disegni per fartelo capire, se hai pazienza stasera lo posto.

[Rulez]

E le combinazioni sarebbero?

[Diablo81]

Posso darti un'ultima risposta rulez poi devo andare e riprendo stasera. Dai un'occhiata qui:

http://it.wikipedia.org/wiki/Combinazione

In maniera particolare al paragrafo "ordine lessicografico" (che è una parte dell'algoritmo che ti serve) e successivamente al paragrafo "multi insiemi" che è il secondo pezzo che ti serve.
Se ti risulta difficile interpretare questo metodo (io stesso non ricordavo come si calcolano le combinazioni, intendo la formuletta per la serie e sono dovuto andarmelo a rivedere su wikipedia), come ti ho detto stasera ti faccio vedere una soluzione che è più complessa nell'implementazione, ma più semplice dal punto di vista comprensivo (e costa anche di meno).
Ora scappo a dopo.

[FuckAuthority]

cmq rulez che brutte cose che fai
sei proprio gobbo :asd:

[Milton]

Allora occhio e croce ho trovato due metodi, uno con complessità n^2 e l'altro n log n. Il primo è puramente matematico: ti calcoli le combinazioni su n e poi le combinazioni tra le combinazioni su n e sugli n-1 simboli (di = e <).

L'altro metodo è più "euristico" e parla di grafi, ma ora non te lo posso descrivere perché è un pò più lungo e dovrei farti un paio di disegni per fartelo capire, se hai pazienza stasera lo posto.

secondo me il primo non funziona, perchè la non puoi usare combinazioni e simboli, otterresti informazioni ridondanti

cioè facendo l'esempio per n=3 otterresti:

a b c , a c b,

b a c , b c a,

c a b , c b a

e per i simboli

< = , = <, < <, = =


combinando ogni combinazione di oggetti con una di simboli ottieni piu volte le stesse informazioni, basta pensare al fatto che applicheresti la coppia ( = = ) ad ogni combinazione, quindi avresti 6 uguaglianze che dicono la stessa cosa

questo se ho ben capito cosa volevi fare tu :asd:

[Milton]

Sono tutte idee che mi erano già venute "circa" ma non mi hanno portato alla soluzione..


secondo me dall'albero puoi estrarre la funzione ricorsiva, però non ci ho provato, ora sinceramente ho gia troppe cose da studiare per i miei di corsi :asd:

però se te lo disegni anche per solo i primi 4 livelli vedi che c'è simmetria parziale sia tra due livelli consecutivi che tra due sotto alberi "vicini"

[Diablo81]

si milton, hai ragione, al secondo passo non puoi usare le combinazioni, ma le permutazioni, altrimenti hai una ripetizione di simboli, non ci avevo pensato. In ogni modo il metodo rimane: al primo step usi le combinazioni ed al secondo le permutazioni delle prime combinazioni che hai creato (garantendo così l'unicità dei simboli).

Detto questo, il secondo metodo che proporrò (stasera, perché ora sono appena rientrato e sto andando in piscina) è, come ho detto, basato su grafi. In linea teorica, il tutto può essere riportato su alberi, ma hai la necessità (per come l'ho vista io) di riportare le relazioni (nei grafi indicate dagli archi) in qualche maniera sugli alberi.

Scappo e dopo ti spiego rulez, facendoti, se ci riesco qualche schizzo.

Ps. per la cronaca per poter calcolare il numero finale che serve a rulez, nella seconda soluzione che ho tirato giù devi usare una ricerca in profondità ricorsiva.

PPs. sempre per la cronaca sono sicuro che esistono metodi più semplici dei due che ho postato, ma ora non mi vengono in mente :asd:

[Diablo81]

Provo a spiegare il secondo metodo.

L'idea è quella di generare una sorta di n automi a stati finiti per poter scandire le varie combinazioni dei simboli. Per ogni carattere creremo un piccolo grafo che rappresenta tutte le possibili combinazioni degli n simboli con le due relazioni < e =. Alla fine contando le foglie di ogni grafo (complessità log n con ricerca in profondità ricorsiva) e sommandole fra loro, otteniamo il numero totale di combinazioni.

Questo rappresenta un singolo piccolo grafo:

[/URL]

(Scusate la pessima qualità di paint)

Arrivati a questa rappresentazione (di facile costruzione in un tempo asintoticamente pari ad O(n^2)), si deve fare una visita in profondità per calcolare il numero delle foglie. Per avere un'idea di come farla, puoi dare un'occhiata qui:

[url]http://limongelli.dia.uniroma3.it/asd/materiale08/eserc05.pdf (http://img208.imageshack.us/my.php?image=tempk.jpg)

Nella sezione visita in profondità

[Diablo81]

Dimenticavo: per questo tipo di cose wallace è molto bravo. Io, come ho già detto, sono una sega, nel senso che trovo delle soluzioni un pò macchinose. Si dovrebbe invitare wal alla discussione :asd:

[Milton]

mmmm

tu dici di creare n grafi praticamente? ognuno dei quali parte da un simbolo e si sviluppa sui restanti n-1 giusto?

ma cosi non dovresti avere n strutture dati di complessità >n?

ed anche in tempo non sono cosi convinto che sia in O(n^2), alla fine è vero che una DFS agisce in O(n^2) dove n sono i nodi che nei vari grafi risultano >> dei nostri n che sono i simboli

poi cmq nei grafi rimane il problema delle ridondanze no?

questo sperando che l'ora non mi abbia tirato botte di sonno con allucinazioni :asd:

[Diablo81]

mmmm

tu dici di creare n grafi praticamente? ognuno dei quali parte da un simbolo e si sviluppa sui restanti n-1 giusto?
[quote]

si il concetto è questo.

[quote]
ma cosi non dovresti avere n strutture dati di complessità >n?


Creare un grafo ha complessità n*(n-1), quindi è nei limiti imposti. Il problema qui in realtà è lo spazio, visto che il prof gli impone O(n) e con questa soluzione si creano strutture più grandi.



ed anche in tempo non sono cosi convinto che sia in O(n^2), alla fine è vero che una DFS agisce in O(n^2) dove n sono i nodi che nei vari grafi risultano >> dei nostri n che sono i simboli


In tempo, come ho detto, la creazione dei grafi è di n*(n-1) e la visita in profondità è n*log n (log n per ogni grafo).



poi cmq nei grafi rimane il problema delle ridondanze no?


mm no non mi sembra, dove sbaglio?



questo sperando che l'ora non mi abbia tirato botte di sonno con allucinazioni :asd:

Vale lo stesso discorso per me :D .

[Milton]

Creare un grafo ha complessità n*(n-1), quindi è nei limiti imposti. Il problema qui in realtà è lo spazio, visto che il prof gli impone O(n) e con questa soluzione si creano strutture più grandi.

sisi io di spazio dicevo :D





In tempo, come ho detto, la creazione dei grafi è di n*(n-1) e la visita in profondità è n*log n (log n per ogni grafo).

nono la DFS ha costo O(E+V), che nel caso peggiore di grafo denso possiamo considerare O(n^2)

link (http://en.wikipedia.org/wiki/Depth-first_search), che poi ad esser onesti lo sono andato a riguardare non me lo ricordavo :asd:





mm no non mi sembra, dove sbaglio?



dalla figura che hai postato hai due percorsi che fanno uno a=b=c ed uno a=c=b che sono uguali, quindi alla fine se il metodo è contare le foglie ( che era lo stesso che avevo in mente io ) ti trovi a contare piu volte la stessa

cmq discutere di tutto questo a quest'ora è puro autolesionismo ingegneristico :asd:

[Diablo81]

Si hai perfettamente ragione. Fra l'altro anche io avevo completamente dimenticato il caso peggiore della DFS :asd: .
Hai ragione anche sul doppione, non avevo considerato che a=b=c è un doppione di a=c=b :look: .
Ora dovrei pensare a come eliminare i doppioni, ma visto che sto lavorando a quest'ora, premo il pulsante rosso abort :asd: . Se servirà ancora a rulez ci penserò domani sul treno che ho 3 ore a disposizione :D .

[waL]

Dimenticavo: per questo tipo di cose wallace è molto bravo. Io, come ho già detto, sono una sega, nel senso che trovo delle soluzioni un pò macchinose. Si dovrebbe invitare wal alla discussione :asd:

non esageriamo :asd:

cmq devi farlo per forza ricorsivo?

[CeLesTiaL]

edit: no ho failato ho visto ora il post sry

[Rulez]

ho letto tutto e ho notato che vi siete accorti del vincolo anche di spazio..


non esageriamo :asd:

cmq devi farlo per forza ricorsivo?

no no.. puoi farlo come vuoi ma col calcolo combinatorico e in maniera non ricorsiva la vedo dura!! E' che con la programmazione dinamica per forza devi dare una definizione ricorsiva della soluzione

Ieri gli ho rotto i coglioni a lungo e infine siamo arrivati alla soluzione con il prof (però francamente sullo spazio occupato avrei qualcosa da ridirgli) ..

Comunque è bel casino.. oggi vi enuncio la "soluzione" a cui siamo arrivati con lui.. ma non voglio stare lì a spiegare per bene il perchè di una cosa o dell'altra perchè è un bel po' incasinato! .. Oltretutto per una dimostrazione di correttezza non saprei nemmeno da dove iniziare!!
Comunque programmazione dinamica era infatti!

Comunque pensate che il buon prof lo aveva dato ad un esame (seppure appello fuori corso) :eek: e lo studio di questa sequenza è stato fatto come progetto di tesi.. cioè e noi in 2 ore dovremo risolverlo.. + altri 3 esercizi!?!?

[Diablo81]

Effettivamente per un esame è un pò impegnativo. Cioè, alla soluzione uno ci arriva, ma di certo ad un esame diventa complicato.

Comunque per lo spazio rulez ho fatto un paio di "osservazioni" mie mentali e non credo sia possibile rimanere in uno spazio così piccolo, o meglio in un certo istante ci puoi anche stare, ma nel complesso lo sfori.

[Rulez]

Si infatti la soluzione che utilizza lui (e che sto scrivendo) opera su una matrice .. dunque la consegna sicuramente è sbagliata.. è n^2

[BaLoOo]

Posso darti un'ultima risposta rulez poi devo andare e riprendo stasera. Dai un'occhiata qui:

http://it.wikipedia.org/wiki/Combinazione

In maniera particolare al paragrafo "ordine lessicografico" (che è una parte dell'algoritmo che ti serve) e successivamente al paragrafo "multi insiemi" che è il secondo pezzo che ti serve.
Se ti risulta difficile interpretare questo metodo (io stesso non ricordavo come si calcolano le combinazioni, intendo la formuletta per la serie e sono dovuto andarmelo a rivedere su wikipedia), come ti ho detto stasera ti faccio vedere una soluzione che è più complessa nell'implementazione, ma più semplice dal punto di vista comprensivo (e costa anche di meno).
Ora scappo a dopo.

(D3*(C2,1-1))+1

quello che dici te dovrebbe essere quello ma bisognerebbe aggiustarsela :argh: con -1 (toglie le tre 3! variabili*=) e +1 (insirisce una variabile con = , che da la stessa informazione delle sei.. :/) oppure un -5 (che toglie le cinque superflue).

non entro nel campo della programmazione, perche non ne so una cippa, solo mi e' rimasto un po il calcolo combinatorio dalle superiori, era solo una appunto sull'uso di una combinazione proposta da diablo

[Rulez]

Soluzione del prof...
La spoilero .. così magari qualcuno che ci vuole ancora provare ..


Tento di spiegarmi il meglio possibile!

L'idea è quella, come avevo scritto, di pensare al passaggio da 2 a 3 variabili.. e soprattutto, di considerare il blocchetti di variabili concatenate da "=" come blocchetti indivisibili (poi tento di spiegare il perchè), un po' come era venuto in mente a me e a milton...

Definiamo: E(n,d) La funzione che ci restituisce il numero di espressioni distinte con: n=numero_variabili e d=numero_blocchi_distinti.
Questo E(n,d) può essere visto quindi anche come il numero di espressioni con necessariamente d-1 simboli di "<" e 1<=d<=n sempre!

Adesso passiamo alla definizione ricorsiva.. in pratica si tratta di scoprire come definire E(n,d) in funzione di sottoproblemi che hanno n-1 variabili..
Qui ci vuole un po' l'untuizione per nulla banale:
E(n,d) = <fattore da scoprire1>*E(n-1,d) ??+?? <fattore da scoprire2>*E(n-1,d-1>

Dove E(n-1,d), avendo lo stesso d, significa che siamo passati a E(n,d) aggiungendo un simbolo di =; viceversa E(n-1, d-1) significa che ci siamo passati tramite un simbolo di "<".
Il ??+?? significa che non sono ancora oggi sicuro sia un +! :D

Quindi resta da scoprire il 2 fattori incognita che dunque corrispondono:
>>Il primo corrisponde ai possibili modi in cui possiamo aggiungere una variabile (passando quindi da n-1 a n) tramite il simbolo di uguale. Qui è abbastanza semplice da trovare perchè, con d blocchetti da considerare indivisibili (poi tento di spiegare il perchè), possiamo legare la variabile la massimo in d modi.. quindi il primo fattore è proprio "d".
>>Per il secondo (e qui è un po' un casino), è in numero di possibili posti dove possiamo inserire un simbolo di "<" passando da n-1 ===> a n e passando da d-1 ===> a d blocchetti! Beh qui non voglio dilungarmi troppo! Vi dico solo che i blocchetti vanno considerati indivisibili (**vedi nota sotto**) e che quindi qui abbiamo (d-1)+1 modi di mettere il "<" .. e dunque anche il secondo fattore è d!!

Nota: perchè infine verrà fatta una sommatoria che comprende tutte le dimensioni possibili di d, e che quindi ricopre i casi in cui i blocchetti vengono rotti da un simbolo di < ..
cioè se ad esempio abbiamo: a=b<c, il caso in cui la variabile d venga messa tra a e b è compreso nella sommatoria finale (che devo ancora scriver lol).. dunque non verrà contata da E(n,d) la combinazione (sempre guardando l'esempio) a<d=b<c (ho sottolineato il numero di blocchetti che passa da 2 a 3.. ma che non viene condato dalla funzione E(n,d).

Dunque dulcisi in fondo:
E(n,d)=d*E(n-1,d) ??+?? d*E(n-1,d-1).
ed in numero finale di combinazioni (quello che cerchiamo) è dato da:
E(n)=SUM[d=1 to n](E(n,d))

Bene, tutto l'ambaradan di E(n,d) è riconducibile ad una matrice n*n dove nelle righe metto in numero di variabili .. e nelle colonne metto in numero di blocchetti d.
Inizializziamo la prima colonna con tutti 1, perchè significa il numero di combinazioni distinte con n crescente e un solo (d=1) blocco.
La prima colonna va invece inizializzata con tutti 0 (ad eccezzione dell'elemento 1,1) in quando sarebbero i modi per dividere una sola variabile (n=1) in d crescenti blocchetti.. quindi 0!
Bene dai, adesso per calcolare i vari E(i,j) basta fare la somma (sempre se ??+?? è una somma .. devo ancora riguardarmelo e convincermi) di d-volte l'elemento sopra cioè d*E(i-1,j) + d-volte l'elemento in diagonale in alto a sinistra cioè d*E(i-1,j-1).

disegnetto :D


1 2 ... d ... n
1|1 0 ... 0 ... 0
2|1
.|...
.|1
.|...
n|1




E per calcolare il numero di combinazioni per un certo n, basta fare la somma degli elementi della n-esima riga fino a n...
Dimostrazione di correttezza... mmm auguri :D



ps. Non so ancora se sia giusto o no .. mah.. ora vediamo

[Rulez]

Per n = 1 viene 1 combinazione ..ok
Per n = 2 vengono 3 combinazioni ..ok
Per n = 3 vengono 13 combinazioni ..ok
Per n = 4 vengono 75 combinazioni ..mah

[Diablo81]

Rulez, domanda che esula dall'argomento: ma in che esame ti stanno facendo fare questa roba?

[Radical]

se è algoritmi e strutture dati mi pare poco pertinente (dà poco risalto all'algoritmo e alle strutture usate) ma è l'unica che mi viene in mente

[Rulez]

E' un esame delle laurea specialistica .. algoritmi avanzati!
Tra l'altro materia interessantissima nella quale studiamo i vari paradgmi e tecniche di programmazione da usare in base al tipo di problema.. studiamo il greedy, il divide et impera, la programmazione dinamica, branch & bound, backtracking, algoritmi probabilistici (numerici, las vegas e montecarlo), ricerca locale (con tabu search e la tecnica simulate annealing) ed infine un cenno agli algormitmi di aprossimazione per i problemi np-difficili!

Comunque in generale gli esercizi sono più fattibili di questo .. decisamente :D e si tratta quasi completamente nel capire quale tecnica usare, riconducendolo a esercizi più generali visti in classe!!

[Radical]

algoritmi avanzati e fate ancora i greedy, divide et impera e programmazione dinamica? ma algoritmi e strutture dati 1 l'avete fatto?

[Rulez]

Si certo nella triennale.. ma fidati che li guardiamo totalmente sotto un altro aspetto! In algoritmi e strutture dati avevamo visto un 10% di quello che abbiamo visto quest'anno!! Per dire nel greedy vediamo il matroide.. è una struttura particolare che, se riesci a caratterizzare il problema con tale struttura, allora è possibile risolvere il problema tramite un algoritmo greedy! :D anche per gli altri argomenti vediamo dei divide et impera per nulla banali (es. strassen che moltiplica 2 matrici n*n con T(n)=7*(n/2)+il ricombina.. oppure la mediana) .. Riguardo alla programmazione dinamica basta che guardi la risoluzione di questo esercizio per capire quanto è più approfondita rispetto a quanto ti insegnano nella triennale :asd:


ps. cmq puoi mettere risolto diablo! :D

[happo]

ok faccio io :)

[Milton]

Per n = 1 viene 1 combinazione ..ok
Per n = 2 vengono 3 combinazioni ..ok
Per n = 3 vengono 13 combinazioni ..ok
Per n = 4 vengono 75 combinazioni ..mah

non ho letto la soluzione ne tutto quello che c'è dopo, cmq n=4 75 combinazioni è giusto, mi usciva lo stesso dalla costruzione intuitiva dell'albero

[Rulez]

Ok grazie, allora funziona!!

[Diablo81]

La mia domanda circa l'esame è che ritengo onestamente inutile imparare a fare cose del genere. Mi spiego meglio perché non mi piace essere frainteso: sforzare il cervello è una cosa molto importante, anzi direi fondamentale. Applicare, però, le risorse celebrali in questa tipologia di problemi lo vedo un pò inutile. Cerco di spiegarmi ancora meglio: applicare il cervello su greedy, problemi np-hard (non np-difficili, non se pò sentì :asd: :D ) etc è molto produttivo, nel senso che successivamente davanti a problemi complessi, lo studente sa applicare alle sottoclassi dei problemi delle buone/ottime soluzioni.
Andare, però, a ravanare ed arrovellarsi il cervello su strani algoritmi non ha veramente senso. Un problema del genere uno lo risolve con un automa a stati finiti e non con un programma imperativo. Con il primo ci metti un minuto, con il secondo abbiamo visto tutti le difficoltà.
In definitiva: meglio impiegare le proprie risorse nei pattern, piuttosto che in applicazioni improbabili dei pattern stessi.

Posto tutto questo è stato comunque divertente :D .

[Radical]

beh np-hard pare un film porno però, meglio np-completo

[Milton]

np-hard è un'altra classe radical :asd:

[Radical]

a me gli np-hard non li hanno ancora nemmeno accennati :asd: e wikipedia nelle classi di complessità non ne fa cenno

[Rulez]

Comunque si diablo, è stato un po' un giochino rompicapo questo .. però negli esami classici, come dici te, l'importante è applicare il metodo e capire al volo quale usare per avere la miglior resa.. Questo era un po' una "sfida" che ci era rimasta lì :asd:

Comunque sarà ma la programmazione dinamica fa lavorare parecchio il cervello .. almeno a me! Cioè perchè mi sembra strano come riuscire a volte a non eseguire una ricerca esaustiva o semi-esaustiva quando le sottoistanze non sono disgiuste! Un esercizio di programmazione dinamica, decisamente più fattibile, presente su appelli "normali" per esempio è quello della sottosequenza massima .. cioè dati n numeri, determinare la sottosequenza crescente di cardinalità maggiore! Ecco questo francamente prima che mi insegnasse a fare un bon approccio al problema non sarei riuscito a risolverlo in maniera efficiente! :D

[Diablo81]

Si, come ho detto è molto buono per mettere in moto il cervello. Sostanzialmente il problema è che alla fine dei tuoi studi (a meno che tu non vada a fare il ricercatore al MIT o qualcosa di simile che ti auguro con tutto il cuore ovviamente), sarai costretto ad usare cose che altri hanno fatto e distribuito in librerie, fondamentalmente per 3 motivi:

1) il tempo: ci metteresti troppo a rifare tutto da capo e costerebbe troppo alle aziende
2) la validità della soluzione e conseguentemente l'assenza di bug: quelle nelle librerie sono funzioni testate e ritestate e sviscerate fino alla morte
3) Per quanto una persona sia in gamba, generalmente se delle funzioni vengono inserite in delle librerie, sono delle funzioni realmente prestazionali (anche se si può fare di meglio a volte, questo è ovvio, vedi i tanti algoritmi di ricerca che si sono susseguiti e sostituiti nel tempo)

(Poi per carità non è detto che uno non possa andare ad utilizzare una sua funzione lì dove crede sia migliore di quella della libreria per il proprio contesto, questo è ovvio).

Ti ho riscritto questo per spiegarti che il succo del mio post precedente non era insultare il tuo corso od il tuo professore :D, quanto dire a te di prendere "alla leggera" determinate applicazioni dei tuoi studi, percHé probabilmente non ti serviranno mai.

[Diablo81]

Sai che mi hai fatto venire un'idea per l'area?

Si potrebbe aprire un topic con una persona che posta un problemino da risolvere e le altre che postano una soluzione quando la hanno, un pò come la catena nel forum film :D . Se siete interessati si potrebbe fare anche facilmente (ovviamente i problemini dovranno essere semplici, non delle bestialità :asd: ).

[eldiabloz]

Diablo il mio problema è programmare un sistema operativo stabile, facile e veloce ... prego :asd:

L'idea è bella però boh andrebbe pensata bene :D

[Diablo81]

Diablo il mio problema è programmare un sistema operativo stabile, facile e veloce ... prego :asd:

ahahha ecco :D. intendevo qualcosa di semplice ovviamente ^^

[Radical]

io ho già trovato qualcosa di simile a quello che hai proposto tu diablo http://projecteuler.net/ è molto carino :D

[Diablo81]

carino, non lo conoscevo sto progetto!