Computação II
Ciências Moleculares - 1o. Semestre de 2002
Aulas
- 1/3/2002 Algoritmos elementares de ordenação (continuação).
- 5/3/2002 (Yoshi fora de São Paulo)
- 8/3/2002 (Yoshi fora de São Paulo)
- 12/3/2002 (Yoshi fora de São Paulo)
- 15/3/2002 Mergesort: prog8.4.c. Execução do
mergesort: mergesort.txt.
- 19/3/2002 Análise de complexidade dos algoritmos elementares de
ordenação (estudo do número de comparações). Análise do número de
comparações no mergesort (introdução).
- 22/3/2002 Análise do número de comparações no mergesort (continuação).
- 25/3/2002 Semana Santa, recesso escolar
- 29/3/2002 Semana Santa, recesso escolar
- 3/5/2002 LSD Radix sort: prog10.4.c, exemplo de execução; note que o
prog10.4 é um pouco mais rápido que o quicksort para entradas grandes
(inteiros aleatórios de 32 bits) (um exercício interessante é fazer um
comparação empírica mais detalhada da eficiência do quicksort e do LSD
radixsort). Versão do LSD radixsort para listas ligadas: veja este diretório. Escrevi o programa neste diretório
usando o sistema CWEB, de Don Knuth; para maiores
detalhes, visite as páginas sobre o CWEB e o SGB, o
Stanford GraphBase.
- 7/5/2002 Tabela de símbolos. Veja este
diretório para um exemplo completo (esta implementação mantém os objetos
da tabela em uma lista ligada ordenada; não deixe de ver o exemplo de execução). Outras
implementações de tabelas de símbolos. Como vetores característicos: prog12.3.c; como vetores mantendo os
objetos ordenados: prog12.4.c.
- 10/5/2002 Implementações elementares de tabelas de símbolos
(continuação).
- 14/5/2002 Busca binária. Árvores binárias. Programas de
pesquisa de nós de árvores: prog5.14.c, prog5.15.c, e prog5.16.c. Alguns outros programas de
manipulação de árvores: prog5.17.c, e prog5.18.c.
- 17/5/2002 Tabelas de símbolos implementadas com árvores de busca
binária: veja este diretório.
Internal/external path length. Relação entre IPL, EPL, altura e
desempenho do algoritmo de busca.
- 21/5/2002 Algoritmos de rotação de ABs: prog12.11.c. Inserção na raiz em uma ABB: prog12.12.c (desafio: escreva uma versão
não-recursiva deste algoritmo de inserção). Seleção em uma ABB: pog12.13.c.
- 24/5/2002 Partição de uma ABB: prog12.14.c. Remoção de uma ABB: prog12.15.c.
Balanceamento explícito de uma ABB: prog13.1.c.
ABBs construídas com inserções aleatórias; rotina de inserção: prog13.2.c; rotina de remoção: prog13.4.c.
A biblioteca libavl
(veja a documentação e
também um texto mais extenso disponível na página da biblioteca, em
vários formatos).
- 28/5/2002 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.
- 31/5/2002 Recesso escolar
- 4/6/2002 (Yoshi fora de São Paulo)
- 7/6/2002 Continuação de hashing (implementação
de tabelas de hashing com resolução de colisões por encadeamento).
Resolução de colisões por probing linear: veja este diretório
- 11/6/2002 Continuação de hashing (probing linear; comentários sobre
hashing dduplo e hashing dinâmico).
- 14/6/2002 Introdução aos conceitos básicos de grafos. Representação de
grafos: matrizes de adjacência e listas de adjacência. Implementações: g1 (matrizes de adjacência) e g2
(listas de adjacência).
- 18/6/2002 Discussão sobre o EP3. Representações de grafos
(continuação).
- 21/6/2002 Teste de acessibilidade: g3. Existência
de caminho hamiltoniano: g4. Teste de conexidade: g5 (busca em profundidade). Teste de conexidade com busca
em largura (2 versões): g6 e g7.
- 25/6/2002 (Yoshi fora de São Paulo)
- 28/6/2002 (Yoshi fora de São Paulo) Data de entrega do EP3.
February 2002 March 2002 April 2002
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 1 2 3 4 5 6
3 4 5 6 7 8 9 3 4 5 6 7 8 9 7 8 9 10 11 12 13
10 11 12 13 14 15 16 10 11 12 13 14 15 16 14 15 16 17 18 19 20
17 18 19 20 21 22 23 17 18 19 20 21 22 23 21 22 23 24 25 26 27
24 25 26 27 28 24 25 26 27 28 29 30 28 29 30
31
May 2002 June 2002 July 2002
Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa
1 2 3 4 1 1 2 3 4 5 6
5 6 7 8 9 10 11 2 3 4 5 6 7 8 7 8 9 10 11 12 13
12 13 14 15 16 17 18 9 10 11 12 13 14 15 14 15 16 17 18 19 20
19 20 21 22 23 24 25 16 17 18 19 20 21 22 21 22 23 24 25 26 27
26 27 28 29 30 31 23 24 25 26 27 28 29 28 29 30 31
30
Página principal de Computação II (CCM - 1o. Semestre de 2002).
Y. Kohayakawa
<yoshi@ime.usp.br>
Last modified: Fri Jun 21 12:14:06 BRT 2002