Mudanças entre as edições de "SCC-603 2012"

De CoteiaWiki
(→‎Sugestões de leitura)
(→‎Avisos)
 
(89 revisões intermediárias por 2 usuários não estão sendo mostradas)
Linha 4: Linha 4:
 
'''Professora:''' Rosane Minghim (rminghim at icmc.usp.br)
 
'''Professora:''' Rosane Minghim (rminghim at icmc.usp.br)
  
−
Horário de atendimento: <span style="color:red">Quartas-feiras 15:30 às 18:30</span>
+
Horário de atendimento: <span style="color:green">Sextas-feiras 15:00 às 18:00</span>
  
 
Sala: 4-206
 
Sala: 4-206
Linha 11: Linha 11:
 
'''Assistente PAE:''' Rafael Messias Martins (rmartins at icmc.usp.br)
 
'''Assistente PAE:''' Rafael Messias Martins (rmartins at icmc.usp.br)
  
−
Horário de atendimento: Segunda-feira 14:00 às 16:00
+
Horário de atendimento: <span style="color:green">Segunda-feira, 19:00 às 21:00</span>
 +
 
 +
Sala: 3-009
  
−
Sala: 6-208
 
  
  
 
== Avisos ==
 
== Avisos ==
  
−
Ainda não há avisos.
+
# [[Media:(Novo) p2.rar|Notas P2]]
 +
# [[Media:(Novo) p3a.rar|Notas P3]]
 +
# [[Media:(Novo) provas_B.rar|Notas e média de prova]]
 +
# [[Media:(Novo) provas_final.rar|Notas atualizadas, adicionais, média e frequência, mesma senha do arquivo anterior]]
 +
# Revisão de provas 2 e 3 dia 03/07, 10-12, sala 3-102 (ICMC - CAMPUS I)
 +
# Revisão pode ser feita em outro dia também, até no início do próximo semestre.
 +
# rec de prova na primeira semana de aula do próximo semestre. Data, hora (período noturno) e local a serem divulgados aqui.
 +
# o aluno deve passar na rec de trabalho para fazer a rec de prova, no caso de quem ficou de rec nas duas modalidades (prova e trabalho)
 +
 
 +
=== Sobre a Rec. dos Trabalhos (RT) ===
 +
 
 +
# A média dos trabalhos (MT) será calculada sobre os 3 trabalhos com maior nota (o trabalho de menor nota será descartado).
 +
# Poderá fazer a RT quem ficar com 3.0 <= MT < 5.0
 +
# Durante a RT será liberado o acesso para cada trabalho x cuja nota NTx < 5.0
 +
# O objetivo da RT é conseguir nota >= 5.0 para cada NTx
 +
## Caso os 4 trabalhos tenham NTx < 5.0, será apenas necessário resolver 3
  
 
== Cronograma e Critérios de Avaliação ==
 
== Cronograma e Critérios de Avaliação ==
  
−
Não disponível no momento.
+
[[Media:(Novo)Cronograma.pdf|Cronograma e Avaliação]]
  
 
== Material Didático ==
 
== Material Didático ==
  
−
# [[Media:(Novo) Arquivo 01 - Introdução a Grafos.pdf|Arquivo 01 - Introdução a Grafos]]
+
# [[Media: Grafos1_Rosane_2012.pdf|Arquivo 01 - Introdução a Grafos (Revisado)]]
−
# [[Media:(Novo) Grafos2_Rosane_2011.pdf|Arquivo 02 - Grafos Algoritmos]]
+
# [[Media: Grafos2_Rosane_2012.pdf|Arquivo 02 - Grafos Algoritmos (Revisado)]]
 +
# [[Media: Grafos_Caminhos_Graça_Rosane_2012.pdf|Grafos - Caminhos (complementar)]]
 
# [[Media:(Novo) floyd-warshall.pdf|Arquivo 03 - Grafos Caminhos Mínimos]]
 
# [[Media:(Novo) floyd-warshall.pdf|Arquivo 03 - Grafos Caminhos Mínimos]]
−
# [[Media:Arquivo_04_-_Organização_de_Arquivos_-_Folk_Cap._4.pdf‎|Arquivo 04 - Organização de Arquivos - Folk Cap. 4]]
+
# [[Media:scc603-2012-04_organizacao_de_arquivos.pdf‎|Arquivo 04 - Organização de Arquivos (Revisado)]]
−
# [[Media:Arquivo 05 - Fundamentos de Arquivos.pdf‎|Arquivo 05 - Fundamentos de Arquivos]]
+
# [[Media:scc603-2012-05_fundamentos_de_arquivos.pdf‎|Arquivo 05 - Fundamentos de Arquivos (Revisado)]]
−
# [[Media:Arquivo 06 - Armazenamento Secundário, parte 1 (Cap. 3).pdf‎|Arquivo 06 - Armazenamento Secundário, parte 1 (Cap. 3)]]
+
# [[Media:scc603-2012-fundamentos_exemplos.tar.gz‎|Fundamentos de Arquivos: Códigos-exemplo (complementar)]]
−
# [[Media:Arquivo 07 - Armazenamento secundário, parte 2 (Cap. 3).pdf‎|Arquivo 07 - Armazenamento secundário, parte 2 (Cap. 3)]]
+
# [[Media:scc603-2012-06_armazenamento_secundario-1.pdf‎‎|Arquivo 06 - Armazenamento Secundário, parte 1 (Revisado)]]
−
# [[Media:Arquivo 08 - Índices - Cap. 5.pdf‎|Arquivo 08 - Índices - Cap. 5]]
+
# [[Media:scc603-2012-07_armazenamento_secundario-2.pdf‎|Arquivo 07 - Armazenamento secundário, parte 2 (Revisado)]]
−
# [[Media:Arquivo 09 - Processamento Cosequencial.pdf‎|Arquivo 09 - Processamento Cosequencial]]
+
# [[Media:scc603-2012-08_processamento_cosequencial.pdf‎‎|Arquivo 08 - Processamento Cosequencial (Revisado)]]
−
# [[Media:Arquivo 10 - Temas para a Prova 2.pdf‎|Arquivo 10 - Temas para a Prova 2]]
+
# [[Media:Arquivo 08 - Índices - Cap. 5.pdf‎|Arquivo 09 - Índices - Cap. 5]]
 
# [[Media:Arquivo 11 - Árvores B, parte 1.pdf‎|Arquivo 11 - Árvores B, parte 1]]
 
# [[Media:Arquivo 11 - Árvores B, parte 1.pdf‎|Arquivo 11 - Árvores B, parte 1]]
 
# [[Media:Arquivo 12 - Árvores B, parte 2.pdf‎|Arquivo 12 - Árvores B, parte 2]]
 
# [[Media:Arquivo 12 - Árvores B, parte 2.pdf‎|Arquivo 12 - Árvores B, parte 2]]
Linha 45: Linha 62:
 
== Trabalhos ==
 
== Trabalhos ==
  
−
O envio dos trabalhos será feito pelo [http://lcadfs2.lcad.icmc.usp.br/cgi-bin/fernando/sqtpm.pl  SQTPM].
+
O envio dos trabalhos será feito pelo [http://143.107.232.141/cgi-bin/rmartins/sqtpm.pl  SQTPM].
 +
 
 +
* [[Media: scc0603_2012_trab0.pdf|Trabalho 0 - Demonstração do SQTPM]]
 +
* [[Media: scc0603_2012_trab1_a.pdf|Trabalho 1 - Menores Caminhos (Atualizado)]]
 +
** Prazo: 15/05 (Podem continuar submetendo; desconto de 0,5 ponto por dia)
 +
* [[Media: scc0603_2012_trab2_c.pdf|Trabalho 2 - Betweenness (Atualizado)]]
 +
** Prazo: 21/05
 +
* Dicas:
 +
** Cuidado com a memória!
 +
*** Não dupliquem vértices com dados, por exemplo o nome. Cada vértice só deve ter UMA cópia na memória a qualquer momento. Sempre que tiverem que referenciar esse vértice (numa aresta, por ex., ou numa lista de predecessores), usem um ponteiro ou um "id" inteiro, por ex.
 +
*** Cuidado com alocação dinâmica; não se percam pelo mar de ponteiros que vocês mesmo criam. Gerenciem cada ponteiro com cuidado.
 +
*** Lembrem-se: quando vocês tem informação prévia do tamanho da lista (e esse tamanho não muda), um array é muito melhor que uma lista encadeada. Ou seja: tendo o número N de vértices, porque não alocar um array de N posições e atribuir um "id" de 0 a N-1 para cada vértice? Assim vocês poderão acessar qualquer vértice em tempo O(1) com "array[id]".
 +
** Cuidado com o tempo!
 +
*** Evitem buscas completas no grafo se não for estritamente necessário. Se você precisa fazer uma busca linear no grafo toda vez que um vértice é referenciado, algo está errado no seu algoritmo (ver dica anterior sobre o array).
 +
*** Não usem campos como nome (string) para o "id" do vértice. Operações com strings não são eficientes e são complicadas de usar em C, devido à alocação dinâmica. Evitem ao máximo manipulação de strings nesse contexto.
 +
* [[Media: scc0603_2012_trab3a.pdf|Trabalho 3 - Índices]]
 +
* [[Media: scc0603_2012_trab4a.pdf|Trabalho 4 - Árvore B]]
 +
 
 +
== Exercícios de Aula ==
 +
 
 +
# [[Media: SCC603_2012-1_ex1.pdf|Exercício 1 (05/03/12)]]
 +
 
 +
# [[Media: SCC603_2012-1_ex2.pdf|Exercício 2 (20/03/12)]]
  
 
== Listas de Exercícios ==
 
== Listas de Exercícios ==
  
−
# [[Media:Lista 1 - Rosane 2011.pdf‎|Lista 1 - Conceitos sobre Grafos]]
+
# [[Media:scc603_2012-1_lista1.pdf|Lista de Exercícios 1]]
−
# [[Media:Lista 2 - Problemas utilizando Grafos.pdf|Lista 2 - Problemas utilizando Grafos]]
+
# [[Media:scc603_2012-1_lista2.pdf|Lista de Exercícios 2]]
−
# [[Media:Lista 3 - Algoritmos para manipulação de grafos.pdf|Lista 3 - Algoritmos para manipulação de grafos]]
+
# [[Media:scc603_2012-1_lista3.pdf|Lista de Exercícios 3]]
−
# [[Media:Lista 4 - Processamento Cosequencial.pdf|Lista 4 - Processamento Cosequencial]]
+
# [[Media:scc603_2012-1_lista4.pdf|Lista de Exercícios 4]]
−
# [[Media: ExerccicioArquivoIndice_1.pdf |Lista 5 - Arquivos/Índices, exercícios para a aula de "segunda-feira"]]
+
# [[Media:scc603_2012-1_lista5.pdf|Lista 5 - Processamento Cosequencial]]
−
# [[Media:Lista 6 - Estrutura de Arquivos.pdf|Lista 6 - Estrutura de Arquivos]]
+
# [[Media:scc603_2012-1_lista6.pdf|Lista 6 - Estruturas de Arquivos]]
−
# [[Media:Lista 7 - Fundamentos de Arquivos.pdf|Lista 7 - Fundamentos de Arquivos]]
 
−
# [[Media:Lista 8 - Armazenamento Secundário.pdf|Lista 8 - Armazenamento Secundário]]
 
−
# [[Media:Lista 9 - Índices.pdf|Lista 9 - Índices]]
 
−
# [[Media:Lista 10 - Árvores B.pdf|Lista 10 - Árvores B]]
 
−
# [[Media:Lista 11 - Hashing.pdf|Lista 11 - Hashing]]
 
−
# [[Media:Lista 12 - Arquivo, Índice.pdf|Lista 12 - Arquivo, Índice]]
 
−
 
 
−
''' Atenção: pode não representar a matéria toda - estude pelos livros...'''
 
  
 
== Notas ==
 
== Notas ==
−
 
+
# [[Media:(Novo) p2.rar|Notas P2]]
−
Ainda não foram divulgadas.
+
# [[Media:(Novo) p3a.rar|Notas P3]]
 +
# [[Media:(Novo) provas_B.rar|Notas e média de prova]]
 +
# [[Media:Scc603_2012_notas_trabalhos.pdf|Notas dos Trabalhos]]
 +
* Atenção: no Trabalho 3 houve diversos problemas com trabalhos copiados. Para mais detalhes procure o estagiário PAE.
  
 
== Sugestões de leitura ==
 
== Sugestões de leitura ==
  
 
Livro: Como passar em provas e concursos.
 
Livro: Como passar em provas e concursos.
−
*Autor: William Douglas.
+
* Autor: William Douglas.
−
Link: http://bit.ly/y98WhW
+
* Link: http://bit.ly/y98WhW
 +
 
 +
Livro: Data Structures and Algorithms in C++/Java
 +
* Autores: M. T. Goodrich e R. Tamassia
 +
* Link: http://ww0.java4.datastructures.net/
 +
 
 +
Livro: Projeto de Algoritmos
 +
* Autor: N. Ziviani
 +
* Link: http://www.dcc.ufmg.br/algoritmos/
 +
 
 +
Livro: Introduction to Algorithms
 +
* Autores: T. H. Cormen, C. E. Leiserson e R. L. Rivest
 +
* Link: http://mitpress.mit.edu/algorithms/

Edição atual tal como às 15h29min de 6 de julho de 2012

SCC-603 --- Algoritmos e Estruturas de Dados II --- 1º Semestre 2012 [ementa]


Professora: Rosane Minghim (rminghim at icmc.usp.br)

Horário de atendimento: Sextas-feiras 15:00 às 18:00

Sala: 4-206


Assistente PAE: Rafael Messias Martins (rmartins at icmc.usp.br)

Horário de atendimento: Segunda-feira, 19:00 às 21:00

Sala: 3-009


Avisos

  1. Notas P2
  2. Notas P3
  3. Notas e média de prova
  4. Notas atualizadas, adicionais, média e frequência, mesma senha do arquivo anterior
  5. Revisão de provas 2 e 3 dia 03/07, 10-12, sala 3-102 (ICMC - CAMPUS I)
  6. Revisão pode ser feita em outro dia também, até no início do próximo semestre.
  7. rec de prova na primeira semana de aula do próximo semestre. Data, hora (período noturno) e local a serem divulgados aqui.
  8. o aluno deve passar na rec de trabalho para fazer a rec de prova, no caso de quem ficou de rec nas duas modalidades (prova e trabalho)

Sobre a Rec. dos Trabalhos (RT)

  1. A média dos trabalhos (MT) será calculada sobre os 3 trabalhos com maior nota (o trabalho de menor nota será descartado).
  2. Poderá fazer a RT quem ficar com 3.0 <= MT < 5.0
  3. Durante a RT será liberado o acesso para cada trabalho x cuja nota NTx < 5.0
  4. O objetivo da RT é conseguir nota >= 5.0 para cada NTx
    1. Caso os 4 trabalhos tenham NTx < 5.0, será apenas necessário resolver 3

Cronograma e Critérios de Avaliação

Cronograma e Avaliação

Material Didático

  1. Arquivo 01 - Introdução a Grafos (Revisado)
  2. Arquivo 02 - Grafos Algoritmos (Revisado)
  3. Grafos - Caminhos (complementar)
  4. Arquivo 03 - Grafos Caminhos Mínimos
  5. Arquivo 04 - Organização de Arquivos (Revisado)
  6. Arquivo 05 - Fundamentos de Arquivos (Revisado)
  7. Fundamentos de Arquivos: Códigos-exemplo (complementar)
  8. Arquivo 06 - Armazenamento Secundário, parte 1 (Revisado)
  9. Arquivo 07 - Armazenamento secundário, parte 2 (Revisado)
  10. Arquivo 08 - Processamento Cosequencial (Revisado)
  11. Arquivo 09 - Índices - Cap. 5
  12. Arquivo 11 - Árvores B, parte 1
  13. Arquivo 12 - Árvores B, parte 2
  14. Arquivo 13 - Árvores B, parte 3
  15. Arquivo 14 - Árvores B, parte 4
  16. Arquivo 15 - Árvores B+
  17. Hashing

Trabalhos

O envio dos trabalhos será feito pelo SQTPM.

  • Trabalho 0 - Demonstração do SQTPM
  • Trabalho 1 - Menores Caminhos (Atualizado)
    • Prazo: 15/05 (Podem continuar submetendo; desconto de 0,5 ponto por dia)
  • Trabalho 2 - Betweenness (Atualizado)
    • Prazo: 21/05
  • Dicas:
    • Cuidado com a memória!
      • Não dupliquem vértices com dados, por exemplo o nome. Cada vértice só deve ter UMA cópia na memória a qualquer momento. Sempre que tiverem que referenciar esse vértice (numa aresta, por ex., ou numa lista de predecessores), usem um ponteiro ou um "id" inteiro, por ex.
      • Cuidado com alocação dinâmica; não se percam pelo mar de ponteiros que vocês mesmo criam. Gerenciem cada ponteiro com cuidado.
      • Lembrem-se: quando vocês tem informação prévia do tamanho da lista (e esse tamanho não muda), um array é muito melhor que uma lista encadeada. Ou seja: tendo o número N de vértices, porque não alocar um array de N posições e atribuir um "id" de 0 a N-1 para cada vértice? Assim vocês poderão acessar qualquer vértice em tempo O(1) com "array[id]".
    • Cuidado com o tempo!
      • Evitem buscas completas no grafo se não for estritamente necessário. Se você precisa fazer uma busca linear no grafo toda vez que um vértice é referenciado, algo está errado no seu algoritmo (ver dica anterior sobre o array).
      • Não usem campos como nome (string) para o "id" do vértice. Operações com strings não são eficientes e são complicadas de usar em C, devido à alocação dinâmica. Evitem ao máximo manipulação de strings nesse contexto.
  • Trabalho 3 - Índices
  • Trabalho 4 - Árvore B

Exercícios de Aula

  1. Exercício 1 (05/03/12)
  1. Exercício 2 (20/03/12)

Listas de Exercícios

  1. Lista de Exercícios 1
  2. Lista de Exercícios 2
  3. Lista de Exercícios 3
  4. Lista de Exercícios 4
  5. Lista 5 - Processamento Cosequencial
  6. Lista 6 - Estruturas de Arquivos

Notas

  1. Notas P2
  2. Notas P3
  3. Notas e média de prova
  4. Notas dos Trabalhos
  • Atenção: no Trabalho 3 houve diversos problemas com trabalhos copiados. Para mais detalhes procure o estagiário PAE.

Sugestões de leitura

Livro: Como passar em provas e concursos.

Livro: Data Structures and Algorithms in C++/Java

Livro: Projeto de Algoritmos

Livro: Introduction to Algorithms

Disponível em "http://wiki.icmc.usp.br/index.php?title=SCC-603_2012&oldid=30388"