Mudanças entre as edições de "SCC-503(Moacir)"

De CoteiaWiki
(→‎Material Didático)
(→‎RECUPERACAO)
 
(46 revisões intermediárias por 2 usuários não estão sendo mostradas)
Linha 4: Linha 4:
  
 
:'''Professor''': Moacir Ponti Jr (moacir [''arroba''] icmc . usp . br)
 
:'''Professor''': Moacir Ponti Jr (moacir [''arroba''] icmc . usp . br)
−
:Horário Atendimento: Quintas das 16h as 19h - Sala 4-117
+
:Horário Atendimento: Quintas das 16h as 19h - Sala 3-245
  
 
:'''Estagiário PAE''': Paulo Henrique Ribeiro Gabriel (phrg [''arroba''] icmc . usp . br)
 
:'''Estagiário PAE''': Paulo Henrique Ribeiro Gabriel (phrg [''arroba''] icmc . usp . br)
Linha 11: Linha 11:
 
:'''Monitor especial''': Daniel Albuquerque (deyniell [''arroba''] gmail . com)
 
:'''Monitor especial''': Daniel Albuquerque (deyniell [''arroba''] gmail . com)
  
−
:Proxima aula de exercícios: '''Quinta dia 17/03 das 17h às 18h30 - Sala 3-102'''.
+
:Proxima aula de exercícios: '''Quinta dia 19/05 das 17h às 18h30 - Sala 3-102'''.  
−
::: será feita revisão sobre '''listas e arvores''' e um exercício usando busca em grafos.
 
  
 
: [[Media:alg2_00.Apresentacao.pdf|Apresentação da Disciplina]]: programa, avaliação, bibliografia, e outros.
 
: [[Media:alg2_00.Apresentacao.pdf|Apresentação da Disciplina]]: programa, avaliação, bibliografia, e outros.
Linha 21: Linha 20:
 
[[Media:Cron_scc0503_2011-1.pdf‎|Cronograma]], sujeito à alterações, atualizado em: '''09/05'''
 
[[Media:Cron_scc0503_2011-1.pdf‎|Cronograma]], sujeito à alterações, atualizado em: '''09/05'''
  
−
:'''Provas:''' 07/04 (P1), 25/05 (P2) e 23/06 (P3)
+
'''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 ==
 
== Material Didático ==
Linha 35: Linha 37:
 
# [[Media:alg2_09.ArmazenamentoSecundario.pdf|Armazenamento secundário]]
 
# [[Media:alg2_09.ArmazenamentoSecundario.pdf|Armazenamento secundário]]
 
# [[Media:alg2_10.SistemasdeArquivos.pdf|Sistemas de Arquivos]]
 
# [[Media:alg2_10.SistemasdeArquivos.pdf|Sistemas de Arquivos]]
−
# [[Media:alg2_11.OrganizacaodeArquivos_parte1.pdf|Organização de Arquivos - parte 1]]
+
# [[Media:alg2_11.OrganizacaodeArquivos_parte1.pdf|Organização de Arquivos - parte 1]] --> [[Media:FileOrg.tar.gz|código: exemplos de organização de arquivos]]
 
# [[Media:alg2_12.OrganizacaodeArquivos_parte2.pdf|Organização de Arquivos - parte 2]]
 
# [[Media:alg2_12.OrganizacaodeArquivos_parte2.pdf|Organização de Arquivos - parte 2]]
 
# [[Media:alg2_13.Indices.pdf|Índices]]
 
# [[Media:alg2_13.Indices.pdf|Índices]]
 
# [[Media:alg2_14.ProcessamentoCossequencia.pdf|Processamento Co-sequencial]]
 
# [[Media:alg2_14.ProcessamentoCossequencia.pdf|Processamento Co-sequencial]]
−
# [[Media:alg2_15.Arvores_B.pdf|Árvores B]]
+
# [[Media:alg2_15.Arvores_B_parte1.pdf|Árvores B - parte 1]]
−
# [[Media:alg2_16.Arvores_B+.pdf|Árvores B+]]
+
# [[Media:alg2_16.Arvores_B_parte2.pdf|Árvores B - parte 2]]
−
# [[Media:alg2_17.Hashing_Externo.pdf|Hashing Externo]]
+
# [[Media:alg2_17.Hashing_Externo.pdf|Hashing Externo]] - até o slide 30
  
  
Linha 51: Linha 53:
  
 
* [[Media:ParadigmasProjetoAlgoritmos.pdf|Slides sobre Paradigmas de Projeto de Algoritmos]]
 
* [[Media:ParadigmasProjetoAlgoritmos.pdf|Slides sobre Paradigmas de Projeto de Algoritmos]]
 +
* [[Media:lab20110615.tar.gz|Aula de Laboratório - Código-fonte]]
  
 
== Trabalhos Práticos ==
 
== Trabalhos Práticos ==
Linha 62: Linha 65:
  
 
=== Trabalhos ===
 
=== Trabalhos ===
−
# [[Media:Alg2_Trabalho1.pdf‎|Grafos - estruturas de dados e percurso‎]] (aplicação em redes sem fio) - data de entrega: 31/03 até '''11/04''' (segunda feira) ([[Media:t1caso00.tar.gz|Exemplo de caso de teste]])
+
# [[Media:Alg2_Trabalho1.pdf‎|Grafos - estruturas de dados e percurso‎]] (aplicação em redes sem fio) - data de entrega: 31/03 até 11/04 (segunda feira) ([[Media:t1caso00.tar.gz|Exemplo de caso de teste]])
−
# [[Media:Alg2_Trabalho2.pdf‎|Grafos - caminhos mínimos e árvore geradora mínima]] ('''CORRIGIDO em 25/04''') - data de entrega: de 03/05 até '''11/05''' ([[Media:t2casos.tar.gz|Exemplos de casos de teste]]) '''(adicionados mais 2 caso)'''
+
# [[Media:Alg2_Trabalho2.pdf‎|Grafos - caminhos mínimos e árvore geradora mínima]] (CORRIGIDO em 25/04) - data de entrega: de 03/05 até 11/05 ([[Media:t2casos.tar.gz|Exemplos de casos de teste]]) (adicionados mais 2 casos)
−
* '''Observação 1:''' Todos os grafos serão conexos e os vértices começam em 1.
+
# [[Media:Alg2_Trabalho3.pdf‎|Arquivos - organização e índices]] - data de entrega: de 30/05 até 06/06
−
* '''Observação 2:''' Na construção da árvore geradora mínima, considere como vértice inicial o vértice 1.
+
# [[Media:Alg2_Trabalho4.pdf‎|Arquivos - árvores-B]] - data de entrega: de 27/06 até '''03/07''' às '''23h59'''
−
* '''Observação 3:''' Esclarecimento sobre a resolução da primeira parte do problema [[Media:esclarecimento.txt|aqui]].
+
::Algoritmos para busca e inserção em Árvores-B: [[Media:Alg2_BTreeAlgs.txt|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 ==
 
== Listas de Exercícios ==
Linha 72: Linha 76:
 
# [[Media:alg2_lista1.pdf|Grafos I]]
 
# [[Media:alg2_lista1.pdf|Grafos I]]
 
# [[Media:alg2_lista2-1.pdf|Grafos II]] (arquivo corrigido em 7/4)
 
# [[Media:alg2_lista2-1.pdf|Grafos II]] (arquivo corrigido em 7/4)
−
# [[Media:alg2_lista3.pdf|Arquivos]]
+
# [[Media:alg2_lista3.pdf|Arquivos: organização e índices]]
−
# [[Media:alg2_lista4.pdf|Processamento Co-sequencial e Ordenação Externa]]
+
# [[Media:alg2_lista4.pdf|Processamento Co-sequencial]] (Removido o exercício 5)
−
# [[Media:alg2_lista5.pdf|Árvores-B]]
+
# [[Media:alg2_lista5.pdf|Árvores-B]] (Removidos os exercícios 15 a 23 e 25)
 +
# [[Media:alg2_lista6.pdf|Hashing Externo]] (Removido do exercício 5 em diante)
  
 
== Notas ==
 
== Notas ==
  
 
Trabalhos:
 
Trabalhos:
−
# [[Media:alg2-notas_t1.pdf|Notas do Trabalho 1]] -- Revisão de notas com o estagiário PAE no dia 27/04, no horário de atendimento, na Sala 6-206 do CISC, ou por e-mail até dia 29/04 (informar nro. USP no e-mail). Os alunos cujo campo "Nota Final" está em branco devem, obrigatoriamente, procurar os estagiário PAE, para validar a nota.
+
# [[Media:alg2-notas_t1.pdf|Notas do Trabalho 1]]
 +
# [[Media:alg2-notas_t2.pdf|Notas do Trabalho 2]]
 +
# [[Media:alg2-notas_t3.pdf|Notas do Trabalho 3]]
 +
# [[Media:alg2-notas_t4.pdf|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 completa:
−
* [[Media:alg2-notas.pdf|Planilha de notas]] -- atualizada em 29/04 (com a nota da P1) --- revisão das provas no dia 05/05 (quinta-feira) das 17h as 19h
+
* [[Media:alg2-notas.pdf|Planilha de notas]] -- atualizada em ''11/06'' (com a nota da P3 e do T4 e a nota final)
 +
 
 +
Revisão da P3: terça-feira, dia 12 das 17h as 18h30
 +
 
 +
=== RECUPERACAO ===
 +
Data: 2 de Agosto, Terça-feira
 +
 
 +
Horário: das 17h00 as 19h00
 +
 
 +
Sala: 3-012
  
 
== Bibliografia ==
 
== Bibliografia ==

Edição atual tal como às 18h13min de 28 de julho de 2011

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

Outros Materiais

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:

Revisão da P3: terça-feira, dia 12 das 17h as 18h30

RECUPERACAO

Data: 2 de Agosto, Terça-feira

Horário: das 17h00 as 19h00

Sala: 3-012

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].
Disponível em "http://wiki.icmc.usp.br/index.php?title=SCC-503(Moacir)&oldid=18521"