Princípios de Desenvolvimento de Algoritmos

Matemática Aplicada e Computacional - 2o. Semestre de 2003

Aulas

Agosto

5/8/2003 (Yoshi fora de São Paulo)
7/8/2003 (Yoshi fora de São Paulo)
12/8/2003 Discussão inicial sobre a disciplina. Análise de algoritmos. Crescimento de funções.
14/8/2003 Um exemplo simples de análise de algoritmos: busca sequencial em um vetor. Busca binária. Notação do O-grande.
19/8/2003 Notação assintótica. Manipulação de expressões envolvendo termos O-grandes. Estruturas de dados elementares e bibliotecas.
21/8/2003 Programas implementados em vários arquivos. Noção de biblioteca, interface, e cliente. Registros (structs).
26/8/2003 Ponteiros. Vetores; o crivo de Eratóstenes (prog3.5.c). Alocação dinâmica de memória; versão nova do Eratóstenes: prog3.6.c.
28/8/2003 Alocação dinâmica; dois exemplos: a distribuição binomial (prog3.7.c) e pares de pontos no quadrado unitário distando menos que d (prog3.8.c; exemplo de compilação e execução: prog3.8.out).

Setembro

2/9/2003 (Semana da Pátria)
4/9/2003 (Semana da Pátria)
9/9/2003 (Yoshi fora de São Paulo; Rudini Menezes Sampaio deu aula, pela disciplina de didática)
11/9/2003 (Yoshi fora de São Paulo)
16/9/2003 Listas ligadas, introdução. Josephus: prog3.9.c
18/9/2003 Listas ligadas, continuação.
23/9/2003 Discussão sobre o EP (em especial sobre a 2a. parte do EP). Ordenação de listas ligadas: prog3.11.c.
25/9/2003 Um exercício simples: como inverter a ordem das células em uma lista ligada: prog3.10.c. Manipulação mais abstrata de listas; a interface: list.h, e um cliente: prog3.13.c. Implementação das funções de list.h: prog3.14.c. Um exemplo de execução: prog3.13.RUN.txt.
30/9/2003 Strings. Busca de padrão em texto: prog3.15.c. Exemplo de uso: prog3.15.out. A interface string.h (versão simplificada). Esta página pode ser útil. Parte relevante de Kernighan e Ritchie: Apêndice B3. Ordenação de strings (introdução: representação de um conjunto de palavras).

Outubro

2/10/2003 Ordenação de strings: prog3.17.0.c; exemplo de execução: prog3.17.0.out. Versão com a função qsort(): prog3.17.c. Não discutiremos esta versão com o qsort() agora; entretanto, experimente executar as duas versões do programa prog3.17 para comparar seus desempenhos. Experimentem usar um texto mais longo, por exemplo, do Projeto Gutenberg. (Experimente ordenar as palavras da bíblia: bible12.txt, 5091KB, 823633 "palavras".) Como você faria para ordenar as linhas de um texto, e não as palavras? (Veja uma possibilidade aqui: prog3.17.1.c.)
Em exemplo mais complexo: números de pares de pontos à distância menor que um valor dado (lembre que isso foi resolvido com o programa prog3.8.c). Discussão inicial; descrição informal do algoritmo.
7/10/2003 Um problema geométrico (continuação; uma solução mais eficiente que o programa prog3.8.c): prog3.20.c; execução comparando prog3.8.c e prog3.20.c: prog3.20.out.
9/10/2003 Discussão da função gridinsert() em prog3.20.c. Discussão sobre o EP1.
14/10/2003 Tipos abstratos de dados. Breve introdução. Objetos genéricos simples; exemplos: Item.h e Item.h. Filas generalizadas. Interface para pilhas: STACK.h. Um exemplo de cliente (avaliação de uma expressão pós-fixa): prog4.2.c.
16/10/2003 Prova 1
21/10/2003 Pilhas (continuação). Duas implementações de pilhas: prog4.4.c (vetores) e prog4.5.c (listas ligadas). Compilação e execução: prog4.2.out. Outro exemplo de cliente (conversão de notação infixa para pós-fixa): prog4.3.c. Filas. A interface QUEUE.h. Implementações: prog4.10.c (listas ligadas) e prog4.11.c (vetores). Filas implementadas como um tipo de primeira classe: QUEUE1st.h (interface), prog4.19.c (cliente), prog4.20.c (implementação).
23/10/2003 Renato: discussão detalhada sobre o EP2
28/10/2003 Recesso escolar!
30/10/2003 Dsicussão sobre o EP2. Recursão. Fatorial (não use!): prog5.1.c. A função puzzle() termina para todo valor de seu parâmetro? Algoritmo de Euclides implementado de forma recursiva: prog5.3.c. Avaliação de expressões em notação pré-fixa (introdução).

Novembro

4/11/2003 Avaliação de expressões em notação pré-fixa: prog5.4.c; veja um exemplo de execução. Manipulação de listas com recursão: prog5.5.c. Torres de Hanoi (introdução)
6/11/2003 Torres de Hanoi: prog5.7.c; veja um exemplo de execução. O conceito de divisão e conquista. Quicksort. Implementações iniciais: qsort.c e (versão com pivô aleatório).
11/11/2003 Quicksort. Implementação com um algoritmo de partição mais sofisticado: prog7.1.c. Versão com pilhas (sem recursão): prog7.3.c.
13/11/2003 Quicksort. Implementação com a política "mediana de três" para o pivô, e também usando ordenação por inserção para casos pequenos: prog7.4.c. (Ordenação por inserção: prog6.3.c.) Exercício. Compare o tempo de execução dos vários programas de ordenação dados (execute testes para vetores de tamanhos variados; por exemplo, execute os programas como a seguir: ordenas.txt).
Tabelas de símbolos. Exemplo elementar: Item.h, Item.c; ST.h e um driver.c de exemplo. Implementação com listas ligadas ordenadas: ST.c. Exemplo de execução: exemplo.txt [diretório todo]
18/11/2003 Hashing. Fundamentos sobre tabelas de espalhamento. Aritmética modular. Uma implementação com resolução de colisões por encadeamento: veja este diretório; não deixe de ver o exemplo de execução.
20/11/2003 Ordenação de objetos de tipos diversos: veja este diretório para um exemplo básico. Veja este diretório para um segundo exemplo. Exemplo de compilação e execução. Ordenação de cadeias de caracteres: ex3; compilacao e execução.
25/11/2003 Filas de prioridade, heaps e heapsort. Implementação básica de filas de prioridade. Implementação com heaps. Ordenação baseada no uso de filas de prioridade: prog9.6.c. Heapsort. Versão sem uso explícito de filas: veja este diretório.
27/11/2003 Revisão para prova

Dezembro

2/12/2003 Prova 2
4/12/2003 Prova 3

         August 2003             September 2003            October 2003    
     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa 
                     1  2         1  2  3  4  5  6               1  2  3  4 
      3  4  5  6  7  8  9      7  8  9 10 11 12 13      5  6  7  8  9 10 11 
     10 11 12 13 14 15 16     14 15 16 17 18 19 20     12 13 14 15 16 17 18 
     17 18 19 20 21 22 23     21 22 23 24 25 26 27     19 20 21 22 23 24 25 
     24 25 26 27 28 29 30     28 29 30                 26 27 28 29 30 31 
     31

         November 2003            December 2003             January 2004    
     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa 
                        1         1  2  3  4  5  6                  1  2  3 
      2  3  4  5  6  7  8      7  8  9 10 11 12 13      4  5  6  7  8  9 10 
      9 10 11 12 13 14 15     14 15 16 17 18 19 20     11 12 13 14 15 16 17 
     16 17 18 19 20 21 22     21 22 23 24 25 26 27     18 19 20 21 22 23 24 
     23 24 25 26 27 28 29     28 29 30 31              25 26 27 28 29 30 31 
     30

Página principal de mac122 (MAC - 2o. Semestre de 2003).

Y. Kohayakawa <yoshi@ime.usp.br>

Last modified: Thu Nov 27 19:36:20 BRST 2003