SCC-503(Moacir)

SCC-0503 Algoritmos e Estruturas de Dados II

Aulas: Quartas as 21h e Quintas as 19h - Sala 5-003

Professor: Moacir Ponti Jr (moacir [arroba] icmc . usp . br)

Horário Atendimento: Quintas das 16h as 19h - Sala 3-245

Estagiário PAE: Paulo Henrique Ribeiro Gabriel (phrg [arroba] icmc . usp . br)

Horário Atendimento: Quartas das 17h às 19h - Sala 3-012.

Monitor especial: Daniel Albuquerque (deyniell [arroba] gmail . com)

Proxima aula de exercícios: Quinta dia 19/05 das 17h às 18h30 - Sala 3-102.

Apresentação da Disciplina: programa, avaliação, bibliografia, e outros.

Cronograma

Cronograma, sujeito à alterações, atualizado em: 09/05

Provas:

• 07/04 (P1) (Grafos),
• 26/05 (P2) (Arquivos: fundamentos, sistemas e organização, Armazenamento secundário e Índices),
• 30/06 (P3) (Processamento cossequencial, Árvores-B e Hashing externo).

Material Didático

1. Grafos - introdução
2. Grafos - estruturas de dados --> código: lista de arcos e lista de adjacencia em C
3. Grafos - percursos em grafos, grafos ponderados --> código: lista de adjacencia com ponderacao e percursos
4. Grafos - caminhos e coloracao de grafos
5. Grafos - ordenação topológica
6. Grafos - caminhos mínimos (ver também material sobre fila de prioridades do Prof. Siang Wun Song)
7. Grafos - árvores geradoras mínimas --> código: lista de adjacencia com dijkstra e prim
8. Arquivos: terminologia, histórico e implementação básica --> código: manipulacao em alto nível de arquivos texto e binários em C
9. Armazenamento secundário
10. Sistemas de Arquivos
11. Organização de Arquivos - parte 1 --> código: exemplos de organização de arquivos
12. Organização de Arquivos - parte 2
13. Índices
14. Processamento Co-sequencial
15. Árvores B - parte 1
16. Árvores B - parte 2
17. Hashing Externo - até o slide 30

Apostila

• Criação de Bibliotecas e Makefiles em C/C++

Outros Materiais

• Slides sobre Paradigmas de Projeto de Algoritmos
• Aula de Laboratório - Código-fonte

Trabalhos Práticos

Sistema de submissão

O projeto deverá ser entregue apenas pelo Sistema de Submissão de Programas [1], escolhendo a opção Trabalho1. Não esqueça de testar seu Makefile e de inserir arrobas nas linhas de compilação.

ATENÇÃO: Ressubmeter o Primeiro Trabalho até segunda, dia 11/04.

Trabalhos

1. Grafos - estruturas de dados e percurso‎ (aplicação em redes sem fio) - data de entrega: 31/03 até 11/04 (segunda feira) (Exemplo de caso de teste)
2. Grafos - caminhos mínimos e árvore geradora mínima (CORRIGIDO em 25/04) - data de entrega: de 03/05 até 11/05 (Exemplos de casos de teste) (adicionados mais 2 casos)
3. Arquivos - organização e índices - data de entrega: de 30/05 até 06/06
4. Arquivos - árvores-B - data de entrega: de 27/06 até 03/07 às 23h59

Algoritmos para busca e inserção em Árvores-B: Alg2_BTreeAlgs.txt

na funcao de insercao, RRN_atual é chamado inicialmente como a raiz da árvore, chave_promovida é um parâmetro auxiliar para ser processado no retorno das chamadas recursivas no caso de split, e filho_dir_chave_promovida corresponde ao RRN da página nova criada pelo split, e que será descendente da chave promovida.

Listas de Exercícios

1. Grafos I
2. Grafos II (arquivo corrigido em 7/4)
3. Arquivos: organização e índices
4. Processamento Co-sequencial (Removido o exercício 5)
5. Árvores-B (Removidos os exercícios 15 a 23 e 25)
6. Hashing Externo (Removido do exercício 5 em diante)

Notas

Trabalhos:

1. Notas do Trabalho 1
2. Notas do Trabalho 2
3. Notas do Trabalho 3
4. Notas do Trabalho 4 (Em caso de dúvidas, enviar e-mail para o estagiário PAE até dia 11/07. Incluir o número USP no e-mail.)

Planilha completa:

• Planilha de notas -- atualizada em 25/06 (com a nota da P2) --- revisão das provas no dia 30 (quinta-feira) das 16 as 19h

Bibliografia

• SEDGEWICK, R. Algorithms in C: part 5 -- graph algorithms, 3.ed., Addison-Wesley, 2002.
• FOLK, M.J. File Structures. Addison-Wesley, 1992.
• ZIVIANI, N. Projeto de Algoritmos, 3.ed. Cengage, 2010.
• CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L.; STEIN, C. Algoritmos: Teoria e Prática. Campus. 2002.

Leituras complementares

• FEOFILOFF, P. Algoritmos para Grafos, 2011. Disponível em: [2].