24 de dezembro de 2011

Combatendo a censura com algoritmos

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.

Publicado às 15:11 em Curiosidades | 2 comentários

24 de abril de 2010

Coordenadas homogêneas

Conheci as coordenadas homogêneas por acaso. Era 2004, ganhei a modalidade iniciação da Olimpíada Brasileira de Informática e passei o inverno estudando C, acho que por dois motivos: interesse pelos problemas da modalidade programação e desejo de aproveitar bem o curso que os medalhistas fazem na UNICAMP; ou talvez fosse apenas falta do que fazer ou curiosidade mesmo. Não importa.

Confundo os cursos de 2004, 2005 e 2006, mas lembro que no primeiro aprendi com um monitor sobre recursão, representação de grafos e busca em profundidade. Lembro também que foi em 2004 que conheci o CLRS (livro que comprei alguns meses depois e tenho na cabeceira até hoje). Esse post, porém, é sobre um acontecimento mais aleatório relacionado a esse curso e, ouso afirmar, digno de figurar n’O Andar do Bêbado do Mlodinow.

O pessoal da modalidade programação ia tirar cópias de um livro do Stolfi e do Rezende, chamado “Fundamentos de Geometria Computacional” (dá pra baixar aqui). Nem sabia do que estavam tirando xerox, mas vi que era barato e que todos os mais velhos estavam querendo, então também pedi.

Folheei o livro, não entendi nada, deixei num canto e voltei a abrir alguns anos depois, não lembro exatamente quando. E foi aí que fez-se a luz. A primeira parte é sobre coordenadas homogêneas.

Coordenadas homogêneas? A ideia parece simples (até demais) pra ser poderosa. Basicamente você representa uma coordenada em (X, Y) \in \mathbb{R}^2 com uma tripla ordenada [w, x, y] tal que x = \frac{X}{w} e y = \frac{Y}{w}. A reta tem a mesma representação.

1
2
3
4
5
struct ponto {
	int w, x, y;
};
 
typedef ponto reta;

E o que isso tem demais? Você deixa de precisar de pontos flutuantes pra maioria das operações geométricas; ganha pontos no infinito (eles são a interseção entre retas paralelas!) que permitem fazer fórmulas sem preocupação com casos especiais, usar a mesma fórmula pra determinar uma reta gerada por dois pontos ou por um ponto e um vetor etc.; tem representações iguais (e dualidade) entre pontos e retas (e.g. interseção entre retas p e q = reta determinada por pontos p e q); e mais um monte de outras coisas.

Uau! Como eu não ouvi falar disso antes? Eu não sei a razão, mas, embora tenham várias vantagens, as coordenadas homogêneas não são muito populares na universidade, nem entre os maratonistas. No entanto, são usadas em projetos grandes que usam muita geometria (e.g. OpenGL).

Quero código! Vou mostrar como resolvi o problema Symmetry (2002 TopCoder Inv Round 4 – Division I, Level Three).

O enunciado é simples: Dados n (2 \leq n \leq 200) pontos inteiros (com coordenadas de -10000 a 10000) determinar quantas linhas de simetria existem entre eles.

Dá pra fazer em O(n^3) com a seguinte ideia:

  1. Crie uma árvore binária balanceada indexada por retas. (em C++, map <reta,int>)
  2. Para cada par de pontos, determine a reta de simetria entre eles e adicione 2 a essa reta na árvore binária. (O(n^2 log n))
  3. Para cada reta na árvore binária, adicione 1 para cada ponto que pertence a essa reta. (O(n^3))
  4. É fácil ver que a reta é uma reta de simetria do conjunto de pontos se e somente se seu valor na árvore binária for n.

O problema geométrico está no segundo passo: determinar a reta de simetria entre dois pontos. Sejam esses pontos p e q. É preciso:

  1. Determinar o ponto médio entre p e q.
  2. Determinar a reta que passa por p e q (o enunciado garante que p != q).
  3. Determinar uma reta (ou um vetor) perpendicular à reta do passo acima.
  4. Determinar a reta que passa pelo ponto médio e tem a direção do vetor perpendicular do passo 3.

Determinar o ponto médio sem usar ponto flutuante seria trivial de qualquer forma (basta multiplicar todas as coordenadas por dois), mas com coordenadas homogêneas isso é desnecessário. É fácil ver que o ponto médio m entre p = [w_0, x_0, y_0] e q = [w_1, x_1, y_1] é:

m = [ 2 w_0 w_1 , w_1 x_0 + w_0 x_1 , w_1 y_0 + w_0 q_1 ]

1
2
3
ponto ponto_medio(ponto p, ponto q) {
	return (ponto) { 2*p.w*q.w, q.w*p.x+q.x*p.w, q.w*p.y+q.y*p.w };
}

Três pontos [w_0, x_0, y_0], [w_1, x_1, y_1], [w_2, x_2, y_2] são colineares se

 \left| \begin{array}{ccc} w_0 & x_0 & y_0 \\ w_1 & x_1 & y_1 \\ w_2 & x_2 & y_2 \end{array} \right| = 0 ,

o que nos permite concluir que a reta r = \langle W, X, Y \rangle que passa por p = [ w_0, x_0, y_0 ] e q = [ w_1, x_1, y_1 ] é:

r = \langle +x_0 y_1 - y_0 x_1, -w_0 y_1 + w_1 y_0, w_0 x_1 - w_1 x_0\rangle.

1
2
3
ponto reta_determinada_por(ponto p, ponto q) {
	return (reta) { +p.x*q.y-q.x*p.y, -p.w*q.y+q.w*p.y, +p.w*q.x-q.w*p.x };
}

(um ponto [w, x, y] pertence a r se Ww + Xx + Yy = 0)

1
2
3
int ponto_na_reta(ponto p, reta r) {
	return p.w*r.w + p.x*r.x + p.y*r.y == 0;
}

Agora a parte mais legal: a fórmula para determinar uma reta que passa por dois pontos funciona com pontos no infinito (pensemos em pontos no infinito como vetores, porque eles tem direção mas tem w = 0): o resultado é a reta determinada por um ponto e uma direção. O vetor perpendicular à reta \langle W, X, Y \rangle é [ 0, X, Y ].

1
2
3
ponto ponto_infinito_na_reta_perpendicular(reta r) {
	return (reta) { 0, r.x, r.y };
}

E isso é tudo. Agora basta criar uma representação única da reta pra guardar na árvore binária.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
reta reformata_reta(reta r) {
	if (r.w < 0) {
		r.w = -r.w;
		r.x = -r.x;
		r.y = -r.y;
	} else if (r.w == 0) {
		if (r.x < 0) {
			r.x = -r.x;
			r.y = -r.y;
		} else if (r.x == 0 && r.y < 0) {
			r.y = -r.y;
		}
	}
	int d = gcd(r.w, gcd(abs(r.x), abs(r.y)));
	return (reta) { r.w/d, r.x/d, r.y/d };
}

Usando essas funções, primeiro e segundo passos da solução são:

map <reta,int> M;
for (int i = 0; i < n; i++) {
	for (int j = i+1; j < n; j++) {
		reta s = reformata_reta(reta_determinada_por(P[i], P[j]));
		ponto pm = ponto_medio(P[i], P[j]);
		ponto dir = ponto_infinito_na_reta_perpendicular(s);
		reta r = reformata_reta(reta_determinada_por(pm, dir));
		if (M.find(s) == M.end())
			M[s] = 0;
		if (M.find(r) == M.end())
			M[r] = 0;
		M[r]+= 2;
	}
}

Terceiro e o quarto são:

1
2
3
4
5
6
7
8
int output = 0;
for (map <reta,int>::iterator i = M.begin(); i != M.end(); i++) {
	for (int j = 0; j < n; j++)
		if (ponto_na_reta(P[j], i->first))
			i->second++;
	if (i->second == n)
		output++;
}

O código completo ficou com umas 90 linhas com comentários e linhas em branco e foi aceito na primeira submissão (ok, na verdade na segunda, mas não foi devido à geometria muito menos à precisão): symmetry.cpp. Não é lindo?

Publicado às 00:49 em Algoritmos geométricos | Um comentário

17 de junho de 2007

Crivo de Eratóstenes

Encontrar números primos é um problema comum em olimpíadas e maratonas de programação. Até hoje não existe uma maneira fácil de determinar se um número é ou não primo, mas para resolver estes problemas é indispensável o conhecimento de alguns algoritmos clássicos e simples, como o Crivo de Eratóstenes.

O Crivo de Eratóstenes é um método bastante prático para encontrar os primos de 2 até um valor limite, que pode ser feito a mão e é fácil de implementar.

O algoritmo consiste em:

  1. Determinar (ou receber na entrada do programa) o valor limite, isto é, o maior número que desejamos saber se é primo.
  2. Fazer a raiz quadrada do valor limite. Pode-se arredondar para baixo caso a raiz não seja exata (e quase nunca é).
  3. Criar um vetor (lista) com os números de 2 até o valor limite.
  4. Para i=2 até raiz do valor limite, caso o número (i) não esteja riscado insira-o na lista dos primos (ou imprima-o, ou não faça nada, isso depende da utilidade que você quer dar para o crivo) e risque todos os seus múltiplos na lista.

Há várias maneiras de implementar este algoritmo. Eu pseudocodaria (meu pseudocódigo é bem próximo de uma linguagem normal, porque acho que assim é mais fácil de entender e depois implementar) ele assim:

/* Primeiro passo */
recebe valorLimite

/* Segundo passo */
raiz \leftarrow \sqrt{valorLimite}

/* Terceiro passo */
para i \leftarrow 2 até valorLimite
    vetor[i] \leftarrow i
fim-para

/* Quarto passo */
para i \leftarrow 2 até raiz
    se vetor[i] = i
        imprima "O número " i " é primo."
        para j \leftarrow i+i até valorLimite, de i e i
            vetor[j] \leftarrow 0
        fim-para
    fim-se
fim-para

Vêem como é simples?

Crivo de Eratóstenes implementado em C

#include <stdio.h>
#include <math.h> // necessário para raiz
 
#define NMAX 1000000 // valor máximo para o valor máximo
 
int main() {
    int i, j, vetor[NMAX];
    int valorMaximo, raiz;
 
    // Primeiro passo
    scanf("%d", &valorMaximo);
 
    // Segundo passo
    raiz=sqrt(valorMaximo);
 
    // Terceiro passo
    for (i=2; i<=valorMaximo; i++) {
        vetor[i]=i;
    }
 
    // Quarto passo
    for (i=2; i<=raiz; i++) {
        if (vetor[i]==i) {
            printf("%d é primo!n", i);
            for (j=i+i; j<=valorMaximo; j+=i) {
                vetor[j]=0; // removendo da lista
            }
        }
    }
 
    return 0;
}

No USACO Training Program Gateway (programa de treinamento para olimpíadas dos estado-unidenses) há um problema muito interessante (Prime Palindromes) cujo objetivo é determinar palíndromos primos de X a Y. Uma das melhores situações que já encontrei para usar o Crivo e sem dúvidas é um ótimo treinamento. Além de determinar primos, você terá que determinar palíndromos e é outro ótimo exercício lógico-matemático.

Divirtam-se e qualquer dúvida usem os comentários!

Publicado às 10:40 em Curiosidades | 43 comentários

15 de junho de 2007

Escada perfeita (OBI2006)

Depois de meses sem postar, resolvi que a partir de agora darei mais atenção pra este blog. Muita gente me manda e-mail e comentários com dúvidas e gostaria de deixar bem claro que eu não faço trabalhos de faculdade pra ninguém, mas que se você tiver uma dúvida real onde eu possa ajudar eu ajudarei de bom grado.

Pensei muito sobre o que postar aqui, tenho rascunhos sobre buscas em grafos e sobre resoluções de problemas de grafos, mas resolvi quebrar toda a ordem e, a partir de um scrap de orkut, acabei me lembrando do problema Escada perfeita, da OBI 2006, e me deu vontade de resolvê-lo aqui.

Por que o problema Escada Perfeita?

A programação deste problema é extremamente simples, mas a sua lógica (matemática pura) é muito inteligente. Tente resolver o problema antes de ver minha solução e, caso não consiga, depois veja como a solução é bonita.

Vamos ao enunciado…

Uma construtora, durante a criação de um parque temático, encontrou no terreno um conjunto de várias pilhas de cubos de pedra. Ao invés de pagar pela remoção dos cubos de pedras, um dos arquitetos da empresa achou interessante utilizar as pedras para decoração do parque, determinando que as pedras fossem rearranjadas no formato de “escada”. para isso, os funcionários deveriam mover alguns cubos para formar os degraus das escadas. Só que o arquiteto decidiu que, entre uma pilha e outra de pedras deveria haver exatamente uma pedra de diferença, formando o que ele chamou de escada perfeita. O exemplo abaixo mostra um conjunto de cinco pilhas de pedras encontradas e as cinco pilhas como ficaram após a arrumação em escada perfeita.

Tarefa

Dada uma seqüência de pilhas de cubos de pedras com suas respectivas alturas, você deve determinar o número mínimo de pedras que precisam ser movidas para formar uma escada perfeita com exatamente o mesmo número de pilhas de pedras encontrado inicialmente (ou seja, não devem ser criadas ou eliminadas pilhas de pedras). O degrau mais baixo da escada deve sempre estar do lado esquerdo.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha contém um inteiro n que indica o número de pilhas de pedras. A segunda linha contém N números inteiros que indicam a quantidade de cubos de pedras em cada uma das pilhas, da esquerda para a direita.

Saída

Seu programa deve imprimir, na saída padrão, uma única linha, contendo um inteiro: o número mínimo de cubos de pedras que devem ser movidos para transformar o conjunto de pilhas em uma escada perfeita, conforme calculado pelo seu programa. Caso não seja possível efetuar a transformação em escada perfeita, imprima como resultado o valor -1.

Exemplos

Exemplo 1

Entrada
5
5 4 5 4 2

Saída
5

Exemplo 2

Entrada
6
9 8 7 6 5 4

Saída
9

Exemplo 3

Entrada
2
1 5

Saída
-1

OK. Estão prontos?

Depois de pensar um pouco, conclui-se que:

  1. A escada perfeita é uma PA de razão 1 (aumenta de um em um). Você lembra disso do seu primeiro ano do Ensino Médio? Senão, é bom dar uma relembrada. As fórmulas (simples e facilmente deduzíveis) da PA são:

    Termo geral da PA

    a_{n} = a_{1} + (n-1).r

    Soma de PA

    \displaystyle S_{n} = (a_{1}+a_{n}).\frac{n}{2}

  2. Sabemos quanto vale n (o número de pilhas, número de elementos da PA) e conseguimos calcular a soma de todos os elementos (podemos fazer isso até durante o loop da entrada, certo?)
  3. Sabemos quanto vale a razão (r=1).
  4. Substituindo o que sabemos nas fórmulas conseguimos formar um sistema de equações básico e desta forma torna-se fácil descobrir o valor do primeiro e do último termo da PA (a_{1} e a_{n}). Resumindo um pouco os cálculos, depois de alguma manipulação algébrica você chega a: \displaystyle a_{n} = \frac{\frac{2.S_{n}}{n}+n-1}{2}

    \displaystyle a_{1} = 1 + a_{n} - n

  5. Agora que já sabemos onde começa e onde termina a escada basta fazer um loop em cada fila de blocos e adicionar à uma variável movimentos a quantidade de quadradinhos que estão sobrando nesta fileira (por exemplo, na primeira fileira da figura do enunciado está sobrando três quadradinhos para chegar ao a_{1}=2). Ao mesmo tempo, adicionamos à outra variável (moves) a quantidade de quadradinhos que devem ser retirados ou colocados na fileira (porque depois se esta variável não for igual a 0 imprimimos -1). Ficou claro?

Implementação

Variáveis

  • n: número de degraus (fileiras de blocos)
  • a: a_{1}, número de blocos do primeiro degrau.
  • b: a_{n}, número de blocos do último degrau.
  • soma: S_{n}, soma da PA.
  • pilha[]: vetor de degraus.
  • movimentos e moves: explicados no quinto passo da solução.
  • i e j: variáveis auxiliares para fazer os loops.

Codeado em C

#include <stdio.h>
#define PMAX 10001
 
int main() {
    int i, j;
    int n;
    int soma=0;
    int a, b;
    int pilha[PMAX];
    int moves=0;
    int movimentos=0;
 
    scanf("%d", &n);
    for (i=0; i<n; i++) {
        scanf("%d", &pilha[i]);
        soma+=pilha[i];
    }
 
    b=(((2*soma)/n)+(n-1))/2;
    a=1+b-n;
 
    for (i=0; i<n; i++) {
        moves+=(pilha[i]-(i+a));
        if (pilha[i]>i+a) {
            movimentos+=(pilha[i]-(i+a));
        }
    }
 
    if (moves!=0) {
        printf("-1n");
    } else {
        printf("%dn", movimentos);
    }
 
    return 0;
}

Prontinho! Qualquer dúvida escrevam seus comentários.

Publicado às 09:38 em Algoritmos gulosos | 6 comentários

26 de janeiro de 2006

Grafos Ponderados

Um grafo é ponderado quando suas arestas possuem um peso. O que significa isso? Bom… Vamos supor que eu queira ir de um lugar pra outro, mas o mais importante pra mim não seja a distância entre eles mas o pedágio que vou ter que pagar para pegar cada aresta (estrada). Nesse caso, o peso de cada aresta seria o custo que eu tenho pra passar pela estrada. O problema então seria calcular o caminho onde eu pago menos (o caminho que tem a menor soma de preços) e não o menor caminho no grafo “não-ponderado” (onde consideramos aresta=1 e nada=0).

Neste grafo, por exemplo, o menor caminho de 0 a 3 não é a aresta 0–3, mas sim a aresta 0–2 e depois a aresta 2–3.

Para representar um grafo ponderado usando a matriz de adjacência, onde antes marcávamos “1”, marcamos o peso que temos de ir de um vértice para o outro e onde marcávamos “0” marcamos \infty{} (infinito)*.

  0 1 2 3 4 5
0 \infty \infty 3 5 \infty \infty
1 \infty \infty 2 \infty \infty \infty
2 3 2 \infty 1 \infty \infty
3 5 \infty 1 \infty \infty \infty
4 \infty \infty \infty \infty \infty 7
5 \infty \infty \infty \infty 7 \infty

* Na verdade, só fazemos isso porque neste caso iríamos querer o menor caminho e o 0 poderia atrapalhar, porque poderíamos ter um caminho sem pedágio, por exemplo, mas isso sempre depende do caso.

Usando listas de adjacência, podemos representar as ligações de cada vértice com dois vetores (um para dizer a qual ele se liga e outro o peso desta ligação) ou com um vetor de structs como:

struct edge {
    int destino, peso;
};

Publicado às 09:31 em Grafos | 7 comentários

Próxima Página »