90
edits
Changes
Created page with "\usepackage{amsmath} A contagem é fundamental para o estudo da matemática discreta, a complexidade de algoritmos, combinatórios, e alguns ramos da álgebra tais como a teor..."
\usepackage{amsmath}
A contagem é fundamental para o estudo da matemática discreta, a complexidade de algoritmos, combinatórios, e alguns ramos da álgebra tais como a teoria do grupo finito. Este capítulo apresenta uma variedade de técnicas que estão disponíveis no Maple para contar uma coleção diversa de objetos discretos, incluindo combinações e permutações de conjuntos finitos. Objetos podem ser contados usando fórmulas ou outros algoritmos, ou listando-os e observando diretamente o tamanho da lista. A última abordagem por um número de procedimentos Maple que pode ser usado para gerar estruturas combinatórias.
A maioria dos procedimentos Maple relevantes a este capítulo pertence em um ou dois pacotes. O pacote “combinat” é a parte padrão da versão da biblioteca 3Maple.
Um novo pacote “combstruct” está disponível como uma biblioteca compartilhada para MapleV, versão 3, e é um pacote padrão da versão 4. Você pode acessar os serviços oferecidos por qualquer um desses pacotes usando o comando “with” para carregá-lo na sua sessão Maple. (Se você está usando Maple V, versão 3, você também deve colocar with(share) antes de digitar with(combstruct)).
É útil saber que o pacote combstruct, enquanto provê uma grande variedade de procedimentos, organiza algumas das funções básicas em grupos relacionados a um objeto combinatório particular (como, por exemplo, combinações ou partições). Para muitos tipos de objetos combinatórios, existem procedimentos Maple para fazer as seguintes operações.
# Você pode construir todos os objetos daquele tipo associado a um inteiro dado. Ao procedimento para fazer isso é geralmente dado um nome refletindo o tipo de objeto. (Por exemplo, “permute” and “partitions”.)
# Você pode contar todos os objetos daquele tipo associado a um inteiro dado. Aqueles procedimentos geralmente começão com a string “numb” e são completados por uma abreviaçãodo tipo de objeto sendo contado. (Por exemplo, “numbperm” e “numbpart”.)
# Você pode gerar um objeto aleatório daquele tipo associado a um inteiro dado. Uma abreviação do tipo de objeto sendo gerado, prefixado com a string “rand” é como essas rotinas são normalmente nomeadas. (Por exemplo, “randperm” e “randpart”.)
Claro, também existem muitas outras funções que não se encaixam neste esquema.
===1. Funções Maple relevantes===
O pacote “combinat” contém muitas funções pertinentes à contagem e geração de estruturas combinatórias. A lista de funções neste pacote é:
'''''with(combinat);'''''
Existe outro pacote, “combstruct”, disponível no Maple V, versão 4, que também lida com estruturas combinatórias. A maior parte do que este pacote faz está além do escopo deste livro, mas algumas de suas funções expandem o que o pacote “combinat” faz. O pacote “combstruct” fornece funções “interstructs”.
'''count''' Para contar o número de objetos de um dado tamanho<br />
'''draw''' Para gerar um objeto aleatório de um dado tamanho<br />
'''allstructs''' Para gerar todos os objetos de um dado tamanho<br />
'''iterstructs''' Para gerar a “próxima” estrutura de um dado tamanho<br />
As estruturas relevantes que “combstruct” pode lidar são permutação, combinação/subconjunto, partição.
Para acessar os serviços fornecidos pelo pacote “combstruct”, digite:
'''''with(combstruct);'''''
Se você estiver usando a versão 3 do Maple, primeiramente você terá que utilizar o comando “with(share)”, já que o pacote “combstruct” é parte da biblioteca na versão 3.
As funções no pacote “combinat” para combinações são “numbcomb”, “choose”, e “randcomb”. Este é o número de formas de escolher duas frutas a partir de uma maçã, uma laranja e uma pera.
'''''numbcomb([apple, orange, pear], 2);'''''
Aqui estão as possíveis escolhas:
'''''choose([apple, orange, pear], 2);'''''
A função “numbcomb” conta o número de combinações (ou r-combinações) de um conjunto. A função “choose” lista as combinações. Portanto sempre existirão elementos “numbcomb” listados por “choose”.
'''''nops(%);'''''
E se tivermos duas maçãs e nenhuma pêra (um exemplo com elementos indistinguíveis):
'''''numbcomb([apple, apple, orange],2);'''''
Com as escolhas:
'''''choose([apple, apple, orange],2);'''''
Se nós não fornecemos o segundo argumento, todas as combinações possíveis de todos os tamanhos possíveis são consideradas.
'''''numbcomb([apple, apple, orange]);'''''<br />
'''''choose([apple, apple, orange]);'''''
Nós também podemos escolher combinações aleatórias.
'''''randcomb([chocolate, vanilla, cookiedough],2);'''''
'''''randcomb(5,3);'''''
Neste exemplo, o '''5''' representa o conjunto '''''<math>{1, 2, 3, 4, 5}</math>'''''.
Usando ''combstruct'', nós resolveríamos os problemas acima da seguinte forma:
'''''count(Combination([apple,orange,pear]),size=2);'''''
'''''allstructs(Combination([apple,orange,pear]), size=2);'''''
'''''draw(Combination([chocolate,vanilla,cookiedough]),size=2);'''''
Coeficientes binomiais podem ser calculados tanto chamando a função ''numbcomb'' como um inteiro como primeiro argumento,
'''''numbcomb(10,5);'''''
ou nós podemos calcular '''''<math>C(n, r)</math>''''', usando a função ''binomial''. Então nós resolvemos o exemplo 7 na seção 4.3 da seguinte forma:
'''''binomial(10,5);'''''
Quando '''n''' e '''r''' são inteiros não negativos e '''''<math>r \leq n</math>''''', ''binomial'' e ''numbcomb'' se comportam de forma idêntica. O procedimento ''binomial'' é mais geral, e expande a definição dos coeficientes binomiais. Não vamos discutir seu uso mais geral aqui.
A contagem é fundamental para o estudo da matemática discreta, a complexidade de algoritmos, combinatórios, e alguns ramos da álgebra tais como a teoria do grupo finito. Este capítulo apresenta uma variedade de técnicas que estão disponíveis no Maple para contar uma coleção diversa de objetos discretos, incluindo combinações e permutações de conjuntos finitos. Objetos podem ser contados usando fórmulas ou outros algoritmos, ou listando-os e observando diretamente o tamanho da lista. A última abordagem por um número de procedimentos Maple que pode ser usado para gerar estruturas combinatórias.
A maioria dos procedimentos Maple relevantes a este capítulo pertence em um ou dois pacotes. O pacote “combinat” é a parte padrão da versão da biblioteca 3Maple.
Um novo pacote “combstruct” está disponível como uma biblioteca compartilhada para MapleV, versão 3, e é um pacote padrão da versão 4. Você pode acessar os serviços oferecidos por qualquer um desses pacotes usando o comando “with” para carregá-lo na sua sessão Maple. (Se você está usando Maple V, versão 3, você também deve colocar with(share) antes de digitar with(combstruct)).
É útil saber que o pacote combstruct, enquanto provê uma grande variedade de procedimentos, organiza algumas das funções básicas em grupos relacionados a um objeto combinatório particular (como, por exemplo, combinações ou partições). Para muitos tipos de objetos combinatórios, existem procedimentos Maple para fazer as seguintes operações.
# Você pode construir todos os objetos daquele tipo associado a um inteiro dado. Ao procedimento para fazer isso é geralmente dado um nome refletindo o tipo de objeto. (Por exemplo, “permute” and “partitions”.)
# Você pode contar todos os objetos daquele tipo associado a um inteiro dado. Aqueles procedimentos geralmente começão com a string “numb” e são completados por uma abreviaçãodo tipo de objeto sendo contado. (Por exemplo, “numbperm” e “numbpart”.)
# Você pode gerar um objeto aleatório daquele tipo associado a um inteiro dado. Uma abreviação do tipo de objeto sendo gerado, prefixado com a string “rand” é como essas rotinas são normalmente nomeadas. (Por exemplo, “randperm” e “randpart”.)
Claro, também existem muitas outras funções que não se encaixam neste esquema.
===1. Funções Maple relevantes===
O pacote “combinat” contém muitas funções pertinentes à contagem e geração de estruturas combinatórias. A lista de funções neste pacote é:
'''''with(combinat);'''''
Existe outro pacote, “combstruct”, disponível no Maple V, versão 4, que também lida com estruturas combinatórias. A maior parte do que este pacote faz está além do escopo deste livro, mas algumas de suas funções expandem o que o pacote “combinat” faz. O pacote “combstruct” fornece funções “interstructs”.
'''count''' Para contar o número de objetos de um dado tamanho<br />
'''draw''' Para gerar um objeto aleatório de um dado tamanho<br />
'''allstructs''' Para gerar todos os objetos de um dado tamanho<br />
'''iterstructs''' Para gerar a “próxima” estrutura de um dado tamanho<br />
As estruturas relevantes que “combstruct” pode lidar são permutação, combinação/subconjunto, partição.
Para acessar os serviços fornecidos pelo pacote “combstruct”, digite:
'''''with(combstruct);'''''
Se você estiver usando a versão 3 do Maple, primeiramente você terá que utilizar o comando “with(share)”, já que o pacote “combstruct” é parte da biblioteca na versão 3.
As funções no pacote “combinat” para combinações são “numbcomb”, “choose”, e “randcomb”. Este é o número de formas de escolher duas frutas a partir de uma maçã, uma laranja e uma pera.
'''''numbcomb([apple, orange, pear], 2);'''''
Aqui estão as possíveis escolhas:
'''''choose([apple, orange, pear], 2);'''''
A função “numbcomb” conta o número de combinações (ou r-combinações) de um conjunto. A função “choose” lista as combinações. Portanto sempre existirão elementos “numbcomb” listados por “choose”.
'''''nops(%);'''''
E se tivermos duas maçãs e nenhuma pêra (um exemplo com elementos indistinguíveis):
'''''numbcomb([apple, apple, orange],2);'''''
Com as escolhas:
'''''choose([apple, apple, orange],2);'''''
Se nós não fornecemos o segundo argumento, todas as combinações possíveis de todos os tamanhos possíveis são consideradas.
'''''numbcomb([apple, apple, orange]);'''''<br />
'''''choose([apple, apple, orange]);'''''
Nós também podemos escolher combinações aleatórias.
'''''randcomb([chocolate, vanilla, cookiedough],2);'''''
'''''randcomb(5,3);'''''
Neste exemplo, o '''5''' representa o conjunto '''''<math>{1, 2, 3, 4, 5}</math>'''''.
Usando ''combstruct'', nós resolveríamos os problemas acima da seguinte forma:
'''''count(Combination([apple,orange,pear]),size=2);'''''
'''''allstructs(Combination([apple,orange,pear]), size=2);'''''
'''''draw(Combination([chocolate,vanilla,cookiedough]),size=2);'''''
Coeficientes binomiais podem ser calculados tanto chamando a função ''numbcomb'' como um inteiro como primeiro argumento,
'''''numbcomb(10,5);'''''
ou nós podemos calcular '''''<math>C(n, r)</math>''''', usando a função ''binomial''. Então nós resolvemos o exemplo 7 na seção 4.3 da seguinte forma:
'''''binomial(10,5);'''''
Quando '''n''' e '''r''' são inteiros não negativos e '''''<math>r \leq n</math>''''', ''binomial'' e ''numbcomb'' se comportam de forma idêntica. O procedimento ''binomial'' é mais geral, e expande a definição dos coeficientes binomiais. Não vamos discutir seu uso mais geral aqui.