Diário de Bordo

CCM0128, turma 22 - Primeiro Semestre de 2013

	Fevereiro
	Março

	Abril
	Maio

Junho

Esta página estará em permanente construção até o final do semestre...

Fevereiro

26 de fevereiro (aula 1):
- Apresentação da disciplina.
- Definição de novos nomes (sinônimos) para tipos já existentes (typedef).
- Registros ou estruturas (structs) em C:
  - Declaração de um tipo struct. Exemplos.
  - Variáveis tipo tipo struct.
  - Acesso aos campos de uma struct.
  - Atribuição (cópia) de uma struct a outra.
  - Passagem (por cópia) de structs como parâmetros para funções ou como valores devolvidos por funções.
  - Exemplo: função Data dia_seguinte(Data d), que recebe uma struct contendo uma data (o tipo Data é uma struct com três campos inteiros dia, mes e ano) e devolve outra struct com a data correspondente ao dia seguinte à data recebida.
  - Ponteiros para structs e a notação "->".
  - Funcões que recebem ponteiros para structs.
  - Exemplo: função void incr_data(Data *pd), que recebe um ponteiro para uma struct contendo uma data. A função altera os campos dessa struct, de modo que ela passe a conter o dia seguinte à que estava em *pd na ocasião da chamada à incr_data.
  - Alocação dinâmica de structs.
- Leitura recomendada: notas de aula do Prof. Paulo Feofiloff sobre structs.
28 de fevereiro (aula 2):
- Uma função auxiliar conveniente: mallocc ("malocar ou morrer").
- Listas encadeadas:
  - Estrutura de uma lista encadeada.
  - Listas encadeadas com cabeça e sem cabeça.
  - Função que imprime os elementos de uma lista encadeada. Versões iterativa e recursiva, para os casos de lista com cabeça e lista com cabeça.
  - Função que busca um elemento dado numa lista encadeada. Versões iterativa e recursiva, para os casos de lista com cabeça e lista com cabeça.
  - Função que insere um novo elemento num ponto qualquer (após uma célula especificada por seu endereço) de uma lista encadeada com cabeça.
  - Função que remove uma célula especificada de uma lista encadeada com cabeça. A função recebe o endereço da célula anteior à que se deseja remover.
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre listas encadeadas.

Março

5 de março (aula 3):
- Listas encadeadas (continuação):
  - Função de "busca e remoção" para listas encadeadas com cabeça.
  - Função de "busca e inserção" para listas encadeadas com cabeça.
  - Variações: listas encadeadas circulares, listas duplamente encadeadas, etc.
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre listas encadeadas.
- Fazer em casa: Exercícios das notas de aula sobre listas encadeadas. Vários desses exercícios pedem duas versões de uma mesma função: uma versão iterativa e uma versão recursiva. Não deixe de fazer as versões recursivas!
7 de março (aula 4):
- Filas:
  - Primeira implementação (não circular) de fila usando um vetor.
  - Aplicação: distâncias (num grafo dirigido) de um certo nó aos demais nós do grafo.
  - Implementação de fila usando um vetor circular.
  - Implementação de fila usando uma lista encadeada com cabeça.
  - Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre filas.
12 de março (aula 5):
- Modularização de programas C:
  - Divisão de um programa C em arquivos-fonte (módulos) compilados separadamente.
  - O esquema interface/implementação/cliente.
  - Exemplo: módulo contendo apenas a função mallocc. Arquivo mallocc.h (interface), arquivo mallocc.c (implementação) e programa que chama a função mallocc (cliente do módulo).
- Módulo fila:
  - A interface do módulo fila (arquivos item.h e fila.h).
  - Implementação de um módulo fila usando um vetor circular (arquivo fila_vetor_circular.c). Uso de static para declarar variáveis não-locais privativas de um certo módulo (no caso, o módulo fila_vetor_circular.c).
- Variáveis globais (também conhecidas como variáveis externas, pois são definidas externamente a qualquer função).
- Variáveis locais e variáveis globais: tempo de vida e visibilidade (ou escopo, ou alcance).
  - O tempo de vida é determinado pelo modo de alocação da variável, que pode ser "automático" (na pilha de execução) ou "estático".
  - Variáveis locais são normalmente alocadas na pilha de execução. Variáveis globais têm sempre alocação estática.
  - Uso de static para mudar o modo de alocação de uma variável local.
  - Uso de static para reduzir a visibilidade de uma variável global ou de uma função.
14 de março (aula 6):
- Módulo fila (continuação):
  - Implementação de um módulo fila usando uma lista encadeada com cabeça (arquivo fila_lista_encadeada.c).
- Conceitos: tipo de dados, tipo de dados abstrato (abstract data type ou ADT) e tipo de dados de primeira classe.
  - Observação: Cada uma das duas implementações do módulo fila vistas anteriormente (fila implementada usando um vetor circular e fila implementada usando uma lista encadeada com cabeça) define um tipo de dados que é abstrato, mas não é de primeira classe.
- Três exemplos de um tipo Fila de primeira classe:
  - Tipo de dados de primeira classe para uma fila implementada com um vetor circular. Agora o tipo Fila é de primeira classe, mas não é abstrato.
  - Tipo de dados de primeira classe para uma fila implementada com uma lista encadeada. Como o tipo Fila do exemplo anterior, este tipo é de primeira classe, mas não é abstrato.
  - Tipo Fila que é abstrato e de primeira classe. Este ADT de primeira classe tem duas implementações intercambiáveis: uma implementação usando um vetor circular e uma implementação usando uma lista encadeada com cabeça.
- Tarefa de casa: Considere esta modificação do exemplo de fila de primeira classe (porém não abstrata) implementada como lista encadeada. Para ver que modificações foram feitas, use o programa diff (do Linux) e examine as diferenças entre os arquivos fila_vetor_circular.h.original e fila_vetor_circular.h e entre os arquivos fila_vetor_circular.c.original e fila_vetor_circular.c. O exemplo modificado funciona ou não? Explique o que acontece.
19 de março (aula 7):
- Pilhas:
  - Implementação de pilha usando vetor.
  - Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre sobre pilhas.
- Módulo pilha:
  - A interface do módulo pilha (arquivos item.h e pilha.h).
  - Implementação do módulo pilha usando um vetor (arquivo pilha_vetor.c).
  - Implementação (mencionada em classe mas não vista em detalhe) do módulo pilha usando uma lista encadeada sem cabeça (arquivo pilha_lista_encadeada.c).
  - Exemplo de cliente do módulo pilha.
  - Um exemplo mais interessante de uso do módulo pilha: balanceamento de parênteses e colchetes. Nesse exemplo a pilha é de chars e a função bem_formada verifica se uma sequência de parênteses e colchetes é bem formada ou não.
- Outro exemplo de uso de pilha: função que recebe uma expressão na notação infixa e devolve a expressão traduzida para a notação posfixa (notação polonesa). O funcionamento dessa função foi descrito, mas o código da função não foi visto em classe. Ele está nas notas de aula sobre pilhas.
21 de março (aula 8):
- Noções de análise de algoritmos.
  - Notação assintótica:
    - Motivação.
    - Definição de "O grande".
    - Definição de "Θ grande".
    - Notação assintótica em equações
  - Relações de recorrência básicas.
  - Referências:
    - Sedgewick, da seção 2.2 à 2.5
    - CLRS, seção 3.1
    As definições de O(g(n)) e Θ(g(n)) vistas em classe são as que estão no CLRS. Também segui o CLRS na parte de notação assintótica em equações. Nos outros tópicos (motivação, relações de recorrência básicas), segui o Sedgewick.
- Tarefa de casa (preparação para a primeira prova):
  - Exercícios 7, 8, 9, 10, 11, 16, 17, 18 e 19 das notas de aula do Prof. Paulo Feofiloff sobre recursão e algoritmos recursivos.
  - Exercícios de 1 a 19 e exercícios 22, 23, 25, 26 e 27 das notas de aula sobre listas encadeadas. Quando um exercício tiver uma parte que pede uma função recursiva, não deixe de fazer essa parte!
  - Exercícios de 8 a 11 das notas de aula sobre filas.
  - Exercícios 1, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13 e 14 das notas de aula sobre pilhas.

Abril

2 de abril (aula 9):
- O problema da intercalação (merge): Dadas duas sequências ordenadas, gerar uma terceira sequência ordenada contendo todos os elementos das duas sequências dadas.
  - Solução no caso de sequências implementadas como vetores.
  - Solução no caso de sequências implementadas como listas encadeadas sem cabeça.
- Ordenação por intercalação (mergesort).
  - Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre o mergesort.
  - Leitura adicional: Seção 2.3 do CLRS ou capítulo 8 do Sedgewick.
  - Esta figura ilustra bem o mergesort.
- Conversa sobre uma solução O( n + m √ n ) do EP1.
4 de abril (aula 10):
- Exercícios:
  - (Revisão) Escreva uma função que imprima os elementos de uma lista encadeada sem cabeça. Faça duas versões: uma iterativa e uma recursiva.
  - Escreva uma função recursiva que imprima os elementos de uma lista encadeada sem cabeça em ordem reversa.
- Recursão de cauda (tail recursion). Quando a recursão é de cauda, um compilador pode gerar código otimizado para que as chamadas recursivas não usem espaço adicional na pilha de execução. Essa otimização, denominada tail call optimization, é feita por todos os bons compiladores.
- Mais exercícios:
  - Escreva uma função que encontre uma célula de conteúdo mínimo numa lista encadeada sem cabeça e não vazia. Faça duas versões: uma iterativa e uma recursiva. (Este é o exercício 3 das notas de aula sobre listas encadeadas.)
  - Na resolução do exercício anterior, a versão iterativa e a versão recursiva da função examinam os elementos da lista em ordens diferentes. A versão iterativa examina os elementos na ordem em que eles aparecem na lista. A versão recursiva examina os elementos na ordem inversa à da lista. Escreva uma segunda versão recursiva que examine os elementos da lista na mesma ordem que versão iterativa.
  - Escreva uma função que inverte a ordem das células de uma lista encadeada sem cabeça (a primeira célula passa a ser a última, a segunda passa a ser a penúltima etc.). Faça isso sem usar espaço auxiliar, apenas altere os ponteiros. Dê duas soluções: uma iterativa e uma recursiva. (Esse é o exercício 19 das notas de aula sobre listas encadeadas.)
9 de abril (aula 11):
- A estrutura de dados heap.
- O algoritmo heapsort. Desempenho do heapsort.
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre o heapsort.
- Tópico de C necessário para o EP2: argumentos na linha de comando.
11 de abril (aula 12):
- Primeira prova: : enunciado, solução.
16 de abril (aula 13):
- O problema da separação. Algoritmo da separação. Desempenho do algoritmo da separação.
- Quicksort. Desempenho do quicksort.
- Eliminação da "recursão de cauda" (tail recursion) no Quicksort.
- Controle da altura da pilha de execução no Quicksort.
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre o quicksort.
18 de abril (aula 14):
- Árvores binárias:
  - Definições.
  - Varreduras e-r-d (inorder traversal) , r-e-d (preorder traversal) e e-d-r (posteorder traversal).
  - Função que recebe uma árvore binária não vazia e devolve o primeiro nó da árvore na ordem e-r-d.
  - Função que devolve a altura de uma árvore binária.
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre árvores binárias.
23 de abril (aula 15):
- Árvores binárias (continuação):
  - Nós com campo pai.
  - Função que recebe o endereço de um nó e devolve o endereço do nó seguinte na ordem e-r-d.
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre árvores binárias.
- Árvores binárias de busca:
  - Definição.
  - Função de busca. A função recebe uma chave e devolve o endereço de um nó com essa chave, ou o endereço nulo se não existir tal nó.
  - Desempenho do algoritmo de busca.
  - Comentários sobre buscas por intervalos de valores da chave.
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre árvores binárias de busca.
25 de abril (aula 16):
- Árvores binárias de busca (continuação):
  - Inserção de nó.
  - Remoção de nó.
  - Desempenho dos algoritmos de inserção e remoção.
  - Comentários sobre árvores binárias de busca balanceadas (árvores AVL, red-black trees).
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre árvores binárias de busca.
- Introdução às tabelas de espalhamento (hash tables).
30 de abril (aula 17):
- Tabelas de espalhamento (hash tables).
  - Uma implementação de tabela de hash. A implementação vista em classe usa o esquema de resolução de colisões conhecido como separate chaining with linked lists.
  - Referência: Kernighan & Ritchie, seção 6.6.
- Conversa inicial sobre a linguagem Python.
  - Linguagens de scripting.
  - Python pode ser usada como uma scripting language ou como uma linguagem de programação de propósito geral.
  - Linguagens com tipos estáticos (static typing) e linguagens com tipos dinâmicos (dynamic typing).
    - Tipos estáticos: Fortran, Pascal, C, C++, Java, Haskell, Scala, ...
    - Tipos dinâmicos: Lisp, Scheme, Perl, Python, JavaScript, Erlang, Ruby, ...
  - Linguagens com tipos fortes (strong typing) e linguagens com tipos fracos (weak typing).
    - C é uma linguagem com tipos estáticos e fracos.
    - Python é uma linguagem com tipos dinâmicos e fortes.
- Tarefa de casa: Instale a linguagem Python 3 em seu computador.
  - A versão mais recente (que hoje é Python 3.3.1) pode ser baixada do sítio oficial de Python.
  - Também é possível instalar Python 3 por meio do gerenciador de pacotes da sua distribuição de Linux. (Toda distribuição inclui pacotes com Python 3.) Quem tiver a distribuição Ubuntu, instale os pacotes python3 e idle3.
- Tarefa de casa: Começe a estudar o tutorial de Python 3.

Maio

2 de maio (aula 18):
- Python:
  - É uma linguagem interpretada: os programas escritos em Python são executados pelo interpretador Python.
    - Na verdade o "interpretador Python" tem dois componentes: um compilador que traduz o programa fonte Python para bytecodes e uma máquina virtual que interpreta os bytecodes.
  - O modo interativo ("calculadora") do interpretador Python.
  - Uso de primeira linha começando com "hash-bang" (!#) para que um programa Python seja diretamente executável.
  - Números inteiros e reais (floats), strings, atribuição múltipla, comando while, argumentos na linha de comando (exemplos: scripts teste.py e fib.py), listas, conjuntos e dicionários.
7 de maio (aula 19):
- Python:
  - Variáveis, dados e "coleta de lixo":
    - Em vez de conter diretamente um dado, cada variável contém o endereço de uma "estrutura dado". Essa estrutura é um objeto com vários campos, que representa o dado associado à variável.
      - Um dos campos do objeto contém o tipo do dado.
      - Outro campo contém o valor do dado.
      - Um terceiro campo é um contador de referências que indica quantas variáveis apontam para esse objeto. O interpretador Python usa o contador de referências para liberar automaticamente a memória ocupada por objetos que deixaram de ser referenciados (e portanto não estão mais associados a nenhuma variável).
    - Uma variável não tem tipo, quem tem tipo é o objeto associado à variável. Mas podemos pensar que a variável tem um tipo que pode mudar ao longo do tempo: o tipo do objeto atualmente associado a ela (o último objeto atribuído à variável).
    - A chamada type(x) devolve o tipo atual de x, ou seja o tipo do objeto associado a x.
    - A chamada id(x) devolve o endereço do objeto associado a x.
    - A chamada sys.getrefcount(x) devolve o valor contador de referências do objeto associado a x.
    - Uma mesma variável pode, ao longo do tempo, ser sucessivamente associada a dados "pequenos" (como por exemplo o inteiro 42) e a dados "grandes" (como uma lista com milhões de elementos). Isto é possível porque o conteúdo real da variável é o endereço do objeto associado a ela.
    - Os objetos associados às variáveis são alocados dinâmicamente. Em outras palavras, a cada criação de objeto o interpretador Python executa automaticamente uma função similar à função malloc da biblioteca de C.
    - Se não há mais nenhuma variável apontando para um determinado objeto, a memória ocupada pelo objeto é liberada. Em outras palavras, o interpretador Python executa automaticamente uma função similar à função free da biblioteca de C. A responsabilidade pela liberação da memória não é do programador.
    - O processo de liberação da memória ocupada por objetos que deixaram de ser usados é denominado coleta de lixo (garbage collection). O interpretador Python implementa um esquema de coleta de lixo baseado nos contadores de referências e na detecção de referências cíclicas.
    - Leitura: capítulo 6 do livro "Learning Python", de Mark Lutz.
  - Tópicos diversos:
    - Em Python nao há i++ nem i--. (Use i += 1 em vez de i++.)
    - O comando if, o comando for e a função range().
    - Condições lógicas envolvendo intervalos podem ser expressas de maneira bem próxima à notação usual em matemática. Exemplo: if 3.5 <= x < y < 5: ...
    - Comando break e cláusula else em laços.
    - Exemplo de laço com else: programa que imprime o n-ésimo número primo (o mesmo programa sem cláusula else no laço).
    - Usamos o programa que imprime o n-nésimo número primo para comparar as sintaxes e os desempenhos de várias linguagens: Python, C, Java, Ruby e Scala (script, aplicação).
    - Programa que copia a entrada padrão para a saída padrão.
    - Funções.
9 de maio (aula 20):
- Python:
  - Tuplas.
  - A função input e o método readline.
  - Módulos.
  - Documentação de funções.
14 de maio (aula 21):
- Exceções em Python:
  - ...
16 de maio (aula 22):
- Conceitos de orientação a objetos:
  - ...
21 de maio (aula 23):
- Segunda prova.
23 de maio (aula 24):
- Orientação a objetos em Python:
  - ...
28 de maio (aula 25):
- Aula sobre o EP4. Tópicos de Python necessários para o EP4.

Junho

4 de junho (aula 26):
- Orientação a objetos em Python:
  - Campos e métodos de classe.
  - Herança.
  - Herança múltipla.
  - Exception classes.
6 de junho (aula 27):
- Iteradores, geradores e expressões geradoras em Python.
- Enumeração de subsequências em ordem lexicográfica.
11 de junho (aula 28):
- Uso de um gerador para enumerar subsequências em ordem lexicográfica
- O problema das rainhas.
  - Soluções em Python:
    - Primeira solução (enumera e percorre todas as permutações das colunas)
    - Segunda solução (usa backtracking para evitar a enumeração de todas as permutações das colunas)
    - Terceira solução (recursiva)
  - Solução em C, não vista em classe (usa backtracking e implementa o mesmo algoritmo que a segunda solução acima)
13 de junho (aula 29):
- Revisão da segunda prova. Solução da questão 4.
- Tópico especial: Diffie-Hellman key exchange.
18 de junho (aula 30):
- ...
20 de junho (aula 31):
- Terceira prova.
25 de junho (aula 32):
- ...
27 de junho (aula 33):
- Quarta prova (substitutiva).

Last modified: Wed Jun 19 12:11:28 BRT 2013
Francisco Reverbel
reverbel at ime.usp.br