Laboratório de Programação II (Lab2)

Bibliografia

Consulte a regulamentação da disciplina, que contém uma variada seleção de livros.

Sobre a linguagem C, veja aqui uma lista de referências, mas a minha principal sugestão é sempre o livro de Kernighan e Ritchie, apesar da desatualização (há documentos na internet que falam das adições de C99, como este e este).

Sobre a linguagem C++, a minha sugestão é sempre o livro do Bjarne, embora eu o tenha consultado mais como referência do que lido linearmente (e isso com relação à 3ª edição).

Sobre conceitos de linguagens de programação em geral, eu particularmente aprendi bastante com o livro do Watt (editora), embora eu lembre de nem sempre concordar quando ele fala mal de C. :-)

Sobre a produção de código relativamente curto mas possivelmente elaborado, acho que o livro do Bentley é uma boa referência. A propósito, ele tem um apêndice sobre otimização de código (outro resumo); sobre esse assunto, veja também a página da Wikipédia.

Sobre a produção de código em larga escala… bom, isso não faz parte da minha experiência pessoal, mas este livro é famoso no assunto (alguns argumentam, porém, que ele é mais longo do que o necessário).

Trabalhos

Abaixo está a lista em construção dos trabalhos da disciplina. Alguns deles terminam com uma análise experimental.

1. Quicksort (entrega: 2015-03-31)

   Tópicos abordados:

   • Recursividade “de Cauda”
   • Quicksort em espaço O(lg n)
   • Quicksort em tempo O(n*lg n)

2. Compactação de Arquivos (entrega: preferivelmente em 02/junho)

   Tópicos abordados:

   • Operações de bit
   • Manipulação de arquivos
   • “Heaps” binários
   • Codificação de Huffman

3. Heap genérico em C (entrega: até 30/junho)

   • Resumo do trabalho: deverão ser feitas duas implementações de heap binário "genérico". Com elas, um programa pode criar e manipular heaps de diferentes tipos (um heap de inteiros, outro de strings, etc), sem haver repetição de código.

     A primeira implementação será feita em C, à moda da função qsort. A ideia é que cada função receba não um ponteiro para heaps do tipo "X", mas sim um ponteiro void*, que apontará para o heap desejado. Para que a função saiba como manipular o heap, ela recebe também o número de bytes de cada elemento do heap, e também um ponteiro para uma função que, dados ponteiros para dois elementos, compara os elementos em questão. Na prática, essa abordagem pode levar a uma implementação um pouco mais lenta do que uma feita especialmente para um tipo primitivo fixo (devido às indireções com ponteiros), mas em compensação evita a repetição de código.

     A segunda implementação será feita em C++, à moda da função sort. A ideia é utilizar templates para permitir uma gerência de tipos em tempo de compilação, aumentando a segurança e a eficiência do código resultante.

     Ao final, as duas implementações de heap devem ser comparadas. Para isso, o seu programa deverá avaliar os tempos de execução de duas implementações genéricas do heapsort, uma usando a implementação de heap em C e a outra usando a implementação de heap em C++. A comparação entre os heapsorts deverá ser feita para vetores de pelo menos dois tipos diferentes (int's, strings, etc) e o seu programa deve fornecer entradas grandes o suficiente para fazer os algoritmos executarem em tempo apreciável, digamos, uns 20 segundos por heapsort. Sugestão: ordene inteiros e strings; as strings podem ser linhas de arquivos-texto, comparadas lexicograficamente; os inteiros podem ser obtidos aleatoriamente ou a partir de linhas de arquivos-texto, de alguma maneira: o tamanho da linha, o número de ocorrências de determinados caracteres, etc.

     Consulte as hiperligações acima para instrução técnica básica e recorra a mim em caso de dúvida. Boa programação!

Aulas

• Aula 1 (2015-02-24, terça-feira): introdução à disciplina; recursão de cauda; quicksort usando O(log n) de memória.

  Objetivos:

  • Familiarizar-se com o ambiente de programação do laboratório.
  • Compreender o conceito de recursão de cauda e aprender uma otimização possível.
  • Utilizar a técnica para implementar uma versão do quicksort que utiliza O(log n) de memória.

  Tarefa:

  • Implemente a versão natural do quicksort, com duas chamadas recursivas.
  • Implemente uma versão do quicksort na qual a chamada recursiva de cauda é substituída por um laço – mas sempre a mesma chamada, isto é, sempre a da direita, ou sempre a da esquerda.
  • Implemente uma versão do quicksort na qual a chamada recursiva de cauda é substituída por um laço, e na qual a chamada recursiva não eliminada é sempre feita sobre a menor metade do vetor, seja esta a da direita ou a da esquerda.
  • Faça um programa em C que:
    • Cria um vetor de inteiros aleatórios.
    • Ordena o vetor com cada uma das versões do quicksort. ATENÇÃO: os vetores a serem ordenados pelas diferentes versões do quicksort devem ser iguais, isto é, possuir os mesmos elementos, na mesma ordem.
    • Verifica se os vetores foram ordenados corretamente.
    • Imprime o número máximo de chamadas recursivas realizadas por cada versão, isto é, a altura máxima da pilha de recursão de cada versão do Quicksort.
  • Entrega: a implementação desta aula faz parte do trabalho 1, a ser entregue posteriormente.

• Aula 2 (2015-03-03, terça-feira): seleção em tempo linear (mesmo com elementos repetidos); quicksort O(n*lg n) no pior caso; funções que retornam múltiplos valores em C; modularização de código-fonte C.

  Objetivos:

  • Compreender o algoritmo de seleção de Blum et al., que executa em tempo linear, e uma variação dele que aceita elementos repetidos.
  • Utilizar o algoritmo acima para obter uma versão do Quicksort que executa em tempo O(n*lg n) mesmo no pior caso.
  • Compreender como implementar funções que retornam múltiplos valores em C.
  • Compreender como modularizar o código-fonte em C.

  Tarefa:

  • Compreenda e implemente o algoritmo de seleção linear de Blum et al.. Veja a Wikipédia ou esta página de David Eppstein.

    Essa primeira versão pode supor que todos os elementos do vetor são distintos.

  • Use o algoritmo de particionamento acima para gerar uma versão do Quicksort cujo pivô escolhido é sempre a mediana do vetor.

    Atente para o fato de que o algoritmo de seleção já particiona o vetor com relação ao pivô!

    Essa versão não precisa executar sempre em O(n*lg n) caso o vetor possua elementos repetidos.

  • Implemente uma função de particionamento que divida o vetor em 3 partes: os elementos MENORES / IGUAIS / MAIORES que o pivô, respectivamente.

    Observação: a sua função deve, ao final, informar o início e o fim do trecho do vetor que possui os elementos iguais ao pivô. Como, em C, uma função só pode retornar um valor, uma maneira de fazer isso é receber dois argumentos adicionais, a saber, ponteiros apontando para variáveis que armazenarão os dados de início e fim. Outra possibilidade é declarar e retornar uma estrutura que armazene os dois dados em questão.

  • Usando a função de tripartição acima, implemente uma variação do algoritmo de seleção linear que permite elementos repetidos no vetor (sem comprometer a complexidade assintótica linear).

  • Usando o algoritmo de seleção do item anterior, implemente uma versão do Quicksort que sempre executa em tempo O(n*lg n).

  • Faça um programa em C que:

    • Cria um vetor de inteiros aleatórios.

    • Ordena o (mesmo) vetor com cada uma das versões do quicksort desta aula e da aula anterior.

      OBSERVAÇÃO: certifique-se de que cada versão do quicksort recebe o mesmo vetor para ordenar (ou seja, não forneça o vetor ordenado por uma versão como entrada para a versão seguinte).

    • Verifica se os vetores foram ordenados corretamente.

    • Calcula o tempo utilizado por cada versão.

    • Imprime o número máximo de chamadas recursivas realizadas por cada versão, isto é, a altura máxima da pilha de recursão de cada versão do Quicksort, assim como o tempo utilizado por ela.

    • Modularize o seu código-fonte!

      Por exemplo, você pode colocar a função main em um arquivo main.c, ao passo que as diversas versões do Quicksort podem ficar num arquivo quicksort.c.

      Para manter a coesão do seu código fisicamente modularizado (isto é, fragmentado em arquivos .c), use arquivos de cabeçalho (.h) !

  • Entrega: a implementação desta aula faz parte do trabalho 1, a ser entregue posteriormente.

• Aula 3 (2015-03-10, terça-feira): caso base do Quicksort via ordenação O(n²).

  Objetivos:

  • Experimentar uma variação do Quicksort em que o caso base da recursão é tratado por um algoritmo de ordenação O(n²).

  Tarefa:

  • Observe que o Quicksort pode ser modificado de forma que, para instâncias de tamanho ≤ k (um natural positivo qualquer), a ordenação é feita por meio de um algoritmo de ordenação O(n²), como a ordenação por inserção.

    Assim sendo, das versões do Quicksort implementadas nas tarefas anteriores, selecione alguma (por exemplo, a sua favorita) e implemente uma variação dela na qual é recebido um argumento adicional "k", para tamanhos de vetor abaixo do qual a ordenação é feita por um algoritmo O(n²).

  • Como o Quicksort executa em O(n*lg n) em média, então o esperado é que, para valores grandes de "k", essa nova versão do Quicksort execute mais lentamente que a original. Por outro lado, um bom algoritmo de ordenação O(n²) pode executar mais rapidamente que o Quicksort para instâncias pequenas, de forma que a nova versão do Quicksort pode executar mais rapidamente que a original para pequenos valores de "k".

    Faça então uma análise experimental para avaliar o melhor valor de "k". Essa análise deve levar em conta diferentes tamanhos de vetor!

  • Acrescente ao programa da tarefa anterior (que ordena um vetor aleatório com diversas versões do Quicksort, e compara os resultados) a nova versão do Quicksort.

  • Entrega: a implementação desta aula faz parte do trabalho 1, a ser entregue posteriormente.

• Aula 4 (2015-03-17, terça-feira): sem conteúdo novo, apenas continuidade das tarefas anteriores.

• Aula 5 (2015-03-24, terça-feira): percurso de vetores via ponteiros.

  Objetivos:

  • Compreender ponteiros, suas operações e aritmética em C, e como utilizá-los para percorrer vetores.
  • Implementar uma versão do Quicksort que percorra vetores utilizando ponteiros, e avaliar o impacto dessa modificação na performance do código.

  Tarefa:

  • Entenda os operadores * e & relativos a ponteiros (veja na Wikipédia).

  • Entenda (veja na Wikipédia):

    • O que significa p+i se p é um ponteiro e i um inteiro.

    • Que v[i] significa *(v+i).

  • Entenda subtração de ponteiros (veja isso e mais em cs.umd.edu) e o tipo ptrdiff_t (veja em cppreference.com).

  • (Opcional) Se você quiser saber como C99 facilitou o percurso de matrizes passadas como argumento de função, dê uma olhada nesta excelente série sobre VLA's: 2001-10-01, 2001-12-01, 2002-01-01, 2002-03-01 (este último texto também ensina como declarar struct's cujos últimos membros são vetores cujo tamanho só é decidido em tempo de execução ("flexible array members").

  • Escreva uma versão do Quicksort usando acesso/incremento de ponteiros ao invés de indexação de vetores, tanto na função do Quicksort propriamente dita quanto no particionamento e etc. Você escolhe a versão do Quicksort que será tomada como base.

    Exemplo, para esclarecer melhor o ponto: ao invés deste estilo

    int primeiro_zero_indice (int v[], int n)
      {
      int i = 0;
      for ( ; i < n ; ++i ) { if (v[i] == 0) return i; }
      return -1;
      }
    

    use este

    int* primeiro_zero_ponteiro (int *primeiro, int *ultimo)
      {
      int *p = primeiro;
      for ( ; p <= ultimo ; ++p ) { if (*p == 0) return p; }
      return NULL;
      }
    

    ou algo ainda mais otimizado.

  • Inclua essa nova versão do Quicksort no programa das tarefas anteriores e compare a performance dela com a da versão que você tomou por base.

  • Entrega: a implementação desta aula faz parte do trabalho 1, a ser entregue na próxima semana.

• 2015-03-31, terça-feira: entrega do trabalho 1 (leia abaixo; dúvidas: me mande um e-mail).

  Entrega do trabalho: o trabalho deverá ser apresentado no gabinete do professor (bloco 910, piso superior). As apresentações serão individuais, com duração de no máximo 20 minutos (mas preferencialmente menos), em algum horário nos intervalos 08-12h e 14-17h. Se desejar, você pode reservar um horário específico por e-mail.

  Conteúdo a ser apresentado:

  • Você deve apresentar um programa que cria um vetor de números aleatórios e então o ordena com as várias versões do Quicksort solicitadas nas aulas 1 a 5. O tamanho do vetor e o intervalo dos números aleatórios devem ser solicitados ao usuário no início da execução do programa.

  • A aula 2 descreve o que deve ser impresso na tela a respeito da execução de cada versão do Quicksort.

  • Além da execução do programa, o código-fonte deverá ser explicado.

  Dicas:

  • Leia com atenção as tarefas das aulas 1 a 5!

  • Veja as dicas de programação presentes nesta página.

  • Cuide do seu código: não deve haver cópia entre os alunos.

  Bom trabalho!

• Aula 6 (2015-04-07, terça-feira): início do trabalho 2 (data de entrega do trabalho: a ser informada posteriormente).

  • Resumo do trabalho: você deverá produzir um compactador e descompactador de arquivos, utilizando para isso a técnica da codificação de Huffman. A aplicação pode ser chamada, por exemplo, assim:

    nome_do_programa --compactar arquivo_origem arquivo_destino
    

    Naturalmente, a opção --descompactar deve também ser aceita.

  • Linha geral da técnica: o conteúdo de um arquivo é uma sequência de símbolos – digamos, os caracteres de um texto. Para se fazer o armazenamento, usa-se uma codificação: cada símbolo é armazenado por meio de uma sequência de bits (o "código" do caractere). Frequentemente (por exemplo, na tabela ASCII), a codificação é tal que os códigos correspondentes aos diversos símbolos têm todos o mesmo número de bits. Entretanto, é fácil perceber que, se num certo arquivo alguns símbolos ocorrem muito mais frequentemente do que outros, então é possível diminuir o tamanho do arquivo codificado utilizando-se códigos mais curtos para símbolos mais frequentes, e códigos mais longos para símbolos menos frequentes. A codificação de Huffman é então uma técnica que, dados os números de ocorrências dos símbolos de um arquivo, obtém códigos para esses símbolos de forma a minimizar o tamanho do arquivo codificado.

    Outras informações sobre o funcionamento da técnica podem ser obtidas no Cormen (§16.3) e na Wikipédia.

  • Tarefas da aula de hoje: em princípio, você pode seguir o seu próprio roteiro nesta implementação. Em todo caso, aqui está uma sugestão de tarefas para a aula de hoje:

    1. Comece implementando o processo de compactação. Para tanto, leia o arquivo de entrada caractere por caractere (fgetc), contando quantas vezes cada um ocorre.

       Dica: lembre que, em C, os valores possíveis para um char vão de CHAR_MIN a CHAR_MAX (limits.h). Logo, é fácil registrar num vetor quantas vezes cada valor de char ocorre no arquivo de entrada. O vetor em questão, aliás, não é grande, pois, em C, um char ocupa exatamente 1 byte, que geralmente tem apenas 8 bits.

       ATENÇÃO: CHAR_MIN pode ser um número negativo!

    2. Crie um "monte binário de mínimo" ("binary min-heap") com (apenas) os caracteres que ocorrem na entrada; a chave de cada caractere deve ser o seu número de ocorrências no arquivo.

       As operações básicas de heap a serem implementadas são "construir_heap" (O(n)), "extrair_mínimo" e "inserir_no_heap" (ambas O(lg n)), mas você provavelmente desejará escrever primeiro as operações "descer_no_heap" e "subir_no_heap" ("sift-down/up").

       ATENÇÃO: os elementos do "heap" são inicialmente apenas os caracteres e seus números de ocorrências, mas, posteriormente (na construção da árvore de Huffman), esses elementos podem ser árvores de caracteres. Isso não afeta a essência do funcionamento das operações de "heap", e você certamente pode escrever uma versão inicial da sua implementação de "heap" e depois adaptá-la de acordo com a necessidade, mas você pode considerar útil usar typedef para definir o tipo dos elementos do "heap" (assim depois você não terá que fazer modificações no tipo das variáveis locais das funções de "heap"), assim como escrever funções para comparar e copiar elementos do tipo em questão (de forma que, se depois você mudar a definição do tipo dos elementos, apenas essas funções terão que ser modificadas).

    3. Construa a árvore de Huffman.

    4. O próximo passo é escrever o arquivo compactado. Uma sugestão é gravar a árvore de Huffman no início do arquivo e em seguida gravar, caractere a caractere, os códigos dos caracteres do arquivo de entrada.

  Boa programação!

• Aula 7 (2015-04-14, terça-feira): continuação da implementação do trabalho 2.

• 2015-04-21, terça-feira: sem aula: Feriado Nacional – Tiradentes.

• Aula 8 (2015-04-28, terça-feira): continuação da implementação do trabalho 2.

• Aula 9 (2015-05-05, terça-feira): continuação da implementação do trabalho 2.

• Aula 10 (2015-05-12, terça-feira): continuação da implementação do trabalho 2.

• Aula 11 (2015-05-19, terça-feira): continuação da implementação do trabalho 2.

• Aula 12 (2015-05-26, terça-feira): finalização da implementação do trabalho 2.

  • Apresentação do trabalho 2: preferivelmente em 02/junho (o trabalho 3 terá que ser entregue até 30/junho! leia abaixo; dúvidas: me mande um e-mail).

  • Requisitos: o seu programa deve comprimir e descomprimir arquivos de quaisquer tamanhos ou extensões (veja abaixo alguns exemplos). O resultado da descompressão deve ser idêntico ao arquivo original:

    $ diff -s Original_files/empty_file.txt Decompressed_files/empty_file.txt 
    Files Original_files/empty_file.txt and Decompressed_files/empty_file.txt are identical
    
    $ diff -s Original_files/ch05-patterns.pdf Decompressed_files/ch05-patterns.pdf 
    Files Original_files/ch05-patterns.pdf and Decompressed_files/ch05-patterns.pdf are identical
    

  • Seguem abaixo alguns resultados computacionais para referência. Naturalmente, os tamanhos exatos dos arquivos comprimidos devem diferir nas diversas implementações, mas a diferença deve ser pequena para arquivos grandes.

    • empty_file.txt

      $ time ./program.bin --compress Original_files/empty_file.txt Compressed_files/empty_file.txt.huf 
      Successful execution.
      
      real	0m0.001s
      user	0m0.000s
      sys	0m0.001s
      
      $ time ./program.bin --decompress Compressed_files/empty_file.txt.huf Decompressed_files/empty_file.txt
      Successful execution.
      
      real	0m0.001s
      user	0m0.000s
      sys	0m0.001s
      
      $ ls -lh Original_files/empty_file.txt Decompressed_files/empty_file.txt 
      -rw-rw-r-- 1 pablo pablo 0 Mai 26 10:26 Decompressed_files/empty_file.txt
      -rw-r--r-- 1 pablo pablo 0 Mai 19 15:46 Original_files/empty_file.txt
      

    • adventures_sherlock_holmes.txt

      $ time ./program.bin --compress Original_files/adventures_sherlock_holmes.txt Compressed_files/adventures_sherlock_holmes.txt.huf
      Successful execution.
      
      real	0m0.241s
      user	0m0.233s
      sys	0m0.008s
      
      $ time ./program.bin --decompress Compressed_files/adventures_sherlock_holmes.txt.huf Decompressed_files/adventures_sherlock_holmes.txt
      Successful execution.
      
      real	0m0.267s
      user	0m0.264s
      sys	0m0.004s
      
      $ ls -lh Original_files/adventures_sherlock_holmes.txt Compressed_files/adventures_sherlock_holmes.txt.huf 
      -rw-rw-r-- 1 pablo pablo 3,6M Mai 26 10:30 Compressed_files/adventures_sherlock_holmes.txt.huf
      -rw-r--r-- 1 pablo pablo 6,2M Mai 19 15:46 Original_files/adventures_sherlock_holmes.txt
      

    • Stavechurch-heddal.bmp

      $ time ./program.bin --compress Original_files/Stavechurch-heddal.bmp Compressed_files/Stavechurch-heddal.bmp.huf 
      Successful execution.
      
      real	0m1.033s
      user	0m1.017s
      sys	0m0.016s
      
      $ time ./program.bin --decompress Compressed_files/Stavechurch-heddal.bmp.huf Decompressed_files/Stavechurch-heddal.bmp
      Successful execution.
      
      real	0m1.855s
      user	0m1.843s
      sys	0m0.012s
      
      $ ls -l Original_files/Stavechurch-heddal.bmp Compressed_files/Stavechurch-heddal.bmp.huf 
      -rw-rw-r-- 1 pablo pablo 26991546 Mai 26 10:34 Compressed_files/Stavechurch-heddal.bmp.huf
      -rw-rw-r-- 1 pablo pablo 27423162 Mai 26 09:55 Original_files/Stavechurch-heddal.bmp
      

    • ch05-patterns.pdf

      $ time ./program.bin --compress Original_files/ch05-patterns.pdf Compressed_files/ch05-patterns.pdf.huf
      Successful execution.
      
      real	0m0.008s
      user	0m0.008s
      sys	0m0.000s
      
      $ time ./program.bin --decompress Compressed_files/ch05-patterns.pdf.huf Decompressed_files/ch05-patterns.pdf
      Successful execution.
      
      real	0m0.013s
      user	0m0.013s
      sys	0m0.000s
      
      $ ls -l Original_files/ch05-patterns.pdf Compressed_files/ch05-patterns.pdf.huf 
      -rw-rw-r-- 1 pablo pablo 172734 Mai 26 10:40 Compressed_files/ch05-patterns.pdf.huf
      -rw-r--r-- 1 pablo pablo 173500 Mai 19 15:46 Original_files/ch05-patterns.pdf
      

    • Huffman_coding_Wikipedia.html

      $ time ./program.bin --compress Original_files/Huffman_coding_Wikipedia.html Compressed_files/Huffman_coding_Wikipedia.html.huf
      Successful execution.
      
      real	0m0.006s
      user	0m0.006s
      sys	0m0.000s
      
      $ time ./program.bin --decompress Compressed_files/Huffman_coding_Wikipedia.html.huf Decompressed_files/Huffman_coding_Wikipedia.html
      Successful execution.
      
      real	0m0.008s
      user	0m0.008s
      sys	0m0.000s
      
      $ ls -l Original_files/Huffman_coding_Wikipedia.html Compressed_files/Huffman_coding_Wikipedia.html.huf 
      -rw-rw-r-- 1 pablo pablo  99144 Mai 26 10:44 Compressed_files/Huffman_coding_Wikipedia.html.huf
      -rw-rw-r-- 1 pablo pablo 140431 Mai 26 10:19 Original_files/Huffman_coding_Wikipedia.html
      

  Boa programação!

• Aula 13 (2015-06-02, terça-feira): apresentação do trabalho 2.

• Aula 14 (2015-06-09, terça-feira): continuação do trabalho 3.

• Aula 15 (2015-06-16, terça-feira): continuação do trabalho 3.