[obm-l] Armazenamento de Matriz em Vetor

[Henrique Rennó]

Olá pessoal da lista!!!

Estou com um problema para representar uma matriz na forma de um
vetor. Suponha que tenhamos uma matriz diagonal inferior:

1 0 0 0 0
6 3 0 0 0
4 2 6 0 0
8 3 7 1 0
9 5 2 7 4

Não há necessidade de representar essa matriz armazenando todos os
elementos, pois sabemos que acima da diagonal principal todos os
elementos são zero. Dessa forma, podemos armazenar apenas os elementos
da diagonal principal e da parte inferior seguindo a seguinte regra:

pos = [(1+i)*i]/2 + j

onde pos é a posição no vetor e a posição na matriz inicia em i = 0, j
= 0 (i = linha, j = coluna). Uma matriz de dimensão N tem seus
elementos na forma:

0,0 0,1 0,2 ... 0,N-1
1,0 1,1 1,2 ... 1,N-1
  .....
  .....
  .....
N-1,0 N-1,1 ... N-1,N-1

Por exemplo, se i = 3 e j = 2, pos seria 8 e o elemento 7 estaria
nesta posição. (O vetor se inicia na posição zero - 0).

O problema é saber uma forma de, conhecendo pos (a posição do elemento
no vetor), saber quais os valores de i e j (linha e coluna) do
elemento na matriz.

Estou com essa dúvida porque estou desenvolvendo um programa em C para
mexer com matrizes que estão nessa forma (os elementos acima da
diagonal superior são todos zeros) e para dimensões maiores, por
exemplo 1, teríamos um número imenso de zeros ocupando memória sem
necessidade.

Obs: caso a matriz possua todos os elementos nulos abaixo da diagonal
principal, acredito que trocando i por j e j por i na igualdade acima
para o cálculo de pos funciona normalmente, mas o que preciso mesmo
não é este caso.

Agradeço a atenção de todos,

Abraços!!!

--
Henrique

=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=

[obm-l] Re: Armazenamento de Matriz em Vetor

[Henrique Rennó]

Só acrescentando uma explicação.

Encontrei a igualdade -- pos = [(1+i)*i]/2 + j -- utilizando a soma de
uma progressão aritmética composta pelos elementos que estão antes da
linha do elemento a ser armazenado e depois somando o valor da coluna.
No caso do elemento 7 na linha 3 (i = 3), coluna 2 (j = 2), a PA é
1,2,3 (a quantidade de elementos das linhas anteriores) e a soma
fornece quantos elementos existem antes da linha que estou a calcular
a posição, no caso 3. Em seguida, soma-se o valor da coluna para achar
qual o deslocamento horizontal do elemento na matriz.

Novamente agradeço a atenção,

Abraços!!!

--
Henrique

=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=

Re: [obm-l] Anal. Comb. do ITA

[Ronaldo Luiz Alonso]

Sugestao: Note que
     c(n,2) = n*(n-1)/2  
dá o número de diagonais (combinações c/ 2 pontos).
    c(n,3) = n(n-1)(n-2) /6  dá 
o número total de triângulos. (T)
 
    Qual é o número de triangulos 
que tem dois lados do polígono? (A)
 -- considere os lados 
consecutivos.
    Qual é o número de triangulos 
que tem um lado do polígono? (B)
    -- considere os lados não 
consecutivos.
 
(faça um desenho que ajuda).   

P triangulossem nenhum lado do poligono 
=  T - A - B.
No caso do problema apenas UM polígono 
satisfaz a condição    P = 
2n.    
  
   Acho que é isso.  Alguém deve 
resolver ... :)

  - Original Message - 
  From: 
  gustavo 
  To: obm-l@mat.puc-rio.br 
  Sent: Monday, April 10, 2006 10:35 
  PM
  Subject: [obm-l] Anal. Comb. do ITA
  
  Quem puder ajudar ,agradeço desde já 
  !!
   
  (ITA)Considere (P) um polígono regular de n 
  lados. Suponha que os vértices de (P) determinam 2n triângulos , cujos lados 
  não são lados de (P). O Valor de n é ?    SOL 
  8

[obm-l] Palestra do Prof. Nicolau no Ciência as S eis e Meia

[Olimpiada Brasileira de Matematica]

DIVULGAÇÃO


Caros membros da lista de discussão e sócios da AOBM que residem ou 
estão no Rio de Janeiro.


O Prof. Nicolau estará oferendo uma palestra no Espaço Cultural da FINEP
Projeto Ciência às Seis e Meia amanhã 12 de Abril às 18:30 horas.


*Nicolau Saldanha – PUC-Rio – 12/04*
*Georg Cantor: ao infinito e além*

Georg Cantor (1845-1918) foi um dos matemáticos mais originais de seu 
tempo.
No início de sua carreira dedicou-se ao estudo de problemas de análise, 
mas foi
estudando conjuntos de números reais que deu sua melhor contribuição à 
matemática.
Ele descobriu no assunto muito mais riqueza do que até então se supunha: 
na verdade,
os conjuntos de Cantor foram os primeiros fractais (muito antes da 
palavra existir) e
continuam sendo dos mais importantes. Depois disso, Cantor passou a 
estudar questões
ainda mais abstratas, que o levaram a criar a teoria dos conjuntos. É de 
Cantor a descoberta
de que existem tipos diferentes de infinitos e de que é impossível fazer 
uma lista
x_0, x_1, x_2, ... de números reais que não deixe a maioria dos números 
reais de fora.
A teoria dos conjuntos de tal forma revolucionou a matemática que 
Hilbert diria:

"Ninguém nos expulsará do paraíso que Cantor criou."

O Espaço Cultural FINEP tem 200 lugares e fica na Praia do Flamengo, 200 -
pilotis (Rio de Janeiro).
Para mais informações, escreva para [EMAIL PROTECTED] 
.



Abraços, Nelly
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=

[obm-l] RE: [obm-l] dúvida fatorial

[Paulo Santa Rita]

Ola Gandhi e demais colegas
desta lista ... OBM-L,

O estudante Paulo Santa Rita agradece a referencia !

O nosso principal problema de contagem e a hipotese do continuo ... qualquer 
que seja um eventual insight sobre contagem, me parece que ele sera tanto 
mais valido e o seu desenvolvimento justificavel se de alguma maneira 
contribuir para o esclarecimento desta questao.


O problema da hipotese do continuo e a primeira tentativa de se lancar 
alguma luz no universo muito pouco conhecido da cardinalidade dos conjuntos 
não enumeraveis. De fato. NO QUE RESPEITA AS SUAS CARDINALIDADES, nos 
podemos dividir os conjuntos em dois grandes blocos : no primeiro bloco, 
colocamos os enumeraveis; no segundo, os não enumeraveis. A rigor, no 
primeiro bloco, há um único conjunto, oconjunto dos numeros naturais. E 
no segundo ?


No conjunto dos conjuntos não enumeraveis existem diversas cardinalidades. 
Em tese, ao menos uma quantidade enumeravel delas, representada pela suposta 
sequencia cantoriana de “alefes”, vale dizer, ALEFE1, ALEFE2, ...  Quando 
nos provamos - digamos, usando o raciocinio da diagonal de cantor - que um 
conjunto e não enumeravel nos estamos apenas exibindo o mais elementar e 
quase único conhecimento sobre esse tipo de conjunto. Em verdade, uma tal 
prova e uma confissao de ignorancia :


“O conjunto e infinito e não admite uma bijecao com N mas eu não sei 
identificar qual alefe corresponde a sua cardinalidade”


Assim, toda prova desta natureza e intrinsecamente incompleta e nos nos 
damos satisfeito simplesmente porque esta ignorancia e tipica do nosso 
tempo. O ideal e que para cada ALEFE da sequencia de Cantor tivessemos um 
CONJUNTO PADRAO e pudessemos provar algo proximo de ...


TEOREMA 1 : A todo conjunto infinito corresponde um único conjunto padrao 
com o qual ele pode manter uma bijecao.


Se esta ideia pudesse ser desenvolvida de alguma forma, N seria o primeiro e 
mais simples conjunto padrao, correspondente a primeira cardinalidade 
infinita. Bom, a priori, isso se parece apenas a um “sonho de uma noite de 
verao” ...


Mas, alem de ser o nosso mais importante problema de contagem, a hipotese do 
continuo  NAO E e uma questao diafana ou transcendente que não guarda 
vinculacao direta com a nossa praxis. Para ver isso claramente, considere :


Um conjunto A de funcoes analiticas, duas a duas distintas,  definidas em C 
( C e o conjunto dos numeros complexos )  tal que para cada z pertencente a 
C fixado,  o conjunto { f(z), f variando em A}  seja enumeravel.


Pergunto : A e um conjunto enumeravel ?

E respondo propondo um exercicio :
Prove que se a HIPOTESE DO CONTINUO e falsa, entao qualquer A sera sempre um 
conjunto enumeravel. Se, porem, a HIPOTESE DO CONTINUO e verdadeira, entao 
existe ao menos um conjunto A não enumeravel.


Maravilha, não ? A HIPOTESE DO CONTINUO, este ser hibrido, tal como a 
quimera da mitologia grega, tem realmente diversas facetas, uma das quais e 
estar proxima a nos sem nos a percebermos ...  mais que isso, como Godel e 
Cohen provaram que a HIPOTESE DO CONTINUO e independente dos demais axiomas 
da Teoria dos conjuntos, vale dizer, tanto faz supormos que ela e verdadeira 
ou falsa, a “natureza” do conjunto A descrito acima se torna altamente 
problematico ( ou emblematico ? )


A) Ele esta definido atraves de uma propiedade clara. Pelo AXIOMA DA 
ESPECIFICACAO (aussonderungsaxion) da teoria dos conjuntos ele esta bem 
definido.
B)  O que se dizer de um conjunto cuja cardinalidade depende de uma 
propriedade   que pode ser valida ou não ? Que e enumeravel e nao-enumravel 
ao mesmo tempo ? No minimo, que não esta bem definido ...


Esses paradoxos sao idiossincrasias tipicas da Teoria dos conjuntos ... E 
nao me parece que qualquer interpretacao particular desta teoria podera ter 
carater peremptorio sobre estas questoes que tangenciamos... Se muito, uma 
particular interpretacao pode ter carater pratico e/ou didatico.


Se conseguissemos visualizar os CONJUNTOS PADROES a que nos referimos acima 
nao so a natureza da cardinalidade do conjunto A ja aludido estaria 
esclarecida como tambem a hipotese do continuo. Ora, se estes padroes 
existem, eles devem emergir da analise do processo de contagem... Deve 
existir, portanto,  alguma propriedade da contagem que ainda nao percebemos 
e que, trazida a plena luz, nos permitira ver estes padroes.


Uma das construcoes bem conhecida dos numeros naturais parte do CONJUNTO 
VAZIO.


Nos colocamos 0={}. A seguir, 1={0}={{}}. E mais : 2={0,1}={{},{{}}} e assim 
sucessivamente. Todo numero natural sera igual ao conjunto dos seus 
predecessores ( vEJA : Paul Halmos, NAIVE SET THEORY, SPRINGER VERLAG ). 
Existe um pressuposto nesta construcao. Qual seria ?


EXISTE UM UNICO CONJUNTO VAZIO

Este pressuposto e consistente com a interpretacao combinatoria de 
BINOM(N,0). Nos colocamos:


BINOM(N,0)=1

Pois de um conjunto com N elementos so podemos tirar UM UNICO  conjunto com 
0 elementos, o conjunto vazio, 

[obm-l] Desigualdade com substituição trigonométri ca

[Dymitri Cardoso Leão]

Inegavelmente, as substituição trigonométricas em certos casos são 
ferramentas poderosíssimas.
Mas gostaria de saber até que ponto só há solução utilizando as mesmas. 
Vejam o exemplo abaixo, que gerou minha dúvida:


* Mostre que, dentre quaisquer quatro reais distintos X1,X2,X3,X4 no 
intervalo (0,1], existem pelo menos dois Xi,Xj que satisfazem a desigualdade 
a seguir:


0 < Xi.sqrt(1-Xj²) - Xj.sqrt(1-Xi²) < 1/2.

obs: Notações- sqrt(x) -> Raíz quadrada de x; >= -> maior que ou igual a, 
etc...


A seguir, vou mostrar uma solução com substituição trigonométrica:

Solução 1:0 < X1,X2,X3,X4 <= 1
 0º < a1,a2,a3,a4 <= 90º  (os "ai" são todos distintos também)

X1 = sen(a1)
X2 = sen(a2)
X3 = sen(a3)
X4 = sen(a4)

Vamos dividir o intervalo (0º, 90º] em três sub-intervalos, que são (0,30º], 
(30º,60º], (60º, 90º]. Pelo princípio da casa dos pombos, há dois números 
dentro de um mesmo sub-intervalo, ou seja,


  0º < ai - aj < 30º , mas xi sen ai -> sqrt(1-xi²) = cos(ai); xj = senj -> 
sqrt(1-xj²) = cosj.


Aplicado a função seno na desigualdade acima, 0 < sen(ai).cos(aj) - 
sen(aj).cos(ai) < 1/2 ->


0 < Xi.sqrt(1-Xj²) - Xj.sqrt(1-Xi²) < 1/2 (c.q.d)


Solução 2: Na verdade, esta foi a primeira solução que tentei. Não usei 
trigonometria, e fui construindo a desigualdade passo a passo no braço (pra 
que isso? hehehe). Analogamente, dividi em 3 sub-intervalos, mas não 
consegui provar no 3º. A solução ficou um pouco grande pra digitar, mas
eu publiquei na internet: 
http://dymitri.leao.vila.bol.com.br/desigualdade.htm.

Obs: Lá na solução do site, eu botei o intervalo [0,1], mas é mesmo (0,1]!

Gostaria de saber se tem como resolver sem trigonometria, mais ou menos da 
forma como eu publiquei no site acima, ou se a substituição era realmente a 
chave da questão.



Atenciosamente, Dymitri Cardoso Leão.

_
Inscreva-se no programa beta do novo Windows Live Mail e seja um dos 
primeiros a testar as novidades. Saiba mais: 
http://www.ideas.live.com/programpage.aspx?versionId=5d21c51a-b161-4314-9b0e-4911fb2b2e6d


=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=

[obm-l] duvida

[Marcus]

Eu gostaria de
ajuda nesses  três problemas, obrigado.

 

Resolver

a) 2cos2[(x2+x)/6]
= 2x +2-x

b) senx = x2+x
+8

 

 

Find ,
where a is real number.

 

 

[obm-l] divisibilidade

[Júnior]

Sejam a, b, c números inteiros tais que 100a + 10b + c seja divisível
por 109. Mostre que (9a-c)^2 +9b^2 também é divisível por 109.

Júnior.

Re: [obm-l] Armazenamento de Matriz em Vetor

[Ojesed Mirror]

Para calcular a linha use i=(sqrt(8*pos + 9)-3)/2 e arredonde para cima.
Para calcular a coluna use a formula que calcula pos.

Ojesed.

- Original Message - 
From: "Henrique Rennó" <[EMAIL PROTECTED]>

To: 
Sent: Tuesday, April 11, 2006 11:11 AM
Subject: [obm-l] Armazenamento de Matriz em Vetor


Olá pessoal da lista!!!

Estou com um problema para representar uma matriz na forma de um
vetor. Suponha que tenhamos uma matriz diagonal inferior:

1 0 0 0 0
6 3 0 0 0
4 2 6 0 0
8 3 7 1 0
9 5 2 7 4

Não há necessidade de representar essa matriz armazenando todos os
elementos, pois sabemos que acima da diagonal principal todos os
elementos são zero. Dessa forma, podemos armazenar apenas os elementos
da diagonal principal e da parte inferior seguindo a seguinte regra:

pos = [(1+i)*i]/2 + j

onde pos é a posição no vetor e a posição na matriz inicia em i = 0, j
= 0 (i = linha, j = coluna). Uma matriz de dimensão N tem seus
elementos na forma:

0,0 0,1 0,2 ... 0,N-1
1,0 1,1 1,2 ... 1,N-1
 .....
 .....
 .....
N-1,0 N-1,1 ... N-1,N-1

Por exemplo, se i = 3 e j = 2, pos seria 8 e o elemento 7 estaria
nesta posição. (O vetor se inicia na posição zero - 0).

O problema é saber uma forma de, conhecendo pos (a posição do elemento
no vetor), saber quais os valores de i e j (linha e coluna) do
elemento na matriz.

Estou com essa dúvida porque estou desenvolvendo um programa em C para
mexer com matrizes que estão nessa forma (os elementos acima da
diagonal superior são todos zeros) e para dimensões maiores, por
exemplo 1, teríamos um número imenso de zeros ocupando memória sem
necessidade.

Obs: caso a matriz possua todos os elementos nulos abaixo da diagonal
principal, acredito que trocando i por j e j por i na igualdade acima
para o cálculo de pos funciona normalmente, mas o que preciso mesmo
não é este caso.

Agradeço a atenção de todos,

Abraços!!!

--
Henrique

=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=


--
No virus found in this incoming message.
Checked by AVG Free Edition.
Version: 7.1.385 / Virus Database: 268.4.1/307 - Release Date: 10/4/2006


=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=

[obm-l] Livro Geometria Plana e Espacial

[Bruna Carvalho]

Alguem poderia me indicar alguns livros, autores
bons para Geometria Plana e Espacial, sem ser os livros da coleção
fundamentos de matemática elementar.