Problema di ottimizzazione in $NN$
Ciao a tutti, pensavo a questo problema:
Ho a disposizione solo l'$1$ e il $+$. Partendo da questi elementi, posso creare tutti gli altri numeri, ad esempio $2=1+1$, $3=1+2$, $5=2+3$.
Ora, dato per esempio $5$, posso arrivarci facendo appunto $2=1+1$, $3=1+2$, $5=2+3$, che sono 3 operazioni, oppure anche $2=1+1$, $3=2+1$, $4=3+1$, $5=4+1$, ma mi sono servite 4 operazioni.
Problema: dato $n>1$, $n in NN$,
a) Quante operazioni servono per costruire $n$ col minor numero di operazioni possibile?
b) Quale algoritmo si può seguire per generare appunto tale successione ottimale?
Per quanto riguarda la a), ad occhio mi verrebbe da dire che: tutti i numeri del tipo $2^m$ hanno bisogno di $m$ operazioni almeno (facendo sempre la divisione per $2$, $1+1=2$, $2+2=2^2$, $2^2+2^2=2^3$ ecc), quindi preso $2^m <= n <= 2^(m+1)$ allora $op(2^m) <= op(n) <= op(2^(m+1)) " " => m <= op(n) <= m+1$, quindi concluderei che $[log_2 n] <= op(n) <= [log_2 n] + 1$. Però sarei interessato al numero ESATTO di operazioni necessarie...
Per la questione b) non saprei da dove partire
Idee? Grazie!
Ho a disposizione solo l'$1$ e il $+$. Partendo da questi elementi, posso creare tutti gli altri numeri, ad esempio $2=1+1$, $3=1+2$, $5=2+3$.
Ora, dato per esempio $5$, posso arrivarci facendo appunto $2=1+1$, $3=1+2$, $5=2+3$, che sono 3 operazioni, oppure anche $2=1+1$, $3=2+1$, $4=3+1$, $5=4+1$, ma mi sono servite 4 operazioni.
Problema: dato $n>1$, $n in NN$,
a) Quante operazioni servono per costruire $n$ col minor numero di operazioni possibile?
b) Quale algoritmo si può seguire per generare appunto tale successione ottimale?
Per quanto riguarda la a), ad occhio mi verrebbe da dire che: tutti i numeri del tipo $2^m$ hanno bisogno di $m$ operazioni almeno (facendo sempre la divisione per $2$, $1+1=2$, $2+2=2^2$, $2^2+2^2=2^3$ ecc), quindi preso $2^m <= n <= 2^(m+1)$ allora $op(2^m) <= op(n) <= op(2^(m+1)) " " => m <= op(n) <= m+1$, quindi concluderei che $[log_2 n] <= op(n) <= [log_2 n] + 1$. Però sarei interessato al numero ESATTO di operazioni necessarie...
Per la questione b) non saprei da dove partire
Idee? Grazie!
Risposte
a) L'asserto che hai messo
"se $2^m <= n <= 2^(m+1)$ allora $op(2^m)<=op(n)<=op(2^m+1)$"
non sono sicuro sia sempre vero. Esempio per "fare" 16 puoi arrivarci con 1+1=2 2+2=4 ecc con sole 4 operazioni, per "fare" 32 con 5 operazioni, ma per "fare" 30 per esempio? Io non sono riuscito ad arrivarci con cinque operazioni (ma forse sono scarso).
Comunque vedo che assumi di poter memorizzare i numeri e di poter fare qualunque somma con ciò che è stato precedentemente calcolato, ho capito bene?
"se $2^m <= n <= 2^(m+1)$ allora $op(2^m)<=op(n)<=op(2^m+1)$"
non sono sicuro sia sempre vero. Esempio per "fare" 16 puoi arrivarci con 1+1=2 2+2=4 ecc con sole 4 operazioni, per "fare" 32 con 5 operazioni, ma per "fare" 30 per esempio? Io non sono riuscito ad arrivarci con cinque operazioni (ma forse sono scarso).
Comunque vedo che assumi di poter memorizzare i numeri e di poter fare qualunque somma con ciò che è stato precedentemente calcolato, ho capito bene?
A me sembra più un problema di informatica. E' trattato perché è utilizzato per trovare l'esponenziale con meno moltiplicazioni. L'uso del metodo binario, seppur non sia ottimale, è il metodo più usato.
Knuth nel suo the art of computer programming analizza il problema nella sezione 4.6.3. del secondo volume.
http://en.wikipedia.org/wiki/Addition_chain
http://en.wikipedia.org/wiki/Addition-c ... nentiation
http://wwwhomes.uni-bielefeld.de/achim/ ... chain.html
Ti rimando comunque all'ottimo manuale di Knuth per approfondimenti.
Knuth nel suo the art of computer programming analizza il problema nella sezione 4.6.3. del secondo volume.
http://en.wikipedia.org/wiki/Addition_chain
http://en.wikipedia.org/wiki/Addition-c ... nentiation
http://wwwhomes.uni-bielefeld.de/achim/ ... chain.html
Ti rimando comunque all'ottimo manuale di Knuth per approfondimenti.
"Rggb":
a) L'asserto che hai messo
"se $2^m <= n <= 2^(m+1)$ allora $op(2^m)<=op(n)<=op(2^m+1)$"
non sono sicuro sia sempre vero. Esempio per "fare" 16 puoi arrivarci con 1+1=2 2+2=4 ecc con sole 4 operazioni, per "fare" 32 con 5 operazioni, ma per "fare" 30 per esempio? Io non sono riuscito ad arrivarci con cinque operazioni (ma forse sono scarso).
Comunque vedo che assumi di poter memorizzare i numeri e di poter fare qualunque somma con ciò che è stato precedentemente calcolato, ho capito bene?
Infatti non si può... Il numero ottimale per 30 è 6...
Il suo calcolo ha ignorato un po' di somme... Il calcolo per sommare 2^n+1 fa ad ogni passaggio 2 somme. Consideriamo 7 per esempio.
Memorizzi in A=1 e B=1
1) A=A+A (2) e B=B+A (3)
2) A=A+A (4) e B=B+A (7)
E B è il tuo risultato.
In totale fa 4 somme contro le 3 di produrre 8. Ovviamente si può fare 7 . Tra l'altro il numero di somme è anche minimale in questo caso.
Una più corretta disequazione sarebbe quindi:
$|__ log_2(n) __| \le op(n) \le 2 |__ log_2(n) __|$
Considerando il metodo descritto sopra si può fare di meglio nel senso che se $|__ log_2(n) __|=m$ allora si sa che il numero ottimale è compreso tra m e m più il numero di 1 nella scrittura decimale ad esclusione del primo.
Avete ragione mi sbagliavo, comunque non aveva la pretesa di essere una dimostrazione, era solo un'osservazione "a occhio" che mi era venuta 
Si è vero il problema ha a che fare anche con l'informatica, nel senso che mi serve di sommare punti su una curva ellittica, ma non essendoci una formula "chiusa" per calcolare $[n]P = P+...+P$, avevo provato a fare semplicemente proprio $P+P+P...+P$ ma il tempo che impiega l'algoritmo è enorme, e quindi cercavo un'ottimizzazione, che a quanto pare è più difficile di quello che pensavo!
Grazie per i link di wiki, ci stanno degli algoritmi interessanti che ora mi leggo...
Si è vero il problema ha a che fare anche con l'informatica, nel senso che mi serve di sommare punti su una curva ellittica, ma non essendoci una formula "chiusa" per calcolare $[n]P = P+...+P$, avevo provato a fare semplicemente proprio $P+P+P...+P$ ma il tempo che impiega l'algoritmo è enorme, e quindi cercavo un'ottimizzazione, che a quanto pare è più difficile di quello che pensavo!
Grazie per i link di wiki, ci stanno degli algoritmi interessanti che ora mi leggo...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo