quarta-feira, 29 de janeiro de 2020

Teorema de Herão

O teorema de Herão é uma dessas coisas que, inexplicavelmente, não ensinam na escola. Ele permite calcular a área de um triângulo (e, consequentemente, de outras formas geométricas) usando apenas os comprimentos dos lados.

Dado um triângulo (a, b, c) com perímetro P (a+b+c) e semiperímetro S (P/2), podemos calcular a área A com:

A=sqrt[S(S-a)(S-b)(S-c)]

Dada uma maneira fácil de calcular A, podemos automatizar a busca por triângulos especiais. Por exemplo, todos aqueles cuja área é igual ao perímetro.


#!/bin/perl
use strict;
use warnings;

for my $a (1..1000) {
  for my $b ($a..1000) {
    for my $c ($b..1000) {
      my $P=($a+$b+$c);
      my $S=$P/2;

      my $A=$S*($S-$a)*($S-$b)*($S-$c);

      if($A>0) {
        $A=sqrt($A);
        print "($a, $b, $c) => $A\n" if int($A)==$A && $A==$P;
      }        
    }  
  }
}


(5, 12, 13) => 30
(6, 8, 10) => 24
(6, 25, 29) => 60
(7, 15, 20) => 42
(9, 10, 17) => 36
Ou então, todos cuja área é metade do perímetro: apenas (3,4,5) com área 6. Nenhum tem área menor que S.

segunda-feira, 23 de dezembro de 2019

Simulação de Vestibular por Sorteio com Múltiplas Categorias de Candidatos

As cotas do vestibular continuam a gerar muita polêmica e eu acredito que a maneira mais sensata de obter uma diversidade de candidatos (e que essa diverdade represente a sociedade em geral) seja o sorteio.

Em geral, o sorteio não é bem aceito. Penso que as pessoas não entendem o quanto de aleatoriedade já existe em suas vidas nem o quanto um sorteio pode conferir de certeza. Sim, porque a lei dos grandes números garante que um sorteio vai produzir um resultado que reflete a sociedade em geral.

Então, para confirmar meu instinto e minhas noções de probabilidade, resolvi fazer um experimento.

O código disponível no Github (vestibular) executa uma simulação. Ele cria um certo número de categorias de candidatos (de A a alguma letra) e associa uma probabilidade a cada categoria. Depois, ele cria um número grande de candidatos e seleciona um subconjunto. Usei 32 mil candidatos e 4 mil vagas - esses números são parecidos com os números do vestibular da UFRGS.

Cada candidato pode pertencer ou não a uma categoria (conforme a probabilidade associada a cada categoria). Então, no fim, eu comparo as ocorrências de cada categoria com as probabilidades.

Comecei com apenas duas categorias (A e B, que podem ser qualquer coisa - renda, raça, orientação sexual, etc). O primeiro número é a ocorrência da categoria entre os selecionados e o segundo, entre parênteses, é a probabilidade da categoria ocorrer entre os candidatos.

A => 0.12 (0.114514116271497)
B => 0.92175 (0.925965705278458)

Elas não somam 100% porque são idependentes. Neste caso, muitos candidatos não serão nem de uma nem de outra, enquanto alguns serão das duas categorias.

Então, testei com 5, sem muita certeza de que seria tão efetivo:

A => 0.4905 (0.487311880876408)
B => 0.91375 (0.911185285166965)
C => 0.062 (0.0692749992396209)
D => 0.67975 (0.677288610810997)
E => 0.6975 (0.677702524827584)

Enfim, arrisquei-me com 26 categorias:

A => 0.2135 (0.20715412621303)
B => 0.45725 (0.471650329974608)
C => 0.71675 (0.73108538383725)
D => 0.5805 (0.579328335678788)
E => 0.53075 (0.536166540009692)
F => 0.846 (0.854714284403585)
G => 0.715 (0.723798764074981)
H => 0.4105 (0.394008616492179)
I => 0.3265 (0.320406213161196)
J => 0.27275 (0.269366680936173)
K => 0.2585 (0.246797740708455)
L => 0.8965 (0.89638224732105)
M => 0.0975 (0.104803230643473)
N => 0.85825 (0.866355336585698)
O => 0.987 (0.988580246762009)
P => 0.35625 (0.348203284986191)
Q => 0.511 (0.510572429950859)
R => 0.8805 (0.880115641163712)
S => 0.7965 (0.791856356494872)
T => 0.095 (0.0838953795182604)
U => 0.63 (0.633186406755971)
V => 0.9105 (0.902297912213314)
W => 0.96425 (0.968405243976715)
X => 0.5935 (0.591812046459516)
Y => 0.4055 (0.399841993741777)
Z => 0.183 (0.18062745412891)

A minha intuição me leva a pensar numa imagem da qual selecionamos alguns pontos. O resultado vai ser uma versão de menor resolução dessa imagem.

Isso me leva a crer que um sorteio conseguiria ser muito mais justo (no sentido de representar os diferentes tipos de pessoas na sociedade) do que podemos pretender. Ele vai encontrar maneiras de categorizar as pessoas que sequer contemplamos. Além das categorias mais discutidas (raça, sexo, renda, etc), deve haver espaço para os introvertidos/extrovertidos, os contemplativos/empreendedores, bom desempenho sob estresse do vestibular/mau desempenho sob estresse do vestibular, etc.

Evidentemente, seria preciso antes aplicar um teste mínimo de conhecimentos. Talvez a polêmica migre para este teste, se bem que é provável que um sorteio nunca seja palatável para muita gente.

segunda-feira, 25 de novembro de 2019

A Melhor Base II

Após verificar que a base 3 é a base mais econômica dentre as bases tradicionais, resolvi experimentar algumas representações diferentes: a base fatorádica e os numerais romanos.

O problema é encontrar o menor número de placas para representar todos os números de 0 a 999.

#!/usr/bin/perl
use Roman;
use Data::Dumper;
use strict;

my %symbols=();

for my $b (0..999) {
  my %s=();
  my $r=factoradic($b);
  print "$r\n";
  my @s=split(//,$r);
  for my $s (@s) {
    $s{$s}++;
    if ($symbols{$s}<$s{$s}) {
      $symbols{$s}=$s{$s};
    }
  }
}

for my $d (keys %symbols) {
  print "$d => $symbols{$d}\n";
}

sub factoradic {
  use integer;
  my $n=shift;
  my $f='';
  my $i=1;
  do {
    $f=($n%$i).$f;
    $n/=$i;
    $i++;
  } while($n>0);
  
  return $f;
}


Para os numerais romanos, encontrei um módulo pronto no CPAN. Não tive tanta sorte com a base fatorádica, mas é muito fácil converter.

Os numerais romanos surpreenderam: são bastante mais econômicos e necessitam apenas 15 placas (mais uma para o zero). Já a fatorádica, requer 22 placas e fica, portanto, entre as bases 5 e 6 no ranking geral.

As placas necessárias seriam: I (3), V (1), X (4), L (1), C (4), D (1), M (1). Para o zero, a melhor opção seria N (de nulla ou nihil).

quarta-feira, 13 de novembro de 2019

A Melhor Base

Suponha que queiras montar um placar eletrônico para uma quadra de basquetebol. As pontuações costumam rondar uma centena; geralmente abaixo, frequentemente acima. Então, são necessários, pelo menos, 3 dígitos decimais. Para cada dígito, são necessárias 10 placas (de 0 a 9). Ao todo são 30 placas.

O que muda se usarmos outras bases? A conta é simples:

Número n de dígitos na base b = log(1000)/log(b)
Total de placas = b*n

Para as bases até 10, os resultados são:


2       19.9315685693242
3       18.8631294686045
4       19.9315685693242
5       21.4601483711009
6       23.1317497608924
7       24.8491879115537
8       26.5754247590989
9       28.2946942029067
10      30

A base 3 é a campeã. Seriam necessárias 19 placas para exibir todas as 1000 possibilidades de 0 a 999.

O valor de 999 em base 3 é 1101000. São 7 dígitos. Como não vamos passar de 999, se tivermos 7 dígitos, o mais significativo só pode ser 1. Então, 6*3 placas garantiriam todas as possibilidades dos 6 primeiros dígitos e uma placa adicional resolveria o sétimo.

quarta-feira, 11 de setembro de 2019

Multiplicação Russa e suas Consequências

A multiplicação russa é interessante porque funciona muito bem na base 2.

A idéia é simples:
  • Crie uma coluna para cada número (maior à esquerda, menor à direita);
  • Divida o número maior por dois até chegar a 1;
  • Multiplique o número menor por dois o mesmo número de vezes;
  • Descarte as linhas em que o número da esquerda for par;
  • Some os números que restavam à direita.
Por exemplo, 3 * 18:

18   3
 9   6
 4  12
 2  24
 1  48

Resultado= 6+48=54


Ela fica mais divertida em base 2:

00010010 00000011
00001001 00000110
00000100 00001100
00000010 00011000
00000001 00110000    

Resultado = 00000110+00110000= 110110


Ou seja, basta ir fazendo shifts.

Uma otimização óbvia é pegar a maior potência de dois para dividir o problema. As multiplicações por potências de dois sempre acabam com apenas uma linha sendo considerada: a maior do lado direito (porque todos os números do lado esquerdo são pares, exceto a última).

8  3
4  6
2 12
1 24

A resposta é 24. nenhuma soma é precisa, porque 8*3=3*2*2*2


E se eu repetir esse processo de sempre pegar a maior potência? Nesse caso, vou poder descrever sucintamente o processo como: para multiplicar m por n, percorro os bits de m e, para cada bit 1, adiciono n deslocado à esquerda pela posição desse bit.

Sucintamente, em Perl (devia ser assembly!), seria algo assim:

#!/usr/bin/perl
use strict;
use warnings;
use integer;

my $n=$ARGV[0];
my $m=$ARGV[1];
my $p=0;
my $total=0;

do {
  $total+=$m<<$p if $n&1;
  $p++;
} while ($n>>=1);

print $total;


Ou seja, se quero multiplicar 46 por 5, como cinco é 101, executo 46<<2 + 46<<0 (46*4+46*1 para os binário-deficientes). A respostá é óbvia, dado que 46*5=46*(4+1).

Uma solução alternativa um pouco mais elegante é essa função recursiva:

#!/usr/bin/perl
use strict;
use warnings;
use integer;

my $n=$ARGV[0];
my $m=$ARGV[1];

sub mult {
  my ($n, $m)=@_;
  
  return $m if $n==1;
  
  my $d=0;
  
  $d=$m if $n&1;
  return $d + mult($n>>1, $m<<1);
}

print mult($n, $m);

sexta-feira, 23 de agosto de 2019

Minha Reforma Ortográfica

Muita gente ficou insatisfeita com a última reforma ortográfica. Eu tenho minhas diferenças com ela também. E com a maneira como os acentos são ensinados na escola.

O problema dos acentos no português é que eles não sabem bem o que querem ser na vida: se indicam tonicidade, ou se indicam o som, ou se indicam as duas coisas.

Eu acho que deveriam apenas indicar a tonicidade (com a exceção única da crase). Já convivemos com porco e porcos; ovo e ovos.

O alfabeto cirílico possui letras para ditongos. Isso também nos ajudaria a eliminar duas categorias de acentos: os hiatos e os paroxítonos terminados em ditongo crescente. Os dois são meio atravessados, porque o que eles querem, na verdade, é deslocar a tonicidade para nos obrigar a pronunciar o ditongo. Querem resolver um problema por segunda intenção.

Podíamos muito bem adicionar umas letras para os ditongos, mas talvez seja mais prático aproveitar o fato de que o y e o w voltaram ao alfabeto e dar-lhes utilidade.

Então, na minha nova ortografia, teríamos: "saude" e "sawdade"; "distancya" e "policya"; "pais" e "pays".

Eu moro num pais tropical com meus pays, temos saude mas a distancya de nossa terra nos traz sawdade. Nenhum acento nessa frase!

quarta-feira, 19 de junho de 2019

Medição de Poluição em Porto Alegre II

O clima em maio e junho está realmente estranho. Fez calor e houve pouca chuva. Além disso, notei que o ar tinha cheiro de São Paulo. Ou seja, tinha cheiro de combustível. Por isso resolvi religar o meu medidor de partículas.

O ar realmente piorou desde minha última medição. Entretanto, ao menos em relação às partículas, ele continua dentro do razoável.


Uma única medição de PM10 passou do 100 (indo de satisfatório para moderadamente poluído). A medição de PM2.5 nunca passou de 44, então permaneceu no reino do ar bom.

O tempo não esteve seco durante esses dias, indo a 100% de umidade relativa todas as noites.

Deduzo que a diferença se deva à falta de chuva e à falta de ventos.