OliForum Matematico

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.

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})? $

Forse bh3u4m chiedeva un algoritmo che lo facesse in tempo ottimo...
E se non lo chiedeva lui, lo chiedo io.

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...

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) $

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

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.

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?

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...).

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

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?

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...

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

Si intende l'ordine della sequenza, non l'ordine di peso o di capacità.

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