Inaugurazione con tartarughe...
Inaugurazione con tartarughe...
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.
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.
-
- Messaggi: 113
- Iscritto il: 01 gen 1970, 01:00
- Località: Catania
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) $
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) $
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.
Resta da dimostrare che $ O(n^2) $ è il tempo ottimo.
- gip
- Messaggi: 86
- Iscritto il: 01 gen 1970, 01:00
- Località: Pisa, Scuola Superiore Sant'Anna
- Contatta:
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?
E quel $ O(n\cdot \log{n}) $, Mind? E' possibile? E in generale come si fa a dimostrare che si è raggiunto l'ottimo?
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?
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?
- gip
- Messaggi: 86
- Iscritto il: 01 gen 1970, 01:00
- Località: Pisa, Scuola Superiore Sant'Anna
- Contatta:
Eh, grazie... intendevo quali fossero le tecniche standard per farlo (se esistono)... io conosco soltanto gli alberi di decisione...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...).