61
edits
Changes
Jump to navigation
Jump to search
##'''Indução Matemática'''
###'''Definições Recursiva e Interativa'''As funções do maple podem ser definidas tanto processualmente (usando a função '''proc''') como explicitamente (usando a notação '''->'''), cada um desses métodos envolve meios interativos e recursivos de definição. Iniciamos nosso estudo, usando a função “'''->” ''' do maple. Se nós quiséssemos definir uma função polinomial '''A(n)= 3n³ + 41n²- 3n + 101''' nós usaríamos o seguinte comando:
####'''omputações Computações e Explorações'''
→Introdução
Agora, seguimos para um exemplo mais complexo,no qual o leitor pode confirmar a corretude da simplificação, construindo uma tabela verdade.
O próximo exemplo ilustra a simplificação do 'Modus Ponens'. Primeiro afirmamos que '''p ''' implica '''q ''' e '''p ''' é verdadeiro.
Então simplificamos a expressão booleana
Determinando que '''q ''' e '''p ''' são verdadeiros, como nós já sabíamos que '''p ''' era verdadeiro, nós concluímos que '''q ''' é verdadeiro.
A função '''bsimp''' é um simplificador geral para expressões booleanas construídas usando os operadores booleanos inativos. A função computa uma expressão booleana simplificada equivalente ao seu argumento. Podemos também usar o maple para determinar se uma expressão é uma tautologia através do uso da função tautology oferecida pelo pacote lógico.
Agora confrontamos nosso exemplo final do uso do maple explorando teoremas matemáticos. Neste caso vamos explorar a conjectura de Goldbach: que é, todo inteiro par maior que 4 pode ser expressado como a soma de dois primos.
O maple pode ser usado para auxiliar na elaboração de provas de várias afirmações matemáticas usando a indução matemática. De fato, com o maple como seu assistente, você pode conduzir inteiramente o processo de descoberta e averiguação de forma intuitiva. É provável que entre os primeiros exemplos de indução matemática, encontremos a verificação da fórmula '''1+2+3+...+n = n(n+1)/2''',a soma dos primeiros n inteiros positivos. O maple se adequa para provar fórmulas como essa porque os passos envolvidos numa prova indutiva incluem manipulação simbólica. É possível gerar uma grande quantidade de dados numéricos para serem examinados.
Através da geração de um grande conjunto de dados numéricos de pouca compreensão, eventualmente será possível determinar a fórmula acima. A saída mostra que n² é um pouco menos que o dobro da soma dos n primeiros inteiros para os valores de n testados. Partindo de um padrão, é possível perceber que a fórmula correta é uma função quadrática de '''n''', resolva para encontrar os coeficientes e então teste se esse procedimento produz a fórmula correta.
Uma técnica útil para experimentos semelhantes é gerar listas de pares que consista da sequencia que esteja interessado e de várias possibilidades que você elabore. Para investigar a hipótese de que a fórmula seja quadrática, devemos começar gerando uma lista de pares semelhantes ao seguinte:
Enquanto o lado direito da fórmula é:
Podemos usar o procedimento subs para verificar o passo base da indução; , neste caso o passo base é '''n=1'''
Os resultados coincidem (concordam), então o passo base é estabelecido. Para o passo indutivo, usamos que a fórmula seja válida para '''n=k'''.
Para somar '''k+1 ''' termos, computamos:
Por fim, a fórmula para '''n=k+1 ''' é:
Os resultados coincidem, então o passo indutivo é verificado. A fórmula agora segue por indução matemática. Assim, podemos concluir que enquanto o maple ainda não é capaz de construir provas inteiramente por conta própria, é uma ferramenta muito efetiva para ser usada na construção de provas interativas.
Usando um pouco de manipulação algébrica, vemos que as duas últimas fórmulas são iguais. Isso completa a prova via indução matemática. Concluímos que nosso palpite sobre a fórmula está correto.
Agora, se quiséssemos definir uma função recursivamente, digamos:
Agora, criaremos uma função similar a '''b''', chamada '''f1''', que encontrará os números Fibonacci.
Enquanto a notação '''->''' para funções é conveniente e intuitiva, ela não oferece todas as facilidades para melhoria da eficiência que estão disponíveis no uso do comando '''proc'''. Para forçar o maple a calcular esses valores de forma eficiente, usamos a opção remember para definições de procedimentos afetados pelo uso do proc. Esta opção exige que o maple lembre de qualquer valor para procedimento que já tenha sido computado através do armazenamento destes em uma tabela Fibonacci.
Esse método processual engloba ambos os casos, o caso base (quando '''n <=2''') e os casos indutivos (como na condição “else”). Adicionalmente, o procedimento tem a indicação da função remember, forçando o maple a manter controle sobre quais valores da função já foram encontrados, para que estes sejam diretamente verificados ao invés de serem novamente computados.
Que é comparável às vezes obtidas para '''f2'''. Note que a implementação puramente recursiva '''f1''' não possibilita o uso para '''f2(100)'''. De fato, um bom exercício é mostrar que para fazê-lo, '''f2''' precisaria de aproximadamente '''f2(99)''' chamadas para operar todos os subcasos que surgirem. Mesmo a um bilhão de subcasos por segundo, isso exigiria mais de seis mil anos para sua conclusão.
Nesta seção do material, exploraremos o modo como o maple pode ser usado para resolver as questões 4,5 e 8 da seção “computações e explorações” do livro.
#*Quantos pares de números primos podem ser encontrados?
Para determinar quantos pares de números primos existem, usaremos o pacote '''numtheory''' do maple, que contém as funções nextprime, '''prevprime''' e '''ithprime'''
Agora, após formada uma lista de primos, queremos extrair quaisquer pares de primos que ocorram nessa lista.
Parece não haver um padrão óbvio ocorrendo.
#**Determine quais números Fibonacci são divisíveis por 5, quais são divisíveis por 7 e quais são divisíveis por 111. Prove que suas conjecturas estão corretas.
Primeiro vamos gerar dados para trabalhá-los (manipulá-los).
Você pode tentar averiguar se esse padrão persiste, substituindo 500 na definição de '''fib_list''' por números muito maiores. (o teste da divisibilidade por 111, nós deixamos pra você).
#***A notória conjectura '''3x + 1''' (também conhecida como conjectura de Collatz e por vários outros nomes) afirma que: independente de qual inteiro x você escolha para iniciar, em iteração com a função '''f(x)''', onde '''f(x) = x/2''', se '''x''' é par e '''f(x) = 3x+1''' se '''x''' é ímpar, sempre produz o inteiro 1. Cheque essa conjectura para tantos inteiros positivos possíveis.
Agora escrevemos uma função que fará a iteração da função Collatz até que o valor obtido seja igual a 1, nós incluímos uma variável 'count' por dois motivos: Primeiro, queremos ter uma idéia de quanto tempo leva para que as iterações estabilizem; Segundo, já que não sabemos ao certo se as iterações vão estabilizar para um dado valor de entrada 'seed', nos codificamos um limite superior para o número de iterações a serem computadas.
