MAC 122 - Princípios de Desenvolvimento de Algoritmos - Turma 41

Segundo Semestre de 2009

Roteiro das aulas

Agosto

18/08 (Aula 1)

• Informações gerais da disciplina
• Introdução à Linguagem C
  Leitura recomendada: Vários tópicos de Projeto de Algoritmos do prof. Paulo Feofiloff podem ser lidos, especialmente os que listamos a seguir:
  
  • Java versus C: um exemplo e uma tabela
  • Leiaute
  • Documentação
  • Inteiros
  • Entrada e saída
  • Precedência entre operadores em C
  • Interfaces de bibliotecas
  • Tabela de caracteres ISO 8859-1
• Leia mais aqui.

20/08 (Aula 2)

• Endereços e apontadores (uma introdução)
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Endereços e ponteiros.

25/08 (Aula 3)

• Consulte um material didático produzido pelo Departamento de Ciência da Computação do IME-USP, e que é utilizado na disciplina MAC0110 Introdução à Computação (em C):
  • Projeto MAC Multimídia
  • Caderno de Exercícios de Introdução à Computação, com os enunciados de vários problemas e com as soluções para alguns exercícios.
    

• Mais alguns exemplos de utilização de endereços e ponteiros.
  • Problema 3 : é o Exercício 3 de Exercícios com Funções - Parte II do Caderno de Exercícios de Introdução à Computação.
  • Problema 4 : Dizemos que um número natural n é palíndromo se lido da direita para a esquerda ou da esquerda para a direita é o mesmo número.
    Exemplos: 278872 e 12321 são palíndromos; 278782 não é palíndromo.
    (a) Escreva uma função que recebe um inteiro n >= 10 e devolve o seu primeiro dígito, seu último dígito e altera o valor de n removendo seu primeiro e último dígitos.
    (b) Escreva um programa que, dado um inteiro positivo n, verifica se n é palíndromo. Suponha que n não contém o dígito 0.

27/08 (Aula 4)

• Problema 5 : é o Exercício 2 de Exercícios com Funções - Parte II do Caderno de Exercícios de Introdução à Computação, com mais uma função cujo protótipo é dado a seguir:
        int ultimo_dia_mes (int mes, int ano);
  Essa função recebe mes e ano e devolve o último dia de mes.

  Exercícios para casa:
  - Exercícios 1, 4 e 6 de Exercícios com Funções - Parte II do Caderno de Exercícios de Introdução à Computação.
  - Escreva uma função que transforma um intervalo de tempo dado em segundos para dias, horas, minutos e segundos. Como seria uma chamada dessa função, a partir da função main?
  

• Algoritmos recursivos
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Recursão e algoritmos recursivos.

Setembro

01/09 (Aula 5)

• Mais algoritmos recursivos
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Recursão e algoritmos recursivos.

  Exercícios para casa:
  - Exercícios 7, 8 e 10 (e os outros exercícios que não vimos em aula) das Notas de aulas do Prof. Paulo Feofiloff sobre Recursão e algoritmos recursivos.

03/09 (Aula 6)

• Mais algoritmos recursivos
  

  Leia mais sobre o Problema das Torres de Hanoi, e veja uma animação da solução para 4 discos.

08/09 (Aula 7)

• Algumas explicações sobre o Exercício-Programa 1.
  
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre
  
  • Caracteres
  • Strings
  • Entrada e saída
  • Arquivos-interface de algumas bibliotecas padrão
  
  Consulte também as duas páginas a seguir sobre
  
  • Uma boa referência sobre a biblioteca da linguagem C.
  • Guia de referência da linguagem C.

10/09 (Aula 8)

• Vetores e Ponteiros
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Endereços e ponteiros.
  Vimos também a função recursiva maximo2_r, que utiliza aritmética de endereços (e aplica a recursão ao subvetor v[1..n-1]).
  
• Crivo de Eratosthenes: dado um inteiro n > 2, determinar todos os naturais primos  <= n.
  Uma solução considerando um limitante superior para n.

15/09 (Aula 9)

• Alocação dinâmica de memória (funções malloc e free, e o operador sizeof)
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Alocação dinâmica de memória.
  (Veja nessas notas a definição da função mallocX.)
• Crivo de Eratosthenes
  Uma solução sem impor um limitante superior para n.
  
• Um exemplo de alocação dinâmica de matrizes bidimensionais.

17/09 (Aula 10)

• Mais um exemplo de alocação dinâmica: vetor de ponteiros para caracteres.
  
• Typedef e structs
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Registros e Structs.

22/09 (Aula 11)

• Structs e apontadores
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Registros e Structs.
  Tente fazer os exercícios que estão propostos nas notas de Registros e Structs do Prof. Paulo Feofiloff.
  
• Veja mais alguns algoritmos interessantes com vetores e recursão nas notas de aulas do Prof. Paulo Feofiloff sobre Vetores.

24/09   Primeira Prova

29/09 (Aula 13)

• Busca, inserção e remoção em vetores
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Vetores.
  
• Listas ligadas (ou listas encadeadas)
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Listas encadeadas.

Outubro

01/10 (Aula 14)

• Mais listas ligadas (ou encadeadas)
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Listas encadeadas.
  Tente fazer os exercícios (1 a 18) que estão propostos nessas notas.

06/10 (Aula 15)

• Argumentos na linha de comando.
  Veja outros exemplos no final das Notas de aulas do Prof. Paulo Feofiloff sobre "Entrada" e "saída".
  
• Algumas explicações sobre o Exercício-Programa 2.
• Problema da intercalação de dois vetores ordenados.

08/10 (Aula 16)

• Mais listas ligadas (ou encadeadas)
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Listas encadeadas.
  Tente fazer os exercícios 19, 25 e 26 que estão propostos nessas notas, e mais o exercício a seguir.
  Exercício: Intercalação de duas listas encadeadas com cabeça, cujas células contém números inteiros em ordem não decrescente.

13/10 (Aula 17)

• Mais listas ligadas (ou encadeadas)
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Listas encadeadas.
  Tente fazer os exercícios 21 a 24 que estão propostos nessas notas.

15/10 (Aula 18)

• Filas (uma implementação em vetor)
  
• Uma aplicação de fila: problema das distâncias
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Filas.
  Tente fazer os exercícios 1 a 5 que estão propostos nestas notas.

20/10 (Aula 19)

• Uma outra implementação de fila em um vetor de modo circular (arquivo fila1.c), e os arquivos fila.h e item.h correspondentes.
  Aqui está o programa completo para o problema das distâncias, utilizando a interface fila.h.

22/10 (Aula 20)

• Uma outra implementação de fila utilizando lista ligada (arquivo fila2.c).
  Resolva o Problema do Labirinto ( exercício 2 do caderno de problemas de Introdução à Computação), utilizando diretamente dois vetores que se comportam como uma fila (armazenando, respectivamnete, os indices de linha e de coluna das posições marcadas), ou chamando as funções que manipulam uma fila.
• Pilhas : uma implementação em vetor (arquivos item.h, pilha.h e pilha.c)).
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Pilhas.

27/10 (Aula 21)

• Uma aplicação de pilha: sequências de parênteses e colchetes bem-formada.
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Pilhas.
  Aqui está o programa completo para verificar se uma sequência de parênteses e colchetes está bem-formada, utilizando a interface pilha.h.
• Mais alguns exercícios com listas ligadas (ou encadeadas).

29/10   Segunda Prova

Novembro

03/11 (Aula 23)

• Uma outra aplicação de pilha: notação polonesa ou posfixa.
  Algoritmo de tradução da notação infixa para a posfixa.
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Pilhas.
  Tente fazer os exercícios que estão propostos nestas notas.

05/11 (Aula 24)

• Mais sobre notação polonesa ou posfixa.
  Algoritmo para calcular o valor de uma expressão posfixa. É o exercício 12 das Notas de aulas do Prof. Paulo Feofiloff sobre Pilhas.
• Problema das n rainhas : determinar uma solução, se existir.

10/11 (Aula 25)

• Algumas explicações sobre o Exercício-Programa 3.

12/11 (Aula 26)

• Mais uma aplicação de pilha: algoritmos "backtracking".
• Problema das n rainhas : determinar uma solução, se existir.
  Aqui está o programa completo.
• Problema das n rainhas : determinar todas as soluções, se existir.
  Aqui está o programa completo. No início desse arquivo estão algumas referências bibliográficas para este problema.
  
• Exerccios:
  
  1. Reescreva as duas soluções do Problema das n rainhas utilizando diretamente as funções que manipulam uma pilha. Ou seja, as funções que estão na interface pilha.h .
     Nesse caso, o tipo Item (de um elemento na pilha) deve ser definido como sendo uma struct com dois campos inteiros: ind_lin e ind_col para armazenar uma posição de uma rainha.
  2. Determinar todas as permutações dos inteiros 1 a n (utilizando o mesmo esquema do problema das rainhas).
  3. Para o Problema do Labirinto ( exercício 2 do caderno de problemas de Introdução à Computação), escreva um programa que determina todos os caminhos possíveis do ratinho até o queijo.
     
  4. Resolva o Problema das Quatro Cores ( exercício 5 do caderno de problemas de Introdução à Computação) de duas formas: a) como está sugerido no seu enunciado e b) utilizando o mesmo esquema do problema das rainhas (para determinar todas as soluções).
• Leitura complementar: Notas de aulas do Prof. Paulo Feofiloff sobre Algoritmos de enumeração.
  Veja os exercícios 6, 7, 9, 10, 12 e 13 dessas notas.

17/11 (Aula 27)

• Busca em vetor ordenado: buscas sequencial e binária
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Busca em vetor ordenado.
  Tente fazer os exercícios que estão propostos nestas notas.
• Algoritmo de ordenação por seleção.
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Ordenação: algoritmos elementares.
  Tente fazer os exercícios propostos nestas notas.

19/11 (Aula 28)

• Algoritmo de ordenação por inserção.
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Ordenação: algoritmos elementares.
  Tente fazer os exercícios propostos nestas notas.
• Mergesort: ordenação por intercalação.
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Mergesort.
  Tente fazer os exercícios propostos nestas notas.
  

24/11 (Aula 29)

• Mergesort: ordenação por intercalação (continuação).
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Mergesort.
  Sobre o problema da intercalação utilizando memória adicional constante : vejam, por exemplo, os dois artigos de B.-C. Huang e M. A. Langston,   um de 1988  e outro de 1990. 
• Heapsort
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Heapsort.
  Tente fazer os exercícios propostos nestas notas.
  

26/11 (Aula 30)

• Heapsort (continuação)
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Heapsort.
• Filas com prioridades (uma aplicação de uso da estrutura heap)
• Quicksort
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Quicksort.
  Tente fazer os exercícios propostos nestas notas.
  

01/12 (Aula 31)

• Quicksort (continuação)
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre Quicksort.
• Estabilidade dos algoritmos de ordenação vistos.
  

03/12 (Aula 32)

• Explicações dobre o EP4.

08/12 (Aula 33)

• Revisão dos algoritmos de ordenação.
• Alguns exercícios.

10/12   Terceira Prova