Archive for the ‘matemática’ Category

O crivo de Eratóstenes – Um método para encontrar números primos.

janeiro 13, 2011

O Problema:

Um inteiro primo é qualquer inteiro que só pode ser dividido exatamente por si mesmo e por 1. O Crivo de Eratóstenes é um métodos de encontar números primos. Ele funciona da seguinte maneira:

a) Crie um array com todos os elementos inicializados com 1 (verdadeiro). Os elementos do array com subscritos primos permanecerão 1. Todos os outros elementos do array serão definidos  como zero.

b) Começando com o subscrito 2 do array (o subscrito 1 deve ser primo), sempre que for encontrado um elemento do array cujo valor seja 1, faça um laço pelo restante do array e defina como zero todos os outros elementos cujo subscrito seja múltiplo do subscrito com valor 1. Para o subscrito 2 do array, todos os elementos além de 2 que forem múltiplos de 2 serão definidos como zero (subscritos 4, 6, 8, 10 etc.). Para o subscrito 3 do array, todos os elementos além de 3 que forem múltiplos de 3 serão definidos como zero (subscrito 6, 9, 12, 15 etc.).

Quando esse processo for concluído, os elementos do array que ainda estiverem definidos como 1 indicam que o subscrito é um número primo. Esses subscritos podem ser impressos.

A Solução:

Esse problema possui uma solução muito fácil de ser implementada. Um algoritmo para resolver esse problema pode ser assim:

{Objetivo: usar o método do Crivo de Eratóstenes para achar números primos}
Algoritmo Crivo_de_Eratóstenes
{cria um vetor de inteiros de tamanho max}
    Inteiro[max] primos;
    
    {Inicializa todos os elementos com 1}
    Para i = 1 até max
        primos[i] = 1;
        i = i + 1;
    {Anula os elementos do array que não são primos}
    Para i = 2 até max
        Se primos[i] == 1
            {Função para anular os múltiplos de i}
            AnulaMultiplos(i);
    {Função para imprimir o subscrito do array quando o elemento do array naquele subscrito é igual a 1}
    ImprimePrimos();
}

Como dá pra perceber o algoritmo é bastante simples, vamos implementar em linguagem C++ esse algoritmo:

#include iostream.h
#include stdlib.h
void imprimePrimos(int primo[], int max);
void anulaMultiplos(int primo[], int max, int subscrito);
int main()
{
    const int max = 10000;
    int primo[max];
    for (int i = 1; i < max; i++)
        primo[i] = 1;
    for (int i = 2; i < max; i++)
        if (primo[i] == 1)
            anulaMultiplos(primo, max, i);
        imprimePrimos(primo, max);
    system("PAUSE");
    return 0;
}
void anulaMultiplos(int primo[], int max, int subscrito)
{
    for (int i = subscrito; i = max)
            break;
        else
            primo[i * subscrito] = 0;
}
void imprimePrimos(int * primo, int max)
{
    for (int i = 0; i < max; i++)
        if (*(primo + i) == 1)
            cout << i << "\t";
        cout << "\n";
}

Nesse caso esse programa gera os números primos até 10000, já que este é o valor de max. Para gerar mais números primos basta mudar esse valor.

Anúncios

Como calcular a área de um polígono irregular

dezembro 5, 2008

Recentemente precisei calcular a área de um polígono irregular. Mas como? Fiz uma pesquisa sobre geometria computacional, e uma das formas que encontrei foi em dividir o polígono em vários triângulos e, após isso, calcular a área de cada triângulo. Tudo bem, mas como dividir o polígono em vários triângulos menores? Por exemplo, como dividir automaticamente o polígono da figura 1 em triângulos? Existem algoritmos para isso, para fazer a triangulação de polígonos.

triangulacao

Figura 1 – Um polígono dividido em vários triângulos

Basicamente o algoritmo funciona da seguinte forma. Divide o polígono em vários polígonos monotone* e depois faz a triangulação de cada um desses algoritmos usando um algoritmo para fazer a triangulação.

Essa é uma das formas de se fazer isso. Uma outra forma é baseada na técnica descrita no post “Como calcular computacionalmente o valor de PI“. Nesse caso podemos fazer o seguinte. Desenhamos o polígono em cima de um outro polígono já conhecido, no caso um retângulo. Sabemos como calcular a área do retângulo. Depois disso, começamos a gerar pontos aleatórios dentro do retângulo (o polígono que queremos calcular a área está em cima do retângulo). Para cada ponto, vemos se o ponto caiu dentro do polígono irregular. Se dividirmos a quantidade de pontos que caiu dentro do polígono pela quantidade de pontos gerada, temos a relação entre a área do polígono e a área do retângulo. Como a área do retângulo é conhecida, fica simples calcular a área do polígono, basta fazer uma multiplicação.

No entanto, fica a questão: Como saber se um ponto está dentro do polígono?  Para efeitos práticos para o cálculo da área dessa forma, podemos traçar uma semi-reta paralela ao eixo x em direção a +x. Se essa semi-reta interceptar um número ímpar de arestas, podemos dizer que ele está dentro do polígono – Figura 2.

dentroforaFigura 2 – Ponto dentro e fora do polígono

Agora que sabemos quando um ponto está dentro de um polígono, precisamos saber que essa semi-reta interceptou uma das arestas. Isso pode ser feito da seguinte forma:

Primeiro, calculamos a equação da aresta. Considerando que os vértices da aresta são (x1, y1) e (x2,y2), temos que a equação é:

x = x1 + (y-y1)\frac{(x2-x1)}{(y2-y1)}

Aplicando a coordenada y do ponto nessa equação, temos um valor de x. Se esse valor for maior que o valor da coordenada x do ponto, sabemos então que o ponto está a esquerda da aresta.

Além disso, se verificarmos que a coordenada y está entre min(y1,y2) e max(y1,y2), então sabemos que a semi-reta intercepta a aresta.

Com isso já podemos calcular a área de um polígono irregular.

Para ilustrar, segue um código Java para isso.

Classe Ponto

classe-ponto

Classe Aresta

classe-aresta

Classe Poligono

classe-poligono

Como primeiro teste, desenhei um polígono e gerei vários pontos aleatórios para testar se o método para verificar se está dentro do polígono está funcionando. Os pontos verdes estão fora do polígono e os amarelo dentro. Desenhei pequenos círculos em volta do ponto gerado, para aproveitar uma rotina que já tenho aqui. Podemos ver que a rotina se mostra adequada para o problema.

teste-ponto-esta-dentro-do-poligono

Figura 3 – Teste do método para verificar se pontoe stá dentro do polígono

Resta agora testar se isso funciona para calcular a área. Para isso, vamos criar um quadrado de lado 1 e gerar pontos aleatórios dentro de um quadrado de lado 2 e calcular a relação entre a quantidade de pontos dentro do quadrado e a quantidade de pontos gerada. Esse valor multiplicado pela área do quadrado maior (4), deve dar a área do quadrado, que sabemos que é 1. Na verdade, como esse método não é exato, a área deve ser próxima de 1, e não exatamente 1. Segue trecho de código usado para teste:

teste-calculo-da-area

Uma das saídas desse programa é mostrada na figura abaixo. Note que o valor da área calculado por esse método é muito próximo ao valor real. Na verdade, podemos aumentar a precisão do algoritmo aumentando o número de pontos gerados.

saida-do-programaFigura 4 – Resultado do programa

A Figura 5 mostra uma figura de exemplo para esse teste, com os pontos gerados:

exemplo-de-pontos-gerados

Figura 5 – Exemplo do teste efetuado

* – optei por não fazer a tradução dessa palavra pois não sei como ela é traduzida em geometria computacional.

Problema das 3 portas

novembro 9, 2008

Probabilidade é um assunto interessante. Em um post antigo falamos sobre o problema dos aniversários e vimos que para um grupo de apenas 30 pessoas a probabilidade de termos 2 aniversariantes no mesmo dia é de mais de 70%, o que não é muito o senso comum.

Outro problema interessante de probabilidade é o problema das 3 portas. Um apresentador de um programa de televisão chama para o palco uma pessoa que deve escolher entre 3 portas. Uma dessas portas tem prêmios e as outras 2 não tem nada. Inicialmente a pessoa escolhe uma porta e, em seguida, o apresentador abre uma porta vazia. Como sempre tem 2 portas que não tem nada atrás delas, sempre haverá uma porta para o apresentador abrir. Feito isso ele pergunta se você quer trocar de porta. E agora?

A grande maioria das pessoas nao troca de porta. Talvez por supertição, pois escolheu seu número da sorte. Mas o que é melhor, trocar de porta ou não? Ou tanto faz? Vamos resolver o problema sem fazer contas…..

Obviamente a chance de você acertar a porta na primeira escolha é de 1/3, 33,33%. Vamos verificar então o que acontece se você trocar de porta.

Inicialmente temos 3 portas, P1, P2 e P3. E você escolheu a porta P1. Temos 3 possibilidades:

  • O prêmio está atrás da porta P: Nesse caso o apresentador abre uma das portas P2 ou P3. Se você trocar você estará trocando o prêmio por nada.
  • O prêmio está atrás da porta P2: Nesse caso o apresentador abrirá a porta P3. Se você trocar de porta você estará trocando pela porta P1, ou seja, estará trocando nada pelo prêmio.
  • O prêmio está atrás da porta P3: Nesse caso o apresentador abrirá a porta P2. Se você trocar de porta você estará trocando pela porta P1, ou seja, estará trocando nada pelo prêmio.

Observe que das 3 possibilidades, 2 são vencedoras. Sendo assim, a probabilidade de ganhar o prêmio caso você troque de porta é de 2/3, ou 66,67%, ou seja, o dobro de chance de levar para casa o prêmio.

Bom, para facilitar, vamos ver um pequeno programa em Java que faz uma simulação sobre esse problema e nos mostra o resultado. É mais fácil de acreditar…

problema-3-portas1

Obs.: O código acima foi construído de forma a diminuir seu tamanho para publicação nesse blog, por isso o uso de operadores não muito indicado por alguns livros, como o operador ternário (?:).

Exponenciais de números racionais

setembro 30, 2008

Qual é o significado de x^p, onde p não é necessariamente um inteiro positivo? O que significa multiplicar x por ele mesmo p vezes nesse caso?

O ponto chave é lembrarmos como funciona quando p é um número inteiro positivo:

x^mx^n = x...x ( m vezes ) x...x ( n vezes ) = x^{m+n}

ou seja, os expoentes são somados. Podemos considerar que essa expressão é verdadeira mesmo para expoentes que não sejam inteiros positivos. Com isso, podemos definir x^{\frac{1}{p}}, onde p é um inteiro positivo, como o número que satisfaz:

x^{\frac{1}{p}}...x^{\frac{1}{p}} ( p vezes ) = x

Dessa forma, x^{\frac{1}{p}} é definido como o o número que multiplicado por ele mesmo px.

De forma semelhante, podemos definir expoentes negativos. O que significa x^{-m} , onde m é um inteiro? Considere o cálculo de x^nx^{-m}:

x^nx^{-m} = x^{n-m} = x...x (n-m vezes )

Como x^n = x...x (n vezes ), se definirmos x^{-m} como:

x^{-m} = \frac{1}{x...x} (m vezes )

o resultado desejado é verdadeiro. Ou seja, o expoente negativo tem o mesmo significado que o inverso de expoentes positivos. Daí segue que:

x^0 = x^mx^{-m} = x^m\frac{1}{x^{m}} = 1

Dessa forma, a exponencial de qualquer número racional da forma \frac{p}{q} é definida.

Fonte: Basic Training in Mathematics, A Fitness Program for Science Students, R. Shankar

Como converter um número em base b para um número no sistema de numeração decimal

setembro 18, 2008

No mundo da computação é muito comum vermos números escritos em sistemas de numeração diferentes do sistema decimal. Atenção especial são dadas para os sistemas de base 2 (binário) e de base 16 (hexadecimal). Mas para muitos de nós o sistema decimal é mais palpável do que qualqer outro. Você sabe como converter qualquer sistema escrito numa base b qualquer para o sistema decimal?

Um número N em uma base b qualquer pode ser escrito da seguinte forma:

N = b_n...b_3b_2b_1b_0

onde b_i é uma letra do alfabeto (dígito) que compõe o sistema de numeração. Para um sistema de numeração binário (base 2), b_i pode ser 0 ou 1. Para um sistema de numeração de base 8 b_i pode ser 0, 1, 2, 3, 4, 5, 6, 7. Para um sistema de numeração de base 16 b_i pode ser 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F e assim por diante.

Para converter o número b_n...b_3b_2b_1b_0 para a base 10 é simples. Basta aplicar a seguinte forma:

D = {b_0}B^{0} + {b_1}B^{1} + {b_2}B^{2} + ....{b_n}B^{n}

onde B é a base do sistema. Para o sistema binário B = 2 e a fórmula se reduz em:

D = {b_0}2^{0} + {b_1}2^{1} + {b_2}2^{2} + ....{b_n}2^{n}

Para ilustrar, o seguinte trecho de código na linguagem Java converte uma string que possui os números em binário para um número em decimal:

Dúvidas de usuários – Progressão geométrica em juros compostos

maio 23, 2008

Para saber mais sobre essa seção clique aqui.

Pergunta

Um usuário chegou a esse blog através da seguinte consulta a um motor de busca: “figura geométrica montante juros compos”. Não dá pra saber exatamente qual é a dúvida do usuário, mas acredito que ele queira ver um gráfico com um exemplo de juros compostos.

Resposta

O assunto sobre juros compostos foi tratado em um post específico. Naquele tópico foi mostrado que o capital inicial cresce com a seguinte fórmula:

F = I {(1+r)}^{n}

onde F é o capital final, I o capital inicial, r a taxa de juros e n a quantidade de meses. Vamos fazer um exemplo com o capital inicial igual a apenas R$ 1,00 e uma taxa de juros de 1% ao longo de 360 meses. A figura abaixo mostra como é a variação do capital ao longo desses 360 meses (30 anos).

A fórmula de juros compostos nos mostra o crescimento exponencial do capital ao longo do tempo. Observe que durante os 30 anos cada R$ 1,00 investido se transformou em pouco menos e R$ 36,00. Interessante, não? Mais interessante ainda é observar que grande parte desses R$ 36,00 se originou durante os últimos 15 anos (segunda metade do período). Durante os primeiros 15 anos foi possível acumular cerca de R$ 6,00 para cada R$ 1,00 investido.

Muito interessante, não? Isso acontece pois os juros rendem em cima dos juros já obtidos.

Dúvidas de usuários – Verificar se um número é ímpar no Matlab

maio 23, 2008

Para saber mais sobre essa seção clique aqui.

Pergunta

Um usuário chegou a esse blog através da seguinte consulta a um motor de busca: “matlab verificar numero impar”. Então acho que a pergunta é: Como verificar se um número é ímpar no Matlab?

Resposta

Como verificar se um número é par ou ímpar? Ora, um número par é aquele que é divisível por 2 e um número ímpar é aquele que não é divisível por 2. Tudo bem, mas como verificar isso no Matlab?

No Matlab temos a função mod(), que fornece o resto da divisão. Essa função recebe 2 argumentos, o primeiro é o número que você quer dividir e o segundo é o número pelo qual você quer dividir. A função mod te fornece o resto dessa divisão. Se o resultado da divisão de um número x por 2 é 1, então esse número é ímpar. Se o resultado for 0, então o número é par. O seguinte trecho de código Matlab mostra isso:

x = 3;

if mod(x,2) == 1
sprintf('é ímpar')
else
sprintf('é par')
end

Juros Compostos

maio 13, 2008

“O juro composto é a maior invenção da humanidade, porque permite uma confiável e sistemática acumulação de riqueza.” Dizem que essa frase foi atribuída a Albert Einstein. Não sei se é verdadeira, mas o fato é que é correta.

Juro composto é o conhecido juros sobre juros, ou seja, é quando o seu juros é reinvestido. Para facilitar, vamos dar um pequeno exemplo antes de entrarmos na matemática dos juros compostos.

Exemplo: Você colocou R$ 1.000,00 em uma aplicação que rende 1% ao mês. No primeiro mês você tem então R$ 1.000,00 x (1 + 0,01) = R$ 1.010,00. No segundo mês você tem R$ 1.010,00 x (1 + 0,01) = R$ 1020,10. Note que enquanto o primeiro rendeu apenas R$ 10,00 o segundo mês rendeu R$ 10,10. Isso acontece pois no segundo mês o rendimento é em cima do valor investido (R$ 1.000,00) e do lucro (R$ 10,00).

Bom, acho que com esse exemplo deu pra ver o poder dos juros compostos. A acumulação de riqueza. Que tal então um pouco de matemática?

Vamos supor que você parta de um capital inicial I , tenha uma rentabilidade média mensal de r e você faça depósitos mensais de D. Quanto dinheiro você terá depois de n meses?

Vamos lá. No primeiro mês você tinha I e fez um depósito de D. Seu dinheiro rendeu r, ou seja, você tem agora:

(I+D)(1+r)

Para facilitar, vamos chamar o termo (1+r) de R. Então por exemplo, se sua rentabilidade é de 1% ao mês, r = 0,01 e R = 1,01.

Substituindo esse valor, ao final do primeiro mês você tem

(I+D)R

Ótimo. No início do segundo mês você deposita mais D e isso vai render mais r. No final do segundo mês você terá:

([I+D]R + D)R

Fazendo isso, no final do terceiro mês você terá:

{[(I+D)R + D]R + D}R

Vamos expandir esse termo:

I({R}^{3}) + D({R}^{3} + D{R}^{2} + D{R}^{1})

Colocando D em evidência temos:

I{R}^{3} + D({R}^{3} + {R}^{2} + {R}^{1})

Aqui já é fácil generalizar para uma quantidade de n meses. Ao final de n meses você terá:

I{R}^{n-1} + D({R}^{n} + {R}^{n-1} +... + {R}^{1})

Bom, o primeiro termo da soma é fácil de calcular. O segundo termo não é direto, pois é uma soma de n termos. No entanto, os termos dessa soma é uma progressão geométrica de grau R com termo inicial também igual a R. A soma dos termos de uma PG é dada por:

S = (primeiro termo) * \frac{{razao}^{numeroDeTermos} - 1}{(razao - 1)}

No nosso caso o primeiro termo é R e a razão também é R. Ao final do n meses você vai ter acumulado um capital F tal que:

F = I{R}^{n} + D*R\frac{{R}^{N} - 1}{R - 1}

Vamos a um exemplo prático: Partindo de um capital inicial de R$ 0,00 e fazendo depósitos de R$ 500,00 mensais, com uma taxa de juros média de 1,5% ao mês, ao final de 30 anos (360 meses) você terá:

F =500*1,015*({1,015}^{360} - 1)/(1,015 - 1) = R$ 7.162.64

Você fez 360 depósitos de R$ 500,00, ou seja, você depositou um total de R$ 180.000,00 e, no final você tem quase 7 milhões de reais apenas de lucro. Esse é o poder dos juros compostos! Por que isso acontece? Veja novamente a equação. Pode se perceber que o resultado final é diretamente proporcional ao montante depositado mensalmente e ao capital inicial. Já a relação com entre o montante final e a taxa de juros não é linear, e sim uma exponencial.

Problema dos aniversários

fevereiro 7, 2008

Num grupo de r pessoas, qual é a probabilidade de pelo menos duas delas fazerem aniversário no mesmo dia?

Este problema tem surpreendido estudantes pois, dependendo do valor de r , a probabilidade procurada é bastante alta. Vamos considerar o ano com 365 dias e, assim, assumiremos r < 365 pois para r \geq 365 a probabilidade desejada seria 1.

O espaço amostral \Omega será o conjunto de todas as seqüências formadas com as datas dos aniversários (associamos cada data a um dos 365 dias do ano). Pode ser verificado que o conjunto das partes de um espaço amostral enumerável é uma \sigma-álgebra. Dessa forma, podemos tomar a \sigma-álgebra F como sendo o conjunto das partes de \Omega e, para qualquer A \in F, P(A) é o quociente entre o número de elementos de A por 365^r, que é o número total de seqüências de tamanho r. Assim, assuminos que todos os dias são eqüiprováveis.

Seja E o evento de interesse, isto é, E = {pelo menos duas pessoas aniversariam no mesmo dia}. Para o complementar de E, temos E^c = {ninguém faz aniversário no mesmo dia}. Iremos calcular a probabilidade de E^c com o auxílio do Princípio Fundamental da Contagem.

Considerando a escolha das idades como sendo r etapas sucessivas precisamos, para as datas serem todas distintas, eliminar as que forem escolhidas em etapas anteriores. O agrupamento formado é um arranjo e, dessa forma, para o total de maneiras de escolhermos r datas diferentes de aniversário, teremos

{(365 )}_{r} = 365\times 364 \times 363\times \ldots \times (365 - r + 1)

Em outras palavras, o produto acima é o número de seqüências que satisfazem a condição de datas distintas de aniversário. Então,

P(E^c) = \frac{{(365)}_{r} }{365^r} = 1\left(1 - \frac{1}{365} \right)\left(1 - \frac{2}{365} \right)\ldots\left(1 - \frac{r-1}{365} \right)

Portanto, a probalidade desejada, de pelo menos dois aniversários no mesmo dia, será P(E) = 1 - P(E^c).

O curioso é que para r = 23, um número relativamente baixo de pessoas, a probabilidade de pelo menos dois aniversários coincidentes já é maior que \frac{1}{2}. A tabela a seguir apresenta alguns valores dessa probabilidade em função de r.

Para r = 10, P(E) = 0,1169

Para r = 20, P(E) = 0,4114

Para r = 30, P(E) = 0,7063

Para r = 40, P(E) = 0,8912

Fonte: Transcrição da página 12 do livro Probabilidade e Variáveis Aleatórias, de Marcos Nascimento Magalhões, publicado pela edusp.

Geração de números aleatórios

novembro 23, 2007

A forma mais comum de se obter números pseudorandômicos em um computador digital é usando o seguinte gerador:

{R}_{i} = (A{R}_{i-1}+C) mod M, i = 1, 2, 3, ...

onde {R}_{0} é a semente, ou valor inicial, M o divisor, C uma constante aditiva e A um multiplicador. A notação mod M significa que a aritimética é feita módulo M, ou seja, {R}_{i} é o resto da divisão de A{R}_{i-1}+C por M. A seqüência resultante terá boa propriedades estatísticas e produzirá longas seqüências sem repetição dependendo dos números escolhidos.

Bons valores para M, Asão:

M = {2}^{31}

A = 764261123

{R}_{0} é escolhido como um número ímpar.

A implementação dessa rotina em matlab é

R0=1;
A=764261123;
C=0;
M=2^31;

R=zeros(1000,1);
R(1)=mod(A*R0+C,M);
for i=2:1000
R(i)=mod(A*R(i-1)+C,M);
end

plot(R);

Esse mesmo código, em linguagem Java, é

double[] R = new double[1000];
double A=764261123;
double C=0;
double M=Math.pow(2, 31);

R[0] = 1;
for (int i=1; i<1000; i++)
R[i]=(A*R[i-1]+C) % M;

Cabe ressaltar que esse gerador é um gerador de números pseudorandômicos. Isso significa que, dada as mesmas condições (semente, A, C e M), a mesma seqüência será gerada. Verdadeiros geradores randômicos devem usar eventos realmente randômicos, como por exemplo o ruído de dispositivos eletrônicos ou o sinal captado por um microfone em um ambiente natural.

Fonte: Random Signal Analysis in Engineering Systems, John J. Komo