Tarefa 8: Escola

Julho 9, 2010

O último laboratório da disciplina era sobre ordenação externa. Esse é um tópico que é dado na disciplina de estruturas de dados (embora não estivesse na ementa na vez que cursei). O problema é basicamente o seguinte: dado um arquivo muito grande em disco, queremos ordená-lo, sem ter que carregá-lo completamente na memória. A ideia para resolver é subdividir o arquivo em blocos de tamanho fixo e pequenos o suficiente para caberem em memória. Lemos cada bloco de uma vez na memória, ordenamos com um algoritmo de ordenação qualquer e escrevemos de volta no arquivo. Imagine agora que temos vários vetores ordenados e queremos fazer uma intercalação entre eles e gerar um único vetor ordenado. Observe que esta é uma generalização do passo do algoritmo Merge-sort.

No caso básico temos dois vetores ordenados e mantemos apontadores para o começo de cada um deles, Pa e Pb, por exemplo. Sejam a[1] e b[1] os valores dos elementos apontados por tais apontadores. Se a[1] for menor do que b[1], então A deverá vir primeiro no vetor final ordenado. Caso contrário será b[1] (no caso de empate tanto faz). Ou seja, colocamos o menor entre a[1] e b[1] no vetor final. Supondo que a[1] foi colocado, a pergunta que devemos fazer é: qual elemento poderia aparecer depois de a[1] num vetor ordenado? É claro que é b[1] ou a[1], pois estes são os menores elementos maiores do que a[1]. Então andamos com o apontador Pa em 1 posição e repetimos o procedimento.

Como generalizar essa ideia? Suponha agora que temos m vetores, dados em uma matriz a[m][n] e apontadores (P1, …, Pm) para o começo de cada um deles. O primeiro elemento no vetor de saída será o menor entre todos os elementos. Só que como os vetores estão ordenados, sabemos que o menor elemento está na primeira posição de algum dos vetores ou seja, queremos min(a[1][1], a[2][1], ….. a[m][1]). Seja i* o vetor com menor elemento. Colocamos então a[i*][1] na saída. Com argumentação semelhante ao caso base, sabemos que o próximo elemento a aparecer depois de a[i*][1] é min(a[1][1], a[2][1], …, a[i-1][1],a[i][2], a[i+1][1], …, a[m][1]). Que é equivalente a ardamos uma posição com o ponteiro de i*. Achar o menor entre dois elementos é fácil, mas e para n elementos? Bom, para isso podemos utilizar a estrutura de fila de prioridades. Dela conseguimos extrair o menor elemento em O(1) e inserir em O(log n). Assim, extraímos a[i*][Pi*] e inserimos a[i*][Pi*+1].

Qual a complexidade do algoritmo? Seja m o número de blocos e n o tamanho de cada bloco. Para cada bloco devemos realizar uma operação de ordenação sobre O(n) elementos, implicando em uma complexidade de O(m*n*log n). Após isso, temos a etapa de intercalação. Observe que a fila de prioridades nunca tem mais de um elemento por vetor, logo tem tamanho no máximo O(m). Isso é importante porque as complexidades das operações sobre a fila são sobre o número de elementos nela. Logo, a remoção é O(1) e a inserção O(log m). Como todo elemento de cada vetor entra e sai da fila, vamos fazer uma operação de inserção e remoção para cada um dos O(n*m) elementos, resultando na complexidade O(n*m*log m). No total temos O(n*m*(log n + log m)) = O(n*m*log(n*m)). Seja N=n*m o tamanho do arquivo. Então a complexidade desse algoritmo O(N*log N).

Um tira no jardim de infância (velho!)

Para quem leu o enunciado, verá que o problema não está descrito desta forma. Decidi colocar um contexo de treinamento contra incêncios de uma escola. Dá para fazer as seguintes correspondências: a escola representa o arquivo, os alunos representam os elementos do arquivo, as salas correspondem aos blocos em memória e o pátio junto com o diretor representam a fila de prioridades. Minha intenção com isso era tornar o problema mais interessante e quem sabe deixar a ideia por trás do algoritmo mais intuitiva. Não sei se foi devido às provas de fim de semestre ou à dificuldade do problema (ou porque muita gente já tinha passado na parte prática), mas essa foi a tarefa com menor número de submissões.

Anúncios

Tarefa 7: RPG

Julho 2, 2010

A tarefa 07 de MC202 consistia em simular uma batalha de RPG em turnos. São dados 2 equipes inimigas, cada qual com vários personagens com atributos diferentes, tais como força, velocidade, resistência e pontos de vida. Cada personagem tem um “período” inversamente proporcional a sua velocidade. Dados os períodos, podemos determinar os instantes de ataque de cada personagem. Quando dois personagens têm mesmo instante de ataque, existem alguns critérios de desempate que não cabe detalhar aqui.

Humano vs. Orc

Para determinar a ordem dos ataques, poderíamos fazer uma simulação discreta, por exemplo iterando sobre o tempo segundo a segundo e a cada instante verificar quem tinha um instante de tempo que caía bem naquele momento. A primeira desvantagem de tal método é que esse algoritmo é proporcional ao valor dos períodos, e a gente acaba iterando sobre instantes de tempo em que ninguém ataca. Além do mais, se os períodos forem números reais, esse tipo de abordagem pode ser impossível! Uma alternativa consiste em usar uma estrutura de dados chamada de fila de prioridades. A prioridade utilizada no caso é o próximo instante de ataque de cada personagem. Com uma fila de prioridades temos acesso ao elemento de maior prioridade em O(1). Assim, sabemos quem será o próximo atacante. Após efetuar o ataque, o próximo instante de ataque de uma personagem é a soma do instante atual e o período. Desta forma, basta reinseri-lo na fila com essa nova prioridade que em O(log n) conseguimos atualizar o heap mantendo suas propriedades.

Fila de Prioridades visualizada como árvore

Outro aspecto importante é a escolha do atacado. A estratégia de ambos os times consiste em atacar sempre o membro do time adversário com menos vida (mais alguns critérios de desempate). Uma observação importante é que todos do mesmo time “miram” no mesmo personagem inimigo até que este morra (porque se este já tinha menos pontos de vida, depois de sofrer os ataques continuará sendo o mais frágil). Isso nos possibilita ordenar inicialmente os membros dos times por ordem de não-decrescente de pontos de vida e, usando lista ligada, descobrir o membro a ser atacado em O(1), removendo-o da lista em caso de morte (também em O(1)). Aqui porém, eu permiti fazer do jeito força-bruta O(n) para escolher o mais fraco.

Esse método de simulação é mais eficiente do que a primeira proposta, sendo O(m log m), onde m é o número de turnos realizados antes de o jogo terminar. Porém, m pode ser proporcional aos valores de entrada, tornando nosso algoritmo pseudo-polinomial. Um exemplo seria dois times com um jogadores cada, um deles o personagem tem ataque 1 e no outro o personagem tem velocidade 0 e vida V. É fácil ver que o número de turnos é O(V), que pode ser tão grande quanto quisermos. Neste caso poderíamos ter feito algo mais eficiente, tal como calcular quantas vezes o personagem do time 1 ia atacar antes do personagem do time 2, mas acho que precisamos de uma ideia mais elaborada para funcionar em casos mais gerais. Porém, não cheguei a nenhuma conclusão se é possível resolver a simulação “analiticamente”.


Tarefa 6: AVL

Maio 29, 2010

Dando continuidade às tarefas de MC202, vou comentar sobre o laboratório 6, que consistia em implementar uma árvore AVL.

A árvore AVL é uma árvore binária balanceada de busca. Isso garante que a altura da árvore fica em torno de log n, onde n é o número de elementos na árvore. Tal propriedade é que possibilita busca, insersão e remocão em tempo log n. Porém, para mantear a árvore balanceada são necessárias operações chamadas de rotação (esquerda ou direita), o que torna a implementação de tal estrutura relativamente complexa.

Considerando que o laboratório pudesse ser complicado demais para se fazer em duas semanas, decidi fornecer um conjunto de cabeçalhos das funções, mais a estrutura da árvore para guiar os alunos na implementação. Isso ainda serve para evitar que os alunos enviassem código pronto copiado da internet, uma vez que dificilmente haverá um código que utiliza a mestra estrutura que eu defini.

Além do mais, optei por cobrar apenas a insersão na árvore, ficando os alunos incumbidos de implementar as rotações. A deleção me pareceu complicada demais a primeira vista e preferi não exigir.

O resultado foi melhor do que eu esperava. O número de submissões que vinha decrescendo a cada laboratório, voltou a atingir 40 (lembrando que para a tarefa Python, esse número fora 27). A minha impressão é de que uma boa parte da dificuldade dos alunos menos experientes é definir as estruturas e funções que servirão de base para a implementação. Ao fornecer a estrutura básica, deixei a eles apenas o trabalho de aplicar os algoritmos da teoria.

O único porém é que uma das minhas funções consistia em, dado um nó i, calcular a altura da subárvore a partir dele. Como havia um campo altura na estrutura do nó, minha ideia era, sempre que houvesse algum tipo de rotação envolvendo i, atualizar sua altura com o máximo da altura do filho esquerdo e do filho direito mais um. Só que essa função deveria ser O(1), uma vez que já temos calculado os valores das alturas do filho esquerdo e direito (hipótese). O problema é que a maior parte dos alunos calculou tal altura recursivamente, chamando a função novamente tanto para o filho esquerdo quanto para o direito, e isso torna a complexidade O(n), o que inutiliza a eficiência da inserção, que era O(log n).

Apesar de tudo, fiquei satisfeito com o resultado e sinto que desta forma os alunos focam mais em entender e aplicar a teoria do que desenvolvimento de sofware. Entretanto essa última habilidade é igualmente importante e deve ser trabalhada. No próximo laboratório, optei por um esquema parecido com o da AVL, mas pretendo deixar a implementação do último trabalho, o qual ainda não defini.


Tarefa 5: DNA

Maio 21, 2010

Nesse extenso intervalo sem postar, especifiquei três laboratórios: python (listas generalizadas), do qual falei no post anterior; dna (árvores binárias), que comentarei nesse post; e avl, a tarefa que está sendo feita atualmente.

A tarefa basicamente pede para avaliar uma expressão através de árvores binárias. Não é difícil encontrar implementações que envolvam avaliações de expressões do tipo:

E para não acontecer de o pessoal pegar código pronto, optei por modificar ligeiramente a especificação. Ao invés de avaliar expressões envolvendo números, o laboratório consistia em avaliar conjuntos. Ao invés de números a expressão consistia de variáveis representando um conjunto de características e no lugar dos operadores de adição, subtração, etc, inclui os operadores de união, interseção e diferença.

A partir daí, deixei os alunos implementarem do jeito que quisessem. Porém, alguns truques facilitam a tarefa:

1) As características eram dadas como strings. Porém, podemos guardar as strings em um dicionário (vetor de strings) e trabalhar só com o índice das strings nesse dicionário (int).

2) Quando os elementos do conjunto estão ordenados, é mais simples (e eficiente) implementar as operações sobre conjuntos. A ideia é parecida com a do merge sort: mantemos ponteiros para cada um dos conjuntos A e B. No começo cada qual aponta para o primeiro elemento do seu respectivo conjunto. Seja o valor do elemento apontado pelo ponteiro do conjunto A e o equivalente para o conjunto B. Na união, se , incluímos na união e andamos com o ponteiro de A. Se fazemos o mesmo com o ponteiro de B, se , incluímos qualquer um dos dois, mas apenas um, pois em conjuntos não consideramos elementos repetidos, e então andamos com ambos os ponteiros. Entendida a ideia, é simples derivar o algoritmo para a operação de interseção e diferença.

Para padronizar a resposta e comparar com minha saída no SuSy, exigi que as características do conjunto final estivessem ordenadas. Porém os alunos não tinham visto ordenação ainda, então passei um código que supostamente iria ordenar um vetor de strings:

qsort(saida, n, sizeof(char*MAXLEN), cmp);

Para quem não sabe, o qsort é uma função que implementa o quicksort e está disponível na biblioteca padrão do C. A função exige que você passe uma função de comparação por parâmetro, que compara duas strings. Porém, se o vetor de strings foi alocado estaticamente (minha sugestão inicial), a função não funciona. Uma alternativa é declarar o vetor como um vetor de ponteiros de char e alocar cada string dinamicamente (porém com tamanho fixo MAXLEN). Aí sim funciona. Outra alternativa, a que acabei sugerindo após descobrir o erro, é ordenar apenas os índices do vetor. Para isso nós orderamos um vetor auxiliar (vetor de permutação), indicando que a posição do i-ésimo elemento é . Inicialmente .

A função de comparação recebe dois inteiros i e j, mas na verdade compara as respectivas linhas da matriz (com strcmp). A vantagem desse método é que as strings continuam no mesmo lugar. O que muda são apenas os índices.


Tarefa 4: Python

Maio 21, 2010

O último post foi a mais de um mês atrás, pois estive muito ocupado. Tive prova e entrega de trabalho de PLI e ainda, com o fim da OBI, comecei a preparar aulas para o pessoal da maratona. Agora com o horário mais folgado, decidi escrever sobre o laboratório 04 de MC202.

O tema central da tarefa 4 de MC202 eram listas generalizadas. Sinceramente não me lembro de ter visto essa estrutura de dados em MC202 (talvez tenha esquecido, afinal cursei-a em 2005). Mas para quem conhece árvores essa estrutura é relativamente fácil de aprender.

Eu estava pensando em algum contexto em que fosse necessário o uso de tais listas, quando me deparei com a estrutura “List” da linguagem de programação python. Ela é justamente uma implementação de listas generalizadas. Propus então que o pessoal implementasse um interpretador para comandos envolvendo as listas generalizadas.

Para simplificar as coisas, restringi os tipos dentro da lista a inteiros. Além do mais os comandos possíveis eram apenas o de impressão e o de atribuição. Mesmo com essas restrições, o exercício ficou bem trabalhoso. Dei duas semanas de prazo e mesmo assim a taxa de submissão foi 27/47 (57,44%) e a média geral foi 3.01 :(


Tarefa 3: Minotauro

Abril 12, 2010

O professor da disciplina sugeriu que o laboratório 3 de MC202 fizesse uso de recursão. Apesar de ser uma técnica ensinada em MC102, é um conceito que demora a ser aprendido, ao meu ver porque exige maior abstração. Enfim, devido a essa dificuldade tal tópico costuma ser revisto em MC202.

A ideia que tive foi a de um problema de percorrer labirintos. A tarefa foi contextualizada com uma história da mitologia grega em que Teseu procura o Minotauro e para não se perder no caminho de volta utiliza uma corda cedida por Ariadne.

Para não ter que tratar múltiplas soluções, especifiquei uma regra de percurso: primeiro tenta-se ir em frente, se não houver sucesso, tente ir à direita e finalmente à esquerda. O primeiro passo consiste em encontrar a entrada, representada por um buraco na parede mais externa. É garantido que haverá exatamente um buraco. Depois disso, aplicamos a técnica de backtracking seguindo as regras acima até encontrar o Minotauro (representado pela letra ‘M’).

Para especializar um pouco mais o problema, exigi no enunciado que fosse impresso, além do caminho utilizado para chegar da entrada ao Minotauro, o caminho por onde ele passou. Essa informação adicional seria útil no caso em que o Minotauro não fosse encontrado, pois sem imprimir o caminho por onde Teseu passou, o mapa de saída seria igual ao de entrada. Porém, por distração acabei especificando que apenas fosse impressa uma string caso o Minotauro não fosse encontrado. Só percebi o erro que tinha cometido quando fui corrigir o laboratório de um aluno, cujo programa era mais ou menos o seguinte:

#include <stdio.h>
int main (){
    printf("O Minotauro eh lenda.");
}

Ele ia passar em 2 dos 12 testes do SuSy se não tivesse esquecido de pular linha.

Alguns alunos também tentaram detectar a existência do Minotauro pelo mapa de entrada: se o caracter ‘M’ fosse rodeado por paredes (‘X’) então ele não poderia ser encontrado. Essa é uma condição suficiente, mas não necessária (por quê?)

Finalmente, não sei se o enunciado é que ficou confuso demais ou se o conceito ainda não foi absorvido, mas o fato é que a maior parte dos alunos não entendeu que não era preciso voltar explicitamente para trás quando uma das direções não era a certa. Isso porque depois de retornar das chamadas recursivas obtemos esse efeito implicitamente.


Tarefa 2: Bandex

Abril 1, 2010

Terça-feira foi o último dia para a submissão da tarefa 2 da disciplina de estruturas de dados.

O problema consistia em simular uma fila mais complexa, onde as pessoas saem pelo começo mas nem sempre entram no final. As pessoas nesse contexto são os alunos da Unicamp, e cada aluno é de um dado ano (2006 até 2010) e pertence a exatamente um grupo de amigos. A regra para entrar na fila é a seguinte: um aluno de um ano $a$, sempre entra na frente de um aluno do ano $b > a$ e atrás de um aluno do ano $c \le a$. A única exceção é que quando algum amigo do seu grupo está na fila, quando o aluno entra na frente deste amigo.

Uma restrição dada no enunciado garante que dois alunos são do mesmo grupo somente se pertencem ao mesmo ano. Essa é uma simplificação importante, pois desta forma garantimos que pessoas do mesmo grupo estão sempre juntas na fila e a ordenação em relação aos anos é mantida.

Minha ideia para esse problema envolvia estruturas de dados diferentes: vetor, lista ligada, pilha e fila de prioridades. Na raíz de tudo temos uma fila de prioridade onde cada elemento (representando os anos) é uma lista ligada. Cada elemento desta lista é uma pilha (representando os grupos). Além disso, mantemos um vetor indexado pelo identificador do grupo apontando para o lugar onde este grupo está na fila. Como os alunos não tinham aprendido fila de prioridades ainda, dei a dica de implementá-la usando 5 filas, uma para cada ano.

Para inserir um aluno, primeiramente verificamos o ano ao qual ele pertence e vamos inserir na lista correspondente. Agora precisamos inseri-lo na frente do seu grupo. Primeiro verificamos se seu grupo está na fila. Se sim, inserimos ele no topo da pilha correspondente ao grupo. Caso contrário, criamos uma pilha para este grupo e colocamos no final da lista ligada.

Para remover um aluno, consideramos a fila com maior prioridade, no caso 2006. Se ela estiver vazia, verificamos a próxima fila. Caso contrário, removemos o topo da primeira pilha. Se a pilha esvaziar, removemos ela da lista ligada.

A complexidade esperada é O(1) para inserção e para remoção. Porém devido a restrições no SuSy, o sistema de avaliação dos programas, não consegui colocar instâncias muito grandes, de forma que algoritmos com inserção O(n), que consiste em procurar o grupo na lista percorrendo-a elemento a elemento, passavam nos testes.

Porém, deixei um teste grande para rodar localmente no meu computador e bonifiquei com 1 ponto as pessoas que passaram nesse teste.