Newsgroup: it.scienza.informatica
Titolo: Problema

Quello che segue e' un semplice problema di algoritmi
ovvero trovare un algoritmo polinomiale e magari
un bel limite inferiore alla complessita' dello stesso.
Ve lo propongo.
Cosi' come l'ho delirato in una notte di febbre.
Se poi a qualcuno interessa sapere da dove esce
(cioe' da una applicazione pratica), glielo diro'.
mi scuso in anticipo per eventuali improprieta'
di linguaggio che sicuramente commettero'
Allora, cominciamo.
Siano n1,...,nN naturali.
Sia I il prodotto cartesiano degli intervalli
[1,n1],[1,n2],...,[1,nN]
indico con ij la componente j-esima di un generico 
i in I
Sia I2 il prodotto di
[0,n1+1],[0,n2+1],[0,nN+1]
Sia A l'insieme delle matrici N-dimensionali, di 
dimensioni (n1 * n2 * ... * nN), ovvero delle 
funzioni da I ai Naturali
Sia t la funzione
 t: (A,I2) -> Naturali
 
 t(X,i)= A[i] se i appartiene a I
         0    se i non appartiene a I 
  ovvero t estende X sul dominio I2
Sia f la funzione
 f: (A,I) -> Naturali       tale che
 f(X,i)=  X[i] +
        + X[t(X,i1-1),i2,...,in] +
        + X[t(X,i1+1),i2,...,in] +
        + X[i1,t(X,i2-1),...,in] +
        + X[i1,t(X,i2+1),...,in] +
        + ...
        + X[i1,i2,...,t(X,in-1)] + 
        + X[i1,i2,...,t(X,in+1)] + 
Sia infine g la funzione
 
 g: A -> A
tale che, per i in I
 
  (g(X))[i]= f(X,i)
Si chiede di
1: non mandarmi a ... (VI prego!)
2: formalizzare meglio f, ma questo solo per 
   colpa della mia pigrizia
3: QUESTO E' IL VERO PROBLEMA
   trovare un algoritmo efficiente che calcoli
   g IN PLACE, ovvero trasformando la rappres.
   di X direttamente in G(X) senza copiarla.
   (X e'rappresentata come una matrice)
   magari e' meglio fermarsi a N=2 o N=3
   Ricordo che all'epoca in cui mi ero cimentato col
   problema avevo trovato una soluzione in O(x^N)
   muovendomi " a scacchiera " ma non ricordo come
   avevo fatto. 
+=+=+=+=+
Esempio:
N=2, n1=n2=3
X=   1 | 2 | 3
    ---+---+---
     4 | 5 | 6
    ---+---+---
     7 | 8 | 9
f(X,(1,1,1))= 1+0+0+2+4=6
f(X,(2,2,2))= 5+2+4+6+8=25
g(X)=
     7 | 11 | 11
    ---+----+---
    17 | 25 | 23
    ---+----+---
    19 | 29 | 23 
=+=+=+=+=+=
Si puo' sadizzare ancora un po' chiedendo di generalizzare
f(X,i) a una funzione che utilizzi tutti i valori di un 
intorno di i e che non sia la "semplice" somma, e chiedendo
di trovare le caratteristiche che una tale f deve avere per
rendere possibile l'algoritmo in place
--Spero di essere stato chiaro, e di non aver fatto errori==
===============================================
Vincenzo Ciancia
Studente del Quarto anno  ( AH AH AH AH AH ...)
Corso di laurea in Informatica
Universita' di Pisa
-----------------------------------------------
Linux e' un regalo
Windows e' solo un pacco
===============================================

 Cosi' come l'ho delirato in una notte di febbre.
Un incubo.
Non ci ho capito niente. Quando riesco a leggerlo magari riesco a
risponderti.
Ma non è che per caso vorresti mappare un numero n-dimensionale in N?
ovvero una cosa del tipo
[a1, a2, a3, ..., an] -> x
e quindi la tua funzione sarebbe:
f([a1, a2, a3, ..., an] ) = x
e l'inversa
g(x) = [a1, a2, a3, ..., an]
Se è questo posso rispolverare i libri, se no devi pazientare che riesca a
trovare il tempo (e soprattutto la voglia) di capire tutta la tua lettera.
--
Alessandro Monti