Inaugurazione con tartarughe...

Programmazione, algoritmica, teoria dell'informazione, ...
Avatar utente
bh3u4m
Messaggi: 547
Iscritto il: 01 gen 1970, 01:00
Località: Milano

Inaugurazione con tartarughe...

Messaggio da bh3u4m »

Comincerei ad inaugurare questa sezione dedicata all'informatica con un problema interessante...

Data una sequenza di tartarughe di cui conosciamo il peso e la portata (il peso massimo che possono reggere sopra di loro) scrivere un programma che trovi la più lunga sottosequenza di tartarughe una sopra l'altra, tale che l'ordine in cui sono posizionate rispetti l'ordine della sequenza data.
Avatar utente
gip
Messaggi: 86
Iscritto il: 01 gen 1970, 01:00
Località: Pisa, Scuola Superiore Sant'Anna
Contatta:

Messaggio da gip »

Banalmente scorrere le tartarughe a una a una vedendo quanto potrebbe essere lunga la sequenza che abbia quella tartaruga sul fondo, tenendo in memoria la lunghezza massima raggiunta e l'indice corrispondente? $ O(n^{2})? $
MindFlyer

Messaggio da MindFlyer »

Forse bh3u4m chiedeva un algoritmo che lo facesse in tempo ottimo...
E se non lo chiedeva lui, lo chiedo io. :)
Avatar utente
gip
Messaggi: 86
Iscritto il: 01 gen 1970, 01:00
Località: Pisa, Scuola Superiore Sant'Anna
Contatta:

Messaggio da gip »

MindFlyer ha scritto:Forse bh3u4m chiedeva un algoritmo che lo facesse in tempo ottimo...
E se non lo chiedeva lui, lo chiedo io. :)
OK, prendo atto del fatto che si può fare di meglio... ora ci penso...
D'altronde di algoritmica ho tutto da imparare... :)
BlaisorBlade
Messaggi: 113
Iscritto il: 01 gen 1970, 01:00
Località: Catania

Messaggio da BlaisorBlade »

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.

Il trucco da usare è che quando si arriva a una tartaruga (ad esempio alla quarta) non c'è bisogno di ricomputare da capo la sottosequenza ottimale di tartarughe da porvi di sopra. Provando tutte le combinazioni come sopra, invece, questo controllo viene rifatto ogni volta. Questo tipo di ottimizzazione è chiamato "programmazione dinamica". Vedere la relativa dispensa su http://ioi.dsi.unimi.it.

Se in quello che scrivi sottointendi questo trucco, allora probabilmente va bene. L'ordine è O(n^2) perché per l'ultima tartaruga dà un contributo 1, la seconda 1, la i-esima dal fondo i-1 perché per essa bisogna controllare (ed eventualmente sommare) tutte le tartarughe successive per vedere se stanno di sopra, quindi

$ \sum^{n}_{i=1} i = \frac {n (n-1)} {2} = O\left(n^2\right) $
Nouth
Messaggi: 42
Iscritto il: 26 feb 2005, 17:28
Località: Brogliano sperduto paese nella di Vicenza provincia

Messaggio da Nouth »

io non ho ben capito cosa chiede il problema!!!
p.s BlaisorBlade hai fatto le Olimpiadi di informatica???
Nouth
MindFlyer

Messaggio da MindFlyer »

Ok, il giochetto della programmazione dinamica va in $ O(n^2) $, e quando ho letto il post di gip pensavo che intendesse proprio quello. Ma noto adesso che lui non memorizza un vettore di lunghezze massime (con un elemento per ogni tartaruga), ma solo la lunghezza massima trovata fino a quel momento. E questo non funziona, perché non è detto che la tartaruga che fino a quel momento ha la pila massima sarà poi contenuta nella pila massima finale: perciò è necessario portarsi dietro più informazione.
Resta da dimostrare che $ O(n^2) $ è il tempo ottimo.
Avatar utente
gip
Messaggi: 86
Iscritto il: 01 gen 1970, 01:00
Località: Pisa, Scuola Superiore Sant'Anna
Contatta:

Messaggio da gip »

Già, mi sbagliavo... è necessario mantenere in memoria il vettore delle tartarughe, non avevo pensato al fatto che altrimenti va ricalcolato ad ogni passata... grazie mille a questo proposito per il link alla dispensa sulla p.d.!

E quel $ O(n\cdot \log{n}) $, Mind? E' possibile? E in generale come si fa a dimostrare che si è raggiunto l'ottimo? :?: :?:
MindFlyer

Messaggio da MindFlyer »

No, $ O(n\cdot \log n) $ era un'allucinazione passeggera.
Per dimostrare l'ottimalità basta far vedere che ogni algoritmo di tempo minore non può calcolare quella funzione (e chi l'avrebbe mai detto...).
kerbero87
Messaggi: 1
Iscritto il: 27 feb 2005, 11:09

Messaggio da kerbero87 »

Non si potrebbe utilizzare l'algoritmo della massima sottosequenza comune?
MindFlyer

Messaggio da MindFlyer »

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?
Avatar utente
gip
Messaggi: 86
Iscritto il: 01 gen 1970, 01:00
Località: Pisa, Scuola Superiore Sant'Anna
Contatta:

Messaggio da gip »

MindFlyer ha scritto: Per dimostrare l'ottimalità basta far vedere che ogni algoritmo di tempo minore non può calcolare quella funzione (e chi l'avrebbe mai detto...).
Eh, grazie... intendevo quali fossero le tecniche standard per farlo (se esistono)... io conosco soltanto gli alberi di decisione...
Nouth
Messaggi: 42
Iscritto il: 26 feb 2005, 17:28
Località: Brogliano sperduto paese nella di Vicenza provincia

Messaggio da Nouth »

scusate se mi intrometto, non so se questo topic è alla mia portata, ma mi potrste spiegare il problema iniziale???
mi sfugge il significato del termine "Ordine", non credo intendiate semplicemente ordine crescente e decrescente, perchè allora non capisco proprio quello che avete scritto
Nouth
MindFlyer

Messaggio da MindFlyer »

Si intende l'ordine della sequenza, non l'ordine di peso o di capacità.
Nouth
Messaggi: 42
Iscritto il: 26 feb 2005, 17:28
Località: Brogliano sperduto paese nella di Vicenza provincia

Messaggio da Nouth »

è proprio quello che non rieco a capire! cos'è l'ordine della seguenza??
Rispondi