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.

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.

Imagine-se num prédio de 100 andares com várias bolas. A partir de um determinado andar (desconhecido), quando você joga uma bola pela janela, a bola quebra. Você quer determinar precisamente qual é esse andar e a única coisa que pode fazer é jogar bolas de andares diferentes.

Se você tem muitas bolas e não se importa em quebrar quantas forem necessárias, você pode realizar uma busca binária. Uma busca binária, para começar com um exemplo, é aquilo que você faz naquele diálogo clássico:

— Pense num número de 1 a 100 e eu vou tentar adivinhar. A cada palpite, você precisa me dizer se o número que você pensou é maior ou menor do que meu chute.
— Pensei.
— 50
— Maior.
— 75
— Menor.
— 63
— Menor.
— 57
— Menor.
— 54
— Menor.
— 52
— Menor.
— 51
— Acertou!

A cada passo numa busca binária você divide o intervalo de possibilidades por dois. Você descarta metade dos números que poderiam ser a solução. Por isso, mesmo que você pense num número de 1 a 1.000.000.000 (um bilhão) eu certamente não vou demorar mais de 30 (isso é, logaritmo de um bilhão na base dois) tentativas para acertar exatamente o número que você pensou.

Por que logaritmo de um bilhão na base dois? Como eu comentei anteriormente, a cada número que eu chuto e você diz se é maior ou menor do que o resultado eu corto meu intervalo por dois. Portanto, o número de chutes necessários (no pior caso) é precisamente a quantidade de vezes que preciso dividir um bilhão por dois até chegar a um (até sobrar um único número possível para eu chutar, que necessariamente vai ser o número que você pensou).

Nosso problema é encontrar quantos 2 tem aí. Dividir um número por 2 k vezes é o mesmo que dividir por $2^k$. Logo, nosso problema é encontrar quanto vale k:

Multiplicando os dois lados da igualdade por $2^k$, temos:

Tirando o logaritmo na base 2, concluímos:

Ou seja, o logaritmo de n na base 2 é o número de vezes que precisamos dividir n por 2 para chegar em 1. Voltando ao problema inicial, como $log_2 100 < 7$, precisaremos jogar no máximo 7 bolas para determinar a partir de qual andar a bola quebrar. Quando você jogar uma bola, se ela quebrar é a mesma coisa que o seu amigo que pensou num número dizendo “O número que eu pensei é menor.” Se ela não quebrar, é equivalente ao seu amigo dizendo “O número que eu pensei é maior.”

Realizando uma busca binária, o pior caso (aquele caso no qual quebraremos mais bolas – e que jogaremos a maior quantidade de vezes) é quando a bola quebra no primeiro andar. Você joga as bolas dos andares 50 (poft!), 25 (poft!), 13 (poft!), 7 (poft!), 4 (poft!), 2 (poft!), 1, jogando um total de 7 e quebrando um total de 6 bolas.

Nada muito novo para quem já conhecia busca binária. Por isso, vamos modificar o problema: Suponha que você não tenha quantas bolas desejar, mas apenas duas bolas. Quando uma bola cai sem quebrar, você pode descer, pegá-la e jogá-la de novo. Qual a menor quantidade de vezes que você vai ter que jogar a bola para com certeza determinar a partir de qual andar as bolas começam a quebrar?

Fazer uma busca binária não funciona mais. No caso de a bola quebrar a partir do primeiro andar, assim que você joga uma bola do andar 50 (uma bola quebra) e outra do 25 (outra bola quebra), você não tem mais bolas e não tem ideia de qual é o andar a partir do qual as bolas começam a quebrar (tudo o que você sabe é que é algum andar entre 1 e 25).

Como usar as duas bolas para determinar exatamente o andar a partir do qual as bolas começam a quebrar jogando as bolas a menor quantidade possível de vezes? Qual é essa quantidade mínima de vezes que será necessário jogar bolas pela janela?

Obrigado ao David por ter me apresentado o problema. A solução é bem legal!

Editado para ficar mais claro: A quantidade mínima que queremos é a do pior caso, isso é, a menor quantidade de vezes que será necessário jogar a bola independente de qual for o andar. Por exemplo, suponha que eu jogue uma bola do andar 5 e não quebre. Aí eu jogue do andar 10 e não quebre. Do 15 e não quebre. E assim sucessivamente (de 5 em 5) enquanto ela não quebrar. Quando ela quebrar, eu pego a outra bola e jogo no último valor que eu joguei menos 4, menos 3, menos 2 e menos 1. O pior caso para esse algoritmo é quando a bola quebrar a partir do andar 99. Jogarei nos andares 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100 (poft!), 96, 97, 98, 99 (poft!), ou seja, 24 vezes. (Mas é possível usar um algoritmo mais esperto que isso: a resposta do problema é menor que 24.)

Editado para programadores: A generalização deste problema (para n andares em vez de 100 e k bolas em vez de 2) caiu na OBI 2010 (o problema se chama Altas Aventuras) e está no SPOJ para quem quiser resolver: ALTAS2. Quem me contou foi o André.

Mohammad Mahdian * (tradução: Tiago Madeira)

Os levantes recentes no Oriente Médio demonstraram a eficácia da internet em ajudar ativistas políticos e sociais a organizarem protestos, disseminarem informações para o público e enviarem notícias de prisões e repressões ao restante do mundo. Ameaçados por esse paradigma, regimes totalitários tentaram controlar e monitorar o acesso de seus cidadãos à web, desenvolvendo ou adquirindo tecnologias de censura e de vigilância da internet. Ao mesmo tempo, uma variedade de ferramentas de violação desses filtros foi desenvolvida para ajudar os usuários a contornarem o filtro da internet acessando sites bloqueados através de intermediários não-bloqueados (os chamados proxies). O artigo de Dan Boneh (Recent Ideas for Circumventing Internet Filtering) dá um ótimo resumo sobre novas e velhas técnicas para construir essas ferramentas.

No coração de todos os métodos de violação existe o seguinte dilema: Para fazer a ferramenta disponível ao público, os endereços de proxy precisam ser comunicados para os usuários. Isso, no entanto, permite que as autoridades obtenham esses endereços (fingindo serem usuários legítimos) e aí bloqueiem todo o tráfego nesses endereços específicos. Ter vários proxies de curta duração alivia o problema, mas a questão permanece: Existe algum método algorítmico esperto para distribuir proxies que diminua o número de proxies necessários para fornecer acesso à internet sem filtro?

O problema de distribuição de proxy

Vamos começar definindo um modelo teórico simples para este problema. Nós gostaríamos de distribuir um conjunto de m proxies para uma população de n usuários: k deles são adversários (agentes da censura) e o restante (n-k) são usuários legítimos. Nós não sabemos as identidades dos adversários, mas podemos assumir que k << n. Na verdade, para simplicidade, pense em k como uma constante, enquanto n cresce ao infinito.

Se um proxy é dado a um adversário, ele pode comprometer o proxy, tornando-o inutilizável para os outros usuários. Uma vez que um proxy é comprometido, nós ficamos sabendo e podemos distribuir outros proxies para os usuários afetados. Nossa meta é garantir que todo usuário legítimo tenha pelo menos um proxy não-comprometido. A questão é: qual é o menor m com o qual conseguimos fornecer essa garantia?

Claramente, o problema pode ser resolvido com n proxies dando pra cada usuário um proxy diferente. Na verdade, podemos fazer muito melhor usando um algoritmo de busca binária: Comece dividindo os usuários em duas caixas e dê pra cada caixa o seu proxy. Uma vez que um proxy é comprometido, divida sua caixa correspondente pela metade e dê para cada uma das metades um proxy. Continue fazendo isso enquanto existe apenas um usuário na caixa. É fácil ver que esse método usa no máximo O(log(n)) proxies. Uma divisão cuidadosa dos usuários em caixas rende uma solução com no máximo $k(1+log_2(n/k))$ proxies.

Podemos resolver o problema com menos de O(log(n)) proxies? Talvez surpreendentemente, nós podemos fazer um pouco melhor. Há um algoritmo randomizado de distribuição de proxies que usa no máximo O(log(n)/loglog(n)) proxies. Um argumento simples de entropia mostra que isso é assintoticamente ótimo para um k constante.

Distribuição de proxies via redes de confiança

Uma forma comum de construir uma base de usuários num país sob censura é através de relações pessoais de confiança. O sistema começa com poucos usuários confiáveis e então cada usuário confiável pode convidar novos usuários em quem ele confia para o sistema. Dessa forma, o conjunto de usuários cresce como uma rede de confiança: uma árvore enraizada na qual o conjunto de usuários confiáveis inicial é filho da raiz e arestas indicam relações de confiança.

Usar uma rede de confiança dificulta que um adversário se infiltre na base de usuários. No entanto, o problema é que uma vez que a rede é infiltrada, o adversário pode convidar novos adversários para a rede. Para levar isso em conta, nós modificamos a formulação do problema como segue: em vez de exigir que um pequeno número de usuários seja adversário, nós assumimos que um pequeno número de usuários e todos os seus descendentes na rede são adversários. Uma forma alternativa de formular esse problema é considerar redes de confiança capacitadas e assumir que o menor corte da raiz para todos os adversários é no máximo um pequeno número k.

O problema de distribuição de proxy em redes de confiança está ainda sem solução em geral. Temos resultados parciais para pequenos k e no caso capacitado. Os algoritmos são não-triviais e precisam olhar para a estrutura da rede de confiança.

Conclusão

O objetivo desse exercício era convencer o leitor de que existe um problema teórico interessante e desafiante no âmago das tecnologias de violação de censura. Modelos e algoritmos para esse problema estão muito próximos dos que são usados na prática e, logo, há potencial para pesquisa nessa área que pode ter um impacto real nas vidas de milhões de pessoas vivendo sob opressão.

* Mohammad Mahdian é um pesquisador senior do Yahoo Research Lab em Santa Clara, CA. É bacharel em Engenharia da Computação pela Universidade de Tecnologia de Sharif, mestre em Ciência da Computação pela Universidade de Toronto e PhD em Matemática pelo MIT. Seus interesses de pesquisa atuais incluem projeto de algoritmos, economia algorítmica e aplicações em publicidade online e redes sociais.

Este texto foi publicado em inglês na última edição da XRDS (revista da ACM para estudantes), cujo tema é Ciência da Computação a serviço da democracia. No site do autor, há o artigo “Fighting censorship with algorithms” completo em PDF disponível para download gratuito. Ainda não li, mas parece interessante.