[obm-l] Re: Contagem de grupinhos de pontos - Análise Numérica

["Bruno França dos Reis" <bfreis@xxxxxxxxx>]

Pessoal,
se interessar a alguém: descobri um método suficientemente eficaz (acho que é o melhor possível para meu caso), usando uma outra propriedade desses números. Na verdade, para cada conjunto de números, eu os tenho numa certa ordem (logo, seria mais correto falar em seqüência de números). Esta ordem apresenta uma propriedade: se o primeiro ponto está no k-ésimo sub-intervalo, então os próximos pontos visitarão cada um dos outros sub-intervalos exatamente uma vez antes de haver outro ponto no k-ésimo intervalo.

Assim, meu algoritmo resumiu-se a determinar o ponto seguinte da sequencia suficientemente próximo do primeiro; o índice desse segundo ponto me dá a informação que preciso: a partir dele obtenho diretamente n, a quantidade de sub-intervalos.


Se continuar interessando, explico de onde me surgiu tal problema:
fiz um algoritmo pra desenhar um diagrama de bifurcação, e eu gostaria de saber quanto pontos atrativos existem para cada valor do parâmetro do problema. Os "dados de entrada" do problema que eu mandei no email anterior eram as coordenadas dos pontos que eu usava para plotar o diagrama de bifurcação.

Abraço
Bruno

2008/5/17 Bruno França dos Reis <bfreis@xxxxxxxxx>:

Olá.

Sejam I um intervalo da reta e I_1, ..., I_n, n intervalos disjuntos, todos contidos em I.
Sejam (a_k)_1, ..., (a_k)_(p_k), p_k pontos do intervalo I_k, para k = 1, ..., n.

Meu problema é: dado o conjunto desses números {a_i_j}, quero determinar n. Algumas informações que podemos assumir para simplificar o problema, válidas na maior parte dos casos:
(a) os pontos dentro de um mesmo intervalo I_k estão "bem distribuidos"
(b) os tamanhos dos intervalos I_k são pequenos se comparados às distâncias entre os intervalos.
(c) I está contido em [0, 1]

Para ilustrar, o que eu tenho é mais ou menos isso:
-----------(I_1)-----------(I_2)-----------(I_3)------------

Já tive algumas idéias para resolver o problema, mas elas não me servem pois:
(i) soma{k = 1..n} (p_k) é grande
(ii) e na verdade eu tenho que fazer essa mesma análise para MUITOS conjuntos de pontos {a_i_j} independentes

Para dar as ordens de grandeza com as quais gostaria de trabalhar, tenho uns 2000 conjuntos a determinar seus "n", cada um dos quais com algo como 1000 pontos.

Em outras palavras: preciso de um algoritmo RÁPIDO. Alguém tem alguma idéia? Alguém já viu isso e poderia me indicar qualquer referência?

Alguns problemas que podemos encontrar: AS VEZES, há alguns intervalos I_k MUITO próximos (isto é: existe k tal que a distância entre I_k e I_(k+1) é pequena se comparada ao tamanho de cada um desses intervalos), mas as distâncias entre seus pontos internos é muito menor que a distância entre os intervalos.

Qualquer comentário será bem vindo, estou precisando de idéias mesmo que não sejam otimizadas.


Obrigado,
Bruno


--
Bruno FRANÇA DOS REIS

msn: brunoreis666@xxxxxxxxxxx
skype: brunoreis666
tel: +33 (0)6 28 43 42 16

e^(pi*i)+1=0

-- 
Bruno FRANÇA DOS REIS

msn: brunoreis666@xxxxxxxxxxx
skype: brunoreis666
tel: +33 (0)6 28 43 42 16

e^(pi*i)+1=0