Eventos com inscrição prévia, do Fórum Internacional do Software Livre às plenárias do Congresso do PSOL nas grandes cidades, costumam ter mesas de credenciamento pelas quais os presentes precisam passar para pegar um crachá.

Quando há muitos participantes é comum que as letras do alfabeto sejam separadas entre essas mesas, de forma a dividir as pessoas pelas iniciais dos seus nomes e assim reduzir o tempo de espera nas filas que se formam.

Exemplo: Se há três mesas de credenciamento, pode-se atribuir a elas os intervalos letras A-I, J-R e S-Z. Nesse caso, alguém com um nome que comece com B (como Bruno) deve se credenciar na mesa A-I, enquanto alguém com um nome que comece com T (como Tiago) deve se credenciar na mesa S-Z.

Uma dificuldade conhecida por todos que já organizaram eventos desse tipo é que alguns particionamentos do alfabeto podem levar a formar umas filas grandes e outras pequenas. Em particular, deixar o mesmo número de letras em cada conjunto costuma ser uma estratégia muito ineficiente, porque em português muitos nomes começam com as letras A, J e M, mas poucos começam com as letras Q, U e X.

O problema que surge a partir dessa constatação é: Como dividir as letras do alfabeto de forma a garantir que o número de participantes por mesa esteja o mais equilibrado possível?

Há uma restrição: As letras precisam ser divididas de forma que formem partições contíguas na ordem alfabética. Isso é, não se pode definir que A e C ficam num conjunto 1, enquanto B fica num conjunto 2. Se A e C estão no conjunto 1, todas as letras entre A e C (B, no caso) também precisam estar no conjunto 1.

Trata-se claramente de um problema de otimização. Para desenvolver um algoritmo (que nada mais é do que um procedimento computacional) para resolvê-lo, convém definir o que esperamos como entrada e o que esperamos como saída.

Entrada:

• $n$: número de letras no alfabeto
• $a_i$: número de participantes que começam com a $i$-ésima letra do alfabeto ($1 \leq i \leq n$).
• $k$: número de mesas de credenciamento (partições que devem ser formadas)

Saída:

• $c_i$: primeira letra da $i$-ésima partição do alfabeto ($1 \leq c_i \leq n$, $1 \leq i \leq k$)

Um parênteses: Enquanto este texto era escrito, o governo do Distrito Federal começou uma campanha de vacinação contra a influenza dividindo idosos em 5 grupos a partir das suas iniciais. De acordo com a Agência Brasil,

• Na segunda-feira (23), devem ser vacinados os idosos cujo nome comece com as letras A, B, C, D e E.
• Na terça-feira (24), pessoas com 60 anos ou mais com nomes iniciados pelas letras F, G, H, I e J.
• Na quarta-feira (25), idosos que tenham nas letras iniciais do nome K, L, M, N e O.
• Na quinta-feira (26), pessoas com 60 ou mais com o primeiro nome iniciado em P, Q, R, S e T.
• Na sexta-feira (27), devem se vacinar os idosos com nomes que comecem com U, V, W, X, Y e Z.

É fácil ver que esse governo teve que resolver o problema proposto aqui para separar as pessoas em 5 dias (que seriam equivalentes a mesas de credenciamento, na nossa formulação). Terá ele feito uma escolha ótima? Infelizmente acho difícil que os idosos que tenham nomes começando com letras entre A e E não tenham que esperar muito mais tempo na fila do que os idosos que tenham nomes começando com letras entre U e Z.

Como definir equilíbrio?

Idealmente gostaríamos de dividir os conjuntos de nomes igualmente. Se $t = \sum a_i$ é o número total de participantes do evento (a soma dos números de participantes com cada letra do alfabeto) e $k$ é o número de mesas de credenciamento, então o número de participantes que gostaríamos de colocar em cada mesa é $\frac{t}{k}$.

Há diferentes formas de medir o quão longe um valor se encontra do seu valor esperado. Uma das medidas mais populares, que decidi usar aqui, é o desvio padrão.

Se $x_i$ é o número de participantes que devem se credenciar na $i$-ésima mesa (para $i$ variando de 1 a $k$), então o desvio padrão dessa solução é:

Exemplo: Suponha que temos 42 nomes que começam com A, 25 nomes que começam com B e 33 nomes que começam com C. Então temos $a_1 = 42$, $a_2 = 25$, $a_3 = 33$ e $t = a_1 + a_2 + a_3 = 42 + 25 + 33 = 100$. Suponha que precisamos dividir esses nomes em duas mesas de credenciamento, portanto $k = 2$. Podemos dividir as pessoas de duas formas diferentes:

1. A e B-C.
2. A-B e C.

Na primeira solução, temos uma mesa com 42 pessoas e outra mesa com 58 (25+33). Na segunda solução, termos uma mesa com 67 pessoas (42+25) e outra mesa com 33. Note que $\frac{t}{k} = \frac{100}{2} = 50$.

Então o desvio padrão da primeira solução é

$$\sigma_1 = \sqrt{\frac{1}{2} ((42-50)^2 + (58-50)^2)} = 8$$

e o desvio padrão da segunda solução é

$$\sigma_2 = \sqrt{\frac{1}{2} ((67-50)^2 + (33-50)^2)} = 17.$$

Como $\sigma_1 < \sigma_2$, dizemos que a primeira solução é mais equilibrada do que a segunda. Nosso objetivo, portanto, é encontrar uma solução que minimize o desvio padrão.

(Note que o desvio padrão nunca é negativo e a solução ideal para o nosso problema, que divide os participantes perfeitamente, tem desvio padrão 0.)

Se você quiser tentar resolver o problema antes de ler sobre a solução, pare de ler aqui. Caso contrário, pode continuar a leitura.

Abordagem gulosa

Uma solução que que alguém poderia sugerir é inicialmente dividir a lista de nomes em $k$ partes e aí tentar, para cada um dos cortes, decidir se é melhor deslocá-lo para frente ou para trás. Talvez uma forma razoável de tomar essa decisão seja ver qual delas minimiza o desvio padrão para o conjunto que estamos deixando para trás.

Exemplo: Suponha que $a_1 = 42, a_2 = 25, a_3 = 27, a_4 = 18, a_5 = 38$ e $k = 3$. Então $\frac{t}{k} = \frac{150}{3} = 50$.

A solução proposta inicialmente divide esses nomes em 3 partes iguais. Os cortes das divisões estariam (1) entre o oitavo e o nono nome da letra B e (2) entre o sexto e o sétimo nome da letra D.

Para diminuir o desvio padrão do primeiro conjunto é melhor mover o primeiro corte para entre as letras A e B, porque 42 é mais próximo de 50 (diferença 8) do que 67 (diferença 17). Já para diminuir o desvio padrão do segundo conjunto é melhor mover o segundo corte para entre as letras C e D, porque 52 é mais próximo de 50 (diferença 2) do que 70 (diferença 20).

A solução encontrada portanto separa as letras em A, B-C e D-E.

Esse tipo de solução é chamado, na Ciência da Computação, de “guloso” (greedy, em inglês). As técnicas gulosas são aquelas que procuram soluções locais ótimas na esperança de encontrarem uma solução global ótima. Note que na solução sugerida otimizamos corte por corte (localmente), sem pensar muito sobre o que nos espera no futuro (global).

Algoritmos gulosos, quando encontram a solução ótima, são uma beleza: normalmente são fáceis de escrever e super rápidos. Porém, nem sempre algoritmos gulosos que funcionam para alguns casos funcionam para todos. Para não nos enganarmos, é sempre bom provar a corretude de um algoritmo guloso, isso é, provar matematicamente que ele funciona para todas as entradas. Já para provar que um algoritmo guloso não funciona basta apresentar um contra-exemplo, isso é, uma entrada para o qual o algoritmo guloso não produz a saída esperada.

Uma tentativa de explicar melhor, em termos lógicos, o parágrafo acima: Suponha que representemos nosso algoritmo como uma função $f$. Uma entrada é representada por $x$ e a saída esperada para $x$ é representada por $y$. Então, se o algoritmo funciona, esperamos que $\forall x (f(x) = y)$ (isso é, para todo $x$, o algoritmo leve $x$ em $y$). A negação dessa proposição lógica é $\exists x (f(x) \neq y)$ (isso é, existe $x$ tal que o algoritmo não leva $x$ em $y$). É por isso que para provar que um algoritmo não funciona para todas as entradas basta apresentar um contra-exemplo.

Afirmo que o algoritmo guloso apresentado acima não é capaz de encontrar a solução ótima para todas as entradas. Você é capaz de construir um contra-exemplo para provar isso?

Se quiser tentar construir um contra-exemplo por sua conta, pare de ler aqui. Caso contrário, pode continuar a leitura para ver o meu contra-exemplo.

Contra-exemplo: Suponha que temos 120 nomes, sendo que 35 começam com A, 8 com B, 27 com C e 50 com D. Queremos dividí-los em três mesas de credenciamento. Então temos $a_1 = 35, a_2 = 8, a_3 = 27, a_4 = 50$ e $k = 3$.

A abordagem gulosa inicialmente divide esses nomes em três partes iguais, conforme ilustração a seguir.

Então, corte por corte, vamos tentar minimizar o desvio padrão do conjunto de nomes que estamos deixando para trás. Para minimizar o desvio padrão do primeiro conjunto é melhor mover o primeiro corte para entre as letras B e C, porque 43 (35+8) é mais próximo de 40 do que 35. Já para minimizar o desvio padrão do segundo conjunto é melhor mover o segundo corte para entre as letras C e D. A solução encontrada pelo algoritmo guloso é portanto separar as letras nos conjuntos A-B, C e D.

O desvio padrão dessa solução é:

$$\sigma_g = \sqrt{\frac{1}{3} (3^2 + 13^2 + 10^2)} \approx 16.67.$$

Essa solução não é ótima para essa entrada, porque se tivéssemos colocado o primeiro corte entre A e B conseguiríamos um desvio padrão menor:

$$\sigma_\star = \sqrt{\frac{1}{3} (5^2 + 5^2 + 10^2)} \approx 12.25.$$

Logo, o algoritmo guloso não funciona para todas as entradas.

O contra-exemplo mostra como ótimos locais não implicam num ótimo global. A gulodice aqui não funcionou, por isso talvez seja melhor construir um algoritmo usando outras técnicas.

Força bruta

Como o computador é uma máquina capaz de executar bilhões de instruções por segundo (é exatamente isso que é medido pelos Hz que usamos para medir os processadores), uma forma de resolver problemas de otimização sem pensar muito é enumerar todas as soluções possíveis e compará-las. Essa abordagem é chamada, na Ciência da Computação, de força bruta (não confundir com bater nas pessoas para elas não reclamarem da fila de credenciamento).

Uma forma intuitiva de resolver este problema testando todas as soluções é construir um algoritmo recursivo que, a cada passo, faça um novo corte dividindo as letras que restam. Isso é, no primeiro passo tentamos colocar um corte entre todo par adjacente de letras, nos restantes tentamos colocar um corte entre todo par adjacente de letras a direita dos cortes já feitos.

Construiremos uma função recursiva $f$ que recebe dois parâmetros: $s$ é o índice da primeira letra do que resta no alfabeto e $m$ é o número restante de mesas que devem ser formadas. $f(s, m)$ vai retornar uma variância não normalizada (que para todos os efeitos é igual ao desvio padrão, porque minimiza ele) da solução ótima considerando as letras a partir de $s$ e dividindo-as em $m$ mesas de credenciamento.

Uma nota sobre desvio padrão e variância: A variância é o desvio padrão ao quadrado (isso é, sem tirar a raiz quadrada), ou seja, $\frac{1}{k} \sum_{i=1}^k \left(x_i - \frac{t}{k}\right)^2$. Como minimizar um número é a mesma coisa que minimizar ele ao quadrado, usamos a variância para não precisarmos nos preocupar em ficar tirando raízes no código. Esse valor $\frac{1}{k}$ é constante. Então o que chamei de variância não normalizada aí em cima é simplesmente $\sum_{i=1}^k \left(x_i - \frac{t}{k}\right)^2$. Minimizar esse valor é a mesma coisa que minimizar o desvio padrão. Nos parágrafos seguintes, chamarei simplesmente de variância o que aqui defini como variância não normalizada.

Vamos considerar que o vetor $a$ de números de nomes por letra é global, assim como o tamanho do alfabeto $n$ e o valor $\mu$ (mu, no código) que é a média $\frac{t}{k}$ que usaremos para computar a variância da solução. Estamos interessados na solução de $f(0, k)$, que é a solução do nosso problema porque é a variância da solução ótima considerando todas as letras e dividindo em $k$ mesas de credenciamento.

Essa recursão tem alguns casos-base para os quais podemos retornar imediatamente valores computados diretamente, a saber:

• $f(n, 0) = 0$ — isso é, se não há letras para serem divididas em conjuntos e não há cortes a serem feitos, então a variância da solução é 0 (não há nada a ser feito).
• $f(s, 0) = \infty$ para qualquer $s \neq 0$ — isso é, se há letras para serem divididas em conjuntos, mas não há mesas para colocá-las, então a variância da solução é infinita (o problema não tem solução).
• $f(n, m) = m \mu^2$ para qualquer $m \neq k$ — isso é, se não há letras para serem divididas e há $m$ mesas, então a variância da solução é $m\mu^2$ porque estamos somando $m$ mesas vazias (com 0 pessoas).

Para os demais $s, m$, temos:

Ou seja, fazemos todos os cortes possíveis (eles são representados por $i$) e minimizamos a variância correspondente a fazê-los: estamos somando a variância do conjunto $[s, i]$ (primeiro parâmetro da soma) com a variância da solução ótima para o conjunto $[i+1, n)$ com $m-1$ mesas (segundo parâmetro da soma).

Então o código da solução usando força bruta, em Python (linguagem escolhida porque está na moda), ficaria como segue:

a = [...]  # parâmetro de entrada (vetor com número de nomes por letra)
k = ...    # parâmetro de entrada (número de mesas)

n = len(a)       # tamanho do alfabeto
mu = sum(a) / k  # média usada para calcular as variâncias (t/k)

inf = float('inf')  # infinito

def f(s, m):
    if s == n and m == 0:
        return 0
    if m == 0:
        return inf
    if s == n:
        return m * mu * mu

    menor = inf
    soma = 0
    for i in range(s, n):
        soma += a[i]
        variancia = (mu - soma) ** 2
        resto = f(i+1, m-1)
        if variancia + resto < menor:
            menor = variancia + resto

    return menor

print("A variância da solução ótima é:", f(0, k))

Essa solução funciona (provar isso é um exercício de indução matemática: prova-se a solução dos casos-base e depois que subsoluções ótimas garantem soluções ótimas). Note que ela tem uma semelhança com o algoritmo guloso na medida em que a cada passo nos preocupamos com uma mesa (corte), porém ela testa todas as possibilidades possíveis de corte em vez de escolher gulosamente onde fazer cada corte.

O problema da força bruta é seu tempo de execução. Por mais rápido que sejam nossos computadores, custos exponenciais não são razoáveis para resolver problemas com entradas suficientemente grandes.

Uma observação sobre o universo: Segundo o consenso científico, o número de átomos no universo observável é por volta de $10^{80}$. Já a idade do universo é cerca de 14 bilhões de anos ($1.4 \times 10^{10}$), o que equivale a cerca de $4.4 \times 10^{26}$ nanossegundos. Suponha que todos os átomos do universo estejam, desde o surgimento do universo, realizando uma instrução computacional por nanossegundo, ou seja, cada átomo do universo seja um computador operando a 1GHz. Então até agora eles teriam realizado cerca de $4.4 \times 10^{106}$ operações. Se o tempo de execução de um algoritmo é exponencial no tamanho da entrada, o universo todo não é capaz de executá-lo para entradas suficientemente grandes — e “grande” nessa colocação são números que consideraríamos razoáveis, como 50 ou 100.

Testar todas as possibilidades costuma levar um tempo exponencial no tamanho da entrada, e no nosso problema não é diferente.

Um esboço relaxado para computar o tempo de execução da força bruta: Para medir o custo de um algoritmo recursivo, temos que construir e resolver uma recorrência. No nosso caso, temos:

$$T(n, k) = \sum_{i=1}^n T(n-i, k-1),$$

onde $T(n, k)$ denota o número de operações necessárias para resolver o problema com entrada $n, k$. Com alguma manipulação algébrica, podemos ver que, para $n > 1$, vale:

$$T(n, k) = T(n-1, k) + T(n-1, k-1),$$

que é exatamente a propriedade dos coeficientes binomiais conforme conferimos no Triângulo de Pascal. Os casos-base são um pouco diferentes dos coeficientes binomiais, por isso não se trata exatamente de dizer que o número de operações da solução seja ${n \choose k}$, mas dá para dizer que se aproxima disso por alguma constante. Portanto, o custo é exponencial no tamanho da entrada, na ordem de $2^n$.

Talvez seja razoável afirmar que a solução com força bruta é suficiente para o escopo do nosso problema quando estamos limitados ao alfabeto latino, que tem 26 letras. Porém, o que fazer caso o alfabeto seja maior — tenha, digamos, 1000 letras? Um algoritmo exponencial não é capaz de terminar na idade do universo neste caso nem com todos os átomos do universo trabalhando para isso. Isso nos motiva a usar programação dinâmica.

Programação dinâmica

Programação dinâmica, diferente do que o nome indica, não tem nada a ver (ao menos diretamente) com programação de computadores. Na verdade, há quem diga que um nome mais adequado para esse método de otimização de programas seria “recursão com uma tabela”.

Muitas vezes um subproblema é resolvido diversas vezes dentro de um procedimento recursivo; em particular, é fácil ver que isso acontece na força bruta proposta na seção acima. Note que $f(1, 3$) precisa do resultado de $f(2, 2), f(3, 2), f(4, 2), \cdots$ e também que $f(2, 3)$ precisa do resultado de $f(3, 2), f(4, 2), \cdots$. A tabela abaixo, mostrando a árvore de recursão para resolver o problema para $n = 6$ e $k = 4$, mostra que várias computações estão sendo repetidas.

A ideia da programação dinâmica é simplesmente tabelar os resultados da recursão para não precisar recalculá-los várias vezes. Usando programação dinâmica, tudo que está em vermelho na ilustração acima pode ser diretamente retornado pela função — não é preciso recomputar $f(s, m)$ mais de uma vez para nenhum par $s, m$.

A forma mais direta de implementar programação dinâmica em cima de um algoritmo recursivo é simplesmente guardar cada resultado da recursão numa tabela e usar os resultados já guardados previamente. Modificando o código da força bruta, temos:

# A linha abaixo inicializa com -1 uma matriz (n+1)x(k+1). Python é esquisito.
pd = [[-1 for i in range(k+1)] for j in range(n+1)]

def f(s, m):
    if s == n and m == 0:
        return 0
    if m == 0:
        return inf
    if s == n:
        return m * mu * mu
    if pd[s][m] != -1:
        # Já temos o resultado de f(s, m) e podemos retorná-lo diretamente.
        return pd[s][m]

    menor = inf
    soma = 0
    for i in range(s, n):
        soma += a[i]
        variancia = (mu - soma) ** 2
        resto = f(i+1, m-1)
        if variancia + resto < menor:
            menor = variancia + resto

    return pd[s][m] = menor

O número de operações agora é proporcional a $kn^2$, que é um valor polinomial no tamanho da entrada — ou seja, a programação dinâmica reduziu a complexidade exponencial do nosso problema e agora podemos resolvê-lo para alfabetos muito maiores. Para alfabetos de até mil letras e para até mil mesas de credenciamento um computador comum deve ser capaz de dar uma solução para o problema de forma eficiente em cerca de 1s. Mais importante, a medida que considerarmos alfabetos maiores o tempo de execução só aumenta por um fator polinomial — não mais exponencial.

A recursão, na solução com programação dinâmica, pode facilmente ser transformada em iterações. Para fazer isso, basta garantir que a tabela seja preenchida na ordem correta: não podemos tentar acessar alguma coisa que ainda não foi computada. O código abaixo mostra como poderia ficar uma implementação iterativa da programação dinâmica:

# Casos-base.
for m in range(k+1):
    pd[n][m] = m * mu * mu
for s in range(n+1):
    pd[s][0] = inf
pd[n][0] = 0

for s in range(n-1, -1, -1):
    for m in range(1, k+1):
        menor = inf
        soma = 0
        for i in range(s, n):
            soma += a[i]
            variancia = (mu - soma) ** 2
            resto = pd[i+1][m-1]
            if variancia + resto < menor:
                menor = variancia + resto
        pd[s][m] = menor

Por isso a programação dinâmica é muitas vezes apresentada como uma estratégia bottom-up e não top-down.

Programação dinâmica é uma técnica recorrente em problemas de olimpíadas de programação, como OBI, ACM ICPC, TopCoder, CodeForces, Google Code Jam e Facebook Hacker Cup, e possui muitas aplicações no mundo real. A Wikipedia tem uma lista de algoritmos clássicos que usam programação dinâmica.

Recuperando a solução

Nas seções anteriores apresentei alguns códigos que, embora encontrem o desvio padrão da solução ótima, não nos dizem qual é a solução — isso é, onde devem ser feitos os cortes. Há diversas formas de recuperar a solução a partir dos algoritmos mostrados. Uma que demandaria uma alteração simples nos códigos seria criar uma outra matriz $n \times k$ que guarda, para cada par $(s, m)$ o ponto em que fizemos o $m$-ésimo corte.

Para recuperar a solução, basta usar essa informação. O código completo ficaria como segue:

from typing import List

def final(a: List[int], k: int):
    """Exemplo de uso: final([35, 8, 27, 50], 3)"""
    n = len(a)       # tamanho do alfabeto
    mu = sum(a) / k  # média usada para calcular as variâncias (t/k)

    inf = float('inf')  # infinito

    pd = [[-1 for i in range(k+1)] for j in range(n+1)]
    sol = [[0 for i in range(k+1)] for j in range(n+1)]

    for m in range(k+1):
        pd[n][m] = m * mu * mu
    for s in range(n+1):
        pd[s][0] = inf
    pd[n][0] = 0

    for s in range(n-1, -1, -1):
        for m in range(1, k+1):
            menor = inf
            soma = 0
            for i in range(s, n):
                soma += a[i]
                variancia = (mu - soma) ** 2
                resto = pd[i+1][m-1]
                if variancia + resto < menor:
                    menor = variancia + resto
                    sol[s][m] = i
            pd[s][m] = menor

    print("A variância da solução ótima é:", pd[0][k])

    # soma[i] vale a soma dos numeros de a[0...i-1].
    soma = [0 for i in range(n+1)]
    soma[0] = 0
    for i in range(1, n+1):
        soma[i] = soma[i-1] + a[i-1]

    print("Partições:")
    s = 0
    for l in range(k):
        e = sol[s][k-l]
        print("%d. %d-%d (tamanho: %d)" % (l+1, s, e, soma[e+1] - soma[s]))
        s = e + 1

A saída desse programa para final([35, 8, 27, 50], 3) (entrada usada como contra-exemplo para o algoritmo guloso) é, como esperado:

A variância da solução ótima é: 150.0
Partições:
1. 0-0 (tamanho: 35)
2. 1-2 (tamanho: 35)
3. 3-3 (tamanho: 50)

(No alfabeto latino, A=0, B=1, C=2, D=3, etc.)

Finalmente

A ideia desse artigo foi mostrar como um problema real pode ser solucionado por meio de diferentes técnicas de projeto de algoritmos. Conhecer essas técnicas é útil para se abordar diversos problemas; não à toa elas são tão valorizadas em competições de programação. Espero que o artigo tenha utilidade para os que se interessarem em estudar Ciência da Computação durante esse estranho período em que muitos estamos fisicamente isolados.

Agradecimentos ao Pedro, que me apresentou o problema; ao Ulysses, que comentou que o problema apareceu na distribuição das vacinas do governo do Distrito Federal; e a todo mundo que chegou até aqui, pela leitura. Comentários são muito bem-vindos.

Algumas pessoas acreditam que a criptografia de ponta a ponta do WhatsApp seja a culpada pelo aplicativo de mensagens ser uma terra sem leis pela qual está sendo manipulada a eleição no Brasil. Casey Newton, no The Verge, opinou que um aplicativo de mensagens deve ter ou criptografia segura ou mecanismos de compartilhamento que permitam que coisas viralizem, mas não as duas coisas.

A explicação pode parecer razoável à primeira vista, afinal a segurança do WhatsApp garante que nem mesmo o Facebook possa ler o conteúdo das mensagens que trocamos no aplicativo.

As questões com a criptografia de ponta a ponta não são exatamente novas. Em julho de 2016, uma juíza bloqueou o acesso de todo o país ao WhatsApp argumentando que “se as decisões judiciais não podem ser efetivamente cumpridas, o serviço não poderá ser mais prestado, sob pena de privilegiar inúmeros indivíduos que se utilizam impunemente do aplicativo WhatsApp para prática de crimes diversos”.

Vale voltar um pouco na história para lembrar que o WhatsApp implementou criptografia de ponta a ponta depois dos vazamentos de Edward Snowden, que mostraram que agências de inteligência americanas coletam comunicações realizadas em todo o mundo com fins comerciais e políticos. Tais vazamentos aumentaram o debate público sobre vigilância e privacidade na rede, debate que se aprofunda à medida que novos problemas aparecem, como fake news e agências de inteligência estrangeiras influenciando eleições, sequestros digitais como o que comprometeu o funcionamento do sistema de saúde britânico e ciberataques como o que atingiu fortemente os computadores da Ucrânia.

É preciso compreender que abrir brechas de segurança num aplicativo usado por mais de 1 bilhão de pessoas coloca a segurança de todos nós em risco. Para além de comprometer a privacidade das comunicações que fazemos pelo aplicativo (de mensagens entre amigos a senhas, números de cartão, fotos, localizações) e permitir que se use o conteúdo das nossas comunicações para vender propaganda, um aplicativo sem criptografia ajuda os poderosos que controlam a infra-estrutura de Internet a controlar nações inteiras e nunca é positivo para os ativistas. Como escreveu Julian Assange na época em que foram divulgados os documentos de Snowden: “A criptografia pode proteger não somente as liberdades civis e direitos dos indivíduos, mas a soberania e independência de países inteiros, solidariedade entre grupos com causas comuns e projetos de emancipação global.”

Pelo acúmulo que temos nos debates sobre a Internet e o ativismo digital, os que lutamos contra o imperialismo e defendemos Edward Snowden devemos defender a criptografia de ponta a ponta sem tergiversar.

A questão então é como impedir fraude nas eleições e a disseminação de desinformação num ambiente que não se consegue monitorar.

Um grupo de pesquisadores fez um interessante estudo sobre a disseminação de notícias falsas em grupos públicos e sugere três ideias que teriam que ser implementadas pelo próprio WhatsApp: restringir o número de contatos/grupos para os quais uma mensagem pode ser encaminhada de uma vez só de 20 para 5 (como foi feito na Índia), diminuir o número máximo de contatos em listas de transmissão (atualmente 256) e diminuir o número máximo de pessoas em grupos criados nos próximos dias (até o dia da eleição).

Essas ideias são, a meu ver, pouco efetivas e prejudiciais ao ativismo. A extrema-direita no Brasil constrói sua rede há anos e já possui muitos milhares de grupos, enquanto quem está criando novos grupos neste momento é justamente quem busca resistir ao bolsonarismo. Além disso, quem encaminha mensagens de forma manual ou por listas de transmissão, sem usar robôs, são as pessoas comuns e não as grandes máquinas. Parece que é a viralização entre pessoas comuns (que compartilham mensagens nos seus grupos de família, amigos, igreja, trabalho) que essas ideias querem combater. São sugestões que podem contribuir para diminuir o alcance de fake news (e também true news) nos próximos dias (ainda que dificilmente poderiam ser implementadas nesse tempo), mas não atacam o centro do problema.

A SaferNet sugere que se insiram mecanismos de fact checking dentro do aplicativo e que se avise ao usuário quando um conteúdo é falso por meio do uso de um hash para identificar arquivos de mídia. Essa ideia pode ser efetiva para o futuro, mas é necessário pensar com cuidado nas implicações que teria na segurança da criptografia. Ainda que se chegue à conclusão de que ela não compromete a nossa segurança, exige bastante cuidado e engenharia para ser implementada: seriam necessárias mudanças profundas tanto do lado do cliente (atualização de todos os aplicativos nos celulares de todas as pessoas) como do lado do servidor do WhatsApp. É impossível realizá-la nos menos de 7 dias que faltam até as eleições e não serve para fazer algum tipo de investigação retroativa.

Nesse conjunto de medidas paliativas, penso em outras duas que podem ser tomadas por empresas no Brasil e que também podem ajudar. A primeira é cumprir o princípio da neutralidade da rede, dessa forma evitando que sejam vendidos planos de Internet que privilegiam o tráfego do WhatsApp sobre os outros. Atualmente, o acesso a Internet de muitos brasileiros é limitado: se você só tem acesso gratuito ao WhatsApp e não a outros sites, é difícil verificar as informações que você recebe. A segunda depende da imprensa tradicional que tanto critica a proliferação de desinformação: elas deveriam retirar de seus sites os mecanismos de paywall que impedem as pessoas de ler o conteúdo das notícias e dessa forma colaboram para um ambiente no qual se lê apenas os títulos.

Para atacar o coração do problema, porém, minha opinião é que a reportagem de capa da Folha do dia 18/10 dá o caminho: é necessário denunciar e investigar profundamente as empresas que financiam, via caixa 2, o disparo de mensagens via WhatsApp, assim como as empresas que fazem esses disparos. A justiça deveria ir atrás do rastro do dinheiro e dos envolvidos nesse tipo de operação ilegal, como fizeram jornalistas da BBC para escrever uma brilhante reportagem que mostra o funcionamento de algumas dessas empresas. É preciso investigar para descobrir, combater e punir quem financia, quem cria e quem dispara as notícias falsas.

Para ajudar nessa investigação é bom lembrar que, embora o conteúdo de mensagens trocadas no WhatsApp seja protegido por criptografia de ponta a ponta, os metadados do sistema não são. Ou seja, é possível exigir do Facebook e ir atrás dos endereços de IP que usaram determinados números de telefone que comprovadamente espalham fake news, assim como saber quantas mensagens tais números enviaram, quando, para que números e que grupos, quantas pessoas tem nesses grupos etc. A polícia e a justiça brasileira sabem disso, por isso colocar a culpa em algum aspecto técnico da plataforma parece cortina de fumaça. Deveríamos responsabilizar as instituições brasileiras por resguardar a democracia no nosso país e não o Mark Zuckerberg, embora ele tenha afirmado no início do ano que faria tudo que fosse necessário para garantir a integridade das eleições no Brasil.

Investigar num ambiente com mensagens criptografadas sem dúvidas dá mais trabalho do que se toda a rede fosse completamente transparente e todas as nossas comunicações estivessem permanentemente violadas, mas é possível e necessário.

Publicado originalmente na Revista Movimento.

Estão transformando “algoritmo” num termo pejorativo e usando ele de forma muito esquisita. Acabei de ler, numa matéria do G1, sobre um programa de computador “sem algoritmos”.

Um algoritmo nada mais é que uma sequência de operações bem definida. É um procedimento que em geral recebe uma entrada, faz um monte de coisas com ela e devolve uma saída.

A ciência da computação é fundamentalmente a ciência dos algoritmos. E, embora os algoritmos não dependam de computadores, os computadores são máquinas que realizam operações que são formalizadas por meio de algoritmos, de forma que é difícil imaginar um programa de computador sem algoritmos.

Um exemplo de algoritmo é o algoritmo de Euclides, de 300 a.C., que encontra o máximo divisor comum entre números inteiros tomando o resto da divisão de um pelo outro sucessivamente.

Nos últimos anos, a palavra “algoritmo” está muito relacionada ao Facebook — como se vê nessa matéria do G1. Isso porque o Facebook usa um algoritmo de aprendizado de máquina para definir as publicações que cada pessoa vê no seu feed de notícias e a ordem em que essas publicações aparecem. O Instagram também usa um algoritmo pro mesmo propósito, mas não parece ser tão odiado.

As críticas sobre o Facebook seriam mais úteis se fossem dirigidas ao seu modelo de negócios, à bestificação das redes sociais, ao monopólio, à coleta de informações em massa e à cultura da pós-verdade, não à existência de algoritmos. Da forma que têm sido feitas, escondem num jargão pretensamente técnico decisões que são tomadas para maximizar lucros mantendo pessoas dentro da plataforma compartilhando coisas, vendo e clicando em publicidade. Ou seja, se fala de “algoritmo” em abstrato mas acaba não se falando de qual algoritmo, isso é, do filtro do Facebook e com que interesses ele é desenvolvido.

Por fim, com WhatsApp Business, API oficial e saída de Jan Koum, eu chutaria que o WhatsApp vai estar também cada vez mais sujeito a “algoritmos” — ou, sem mistificação, interesses comerciais.

Um exercício matemático e computacional sobre os métodos usados para alocar vagas nas eleições proporcionais do Brasil. Estava refletindo sobre isso uns dias atrás e estou colocando aqui para sistematizar, compartilhar e saber o que outras pessoas acham. A epígrafe é: O quociente eleitoral está morto; vida longa à menor sobra!

O Código Eleitoral brasileiro determina a forma como são eleitos os candidatos a cargos proporcionais (deputados e vereadores) no seu capítulo IV. O método consiste, em resumo, em:

1. Calcular o quociente eleitoral $q$, definido como a soma do total de votos válidos (isso é, sem contar abstenções, brancos e nulos) $t$ dividida pela quantidade de vagas a preencher $s$, arredondada para o número inteiro mais próximo. Isso é, $q := \left[\frac{t}{s}\right]$.
2. Para cada partido ou coligação $i$, calcular o quociente partidário $p_i$, definido como o número de votos obtidos pelo partido ou coligação $v_i$ dividido (divisão inteira, ou seja, desprezada a fração) pelo quociente eleitoral $q$. Isso é, $p_i := \left\lfloor \frac{v_i}{q} \right\rfloor \forall i$. Então, $p_i$ é a quantidade inicial de vagas atribuídas ao partido ou coligação $i$.
3. Dividir as $s - \sum_{i} p_i$ vagas restantes de acordo com o Cálculo das Sobras, também conhecido como Cálculo das Médias. Tal método é definido pela repetição do seguinte processo enquanto houver vagas restantes (copiado da lei): “o número de votos válidos atribuídos a cada partido político ou coligação será dividido pelo número de lugares por eles obtidos mediante o cálculo do quociente partidário mais um, cabendo ao partido político ou à coligação que apresentar a maior média um dos lugares a preencher, desde que tenha candidato que atenda à exigência de votação nominal mínima”.

Para além desse algoritmo, vale fazer duas considerações importantes sobre o método que vão reaparecer em outros momentos deste texto:

1. Até a eleição de 2016, os partidos ou coligações $i$ que não tivessem quociente partidário $p_i \geq 1$ não participavam do Cálculo das Sobras. Tal restrição foi removida na reforma eleitoral de 2017.
2. A partir da eleição de 2016, foi imposta uma cláusula de barreira (aprovada em 2015) que exige que candidatos tenham 10% do quociente partidário para poderem ser eleitos (a não ser no caso em que não há candidatos nessa condição). Esse fato vai ser desprezado nesse artigo. Ou seja, vamos assumir que todos os partidos ou coligações que tiverem uma vaga de acordo com o método têm também candidatos aptos a serem eleitos.

A implementação do método descrito acima em C++ (escolhi essa linguagem para usar a fila de prioridades da STL) seria como segue:

// Estrutura usada para ordenar partidos de acordo com suas sobras.
struct party {
  int index, votes, seats;
  bool operator < (const party &o) const {
    return votes / (double) (seats + 1) < o.votes / (double) (o.seats + 1);
  }
};

vector <int> codigoEleitoral(vector <int> v, int s) {
  // Pré-calculo de t, o número total de votos válidos.
  int t = 0;
  for (int i = 0; i < v.size(); i++) {
    t += v[i];
  }

  // Passo 1: calcular o quociente eleitoral.
  int q = round(t / (double) s);

  // Passo 2: calcular o quociente partidário e alocar primeiras vagas.
  priority_queue <party> Q;
  for (int i = 0; i < v.size(); i++) {
    s -= (int) (v[i] / q);
    Q.push((party) {i, v[i], v[i] / q});
  }

  // Passo 3: Cálculo das Sobras ou Médias.
  while (s--) {
    party p = Q.top();
    Q.pop();
    p.seats++;
    Q.push(p);
  }

  // Reconstrução do resultado.
  vector <int> result(Q.size(), 0);
  while (!Q.empty()) {
    party p = Q.top();
    result[p.index] = p.seats;
    Q.pop();
  }

  return result;
}

Sua complexidade é $\Theta((n+s) \log n)$, onde $n$ é o número de partidos ou coligações. O logaritmo vem do uso da heap implementada pela STL (priority_queue).

A partir dessas definições e desse método, gostaria de compartilhar alguns pensamentos.

Equivalência com D’Hondt

Primeiramente, é bom observar que o Método D’Hondt é exatamente o que é chamado de Cálculo das Médias no Código Eleitoral. Como descreve a Wikipedia:

O método [D’Hondt] consiste numa fórmula matemática, ou algoritmo, destinada a calcular a distribuição dos mandatos pelas listas concorrentes, em que cada mandato é sucessivamente alocado à lista cujo número total de votos dividido pelos números inteiros sucessivos, começando na unidade (isto é no número 1) seja maior. O processo de divisão prossegue até se esgotarem todos os mandatos e todas as possibilidades de aparecerem quocientes iguais aos quais ainda caiba um mandato.

A tabela abaixo, da distribuição de 8 vagas para 4 partidos, ajuda a visualizá-lo:

Mais interessante do que perceber que o Cálculo das Médias do Código Eleitoral é o Método D’Hondt, porém, é observar que o método completo brasileiro (não apenas o cálculo das médias) é equivalente matematicamente ao Método D’Hondt, isso é, os dois métodos distribuem as vagas da mesma forma.

Creio que a forma mais fácil de provar isso consista em demonstrar que um partido ou coligação tem uma vaga pelo Código Eleitoral se e somente se tem tal vaga pelo Método D’Hondt. Talvez mostrar que o D’Hondt e o Código Eleitoral decidem as $\sum_i p_i$ primeiras vagas da mesma forma? Será que não bastaria provar que o quociente eleitoral é maior ou igual ao menor número negrito na tabela do D’Hondt (conceito que chamaremos de menor sobra e definiremos melhor até o final desse artigo)? Intuitivamente isso parece não ser muito difícil, mas na prática não fiz e vou considerar que essa prova maravilhosa não cabe nas margens desse artigo.

O importante é que, aceitando esse fato, nota-se que o Código Eleitoral poderia ser simplificado deixando de lado o cálculo do quociente eleitoral e do quociente partidário, aplicando apenas o Cálculo das Sobras/Médias (ou Método D’Hondt) desde o princípio. Sua implementação poderia ser, assim, reduzida para:

vector <int> dhondt(vector <int> v, int s) {
  priority_queue <party> Q;
  for (int i = 0; i < v.size(); i++) {
    Q.push((party) {i, v[i], 0});
  }

  // Cálculo das Sobras ou Médias (D'Hondt).
  while (s--) {
    party p = Q.top();
    Q.pop();
    p.seats++;
    Q.push(p);
  }

  // Reconstrução do resultado.
  vector <int> result(Q.size(), 0);
  while (!Q.empty()) {
    party p = Q.top();
    result[p.index] = p.seats;
    Q.pop();
  }

  return result;
}

A complexidade computacional claramente seria a mesma, mas reduzir o esforço mental para entender o cálculo e também o código — evitando calcular os arredondamentos de quociente eleitoral e quociente partidário — parece bom.

A verdade é que isso nos motiva a perceber que a única utilidade do quociente eleitoral $q$ tem a ver com as duas considerações que fiz acima e informei que iriam aparecer em outros momentos do texto. De fato, em 2018, a única utilidade do quociente eleitoral será barrar candidatos que não tenham 10% desse quociente.

Já o quociente partidário $p_i$ teria importância se ainda houvesse a necessidade dos partidos ou coligações $i$ terem $p_i \geq 1$ para participar do Cálculo das Médias. Sem tal mecanismo, já não serve para nada.

A menor sobra é o xis da questão

O quociente eleitoral tinha importância porque era nele que se devia mirar para eleger o primeiro candidato de um partido ou coligação. Com a mudança no Código Eleitoral, o número fundamental da eleição deixa de ser o quociente eleitoral e passa a ser a menor sobra $x$, que defino como o menor número na tabela do Método D’Hondt que garante vaga.

Matematicamente, $x := \min_i \frac{v_i}{r_i}$, onde $v_i$ é a quantidade de votos do partido ou coligação $i$ e $r_i$ é o número de vagas alocadas ao partido ou coligação $i$ no final do processo.

A menor sobra não é importante apenas para que se saiba quantos votos são necessários para eleger o primeiro candidato de um partido ou coligação (como antes era o quociente eleitoral), mas para saber quantos candidatos cada partido ou coligação vai eleger. Com efeito, é fácil ver que o número de candidatos a serem eleitos por um partido ou coligação é $\left\lfloor\frac{v_i}{x}\right\rfloor$. Isso a torna especialmente interessante, muito mais útil do que o velho quociente.

Refletir sobre a importância da menor sobra sugere um algoritmo que evita a implementação do D’Hondt e da fila de prioridades: uma simples busca binária para encontrar $x$, dado que quanto menor [maior] é $x$ mais [menos] candidatos são eleitos.

vector <int> menorSobra(vector <int> v, int s) {
  int a = 0, b = 0;

  // Encontrando o limite superior para a busca binária.
  for (int i = 0; i < v.size(); i++) {
    b = max(b, v[i] + 1);
  }

  // Busca binária para encontrar x.
  while ((b - a) > 1) {
    int x = (a + b) / 2, y = 0;
    for (int i = 0; i < v.size(); i++) {
      y += v[i] / x;
    }
    if (y < s) {
      b = x;
    } else {
      a = x;
    }
  }

  // Construção do resultado dividindo votos de cada partido por x.
  vector <int> result(v.size(), 0);
  int x = (a + b) / 2;
  for (int i = 0; i < v.size(); i++) {
    result[i] = v[i] / x;
  }

  return result;
}

Esse algoritmo tem complexidade $\Theta(n \log t)$, que me parece razoável.

Por tudo isso, exceto se a sua preocupação for com a cláusula de barreira de 2015 — isso é, com fazer seu candidato atingir 10% do quociente eleitoral —, pareceria que vale esquecer o quociente eleitoral e o algoritmo do TSE, dando centralidade à menor sobra.

Do ponto de vista prático, como, porém, estimar a menor sobra antes de ter os dados de uma eleição (que ainda não tenha acontecido, por exemplo)?

Bem, sabemos que ela é limitada superiormente pelo quociente eleitoral ($x \leq q$), que é fácil de estimar já que se conhece o tamanho do colégio eleitoral, o número de vagas a serem preenchidas e dá pra chutar uma proporção de votos válidos. Ao menos, é bem mais fácil do que estimar a configuração completa do resultado de uma eleição. Então, só por isso, talvez valha, ainda, não descartar o quociente eleitoral.

Alguns roteadores distribuídos pela NET (como alguns da marca TechniColor, mas possivelmente outros) estão bloqueando conexões para a porta 22, o que atrapalha bastante quem precisa fazer conexões via SSH.

A solução óbvia para o problema seria reconfigurar o roteador. Porém, a NET parece estar dificultando cada vez mais o acesso aos roteadores dela.

E é difícil explicar na central de relacionamento que você precisa do usuário e senha para acessar a configuração do roteador e por que você precisa disso… eu tentei, mas acho que meu interlocutor entendeu que eu queria a chave do Wi-Fi e no fim não consegui nada!

Então, sem paciência para resolver o problema da forma correta, resta fazer gambiarras. Felizmente, tais gambiarras podem também ser usadas em outros lugares que bloqueiam conexões para a porta 22 (por exemplo, algumas universidades, escolas e aeroportos, locais de trabalho etc).

A gambiarra trivial seria usar alguma VPN, mas isso não valeria um post.

Então, aqui quero falar de outras duas que encontrei buscando uma solução mais elegante para o problema.

A primeira requer que você possa mudar a porta SSH de algum servidor que tenha acesso

Se você puder mudar o SSH para uma porta alternativa (tipo 2222) em algum servidor alice.com em que você seja root, pode usá-lo como túnel (ok, essa solução é meio parecida com VPN, mas foi mais fácil & barata no meu caso).

Para mudar a porta nesse servidor é só editar /etc/sshd_config, mudar a linha Port 22 para Port 2222 e reiniciar o serviço do SSH — algo como service ssh restart (a depender da distribuição que você estiver usando).

Aí, pra usar esse servidor como túnel, você pode fazer duas coisas (do lado do cliente).

Se você só quer acessar um servidor bob.com, pode usar, como sugerido aqui:

$ ssh -N -L 3333:bob.com -p 2222 alice.com

# em outro terminal
$ ssh -p 3333 127.0.0.1

Se você quer acessar vários servidores — não só bob.com, mas também charlie.com (me parece mais útil), pode criar um proxy do tipo SOCKS num terminal e usá-lo em outros:

$ ssh -D 3333 -N -p 2222 alice.com

# em outros terminais
$ ssh -o ProxyCommand='nc -x 127.0.0.1:3333 %h %p' bob.com
$ ssh -o ProxyCommand='nc -x 127.0.0.1:3333 %h %p' charlie.com

Pra evitar lembrar da sintaxe desse ProxyCommand, que usa netcat e copiei daqui, você poderia adicioná-lo em ~/.ssh/config:

ProxyCommand nc -x 127.0.0.1:3333 %h %p

Aí, depois de criado o túnel, basta usar SSH normalmente:

$ ssh -D 3333 -N -p 2222 alice.com

# em outros terminais
$ ssh bob.com
$ ssh charlie.com

A segunda é para caso você só precise acessar GitHub e Bitbucket

Resolve o problema pra maioria dos usos de Git via SSH e o bom dela é que você pode fazer uma vez e esquecer.

Felizmente, esses serviços disponibilizam servidores/portas alternativas que você pode usar para se conectar neles.

O GitHub oferece conexão SSH na porta 443 do servidor ssh.github.com; o Bitbucket oferece conexão SSH na porta 443 do servidor altssh.bitbucket.org.

Como 443 é a porta de HTTPS (TLS), é bem difícil essa porta estar bloqueada na rede em que você estiver.

Pra evitar ter que editar os remotes de todos os seus repositórios, você pode resolver o problema pra sempre adicionando o seguinte no seu ~/.ssh/config:

Host bitbucket.org
  HostName altssh.bitbucket.org
  Port 443

Host github.com
  HostName ssh.github.com
  Port 443

Se conhecer outras soluções interessantes, fique à vontade para compartilhar na caixa de comentários!