Programming Pearls: Parte 3

Março 21, 2011

Eu ia descrever as colunas 11 a 15 nesse post, mas devido à grande quantidade de informação e coisas interessantes para descrever o post ficaria gigantesco. Vou me restringir às colunas 11 a 13. Em um post futuro fecho com as colunas 14 e 15.

Coluna 11: Sorting

Aqui são revisados os algoritmos de insertion sort e quicksort. O que achei mais interessante nessa coluna foi um exercício em que se pede para ordenar um conjunto de strings de bits de diferentes tamanhos. A solução apresentada é bem elegante:

std::string *x[N];
void bsort(int lo, int up, int depth){
    if(lo <= up) return;
    for(int i=lo; i<=up; i++)
        if(x[i]->length() == depth)
            std::swap(x[i], x[lo++]);
    int m = lo;
    for(int i=lo; i<=up; i++)
        if(x[i]->at(depth) == '0')
            std::swap(x[i], x[m++]);
    bsort(lo, m-1, depth);
    bsort(m, up, depth + 1);
}

No código C++ acima, o conjunto de strings é armazenado em um array de ponteiros para std::string. O uso de ponteiros é necessário para que a troca de elementos seja feita em O(1) e não no tamanho das strings.

A hipótese em cada chamada da recursão é de que o intervalo [lo, up] possui os depth-1 primeiros bits iguais.
O primeiro for trata se separar as strings que têm tamanho exatamente depth, já que elas virão primeiro na ordenação lexicográfica.

O segundo for, separa as strings restantes pelo próximo bit em que elas diferem, ou seja, o depth-ésimo bit. Essa separação é semelhante àquela feita no pivoteamento do quicksort. Depois desse laço, as strings entre [lo, m-1] têm os depth primeiros bits iguais e aquelas entre [m, up] também. Logo, podemos chamar recursivamente a função pois mantivemos a invariante.

É possível verificar que estamos percorrendo cada string um número de vezes igual a seu comprimento. Em cada chamada estamos avançando um bit e depois que atingimos seu comprimento, deixamos a string de lado.

Coluna 12: A Sample Problem

Nessa coluna é abordado o problema de se gerar m números aleatórios entre 1 e n, sem repetição. São apresentados vários algoritmos muito elegantes! A primeiro deles foi proposto pelo Knuth. Segue uma implementação em C++

void gen_knuth(int m, int n){
    for(int i=0; i<n; i++)
        if(rand() % (n-i) < m){
            std::cout << i << "\n";
            m--;
        }
}

Onde a função rand() retorna um inteiro entre 0 e RAND_MAX (que depende de implementação, mas é pelo menos 32767). O que se deseja com rand() % (n-i) é gerar inteiros entre 0 e n-i-1, inclusive, com probabilidade uniforme. A distribuição não fica totalmente uniforme se RAND_MAX não for múltiplo de n-i, mas na prática é uma boa aproximação.

O algoritmo acima imprime m valores com probabilidade uniforme. A prova da uniformidade das probabilidades está no livro do Knuth, mas ainda não tive como consultá-la. Por outro lado, é fácil mostrar que o algoritmo sempre imprime m elementos. Ele não imprime mais do que m elementos pois quando m = 0, o if é sempre falso. Se n-i <= m, o if é sempre verdadeiro. Esse algoritmo é O(n) de tempo e O(1) de espaço. Se n for muito grande, o algoritmo fica muito lento.

Uma outra versão é usando conjuntos para marcar quais elementos já foram selecionados. Um código se encontra abaixo, usando a implementação set da STL. Para quem não sabe, essa estrutura é implementada usando árvore binária balanceada (acho que é a red-black tree), ou seja, inserir um elemento em um set, decidir se um elemento está no set ou remover um elemento de um set são operações que levam tempo O(log n).

void gen_set(int m, int n){
    std::set<int> s;
    while (s.size() < m)
        s.insert(rand() % n);
    std::set<int>::iterator it;
    for(it = s.begin(); it != s.end(); it++)
        std::cout << *it << "\n";
}

Nessa versão sorteamos um número até tirar um que não tenha sido escolhido ainda. Note que esse algoritmo é probabilístico. Assim, podemos descrever sua complexidade em termos do número esperado de vezes que teremos que sortear um número até encontrar m elementos distintos. Esse problema é conhecido como o problema do colecionador de figurinhas e diz que o número esperado de sorteios necessários é O(n log n). Como a inserção é feita em O(log n), o algoritmo tem complexidade O(n log^2 n).

Robert Floyd propôs uma solução que não faz inserções desnecessárias e é determístico.

void gen_floyd(int m, int n){
    set<int> s;
    for(int j = n - m; j < n; j++){
        int t = (rand() % (j+1));
        if(s.find(t) == s.end()) s.insert(t);
        else s.insert(j);
    }
    set<int>::iterator it;
    for(it=s.begin(); it!=s.end(); it++)
        cout << *it << "\n";
}

Esse algoritmo é O(m log n). Não encontrei a prova de que nesse algoritmo os elementos são escolhidos de maneira equiprovável.

Um dos exercícios dessa coluna pede para escolher um número aleatório com probabilidade uniforme de uma lista, sem que se conheça o tamanho da lista! Pode-se pensar que é a versão online do algoritmo de escolher um número aleatório de uma lista.

O algoritmo é bem simples:

int rand_online(){
    int v, pick, cnt = 1;
    while (std::cin >> v){
        if (rand() % cnt == 0)
            pick = v;
        cnt++;
    }
    return pick;
}

O algoritmo lê os elementos a serem sorteados sem no entanto armazená-los. A cada elemento lido v, o algoritmo troca o elemento anteriormente armazenado por v com probabilidade 1/i. Dá para mostrar que a chance de um elemento ser escolhido é uniforme.

Coluna 13: Searching

Fiquei com a sensação de que o nome dessa coluna não espelha muito bem seu conteúdo. Aqui basicamente são apresentadas diferentes estruturas de dados como: array e listas ligadas para manter os elementos do conjunto de maneira ordenada, uma árvore de busca binária (não balanceada, mas que funciona bem nesse caso porque os números inseridos são aleatórios), além de estruturas especializadas que aproveitam o fato dos elementos do conjunto serem inteiros como um array de bits onde o i-ésimo bit é 1 se o inteiro i está no conjunto e uma espécie de hash, que vale a pena detalhar um pouco.

Dado que queremos sortear m elementos de 1 a n, criamos um array de m ponteiros para listas ligadas. Cada lista ligada representa um bucket. O primeiro bucket armazenará os valores de 0 a n/m-1, o segundo de n/m a 2(n/m)-1 e assim por diante. Ao inserir um número t no conjunto, mapeamos esse valor para o bucket correto através de k = t/(n/m). Aí basta inserir na lista ligada apontada pelo bucket k. Embora a inserção na lista seja linear no seu tamanho, como vamos inserir apenas m elementos com valores distribuídos de maneira uniforme, as listas em cada bucket tem tamanho esperado 1! Então essa inserção é muito rápida na prática.

Anúncios

Disk Graphs

Outubro 1, 2010

Semana passada teve início a série de seminários em teoria de computação dos membros do Laboratório de Otimização e Combinatória. Essas palestras ocorrerão intercaladas com os seminários do DTC (Departamento de Teoria de Computação), ocorrendo, a priori, às Sextas-feitas, 10h. Acabei estreando essa série com uma palestra intitulada “Disk Graphs”. A ideia central era definir a classe de grafos chamada disk graphs e mostrar dois problemas clássicos de teoria dos grafos sobre essa classe: o problema da clique máxima e da coloração. Neste post, vou apresentar um pequeno resumo da apresentação (disponível aqui).

Dado um conjunto de discos no plano, definimos um grafo com vértices correspondendo aos centros dos discos. Dois vértices são conectados por uma aresta se seus discos correspondentes se interceptam com área não nula. Denominamos tal grafo Disk Graph (DG).

Exemplo de Disk Graph

Um Disk Graph onde todos os discos têm mesmo tamanho é chamado de Unit Disk Graph.

Exemplo de Unit Disk Graph

No caso particular em que os discos não podem se sobrepor, apenas se tangenciar, chamamos o DG de Coin Graph (CG).

Exemplo de um Coin Graph

Em seguida falei sobre a relação entre diferentes classes de grafos. A mais interessante é devido ao Teorema de Koebe (também conhecido como circle packing theorem) que diz basicamente que grafos planares e coin graphs são equivalentes. Eu desconfiava que todo grafo planar é também um disk graph. O prof. Stolfi, que estava presente, provou com um argumento bem simples: dado um coin graph, a menor distância entre bordos de discos que não se tangenciam é positiva, enquanto a de discos que se tangenciam é exatamente 0. Assim, existe um valor suficientemente pequeno do qual podemos aumentar o raio dos discos de forma que os círculos tangentes passem a ter interseção não nula e os não tangentes assim continuem.

Problemas

Um aspecto importante ao enunciar um problema para essa classe de grafos é especificar se a entrada é dada na forma de discos ou na forma de grafo. Observe que se for dada na primeira forma, conseguimos obter a segunda. Porém, mesmo para unit disk graphs, se a entrada estiver na forma de grafo, foi provado que é NP-difícil encontrar um conjunto de discos que formem tal grafo [1]. (Para coin graphs existe um algoritmo que constrói o conjunto de discos a partir de um grafo planar [2]). Para os problemas apresentados, vamos assumir que a entrada é dada na forma de discos.

Primeiramente apresentei o problema da clique máxima para unit disk graphs. Embora seja NP-difícil encontrar a clique máxima em um grafo geral, para unit disk graphs, existe um algoritmo polinomial . Não se sabe, porém, se o problema da clique máxima para disk graphs está em P ou NP.

Depois apresentei o problema da coloração, que continua NP-difícil, mesmo para unit disk graphs e a entrada sendo dada na forma de discos. Foram desenvolvidos algoritmos aproximados e algoritmos online para unit disk graphs e disk graphs. Para unit disk graphs o melhor algoritmo aproximado até agora tem fator de aproximação 3 (limite superior), sendo que não existe algoritmo aproximado com melhor fator de aproximação menor do que 4/3 (limite inferior) a não ser que P=NP. O melhor algoritmo online tem fator de competitividade 5 (limite superior) e não existe algoritmo com fator de competitividade menor do que 2 (limite inferior) a menos que P=NP. Para disk graphs, o algoritmo aproximado tem limites inferior e superior iguais a 4/3 e 5, respectivamente, e o algoritmo online tem ambos limites inferior e superior iguais a log n, ou seja, o algoritmo online para unit disk graphs é o melhor que se pode conseguir.

Sumário com os limites dos fatores de aproximação e competitividade.

Aplicações

Na palestra acabei não falando das aplicações práticas dos disks graphs. Porém, eles são muito utilizados para projetar topologias de rede wireless. Podemos pensar que cada disco representa uma antena wireless posicionada no centro do disco, com alcance equivalente ao raio do mesmo. Assim, o problema da coloração pode ser usado para encontrar uma atribuição de frequências às antenas, considerando que há interferência entre os sinais de antenas cujos círculos se interceptam.

Referências

[1] Breu, H. and Kirkpatrick, D. G. – Unit Disk graph recognition is NP-Hard
[2] Collins, C. R. and K, Stephenson – A Circle packing algorithm