Diário de Bordo

MAC 122 - Poli - Elétrica, Opção Sistemas Eletrônicos - Primeiro Semestre de 2010

Fevereiro Março          Abril Maio          Junho

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

• 22 de fevereiro (aula 1):
  • Apresentação da disciplina.
  • 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 MAC2166) que impõe um limitante superior para o comprimento da sequê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.
  • Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre endereços e ponteiros e sobre alocação dinâmica de memória.

• 25 de fevereiro (aula 2):
  • Equivalência entre vetores e ponteiros. Aritmética de ponteiros (continuação).
  • Breve revisão de ponteiros (ou apontadores) em C:
    • Declaração de variáveis apontadoras (int *p;), uso do operador "endereço de" para inicializar ponteiros (p = &i;), uso do operador "dereferência" (*p) para obter o valor apontado.
    • Passagem de endereços (ponteiros) como parâmetros para funções.
      • Exemplo: função void troca(int *p1, int *p2), que recebe os endereços de duas variáveis inteiras e troca os valores dessas variáveis.
  • Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre endereços e ponteiros.
  • 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.
  • Leitura recomendada: notas de aula do Prof. Paulo Feofiloff sobre structs.

• 1 de março (aula 3):
  • Registros ou estruturas (structs) em C (continuação):
    • 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.
  • Comentários sobre as três formas de alocação dados na memória: alocação estática (variáveis globais), alocação automática (variáveis locais) e alocação dinâmica (via malloc).
  • Listas encadeadas:
    • Estrutura de uma lista encadeada.
    • Listas encadeadas com cabeça e sem cabeça.
    • Função que insere um elemento no início de uma lista encadeada com cabeça.
    • Função que imprime os elementos de uma lista encadeada (versão para listas com cabeça).
  • Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre structs e sobre listas encadeadas.

• 4 de março (aula 4):
  • Listas encadeadas (continuação):
    • Função que imprime os elementos de uma lista encadeada (versão para listas sem cabeça).
    • Função que insere um novo elemento num ponto qualquer (após uma célula especificada) de uma lista encadeada com cabeça.
    • Função que insere um novo elemento num ponto qualquer de uma lista encadeada sem cabeça. O "ponto qualquer" da lista tem de ser especificado por meio de um ponteiro para um ponteiro. Na solução vista em classe, a função recebe um parâmetro Celula **p cujo valor pode ser tanto o endereço da varíavel que guarda o início da lista como o endereço do campo prox da célula após a qual se deseja inserir o novo elemento. (Este é o exercício 8 das notas de aula sobre listas encadeadas.)
    • 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.
    • Função de busca por elemento em lista encadeada (versão para listas com cabeça e versão para listas sem cabeça).
    • Outros tipos de listas: lista encadeada circular, lista duplamente encadeada.
    • Função de "busca e remoção" para listas encadeadas com cabeça.
  • Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre listas encadeadas.
  • Fazer em casa: Exercícios de 1 a 7, de 9 a 19, 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, pular essa parte.

• 8 de março (aula 5):
  • Listas encadeadas (continuação):
    • Função de "busca e inserção" para listas encadeadas com cabeça.
  • 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.
  • Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre listas encadeadas e sobre filas.

• 11 de março (aula 6):
  • Filas (continuação):
    • Implementação de fila usando um vetor circular.
    • Referência: notas de aula do Prof. Paulo Feofiloff sobre filas.
  • 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 mallocX. Arquivo mallocx.h (interface), arquivo mallocx.c (implementação) e programa que chama a função mallocX (cliente do módulo).
  • Módulo fila:
    • A interface do módulo fila (arquivos item.h e fila.h).

• 15 de março (aula 7):
  • Módulo fila (continuação):
    • Implementação do módulo fila usando um vetor circular (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 do módulo fila.
    • Implementação do módulo fila como lista encadeada com cabeça (segunda versão do arquivo fila.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 (escopo, 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".
    • Normalmente as variáveis locais são alocadas na pilha de execução e as variávis globais têm 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.

• 18 de março (aula 8):
  • 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.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. (O balanceamento de parênteses e colchetes foi apenas mencionado em classe.)
  • 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 em aulas anteriores (módulo fila implementado usando um vetor circular e módulo fila implementado usando uma lista encadeada com cabeça) define um tipo de dados que é abstrato, mas não é de primeira classe. O mesmo acontece com módulo pilha visto nesta aula.
    • Exemplo: 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.

• 25 de março (aula 9):
  • Primeira prova.

• 5 de abril (aula 10):
  • Resolução de dúvidas sobre o EP1.
  • Tópico de C necessário para o EP1: argumentos na linha de comando.
  • Leitura recomendada: notas de aula do Prof. Paulo Feofiloff sobre entrada e saída.

• 8 de abril (aula 11):
  • Recursão e algoritmos recursivos.
  • Exemplos:
    • Função recursiva que calcula o fatorial de um inteiro não negativo dado.
      • Simulação da execução dessa função.
    • Função recursiva que devolve o valor de um elemento máximo de um vetor v[0..n-1] dado.
      • Versão que aplica recursão ao subvetor v[0..n-2].
      • Versão que aplica recursão ao subvetor v[1..n-1] e usa uma função auxiliar.
      • Versão que aplica recursão ao subvetor v[1..n-1] e usa aritmética de endereços.
    • Solução recursiva para o problema das Torres de Hanoi com n discos.
      • Simulação de parte da execução dessa função.
    • Função recursiva que calcula a soma dos elementos positivos de um vetor v[ini..fim-1] dado (exercício 8 das notas de aula do Prof. Paulo Feofiloff sobre recursão e algoritmos recursivos).
  • Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre recursão e algoritmos recursivos.
  • Fazer em casa:
    • Exercícios 7, 9, 10, 11, 16, 17, 18 e 19 das notas de aula do Prof. Paulo Feofiloff sobre recursão e algoritmos recursivos.
    • Exercícios 11, 12, 13, 14, 15, 17, 18 e 19 das notas de aula do Prof. Paulo Feofiloff sobre listas encadeadas (soluções recursivas).

• 12 de abril (aula 12):
  • Exercícios:
    • Escreva uma função recursiva que calcule a soma dos dígitos de um inteiro positivo n (exercício 9 das notas de aula do Prof. Paulo Feofiloff sobre recursão e algoritmos recursivos).
    • Escreva uma função recursiva que calcule o piso do logaritmo de n na base 2 (exercício 10 das notas de aula do Prof. Paulo Feofiloff sobre recursão e algoritmos recursivos).
    • Escreva uma função recursiva eficiente que receba inteiros positivos k e n e calcule kⁿ (exercício 19 das notas de aula do Prof. Paulo Feofiloff sobre recursão e algoritmos recursivos).
    • Escreva uma função recursiva que conte o número de células de uma lista encadeada (versão recursiva do exercício 15 das notas de aula do Prof. Paulo Feofiloff sobre listas encadeadas).
    • Escreva uma função recursiva que copie um vetor para uma lista encadeada sem cabeça (versão recursiva do exercício 11 das notas de aula do Prof. Paulo Feofiloff sobre listas encadeadas).
    • Escreva uma função recursiva que imprima os elementos de uma lista encadeada sem cabeça.
    • Escreva uma função recursiva que imprima os elementos de uma lista encadeada sem cabeça em ordem reversa.

• 15 de abril (aula 13):
  • 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. (Este assunto é útil para o EP1!)
    • Solução no caso de sequências implementadas como vetores.
    • Solução no caso de sequências implementadas como listas encadeadas.
  • Noções de análise de algoritmos.
    • Notação assintótica: motivação e definição de "O grande".
    • Leitura recomendada: Sedgewick, da seção 2.2 à 2.4.

• 19 de abril (aula 14):
  • Noções de análise de algoritmos (continuação).
    • Relações de recorrência básicas.
    • Referência: Sedgewick, seção 2.5.
  • Busca em vetor ordenado:
    • Busca sequencial. Desempenho (tempo de execução no pior caso) da busca sequencial.
    • Busca binária. Desempenho da busca binária.
  • Leitura recomendada: notas de aula do Prof. Paulo Feofiloff sobre sobre busca em vetor ordenado.

• 22 de abril (aula 15):
  • 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.

• 26 de abril (aula 16):
  • A estrutura de dados heap.
  • O algoritmo heapsort. Desempenho do heapsort.
  • Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre o heapsort.

• 29 de abril (aula 17):
  • Resolução de dúvidas sobre o EP2.
  • Exercícios:
    • Escreva uma função recursiva que receba o endereço do início de uma lista encadeada sem cabeça e devolva o endereço de uma célula com um elemento máximo da lista (versão recursiva da questão 2 da primeira prova).
    • Simule a execução da função do exercício acima.
    • Escreva uma função recursiva que receba o endereço do início de uma lista encadeada sem cabeça e devolva dois endereços: o endereço de uma célula com um elemento máximo e o de uma célula com um elemento mínimo. Para que sua função possa devolver dois endereços, faça-a receber dois parâmetros adicionais, do tipo Celula ** (ponteiro para ponteiro para célula).
  • Exemplo simples que mostra a necessidade ponteiros para ponteiros: função que recebe o endereço do início de uma lista encadeada e modifica esse endereço, sobrescrevendo-o com NULL.
    • Simulação da execução dessa função.

• 3 de maio (aula 18):
  • Resolução de dúvidas sobre o EP2.
  • Exercícios:
    • Escreva uma função recursiva que calcule o máximo divisor comum de dois inteiros positivos m e n (exercício 18 das notas de aula do Prof. Paulo Feofiloff sobre recursão e algoritmos recursivos).
    • Escreva uma função recursiva que verifique se duas listas encadeadas são iguais, ou seja, se elas tem o mesmo conteúdo (versão recursiva do exercício 17 das notas de aula do Prof. Paulo Feofiloff sobre listas encadeadas). Faça duas soluções, uma para listas sem cabeça e outra para listas com cabeça.
    • Escreva uma função recursiva que copie uma lista encadeada para um vetor (versão recursiva do exercício 12 das notas de aula do Prof. Paulo Feofiloff sobre listas encadeadas).

• 10 de maio (aula 19):
  • Segunda prova

• 13 de maio (aula 20):
  • 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.

• 17 de maio (aula 21):
  • Estabilidade de algoritmos de ordenação.
  • Ordenação de texto.
    • Representação do texto como um vetor de ponteiros (strings). Cada elemento do vetor é uma string com uma linha do texto.
    • Comparação lexicográfica (função strcmp).
    • Exemplo: programa que lê da entrada padrão um arquivo de texto e imprime na saída padrão o arquivo com as linhas ordenadas.
    • Referência: Kernighan & Ritchie, seção 5.6.

• 20 de maio (aula 22):
  • Ponteiros para funções.
    • Exemplo de uso: função de ordenação genérica, que recebe num de seus parâmetros um ponteiro para uma função de comparação.
    • Referência: Kernighan & Ritchie, seção 5.11.

• 24 de maio (aula 23):
  • Tabelas com suporte a busca, inserção e remoção.
    • Implementações elementares (com busca linear):
      • Tabela implementada como vetor de structs.
      • Tabela implementada como lista encadeada.
    • Introdução às tabelas de espalhamento (hash tables).

• 27 de maio (aula 24):
  • Tabelas de espalhamento (hash tables).
    • Tabela implementada como tabela de hash.
    • Referência: Kernighan & Ritchie, seção 6.6.

• 31 de maio (aula 27):
  • Aula sobre o terceiro exercício-programa.

• 7 de junho (aula 28):
  • Problema: Escrever uma função eficiente que receba um vetor de inteiros v[1..n], receba um inteiro s e imprima os pares de elementos do vetor cuja soma é igual a s.
    • Solução 1: usa laços encaixados e "força bruta". Desempenho assintótico: O(n²)
    • Solução 2: ordena o vetor e faz n-1 buscas binárias. Desempenho assintótico: O(n log n).
    • Solução 3: ordena o vetor e o percorre uma vez, usando dois índices -- um que avanca a partir do ínicio do vetor e outro que recua a partir do final do vetor. Desempenho assintótico: O(n log n).
    • Solução 4: usa uma tabela de hash. Faz ninserções e n buscas na tabela. Desempenho assintótico: O(n) (supondo que não há colisões).

• 10 de junho (aula 29):
  • Aula de exercícios e resolução de dúvidas.

• 17 de junho (aula 30):
  • Terceira prova.

• 21 de junho (aula 31):
  • Prova substitutiva.

Last modified: Sun Jun 13 20:39:31 BRT 2010
Francisco Reverbel
reverbel at ime.usp.br