Ciências Moleculares - Computação II

SGB e CWEB

Projetos

• Exercício-programa 1: Ordenação topológica: caso em que não existe uma!
• Exercício-programa 2: Implementação iterativa do algoritmo de geração de permutações (veja all_perms_cweb.w). Estimativa do número de permutações sem ponto fixo (o problema dos chapéus).
• Exercício-programa 3: Implementação do algoritmo de geração de todas as ordenações topológicas de um grafo.
• Exercício-programa 4 (Desafio): Escrever um programa que tem desempenho melhor que o programa football.w do SGB (quando executado sem um parâmetro numérico, i.e., quando o programa football procura sua solução através do algoritmo ganancioso, sem nenhum bracktracking).

Aulas

1. 17/2/98 Introdução; o Stanford GraphBase; o sistema CWEB.
2. 20/2/98 A estrutura de dados para a representação de grafos no SGB. O exemplo QUEEN [queen.w]
3. 24/2/98 [Carnaval!]
4. 27/2/98 A estrutura de dados para a representação de grafos no SGB (continuação); exemplo: montagem da lista dos `arcos reversos' em cada vértice [back_arcs.w | back_arcsC.c]. Geração de grafos usando a função prod() de GB_GATES [prod_graphs.w].
5. 3/3/98 Ordenação topológica (descrição abstrata).
6. 6/3/98 Ordenação topológica (detalhes de implementação; listas lineares, inicialização, inserção, remoção.)
7. 10/3/98 Ordenação topológica---caso em que não existe uma? [top_ord.w]. Exercício-programa 1 [ AMSLaTeX2e | dvi | PostScript]. Uso do CWEB e SGB na rede do CECM.
8. 13/3/98 Programa para geração de grafos aleatórios para o EP1 [rand_graphs.w]. Busca em grafos.
9. 17/3/98 Busca em largura em grafos; implementação (continuação)
10. 20/3/98 Busca em largura em grafos [bfs.w]. Programa para geração de grafos usando GB_WORDS [pick_words.w]. Algoritmo de Dijkstra (introdução)
11. 24/3/98 Algoritmo de Dijkstra, continuação. Implementação [gb_dijk.w]. Filas de prioridade (implementadas como listas circulares duplamente ligadas, com cabeças.)
12. 27/3/98 Módulo GB_DIJK, continuação. Aplicação [miles_span.w]. Pilhas.
13. 31/3/98 Ordenação por pilhas: radix sort (parágrafo 12 de miles_span.w)
14. 2/4/98 Radix sort: o modulo GB_SORT do SGB [gb_sort.w]. Quicksort não-recursivo [qsort_nr.w].
15. 7/4/98 Semana Santa, recesso escolar.
16. 10/4/98 Semana Santa, recesso escolar.
17. 14/4/98 Aula prática; instalação individual do CWEB e SGB.
18. 17/4/98 Quicksort recursivo [qsort_r.w].
19. 24/4/98 [LATIN '98] Aula a ser reposta dia 13/5/98.
20. 28/4/98 [Random Workshop] Aula a ser reposta dia 27/5/98.
21. 5/5/98 Torres de Hanói. Descrição da solução recursiva.
22. 8/5/98 Torres de Hanói, continuação [hanoi_plain.c, hanoi.c].
23. 12/5/98 Torres de Hanói, implementação com listas ligadas [hanoi_linked.c]. Geração de permutações.
24. 13/5/98 Geração de permutações, análise da eficiência do procedimento [all_perms_cweb.w]. Geração dos k-subconjuntos de um conjunto de n elementos [perms_subsets.txt].
25. 15/5/98 Geração de subconjuntos (continuação) [k_subsets.c | k_subsets_i.c | k_subsets2.c | k_subsets2_i.c]. Geração de expressões bem-formadas de parênteses [ebf.c].
26. 19/5/98 Geração de partições de um inteiro [particoes.c, particoes_o.c, particoes_o_k.c].
27. 22/5/98 Subseqüência comum mais longa (descrição abstrata do algoritmo).
28. 26/5/98 Subseqüência comum mais longa [lcs.w]. Discussão sobre geração de permutações e o EP2; implementação em CWEB [all_perms_cweb.w]. Discussão sobre o algoritmo de Knuth, Morris e Pratt para busca de padrões.
29. 27/5/98 Knuth--Morris--Pratt (continuação), implementação [KMP.w | KMP_f.w].
30. 29/5/98 Backtracking e recursão. Algoritmo de geração de todas as ordenações topológicas de um grafo.
31. 2/6/98 Caminhos mais longos em grafos. O programa football.w do SGB.
32. 5/6/98 Aula cancelada.
33. 9/8/98 [From Erdös to Algorithms] Aula cancelada.
34. 16/6/98 O problema das 8 rainhas.
35. 19/6/98 O problema do cavalo.

Last modified: Wed Aug 12 11:23:08 EST 1998