31
edits
Changes
Técnicas Avançadas de Contagem (view source)
Revision as of 08:58, 2 December 2015
, 08:58, 2 December 2015no edit summary
'''2.4. Relações de divisão dividir e conquerconquistar'''
Um bom exemplo de relações de divisão dividir e conquer conquistar é a fornecida pelo algoritmo de busca binária. Aqui, vamos considerar uma aplicação prática deste algoritmo em uma implementação de uma busca binária em uma lista ordenada de números inteiros. O algoritmo procura por chave no IList.
BinSearch := proc(ilist::list(integer), key::integer)
Infelizmente para Socks, o nosso programa funcionou muito bem.
Vamos agora fazer a análise do algoritmo para ver como relações de recorrência divide and conquer são geradas. Em geral, uma relação de recorrência do tipo dive and conquer dividir e conquistar tem a forma
<math> r_} {n = a r_ {n / K} + b </math>
para algumas constantes a, K e b. Agora, a rotina Maple rSolve não tem absolutamente nenhuma dificuldade para lidar com até mesmo o tipo mais geral de relação divide and conquerdividir e conquistar.
rSolve (r (n) = a * r (n / k) + b, r (n));
Subs (b = 2,%);
simplify(%);
'''4. Funções geradoras'''
Funções geradoras são ferramentas poderosas para modelar conjuntos de objetos e suas construções. Por exemplo, se um conjunto de objetos é construído a partir de dois outros através da realização de um produto cartesiano de dois conjuntos subjacentes, em seguida, a função geradora para o novo conjunto é muitas vezes apenas o produto das funções geradoras pelos dois conjuntos subjacentes. Assim, saber como um conjunto é construído pode nos ajudar a construir a sua função geradora.
Se você pensar nas funções geradoras como polinômios. Em seguida, cada objeto do conjunto original está representado nesta expansão do produto dos dois polinômios por um monômio como <math> x ^ 5</math>. Várias combinações diferentes pode levar a um <math> x ^ 5</math>. O coeficiente de <math> x ^ 5</math> na função geradora expandido indica o número de tais objetos no novo conjunto.
Os coeficientes da função geradora expandida forma uma sequência de números - o número de objetos em seu conjunto de cada tamanho. Assim, muitas vezes nos referimos a uma função geradora como a função geradora para a sequência --- seus coeficientes. Em particular, tais sequências também podem ser descritas por relações de recorrência. Aqui, vamos discutir como usar as funções geradoras para nos ajudar a resolver essas relações de recorrência.
A ''''função geradora'''' <math> g(x)</math> para uma sequência <math>\ r_ {{n} \}</math> é a série de potência formal
<math>\ sum_ {k = 0} ^ {\ infty} r_ {k} x ^ {k} = r_ {0} + r_ {1} x + r_ {2} x ^ {2} + r_ {3} x ^ {3} + \ cdots + r_ {n} x ^ {n} + \ cdots </math>
Ele é chamado formal, porque não estamos mesmo interessados em avaliá-lo como uma função de x. Todo o nosso foco está em encontrar fórmulas para seus coeficientes. Em particular, isto significa que não há problemas de convergência a serem investigados.
Maple fornece extensas habilidades para a manipulação de séries de potências formais (ou seja, as funções geradoras). Pertencem ao pacote powseries do Maple, de modo que parar acessa-las, você deve carregar este pacote.
with (powseries);
A primeira coisa que precisamos fazer é aprender a criar uma série de potência. Para isso, o Maple fornece a função '''powcreate'''. Ela toma como argumentos uma seqüência de equações que definem o coeficiente geral. As equações especificam uma maneira de calcular o coeficiente kth em <math> \ sum_ {k = 0} ^ {\ infty} a_ {k} x ^ {k}</math>. Por exemplo, a função exponencial formal, o que tem de representação de série de potência
<math>\ exp (s) = \ sum_ {n = 0} ^ {\ infty} \ frac {s ^ {n}} {n!}</math>
pode ser criado em Maple emitindo a chamada
powcreate (e (n) = 1 / N!);