[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Conjuntos finitos
No livro "Introduction to Algorithms", Cormen et al, na parte que fala
sobre fluxo máximo em grafos, ele utiliza, por exemplo, f(X,Y) onde X
e Y são conjuntos de vértices do grafo e f é o somatório dos fluxos
dos vértices que partem do conjunto X para aqueles no conjunto Y.
Geralmente, em uma rede, um grafo dirigido com pesos nas arestas, na
qual se quer encontrar o fluxo máximo, define-se um vértice como a
origem e outro como destino. Caso seja necessário desconsiderar esses
vértices no cálculo do fluxo poderíamos representar por f(X-o, Y-d),
onde "o" e "d" são origem e destino, respectivamente, e X-o seria o
conjunto X sem o elemento "o" e Y-d o conjunto Y sem o elemento "d",
ou seja, {X}-{o} e {Y}-{d}.
Esse seria um exemplo de utilizar conjuntos e somatórios em uma única
representação através de função.
On 10/29/07, Rodrigo Renji <rodrigo.uff.math@xxxxxxxxx> wrote:
> Olá Marcelo \o/
>
> vou tentar explicar o que eu quis dizer sobre somatório em conjuntos
> finitos com relação de ordem, mas primeiro vou falar sobre minha
> opnião sobre o somatorio comum que aparece na matemática
>
> costuma-se definir
> somatorio k=0 até n f(k)= f(0)+...+f(n),
>
> só que eu me sinto meio desconfortavel usando esses pontinhos, acho
> meio informal, apesar que dá a idéia do que é o somatório, da uma
> noção intuitiva do que acontece, porém eu prefiro não usar esse modo e
> sim, definir da seguinte maneira
>
> somatorio k=0 até n f(k)= [somatorio k=0 até n-1 f(k)] +f(n)
> se n>0, n natural e se n=0
>
> somatorio k=0 até 0 f(k)=f(0)
> , i,e repito o processo tirando o ultimo termo do somatorio até chegar
> no termo minimo, o mesmo faço para definir somatorio com limite
> inferior inteiro e superior inteiro
>
>
> somatorio k=a até a+p f(k)= [somatorio k=a até a+p-1 f(k)] +f(a+p)
> se p>0, p natural e se p=0
>
> somatorio k=a até a f(k)=f(a)
>
> com a inteiro. se a inteiro então a+p=b um número inteiro maior ou igual à "a"
> então fica definido para mim o somatorio com limites nos inteiros.
>
> para provar alguns teoremas de somatorio me parece util definir
> somatorio k=b até a f(k) =0 se a>b (i.e se o limite superior é menor
> que o limite inferior)
>
> com essas definições é possivel demonstrar algumas propriedades de
> somatorios como
>
> somatorio k=a até b f(k) =somatorio k=a+p até b+p f(k-p)
> somatorio k=a até b f(k)=somatorio k=-b até -a f(-k)
> somatorio k=a até b f(k)=somatorio k=a até s f(k) +somatorio k=s+1 até b f(k)
> se s>=a e b>=s+1. propriedade que chamo de abertura de somatorios
> ela é equivalente a definição que postei acima de somatorio, a partir
> de uma se prova outra e vice e versa (porém essa de abertura é mais
> geral de certo modo)
>
> mas ai estava pensando em definir somatorios em outros conjuntos
> finitos, por exemplo, definir formalmente somatorio sobre primos em
> um intervalo etc...
> na verdade eu me divirto um pouco fazendo essas coisas hehe, as vezes
> procurar algo já pronto para mim é o mesmo que contar o final de um
> filme, depois eu volto a postar mais sobre, e as idéias que estou
> tendo sobre esse assunto
>
> abraços
>
> Em 29/10/07, Marcelo Salhab Brogliato<msbrogli@xxxxxxxxx> escreveu:
> > Olá Rodrigo,
> >
> > pensando sobre o que você disse... pelo que sei a notação de conjuntos é
> > geral..
> > { a } é um conjunto finito cuja cardinalidade é 1... e "a" é qualquer
> > coisa.. hehe (bem informal)
> > sobre retirar os elementos, acredito que você pode fazer assim:
> > Seja A um conjunto tal que |A| = n.
> > Como A é finito e enumerável, vamos definir uma bijecao f : I_n -> A
> > onde I_n = { 1, 2, 3, ..., n }.
> > façamos: A_0 = A ... A_k = A_(k-1) \ { f(k) }
> > deste modo, temos: A_1 = A_0 \ { f(1) } ... A_2 = A_1 \ { f(2) }..
> > vamos chegar em A_n = {} ...
> >
> > Agora, não entendi o que você quer definir sobre o somatório em conjuntos
> > finitos com
> > relação de ordem... :))
> >
> > um abraço,
> > Salhab
> >
> >
> >
> >
> > On 10/29/07, Rodrigo Renji <rodrigo.uff.math@xxxxxxxxx> wrote:
> > >
> > > Marcelo, obrigado , a fórmula está estranha pois foi eu formulei
> > > hehehe, e que eu estava pensando no seguinte, se temos um conjunto de
> > > números com uma relação de ordem finito ele possui um máximo e se
> > > formos tirando o máximo do conjunto em cada etapa, se ele é finito
> > > chega "uma hora" que ele se torna o conjunto vazio
> > > ex:
> > > {0, 2.2 ,3}
> > > tira o máximo (3)
> > > { 0, 2.2}
> > > tira o maximo (2.2)
> > > {0}
> > > tira o maximo 0
> > > {}
> > >
> > > acho que o mesmo acontece quando vamos tirando o minimo do conjunto
> > > não é? se ele é um conjunto de numeros com relação de ordem e finito,
> > > chega uma hora que ficamos com o conjunto vazio (só pra explicar o que
> > > eu estava/estou pensando sobre essa questão). A principio estava
> > > pensando que valia pra qualquer conjunto finito, mas é obvio que não
> > > ( conjunto {a} a sendo a letra do alfabeto , é um conjunto finito não
> > > é?, tendo apenas um elemento, ou essa nomenclatura é apenas para
> > > conjuntos númericos ?)
> > >
> > >
> > > esses conceitos eu estou usando para tentar definir formalmente
> > > somatorio sobre um conjunto finito de numeros com relação de ordem.
> > >
> > > abraços
> > > Em 27/10/07, Marcelo Salhab Brogliato<msbrogli@xxxxxxxxx> escreveu:
> > > > Olá Rodrigo,
> > > >
> > > > achei a formulação um tanto estranha... nao acho correto dizer: "Existe
> > n
> > > > tal que S(n) = vazio"... pois n está definido na questão..
> > > > acredito que deveria ser: "Se S(n) = vazio, entao |S(n)| = n ?"
> > > >
> > > > |S(0)| = |S|
> > > > |S(1)| = |S(0) - {max S(n)}| .. como {max S(n)} E S(0), e |{max S(n)}| =
> > 1,
> > > > entao: |S(1)| = |S| - 1
> > > > por inducao: |S(k)| = |S| - k
> > > >
> > > > vamos supor que |S| > n, entao |S(n)| > 0, absurdo! Pois |S(n)| = 0 por
> > > > hipótese..
> > > > vamos supor que |S| < n, entao |S(|S|)| = 0... assim: |S(n)| = 0
> > > > vamos supor que |S| = n, entao |S(n)| = 0... assim: |S(n)| = 0
> > > >
> > > > logo, podemos concluir que S é finito, e que a cardinalidade S é menor
> > ou
> > > > igual a n...
> > > >
> > > > abraços,
> > > > Salhab
> > > >
> > > >
> > > >
> > > > On 10/27/07, Rodrigo Renji <rodrigo.uff.math@xxxxxxxxx> wrote:
> > > > >
> > > > > Seja
> > > > > S um conjunto
> > > > > defino
> > > > > (n natural)
> > > > >
> > > > > S(n+1)=S(n)-{max S(n)}
> > > > > S(0)=S
> > > > >
> > > > > (se S(n) possui máximo) [prestar atenção nessa condição]
> > > > >
> > > > > Se existe n, tal que s(n)=vazio
> > > > > então n é finito e tem n elementos?
> > > > >
> > > > > e se um conjunto é finito vale a propriedade acima?
> > > > > (relaçao de se e somente se).
--
Henrique
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================