Inaugurazione con tartarughe...

Programmazione, algoritmica, teoria dell'informazione, ...
Avatar utente
gip
Messaggi: 86
Iscritto il: 01 gen 1970, 01:00
Località: Pisa, Scuola Superiore Sant'Anna
Contatta:

Messaggio da gip » 28 feb 2005, 18:36

BlaisorBlade ha scritto:Beh, Mind, sei sicuro che quello non vada in tempo ottimo?

Ma quell'algoritmo, che esplorerà tutte le possibili combinazioni, ovvero tutti i sottoinsiemi di tartarughe, non sarà di ordine O(2^n)? O forse no... forse sei stato eccessivamente sintetico ma hai già detto quello giusto.

[...]
O forse intendi questo ordine??? :?:

Avatar utente
gip
Messaggi: 86
Iscritto il: 01 gen 1970, 01:00
Località: Pisa, Scuola Superiore Sant'Anna
Contatta:

Messaggio da gip » 01 mar 2005, 04:51

MindFlyer ha scritto:Un'altra cosa: bisognerebbe anche dimostrare che l'algoritmo di BlaisorBlade funziona, che è un fatto non ovvio (e del quale non sono nemmeno convinto)...

Bisognerebbe dimostrare che, aggiungendo una nuova tartaruga "dal basso", la sequenza massimale che parte con questa tartaruga si ottiene a partire dalle sequenze massimali finora trovate per le altre tartarughe.

Allora BlaisorBlade, come lo dimostri?
Fermo restando il fatto che rimango dubbioso su come lo si possa dimostrare "rigorosamente", io vedrei necessario memorizzare un vettore di lunghezze massime e uno dei pesi raggiunti fino a quel momento, con un elemento per tartaruga; dopodiche' si ripete n volte, ed al piu' su n elementi, una procedura che (qualora la sequenza di tartarughe selezionata non si sia gia' interrotta precendentemente, il che' e' verificabile cofrontando la lunghezza raggiunta con il numero di iterazioni gia' effettuate) controlla se la capacita' della tartaruga successiva (che ha indice k-i, se k e' l'indice della sequenza in questione e i e' il numero di iterazioni gia' effettuate) e' maggiore del peso raggiunto e che in base al risultato del confronto aggiorna i vettori. Alla fine l'elemento con lunghezza massima vince. Non va?

MindFlyer

Messaggio da MindFlyer » 01 mar 2005, 14:27

L'algoritmo è chiaro.
Come dimostri che funziona??

Avatar utente
gip
Messaggi: 86
Iscritto il: 01 gen 1970, 01:00
Località: Pisa, Scuola Superiore Sant'Anna
Contatta:

Messaggio da gip » 03 mar 2005, 14:10

MindFlyer ha scritto:L'algoritmo è chiaro.
Come dimostri che funziona??
Per induzione (due volte)?
Con una tartaruga funziona, poiché non c'è niente da verificare; se poi funziona con n tartarughe, immagino di aggiungerne una sopra tutte le altre, nella sequenza data come input; a questo punto ho che per ogni ciclo l'andamento dei vettori per le tartarughe che stanno sotto di essa va esattamente come se non ci fosse; gli elementi che la riguardano si evolvono invece in base ad un algoritmo più semplice, volto a trovare la più lunga sottosequenza con una certa tartaruga in testa.

**
Un simile algoritmo si può a sua volta dimostrare per induzione: con una tartaruga funziona banalmente; se poi funziona con n tartarughe si ha che aggiungendone una sotto tutte le altre, l'algoritmo si comporta come se avesse n tartarughe per le prime n-1 iterazioni e all'ultima (qualora non si sia interrotto prima) non fa altro che verificare se la nuova tartaruga può sostenere il peso e aggiorna così peso e lunghezza, come è corretto che faccia.
**

A questo punto, avendo per ogni tartaruga un numero che ci dice quanto è lunga la sottosequenza massima che la vede sopra le altre, si vede quale tra queste sottosequenze è la maggiore, ottenendo il risultato finale, visto che tale sottosequenza deve essere una delle suddette, poichè dovrà avere una qualche tartaruga in testa.

The end.

Può funzionare?? :roll:

Ciao!
Marino

MindFlyer

Messaggio da MindFlyer » 03 mar 2005, 19:11

Sarò breve: se sono riuscito a capire quello che avete detto, voi memorizzate ad ogni passo soltanto la lunghezza della sequenza più lunga che ha per base ciascuna tartaruga, ed il relativo peso. Poi aggiungete una nuova tartaruga sotto tutte le altre (non sopra, come mi sembra di capire dal discorso di gip), e vedete se può estendere le pile trovate precedentemente. E ok.

Ma la mia domanda è: se voi non considerate tutte le sequenze che si possono formare a partire da una pila non massima nell'iterazione precedente, come garantite di trovare ugualmente il massimo? Insomma, voi usate un algoritmo "greedy", supponendo che dei passaggi localmente ottimi ottimizzino anche il risultato finale. Ma non mi pare ovvio che funzioni, in questo caso.

manub
Messaggi: 9
Iscritto il: 01 gen 1970, 01:00
Località: Napoli
Contatta:

Messaggio da manub » 06 mar 2005, 15:27

un algoritmo greedy, per essere applicato, richiede (come diceva Mind Flyer) la dimostrazione che la scelta dell'ottimo locale ad ogni iterazione garantisca il raggiungimento della soluzione ottima globale (come ad esempio si può fare per costruire l'albero di copertura minimo di un grafo). credo che questo problema vada risolto mediante programmazione dinamica... purtroppo non sono ferrato nell'argomento, ma seguirò le discussioni con curiosità ;)

Pyv
Messaggi: 11
Iscritto il: 01 gen 1970, 01:00
Località: Latina

Messaggio da Pyv » 09 mar 2005, 20:41

Anzitutto non fate caso al mio nick ridicolo, quando mi stavo registrando non sapevo proprio cosa inventarmi

Spero di cavarvi di impaccio da dimostrazioni inutili se vi dico che si tratta di un problema di zaino a due dimensioni e che ogni approccio greedy non puo' funzionare...

Va utilizzata una programmazione dinamica in due dimensioni circolare, ma visto che il problema non ha dimensioni eccessive (l'ho trovato su "Programming Challenges") e' possibile due array separati. Non capite quello che dico? Non vi preoccupate, sono dettagli implentativi che interessano agli informatici :)

Comunque, bisogna ciclare attraverso tutte le tartarughe dall'ultima alla prima tenendo aggiornato un array pesomin[l] che indica il peso minimo che deve avere una sequenza di l tartarughe. Una volta finito di ciclare le tartarughe, trovare il massimo l tale che esista pesomin[l] (gia' perche' puo' anche non esistere).

Mi fermo qui, vi do' solo degli indizi... Se volete vi posto il codice ma vi avverto che non e' molto comprensibile... di certo non perche' scrivo male codice ma perche' certi passaggi e' difficile capirli solo dal programma, specie se non commentato.

Ciao

P.S.: visto che ci sto vi propongo un problemino informatico/matematico: dato un numero 1<=n<=10^9, determinare la cifra piu' significativa di n^n.

Pyv
Messaggi: 11
Iscritto il: 01 gen 1970, 01:00
Località: Latina

Messaggio da Pyv » 09 mar 2005, 20:44

Ho dimenticato di dire che se avete qualche problema di informatica, se volete, c'e' il forum delle Olimpiadi di Informatica. E' appena nato e non c'e' molto traffico, ma crescera' :)

http://81.208.32.83:8889/ioi-site/pn/ht ... file=index

Ciao e scusate l'intromissione, il forum matematica non e' posto che mi spetterebbe[/url]

MindFlyer

Messaggio da MindFlyer » 09 mar 2005, 21:10

Pyv ha scritto:P.S.: visto che ci sto vi propongo un problemino informatico/matematico: dato un numero 1<=n<=10^9, determinare la cifra piu' significativa di n^n.
Ciau Pyv, e benvenuto nel forum!
Dovrei chiederti di aprire un nuovo topic se vuoi proporre un nuovo problema (è per tenere ordinato il forum).
A presto!

Avatar utente
gip
Messaggi: 86
Iscritto il: 01 gen 1970, 01:00
Località: Pisa, Scuola Superiore Sant'Anna
Contatta:

Messaggio da gip » 09 mar 2005, 23:35

MindFlyer ha scritto:Sarò breve: se sono riuscito a capire quello che avete detto, voi memorizzate ad ogni passo soltanto la lunghezza della sequenza più lunga che ha per base ciascuna tartaruga, ed il relativo peso. Poi aggiungete una nuova tartaruga sotto tutte le altre (non sopra, come mi sembra di capire dal discorso di gip), e vedete se può estendere le pile trovate precedentemente. E ok.

Ma la mia domanda è: se voi non considerate tutte le sequenze che si possono formare a partire da una pila non massima nell'iterazione precedente, come garantite di trovare ugualmente il massimo? Insomma, voi usate un algoritmo "greedy", supponendo che dei passaggi localmente ottimi ottimizzino anche il risultato finale. Ma non mi pare ovvio che funzioni, in questo caso.
Io veramente intendevo memorizzare, per ciascuna tartaruga, la lunghezza della sequenza più lunga che ha sopra tutte le altre quella determinata tartaruga, aggiungendo le successive poi una alla volta dal basso; quando non ce la si può più fare, perchè la nuova tartaruga di base non regge il peso della pila, allora la pila precedente era la più lunga, con quella determinata tartaruga posta alla sommità... siccome poi la pila massima dovrà avere alla sommità una delle tartarughe, e io per ogni tartaruga ho calcolato la pila massima con essa in cima, il massimo lo trovo tra quelli calcolati...
Io non vedo il bug nel ragionamento, ma ci sta benissimo che mi sbagli... sono però curioso di sapere cosa in particolare fa acqua...

P.S.: un dubbio atroce pervade ora la mia mente: non è che si intendesse sequenze nell'ordine dato, ma formate anche da tartarughe non adiacenti nella configurazione di partenza??????? Se sì ritiro tutto quanto, poiché avevo inteso il contrario...

MindFlyer

Messaggio da MindFlyer » 09 mar 2005, 23:41

gip ha scritto:P.S.: un dubbio atroce pervade ora la mia mente: non è che si intendesse sequenze nell'ordine dato, ma formate anche da tartarughe non adiacenti nella configurazione di partenza??????? Se sì ritiro tutto quanto, poiché avevo inteso il contrario...
Oooooh, esatto!!!
Altrimenti il problema sarebbe banalmente O(n), senza programmazione dinamica e altre diavolerie.

Avatar utente
gip
Messaggi: 86
Iscritto il: 01 gen 1970, 01:00
Località: Pisa, Scuola Superiore Sant'Anna
Contatta:

Messaggio da gip » 09 mar 2005, 23:53

MindFlyer ha scritto:
gip ha scritto:P.S.: un dubbio atroce pervade ora la mia mente: non è che si intendesse sequenze nell'ordine dato, ma formate anche da tartarughe non adiacenti nella configurazione di partenza??????? Se sì ritiro tutto quanto, poiché avevo inteso il contrario...
Oooooh, esatto!!!
Altrimenti il problema sarebbe banalmente O(n), senza programmazione dinamica e altre diavolerie.
Amen. Ma qual è il modo banale per avere O(n)?

MindFlyer

Messaggio da MindFlyer » 10 mar 2005, 00:12

Tieni 2 puntatori all'inizio e alla fine della pila massima che stai considerando, e scorri tutte le tartarughe una volta sola. Prova!

Avatar utente
gip
Messaggi: 86
Iscritto il: 01 gen 1970, 01:00
Località: Pisa, Scuola Superiore Sant'Anna
Contatta:

Messaggio da gip » 10 mar 2005, 06:26

Wow, vero! Lombrico-programming.

Pyv
Messaggi: 11
Iscritto il: 01 gen 1970, 01:00
Località: Latina

Messaggio da Pyv » 10 mar 2005, 23:11

Ragazzi fidatevi e' una dinamica a due dimensioni... volete che vi posto il codice? :)

Rispondi