Diário de Bordo

MAC 115 - BMAC - Segundo Semestre de 2008

	Agosto
	Setembro

	Outubro
	Novembro

Dezembro

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

Agosto

5 de agosto (aula 1):
- Apresentação da disciplina.
7 de agosto (aula 2):
- Problema: Dados n > 0 e uma sequência de n números reais, imprimir esses números eliminando as repetições. Resolução (provavelmente já vista em MAC0110) que impõe um limitante superior para o comprimento da seqüência.
- Alocação dinâmica de memória: as funções malloc e free.
- Resolução do problema acima sem limitar de antemão o comprimento da seqüência.
- Equivalência entre vetores e ponteiros. Aritmética de ponteiros.
12 de agosto (aula 3):
- Endereços e ponteiros (revisão de MAC0110).
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre endereços e ponteiros e sobre alocação dinâmica de memória.
- Problema: Escrever uma função expande, cujo protótipo é
  int expande(void **p_area, int *p_n);
  A função expande recebe em *p_area o endereço de uma área alocada dinâmicamente e em *p_n o comprimento (em bytes) dessa área. Ela tenta alocar uma nova área com o dobro do espaço da área original. Caso consiga alocar a nova área, a função copia o conteúdo da área original para os primeiros *p_n bytes da área nova, libera a área original, coloca em *p_area o endereço da área nova, coloca em *p_n o comprimento (em bytes) da área nova, e devolve 1 para quem a chamou. Caso não consiga alocar a nova área, a função devolve 0 para quem a chamou.
- Tarefa de casa: Refazer o problema da aula anterior, desta vez usando a função expande. Faça o vetor com os elementos distintos da seqüência "crescer" quando necessário.
14 de agosto (aula 4):
- Registros (structs): definição e manipulação, structs e ponteiros.
- Definição de novos nomes (sinônimos) para tipos já existentes (typedef).
- Listas encadeadas: Estrutura de uma lista encadeada.
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre structs e sobre listas encadeadas.
19 de agosto (aula 5):
- Listas encadeadas com cabeça e sem cabeça.
- Exemplo: Impressão do conteúdo de uma lista encadeada.
- Busca em uma lista encadeada com cabeça.
- Inserção em uma lista encadeada com cabeça.
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre listas encadeadas.
- Tarefa de casa: Vimos em classe uma função de busca em lista encadeada que devolve um ponteiro para a célula anterior à que contém o valor procurado. Já as notas de aula apresentam uma função de busca que devolve um ponteiro para a célula que contém o valor procurado. Compare essas duas funções. Em que situação a primeira pode ser usada e a segunda não? Qual delas pode ser modificada mais facilmente para funcionar com listas sem cabeça?
- Tarefa de casa: Exercícios 1 a 17 das notas de aula sobre listas encadeadas.
21 de agosto (aula 6):
- Remoção em uma lista encadeada com cabeça.
- Outros tipos de listas: lista duplamente encadeada, lista circular.
- Exercício 17 (esvaziar lista) das notas de aula sobre listas encadeadas.
- Busca-e-remoção em uma lista encadeada com cabeça.
- Busca-e-inserção em uma lista encadeada com cabeça.
- Filas (apenas começamos este assunto).
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre listas encadeadas e sobre filas.
26 de agosto (aula 7):
- 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 circular de fila (não concluímos este assunto).
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre filas.
28 de agosto (aula 8):
- O esquema interface/implementação/cliente.
- Definição da interface de uma fila (arquivo fila.h).
- Implementação circular de uma fila (primeira versão do arquivo fila.c). Uso de static para declarar variáveis não-locais privativas de um certo módulo (no caso, o módulo fila.c).
- Exemplo de cliente de uma fila.
- Implementação uma fila como lista encadeada com cabeça (segunda versão do arquivo fila.c).

Setembro

2 de setembro (aula 9):
- Implementação uma fila como lista encadeada com cabeça (continuação da aula anterior).
- Definições: Tipo de dados, tipo de dados abstrato (abstract data type ou ADT) e tipo de dados de primeira classe.
- Exemplo: Tipo de dados abstrato de primeira classe para filas. Implementação desse tipo usando vetores circulares.
- Leitura recomendada: Sedgewick, seção 3.1, introdução do cap. 4 e seção 4.8.
- Tarefa de casa: Escrever outra implementação para o mesmo ADT de primeira classe, agora usando listas encadeadas.
4 de setembro (aula 10):
- Resolução de dúvidas sobre o EP1.
16 de setembro (aula 11):
- Pilhas.
- Implementação de pilha usando vetor.
- Aplicação: balanceamento de parênteses e colchetes.
- Tipo de dados abstrato (porém não de primeira classe) para uma pilha: interface (arquivo pilha.h) e implementação usando vetor (arquivo pilha.c)
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre pilhas.
- Leitura adicional: Sedgewick, da seção 4.1 à 4.4.
18 de setembro (aula 12):
- O problema da intercalação (merge): dadas duas seqüências ordenadas, gerar uma terceira seqüência ordenada contendo todos os elementos das duas seqüências dadas.
  - Solução no caso de seqüências implementadas como vetores.
  - Solução no caso de seqüências implementadas como listas encadeadas.
- Implementação de uma pilha como lista encadeada.
- Tarefa de casa: Definir a interface de um tipo de dados abstrato mas não de primeira classe para uma pilha (criar um arquivo pilha.h). Criar duas implementações desse tipo (duas versões do arquivo pilha.c), uma usando um vetor e a outra usando uma lista encadeada.
- Tarefa de casa: Definir a interface de um tipo de dados abstrato de primeira classe para uma pilha (criar outro arquivo pilha.h). Criar duas implementações desse tipo (duas versões do arquivo pilha.c), uma usando um vetor e a outra usando uma lista encadeada.
23 de setembro (aula 13):
- Uma questão sobre o EP1: Como implementar as funções soma, subtrai e multiplica para que elas devolvam seus resultados no primeiro parâmetro?
- Aplicação de pilha: Traduzir uma expressão da notação infixa para notação posfixa.
25 de setembro (aula 14):
- Primeira prova.
30 de setembro (aula 15):
- Recursão e algoritmos recursivos.
- Exemplos:
  - Função recursiva que devolve o valor de um elemento máximo de um dado vetor v.
  - Função recursiva que calcula o fatorial de um inteiro não negativo dado.
  - Solução recursiva para o problema das Torres de Hanoi com n discos.
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre recursão e algoritmos recursivos.

Outubro

2 de outubro (aula 16):
- Exercícios 7, 9, 11, 16 e 19 das notas de aula do Prof. Paulo Feofiloff sobre recursão e algoritmos recursivos.
- Busca em uma lista encadeada com cabeça: versão recursiva.
7 de outubro (aula 17):
- Exercícios 10, 11, 14 e 16 das notas de aula do Prof. Paulo Feofiloff sobre listas encadeadas (soluções recursivas).
9 de outubro (aula 18):
- Noções de análise de algoritmos. Notação assintótica: motivação e definição de "O grande". Relações de recorrência elementares.
- Busca linear num vetor não ordenado.
- Busca binária num vetor ordenado.
- Leitura recomendada:
  - Sedgewick, da seção 2.2 à 2.6.
  - Notas de aula do Prof. Paulo Feofiloff sobre busca em vetor ordenado.
14 de outubro (aula 19):
- Algoritmos elementares de ordenação: ordenação por inserção e ordenação por seleção.
- Ordenação por intercalação (mergesort).
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre algoritmos elementares de ordenação e sobre o mergesort.
- Leitura adicional: capítulo 8 do Sedgewick.
16 de outubro (aula 20):
- Versão iterativa do mergesort.
- A estrutura de dados heap (árvore binária quase-completa), que será usada no heapsort.
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre o heapsort.
21 de outubro (aula 21):
- Tópicos de C necessários para o EP2:
  - Argumentos na linha de comando.
  - Leitura de dados de um arquivo.
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre entrada e saída de dados em C.
- A estrutura de dados heap (revisão).
- O algoritmo heapsort.
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre o heapsort.
- Leitura adicional: capítulo 9 do Sedgewick.
23 de outubro (aula 22):
- O problema da separação. Algoritmo da separação. Desempenho do algoritmo da separação.
- Quicksort. Desempenho do quicksort.
- Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre o quicksort.
- Leitura adicional: capítulo 7 do Sedgewick.
30 de outubro (aula 23):
- Eliminação da "recursão de cauda" (tail recursion) no Quicksort.
- Controle da altura da pilha de execução no Quicksort.
- Ordenação de texto: comparação lexicográfica (função strcmp), representação do texto como um vetor de ponteiros (strings).

Novembro

4 de novembro (aula 24):
- Revisão da primeira prova.
6 de novembro (aula 25):
- Segunda prova.
11 de novembro (aula 26):
- Aula sobre o terceiro exercício-programa.
18 de novembro (aula 27):
- Hashing.
25 de novembro (aula 28):
- Hashing (continuação).
27 de novembro (aula 29):
- Terceira prova.

Dezembro

2 de dezembro (aula 30):
- ...
4 de dezembro (aula 31):
- Prova substitutiva (apenas para os alunos que não compareceram a uma das três provas anteriores).
9 de dezembro (aula 32):
- ...
11 de dezembro (aula 33):
- ...

Last modified: Tue Dec 2 16:27:01 BRST 2008
Francisco Reverbel
reverbel at ime.usp.br