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.

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).

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.

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);

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!

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.

Atenciosamente

Acho curiosa essa forma de terminar as correspondências: Att. Querem supor que é abreviação de Atenciosamente. Não é. Além de estar errado, abreviar a saudação é o oposto de ser atencioso. É pior ainda quando está na assinatura do e-mail: o sujeito não se dá sequer ao trabalho de fingir ser atencioso.

A abreviação chega a ser irrelevante. Deveria ser proibida para esta palavra. Quem quer ser atencioso, não encurta a saudação final.

Atenciosamente,

Forinti.

Fourier em SQL (e Perl)

Dada uma nova ferramenta, resolvi experimentar no SQL. A transformada discreta de Fourier resume-se, basicamente, a um montão de multiplicações e somas. É fácil repetir em SQL. Já a FFT nem tanto. SQL simplesmente não se presta a recursões.

Outra desvantagem do SQL é a ausência de suporte a números complexos (Perl oferece o fantástico módulo Math::Complex que, inclusive, reimplementa todas as operações da linguagem). A DFT não exige muito, basta separar a conta em cos() e i*sin(). Mas se fôssemos implementar a FFT, seria preciso fazer a multiplicação por extenso. Isso só seria chato, resolver a recursão é que é o problema do SQL.

Mesmo assim, a DFT pode ser bem útil e, se vamos usá-la num banco, é porque não estamos com pressa mesmo.

Comecei por um algoritmo FFT em Perl para poder conferir os resultados do SQL. O script executa a FFT sobre a função sin(x), assim como a consulta (que escrevi para conferir os resultados do Perl).

DFT de sin(x)

Os dois deram o mesmo resultado, mas a implementação do FFT foi muito mais rápida, como esperado.

O grande porém da FFT é que precisamos ter um número de elementos que seja potência de 2. Com DFT, podemos usar qualquer quantidade. Então, resolvi experimentar numa tabela de pagamentos.

Usei dois anos de pagamentos e obtive o seguinte gráfico (que parece indicar que há um componente trimestral nos pagamentos):

Aprender a implemenar a DFT e a FFT é só o primeiro passo. Analisar os resultados e achar aplicações é o próximo passo.

Desenhando para Entender

A DFT (Transformada Discreta de Fourier) é relativamente simples de entender, mas é um algoritmo de complexidade o(n²). A FFT (Transformada Rápida de Fourier) tem complexidade o(nlogn), mas é mais complicada, naturalmente.

Para ajudar minha compreensão, resolvi desenhar os valores para enxergar as zonas comuns que ajudam o FFT a acelerar as contas.

Com ajuda do GD, excrevi um programa em Perl para gerar uma imagem com os valores das funções-base para diferentes resoluções (potências de dois).

A imagem abaixo vai de 2⁰ a 2¹⁰. Cada valor tem 100 linhas de altura e 2ⁿ divisões. Isto é, a imagem começa com 1 valor, depois 2, depois 4, etc. Deixei linhas pretas para demarcar os valores (cada um ocupa um retângulo de altura 100 e largua 1024/2ⁿ.

O valor de cada célula é e^-i2pik/N. O componente vermelho é abs(re)*255, ou seja, a parte inteira. O componente verde é a parte imaginária e o azul é zero.

Já dá para enxergar por onde otimizar o DFT.

Se adiciono um componente azul para valores negativos da parte real, terminho com isto:

Se faço o mesmo para a parte imaginária, tenho isto:

Já que não tenho 4 componentes de cor, vario a intensidade do azul conforme as partes real e imaginária são postivas ou negativas.

Juntando essas ideias, dá para imaginar como atacar o problema.

Internet com Horário Comercial

Uma aplicação sensível precisa estar disponível na Internet. O administrador, preocupado sempre com a segurança, decide que o melhor é limitar o acesso ao horário comercial. Entretanto, supõe que quem estiver dentro do prédio fora do horário comercial seja de confiança.

A solução é usar o mod_rewrite e aprender a usar o [OR].

  #Disponível externamente somente das 8h às 18h, de segunda a sexta.
  RewriteCond %{TIME_HOUR} ^(00|01|02|03|04|05|06|07|18|19|20|21|22|23)$ [OR]
  RewriteCond %{TIME_WDAY} ^(0|7)$
  RewriteCond %{REMOTE_ADDR} !^192\.168.*$
  RewriteRule ^.*$ - [F,L]

Entre 8h e 18h e aos sábados e aos domingos, o acesso é bloqueado, exceto se o IP iniciar com 192.168.

Por omissão, as regras são analisadas com AND. O que não está claro é como agrupar quando há ORs também.

O código indica que o OR tem precedência. Então, a solução acima interpreta-se como (A OR B) AND C.

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

A prefeitura de Porto Alegre não mede a poluição do ar desde 2010 e tenho percebido alguns estabelecimentos comerciais usando geradores a diesel. Minha conta de luz subiu, nos últimos dois anos, de R$0,59/KWh a R$0,84/KWh. São 42% de aumento e talvez aí esteja o incentivo necessário para o aparecimento dos geradores. Tampouco percebo fiscalização da poluição dos caminhões e dos ônibus. É possível atravessar a cidade deixando um rastro de fumaça negra sem ser interpelado pela autoridade de trânsito.

Por isso, resolvi fazer um pequeno experimento. Comprei um medidor de partículas, o SDS011. Ele mede apenas partículas de 10 micrômetros e de 2,5 micrômetros. O índice de qualidade do ar (AQI) inclui também gases.

Esse pequeno sensor comunica-se via uma porta serial e o pacote inclui também um adaptador USB e o respectivo cabo. Entretanto, nenhum software é oferecido. Felizmente, o protocolo é simples e envolve apenas enviar uma mensagem de 19bytes (a maior parte é de zeros) e receber uma resposta de 12 bytes). O manual descreve todas as interações.

O equipamento tem uma vida útil de 8 mil horas (um pouco menos de um ano de uso contínuo) e pode fazer medições continuamente, mas, neste caso, eu o coloco em estado de hibernação e o acordo para fazer a medição. Assim, ele irá durar vários anos. Entretanto, é preciso esperar 30s depois de acordá-lo para fazer uma medição.

Escrevi um pequeno programa para fazer a leitura uma vez por hora e deixei-o rodando durante uma semana conectado a um Raspberry Pi 3 B.

Alguns poréns devem ser apontados: o aparelho ficou o tempo todo dentro de casa e bem acima do nível da rua na zona norte de Porto Alegre (que, apesar de ser poluída, tem bastante vento).

Em geral, os resultados foram bons (poucas medições passaram de 10μm/m³, sendo 50μm/m³ o limiar do ar bom). Entretanto, houve um pico de 200μm/m³ de PM10 e 49,9μm/m³ de PM2,5. Essa medição já cai na categoria Inadequado. Talvez algum caminhão tenha passado deixando seu rastro.

Se é que posso tirar alguma conclusão deste meu pequeno experimento, é a de que o ar dentro de minha casa está bom. Um estudo mais abrangente e feito por alguém mais capacitado encontrou que o ar de Porto Alegre não é tão bom assim.

Os próximos passos serão:

• Medir em outras regiões (o centro e a região sul);
• Medir ao nível da rua;
• Medir durante um ano inteiro.

Como apagar todos os arquivos, exceto os n mais recentes

Muitas vezes apaguei arquivos antigos com a opção mtime do find, mas agora enfrentei um caso um pouco diferente. Eu precisava deixar 5 cópias de backup numa pasta.

O primeiro passo é enumerar o que é preciso apagar:

ls -1t | tail -n +5
ls -1tr | head -n -5

A opção r do ls inverte a lista e, consequentemente, o tail precisa ser trocado para head.

Essa combinação imprime os arquivos por ordem crescente de data e remove os 5 últimos (os 5 mais recentes). Depois, é preciso escolher a forma de processar a lista.

Uma opção óbvia é o xargs:

ls -1t | tail -n +5 | xargs -d '\n' rm -f --
ls -1tr | head -n -5 | xargs -d '\n' rm -f --

Mas o aninhamento de expressões do shell pode ajudar bastante:

rm -f $(ls -1t | tail -n +5)
rm -f $(ls -1t | head -n -5)

Se for preciso executar o comando numa pasta diferente da atual, basta incluir o caminho no ls:

ls -1dt /var/log/* | tail -n +5

A opção -d evita que o ls tente exibir o conteúdo de subdiretórios; apenas o nome do subdiretório é incluído.