Diário de Bordo

MAC 122 - BE/BM/BMA, turma 42 - Segundo Semestre de 2009

Agosto Setembro          Outubro Novembro          Dezembro

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

• 18 de agosto (aula 1):
  • Apresentação da disciplina: informações gerais, bibliografia, etc.
  • Programa "Hello, World" em C.
  • 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.
  • Tarefa para quem for usar o ambiente de desenvolvimento integrado (ou IDE, de integrated development environment) Code::Blocks: instale esse IDE no seu computador pessoal (aqui há ponteiros para instruções de instalação) e faça a aula dirigida de introdução ao Code::Blocks.
  • Tarefa para quem não for usar o Code::Blocks: use um editor de texto no Linux (gedit, Emacs, Vim, ou outro -- eu prefiro o Emacs, que no início pode ser um pouco difícil, mas é muito poderoso) para criar um programa fonte em C, compile o programa fonte com o gcc e rode o programa compilado. Começe com um programa "Hello, World" e depois vá aumentando a complexidade do programa.

• 20 de agosto (aula 2):
  • Exercício 1 da segunda lista de exercícios com funções usada nas disciplinas de Introdução à Computação.
  • Exercício 2 da segunda lista de exercícios com funções usada nas disciplinas de Introdução à Computação.
  • Uso de ints como valores lógicos em C (a linguagem não tem um tipo boolean).
  • Entrada e saída de inteiros em C (funções scanf e printf).
  • Fazer em casa:
    • Exercícios 3 e 4 da segunda lista de exercícios com funções usada nas disciplinas de Introdução à Computação.
    • Problema: Dizemos que um número natural n é palíndromo se vemos a mesma seqüência de dígitos quando lemos o número da direita para a esquerda e quando o lemos da esquerda para a direita. Exemplos: 567765 e 32423 são palíndromos; 567675 não é palíndromo.
      • Escreva uma função que recebe um inteiro n > 0 e devolve o seu primeiro dígito, seu último dígito e altera o valor de n removendo seu primeiro e último dígitos.
      • Escreva um programa que lê um inteiro positivo n e verifica se n é palíndromo. Suponha que n não contém o dígito 0.

• 25 de agosto (aula 3):
  • Vetores (arrays ou matrizes unidimensionais) em C.
  • Constantes simbólicas (diretiva #define).
  • O pré-processador C (como funcionam as diretivas #include e #define).
  • Passagem de vetores como parâmetros de funções.
  • Problema:
    • Escreva uma função
          int busca(float x, int n, float v[]);
      que devolve a posição em que o real x ocorre no vetor v ou devolve -1 se x não aparece no vetor. O número de elementos do vetor é n.
    • Escreva um programa que lê uma sequência de n números reais e imprime essa sequência eliminando as repetições de elementos.
  • Recursão. Funções recursivas.
    • Exemplo: função recursiva que devolve o fatorial de um inteiro não negativo.

• 27 de agosto (aula 4):
  • Simulação da execução de uma função recursiva.
  • Problema: Escreva uma função que determine o valor de um elemento máximo de um vetor v[0..n-1].
    • Solução iterativa (revisão de MAC0110 ou MAC0115).
    • Solução recursiva. A recursão é aplicada ao subvetor v[0..n-2].
    • Outra solução recursiva. Agora a recursão é aplicada ao subvetor v[1..n-1].
  • Problema: Escreva uma função recursiva que calcule a soma dos elementos positivos do vetor de inteiros v[0..n-1].
  • Leitura recomendada: notas de aula do Prof. Paulo Feofiloff sobre recursão e algoritmos recursivos.
  • Fazer em casa: Exercícios 8, 9, 10, 11, 16, 17, 18 e 19 das notas de aula do Prof. Paulo Feofiloff sobre recursão e algoritmos recursivos.

• 1 de setembro (aula 5):
  • Problema: Escreva uma função recursiva maxmin que calcule o valor de um elemento máximo e o valor de um elemento mínimo de um vetor de inteiros v[0..n-1].
  • Problema: Escreva uma função recursiva que calcule a soma dos dígitos de um inteiro positivo n.
  • Problema: Escreva uma função recursiva que calcule o piso do logaritmo na base 2 de um inteiro positivo n.
  • O problema das Torres de Hanoi. Uma função recursiva que resolve esse problema.

• 3 de setembro (aula 6):
  • Problema: Escreva uma função recursiva para calcular a função de Fibonacci, que é definida como F(0) = 0, F(1) = 1 e F(n) = F(n-1) + F(n-2) para n > 1.
  • Problema: Escreva uma função recursiva que calcula o máximo divisor comum de dois números, usando o algoritmo de Euclides.
  • Problema: Escreva uma função recursiva eficiente que receba inteiros positivos k e n e calcule kⁿ. (Suponha que kⁿ cabe em um int.) Sua função deve executar aproximadamente log₂n multiplicações.

• 8 de setembro (aula 7):
  • Tópicos de C necessários para o EP1:
    • Manipulação de arquivos (fopen, fscanf, fprintf, fclose).
    • Variáveis tipo char.
    • Leitura de arquivos caractere a caractere (fscanf(arq, "%c", &ch)).
    • O valor devolvido por scanf e fscanf. Uso no EP1: detecção de final de arquivo.
    • Manipulação de caracteres. Conversão dos códigos dos dígitos nos ints correspondentes (ch - '0').
  • Relação entre vetores e ponteiros. Aritmética de ponteiros.

• 10 de setembro (aula 8):
  • Exemplo de uso de aritmética de ponteiros:
    • Problema: Escreva uma função que determine o valor de um elemento máximo de um vetor v[0..n-1]. Solução recursiva que usa aritmética de ponteiros para aplicar a recursão ao subvetor v[1..n-1].
  • Alocação dinâmica de memória: as funções malloc e free.
  • O operador sizeof.
  • Problema: Escreva um programa que lê uma sequência de n números inteiros e imprime essa sequência eliminando as repetições de elementos. Solução que não impõe um limitante superior sobre o número de elementos distintos da sequência.

• 15 de setembro (aula 9):
  • Matrizes bidimensionais em C: vetores de vetores.
  • Alocação dinâmica de matrizes. Exemplo.

• 17 de setembro (aula 10):
  • Cadeias de caracteres (strings) em C.
    • Constantes do tipo string ("MAC0122").
    • Inicialização de strings.
    • Leitura e impressão de strings com "%s".
    • Strings declaradas como vetores e strings declaradas como ponteiros.
    • Exemplos: várias implementações da função strlen (da biblioteca <string.h>), que devolve o comprimento de uma string dada.
  • Registros ou estruturas (structs) em C:
    • Declaração de um tipo struct. Exemplos.
    • Variáveis tipo tipo struct.
    • Acesso aos campos de uma struct.
  • Leitura recomendada: notas de aula do Prof. Paulo Feofiloff sobre structs.

• 22 de setembro (aula 11):
  • Definição de novos nomes (sinônimos) para tipos já existentes (typedef).
  • Registros ou estruturas (structs) em C (continuação):
    • Passagem de structs como parâmetros para funções ou como valores devolvidos por funções.
    • Ponteiros para structs e a notação "->".
    • Alocação dinâmica de structs.
  • Problema (revisão de recursão): Escreva uma função que leia uma sequência de inteiros não nulos, terminada por zero, e imprima a sequência em ordem inversa à da leitura. Faça uma versão iterativa e uma versão recursiva. A versão recursiva não deve usar vetores. (Em classe só fizemos a versão recursiva.)

• 24 de setembro (aula 12):
  • Primeira prova.

• 29 de setembro (aula 13):
  • Listas encadeadas: Estrutura (células) de uma lista encadeada.
  • Listas encadeadas com cabeça e sem cabeça.
  • Exemplo: função que imprime o conteúdo de uma lista encadeada (versão para listas com cabeça e versão para listas sem cabeça, versão iterativa e versão recursiva).
  • Busca em uma lista encadeada com cabeça (versão iterativa e versão recursiva).
  • Leitura recomendada: notas de aula do Prof. Paulo Feofiloff sobre listas encadeadas.

• 1 de outubro (aula 14):
  • Assunto usado no EP2: o formato de arquivos PGM, para imagens monocromáticas (em tons de cinza).
  • Inserção de elemento em vetor (versão iterativa).
  • Inserção de elemento numa lista encadeada com cabeça. Comparação com a inserção de elemento em vetor.
  • Remoção de elemento de vetor (versão iterativa).
  • Remoção de elemento de uma lista encadeada com cabeça. Comparação com a remoção de elemento de vetor.
  • Função que desaloca (free) todas as células de uma lista encadeada. (Este é o exercício 18 das notas de aula sobre listas encadeadas.)
  • Leitura recomendada: notas de aula do Prof. Paulo Feofiloff sobre vetores (as partes sobre inserção e remoção) e sobre listas encadeadas. Nas notas sobre vetores, estudar as versões recursivas das funções de inserção e remoção.
  • Fazer em casa: Exercícios de 1 a 17 e exercício 19 das notas de aula sobre listas encadeadas.

• 6 de outubro (aula 15):
  • Tópico de C necessário para o EP2: argumentos na linha de comando.
  • Outro assunto útil para o EP2: intercalação de vetores ordenados.
  • Função iterativa que converte um vetor em lista encadeada. (Isso é a primeira parte do exercício 11 das notas de aula sobre listas encadeadas. Fazer em casa a segunda parte, que é a versão recursiva da função.)

• 8 de outubro (aula 16):
  • Busca-e-remoção em uma lista encadeada com cabeça.
  • Busca-e-inserção em uma lista encadeada com cabeça.
  • Outros tipos de listas: lista duplamente encadeada, lista circular.
  • Função que conta o número de células de uma lista encadeada: versão iterativa e versão recursiva. (Isso é o exercício 15 das notas de aula sobre listas encadeadas.)
  • Leitura recomendada: notas de aula do Prof. Paulo Feofiloff sobre listas encadeadas.
  • Fazer em casa: Exercícios 22, 23, 25, 26 e 27 das notas de aula sobre listas encadeadas.

• 13 de outubro (aula 17):
  • 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 (não concluímos este assunto).
  • Leitura recomendada: notas de aula do Prof. Paulo Feofiloff sobre filas.

• 15 de outubro (aula 18):
  • Implementação de fila usando um vetor circular (continuação).
    • Referência: notas de aula do Prof. Paulo Feofiloff sobre filas.
  • Divisão de um programa C em arquivos-fonte (módulos) compilados separadamente.
  • Modularização de programas C: 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).
  • Definição da interface de uma fila (arquivos item.h e 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).

• 20 de outubro (aula 19):
  • Exemplo de cliente de uma fila.
  • Implementação de uma 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 alcance (ou visibilidade).
    • 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.
  • Pilhas:
    • Implementação de pilha usando vetor.
    • Leitura recomendada: notas de aula do Prof. Paulo Feofiloff sobre sobre pilhas.

• 22 de outubro (aula 20):
  • Definição da interface de uma pilha (arquivos item.h e pilha.h).
  • Implementação de uma pilha usando vetor (primeira versão do arquivo pilha.c).
  • Exemplo de uso de 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.
  • Leitura recomendada: notas de aula do Prof. Paulo Feofiloff sobre sobre pilhas.

• 27 de outubro (aula 21):
  • Aula de exercícios.
    • Escreva uma função recursiva que encontre uma célula de conteúdo mínimo numa lista encadeada sem cabeça. (Isso é a parte recursiva do exercício 3 das notas de aula sobre listas encadeadas.)
    • Escreva uma função que faça uma cópia de uma lista dada (exercício 13 das notas de aula sobre listas encadeadas). Em classe fizemos uma solução iterativa. (Tarefa de casa: Fazer uma solução recursiva.)
    • Escreva uma função que intercala duas listas encadeadas sem cabeça. A função que escrevemos em classe reaproveita todas as células das duas listas dadas. Ela pega essas células e as coloca na lista resultado, destruindo as duas listas originais. (Tarefa de casa: Escreva uma versão da função intercala que crie uma lista resultado com células novas, sem destruir as listas originais.)
    • Escreva uma função que inverte a ordem das células de uma lista encadeada (exercício 19 das notas de aula sobre listas encadeadas). Faça isso sem usar espaço auxiliar; apenas altere os ponteiros. Em casa escrevemos uma solução recursiva. (Tarefa de casa: Escreva uma solução recursiva.)

• 29 de outubro (aula 22):
  • Segunda prova.

• 3 de novembro (aula 23):
  • Exemplo de uso de pilha: avaliação de expressões aritméticas em notação posfixa (também conhecida como notação polonesa). Programa que implementa uma calculadora posfixa simples.

• 5 de novembro (aula 24):
  • Exemplo de uso de pilha: traduzir uma expressão da notação infixa para notação posfixa.
  • Leitura recomendada: notas de aula do Prof. Paulo Feofiloff sobre sobre pilhas.

• 10 de novembro (aula 25):
  • 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 de fila vistas em aulas anteriores (fila implementada usando um vetor circular e fila implementada usando uma lista encadeada com cabeça) definia um tipo de dados "fila" que era abstrato, mas não era de primeira classe.
  • 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.
  • Exemplo: modificação no exemplo anterior para que o tipo de dados Fila seja também abstrato. Temos agora um tipo de dados abstrato de primeira classe.
  • Tarefa de casa: Escrever outra implementação para o mesmo ADT de primeira classe, desta vez usando uma lista encadeada.
  • Leitura recomendada: Sedgewick, seção 3.1, introdução do cap. 4 e seção 4.8.
  • Observações sobre a influência que escolha de um algoritmo tem sobre o tempo necessário para resolver problemas de diferentes tamanhos (tabela 2.1 do Sedgewick).

• 12 de novembro (aula 26):
  • Resolução de dúvidas sobre o EP3.
  • 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.

• 17 de novembro (aula 27):
  • Resolução de dúvidas sobre o EP3.
  • 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.
  • Leitura recomendada: Sedgewick, da seção 2.2 à 2.6.

• 19 de novembro (aula 28):
  • Algoritmos elementares de ordenação: ordenação por inserção e ordenação por seleção. Desempenho da ordenação por inserção e da ordenação por seleção.
  • Estabilidade de algoritmos de ordenação.
  • Ordenação por intercalação (mergesort). Desempenho do mergesort.
  • Leitura recomendada: Notas de aula do Prof. Paulo Feofiloff sobre algoritmos elementares de ordenação e sobre o mergesort.

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

• 26 de novembro (aula 30):
  • 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.

• 1 de dezembro (aula 31):
  • Conversa sobre o EP4.
  • Busca exaustiva com backtracking.
  • Aplicação: programa que acha todas as soluções para o problema das n rainhas.

• 3 de dezembro (aula 32):
  • Resolução de dúvidas sobre o EP4.
  • Exercícios de revisão.
  • Hashing. Tabelas de hash.

• 10 de dezembro (aula 33):
  • Terceira prova.

• 17 de dezembro (aula 34):
  • Prova substitutiva (apenas para os alunos que comprovadamente não puderam comparecer a alguma das três provas anteriores).

Last modified: Wed Dec 9 19:02:11 BRST 2009
Francisco Reverbel
reverbel at ime.usp.br