Organização de Dados II  —  2013/1

Página principal

Informações

Local: Sala do DCC / LAB 2.
Horário: 3as e 5as, das 13h às 15h.
Início: 02 de abril de 2013.

Repositório do código criado em sala de aula:
https://github.com/vigusmao/OrgDados2_2013_1

Ementa:
-   Interpolation search;
-   Self-organizing sequential search;
-   Hashing (técnicas gerais, aplicações, hashing universal, hashing perfeito);
-   Bloom filters;
-   Text searching;
-   Tries;
-   Tópicos especiais em ordenação.

Não haverá aula nos dias:
-   23/04 (feriado de São Jorge);
-   25/04 (estarei em congresso fora do país);
-   30/05 (feriado de Corpus Chirsti);
-   de 11/06 a 27/06 (WG'13 + DGA'13);
-   11/07;


Aulas extras (reposição), sempre das 8h às 10h:
-   05/07;
-   12/07;
-   19/07.


Prova única:
-   23/07 30/07.


Primeiro trabalho:
Implementação dos três métodos de busca auto-organizável vistos em sala.
As instâncias de teste devem ser escolhidas de forma a permitir uma boa observação das diferenças entre os métodos.
Prazo: segunda-feira, 29 de abril, às 23:59. Entrega por e-mail.

Segundo trabalho:
Criação de programa para resolver o problema apresentado na aula de 16/05.
Exigências: (i) crie seu próprio hash map (com arrays e/ou listas); (ii) permita que o usuário selecione uma dentre pelo menos três funções hash, além de uma implementação de hashing universal, que poderá ser utilizado a critério do usuário.
Entrada: uma linha para cada um dos seguintes parâmetros: min_el: o menor elemento do conjunto de inteiros A; max_el: o maior elemento de A (A possuirá todos os inteiros entre min_el e max_el, sendo -1000 ≤ min_el, max_el ≤ 1000); o tamanho k dos subconjuntos de A em que estamos interessados (2 ≤ k ≤ 5); elementos arbitrários de A (um por linha), com repetição. A cada elemento lido a partir do k-ésimo, fica constituída uma k-upla formada pelos k últimos elementos lidos, na ordem em que foram lidos.
Saída: o número de linhas com elementos de A que foram lidas até completar todas as permutações (k-uplas) de elementos de algum k-subconjunto de elementos distintos de A.
Obs.1: O número máximo de linhas de um arquivo de entrada é 1 milhão. Se o programa chegar a ler a última linha do arquivo, ainda sem sucesso, deve reportar falha.
Obs.2: Descarte k-uplas cujos elementos não sejam todos distintos.
Prazo: segunda-feira, 01 de julho, às 23:59. Entrega por e-mail.

Terceiro trabalho:
Implementação do algoritmo de pattern matching visto em sala, com filtros por linhas. Dado um arquivo-texto de entrada com t linhas de no máximo n caracteres cada, o programa deve pre-processar cada linha de forma a obter sua assinatura baseada nas k-uplas de caracteres consecutivos presentes na linha. Cada k-upla é mapeada por uma função escolhida por você a um inteiro de 0 a m-1. A assinatura consiste em uma palavra de m bits, onde os bits 1 são aqueles que correspondem à imagem de pelo menos uma k-upla da linha. Você deve tentar valores diferentes de k e m, e relatar que valores apresentaram melhores resultados para textos grandes aleatórios. Explique também como foi a escolha da função hash.
Prazo: segunda-feira, 8 de julho, às 23:59. Entrega por e-mail.

Confiram, por favor, a lista de trabalhos entregues.

Lista de Exercícios aqui.

Gabarito da Lista aqui.


Bibliografia sugerida

File Organization and Processing     Introduction to Algorithms    
(Alan L. Tharp)     (Cormen, Leiserson, Rivest & Stein)    
         


Conteúdo das aulas

02/04


Introdução: Tópicos Especiais em Como Derrotar o Código do Próximo. :-)

Busca Interpolada (Interpolation Search). Implementação em Python feita em sala de aula disponível aqui.  
 

04/04


Mais sobre Busca Interpolada. Análise de complexidade: caso médio x pior caso. Verificando experimentalmente a complexidade de algoritmos.

O caso do método de ordenação do Python: TimSort. Encontre aqui a descrição do algoritmo pelo próprio autor. O artigo que o inspirou parece ter sido o seguinte:

Optimistic Sorting and Information Theoretic Complexity
Peter McIlroy
SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms),
pp 467-474, Austin, Texas, 25-27 January 1993.


Provavelmente falaremos mais a respeito.  
 

09/04


Arrays. Complexidade das políticas de crescimento por progressão aritmética e geométrica.

Busca auto-organizável (Self-Organizing Search): contador de consultas, transposição passo a passo, reposicionamento à frente.  
 

11/04


Ainda arrays. Problemas envolvendo escalabilidade / limites de memória. Exemplo: encontrar inteiro que não pertença a um array grande dado.

Bit array.  
 

16/04


Problema de busca em matriz ordenada tanto nas linhas quanto nas colunas.

Strings como arrays estáticos de caracteres. Performance de múltiplas concatenações. StringBuffer. Código escrito em sala, como de costume, no github.  
 

18/04


Introdução a hashing. Por que se importar? Por que usar? Por que customizar funções? Exemplo: o complexo algoritmo do Shazam (reconhecedor de músicas).  
 

30/04


Hashing em Java.
O contrato equals()/hashCode().

HashMap.
Exemplo: igualdade da soma de funções: determinar todas as soluções não-triviais da equação f(a) + f(b) + f(c) = f(x) + f(y) + f(z), para a, b, c, x, y, z em {1,...,N}, N dado.
Código no github.  
 

02/05


Objeto --> hashCode() --> endereço físico (i.e. índice do bucket no array subjacente).

Tabelas hash ponteiradas, com links entre elementos. Complexidade da iteração completa sobre o conjunto de elementos. LinkedHashMap.
Exemplo: Cache LRU.  
 

07/05


Funçõs hash: outras aplicações além de indexar tabelas hash. Exemplos: armazenamento de senhas hasheadas, message authentication codes (MAC), verificação de integridade.

Alguns dos métodos mais comuns para se obter funções hash razoáveis: módulo, dobra, one-at-a-time.

Tabelas hash com encadeamento externo (chained hashing): tamanho de cada lista encadeada (bucket) é uma V.A. binomial, com valor esperado igual ao fator de carga.  
 

09/05


Número esperado de pares de chaves sinônimas para funções hash com bom espalhamento. Número esperado de comparações durante consulta a chave pertencente à tabela hash com encadeamento externo (obs.: buckets maiores contribuem com um peso maior para a média).  
 

14/05


Hashing universal. Método para obter família de funções para hashing universal: dada uma chave k, define-se ha,b = ((ak + b) mod p) mod m, para p primo maior do que max(k) e maior do que m, onde m é o tamanho do contradomínio desejado (espaço mapeável, i.e. número de posiçóes do array subjacente).  
 

16/05


Quando abrir mão do conforto do hashing "pré-moldado" e ganhar performance com funções hash customizadas, endereçamento direto, bit arrays etc. Uso de hashing para ganho de escalabilidade.

O problema da coleção de permutações de um subconjunto. Lêem-se k-uplas formadas de elementos de certo conjunto A. O programa deve acusar o primeiro momento em que todas as possíveis diferentes k-uplas, para algum subconjunto de A, já tiverem sido lidas.  
 

21/05


Hashing perfeito.  
 

23/05


Quando os parâmetros a e b do hashing universal primário são escolhidos aleatória e uniformemente, a probabilidade de se conseguir montar um hashing perfeito para um conjunto estático de n chaves exigindo menos que 4n posições de memória para todas as tabelas hash secundárias é maior ou igual a 1/2. Portanto, o número esperado de tentativas (escolhas aleatórias) para aqueles parâmetros é menor ou igual a 2. Para o hashing secundário, como cada bucket apontará uma tabela cujo número de posições é o quadrado do número de chaves naquele bucket, o número de tentativas para os parâmetros do hashing universal secundário associado àquele bucket é também menor ou igual a 2. Dessa forma, toda a construção do hashing perfeito ocupando menos do que 4n posições é conseguida em tempo esperado linear O(n).

Memoização com hashing. Ocasiões em que o padrão de vetores e matrizes simplesmente não funciona. Exemplos de problemas cuja solução por backtracking demandaria a alocação prévia de uma quantidade absurda de memória para se conseguir registrar respostas de subproblemas de forma matricial.

Fibonacci recursivo. Fibonacci não recursivo. Fibonacci recursivo com memoização.

O problema da distribuição das balas pelas crianças por ordem de altura e sem repetição, e sem que qualquer criança fique com zero balas. Abordagem recursiva. Sem memoização: desita! Com memoização: domingo no parque! (Códigos no github.)  
 

28/05


Text searching / pattern matching.  
 

04/06


Bloom filters.  
 

06/06


Implementação de Bloom filters. (Código no github.)  
 

02/07


Tries. Implementação sequencial e encadeada.  
 

04/07


Código para tries em Java. O problema do retângulo de palavras (palavras válidas em cada linha e em cada coluna).  
 

05/07


Fechamento do código para o problema do retângulo de palavras. (Código no github.)
Foi fácil perceber que:
1) Sem a otimização de podar a busca tão logo seja inserida uma palavra que gere prefixos invalidos, o programa rodaria "para sempre".
2) Fazendo a otimização, mas implementando a verificação dos prefixos através de uma varredura de toda a lista de palavras do tamanho desejado para testar se alguma delas possui aquele prefixo (método testaPrefixoPorSubstringNoArrayList), o programa passa a rodar em tempo razoável (15-20 segundos).
3) Implementando a verificação dos prefixos usando tries (método testaPrefixoPorTries), o programa roda instantaneamente.  
 

09/07


Problemas:

-   ordenação de pilha (usando qualquer coisa, usando um número constante de pilhas, usando apenas duas pilhas);
-   pilha de inteiros com push(), pop() e getMin() em tempo constante (usando qualquer coisa, usando apenas pilhas, usando apenas uma pilha de qualquer coisa, usando apenas uma pilha de inteiros);
-   dado um array, determinar o menor subarray cuja ordenação faz que o array inteiro fique ordenado.  
 

12/07


Problemas:

-   external sort;
-   merge de arrays ordenados A e B in-place no array A (que, por hipótese, tem espaço livre no final maior do que o tamanho de B);
-   localização do "índice mágico" em array ordenado (variantes com e sem valores repetidos, ordenação crescente e decrescente);
-   busca em array ordenado de strings com espaços em branco inseridos em posições arbitrárias do array;
-   agrupamento de anagramas (via ordenação e via hashing estilo bucket sort);
-   maior sequência ascendente obtida de array.
 
 

16/07


Algoritmos modernos de ordenação: introdução ao Dual Pivot Quick Sort do Java 7 (Arrays.sort) e comentários breves sobre o Tim Sort do Python.  
 

Voltar ao topo