Mudanças entre as edições de "SCC-603 2012"
De CoteiaWiki
(→Avisos) |
|||
| (98 revisões intermediárias por 2 usuários não estão sendo mostradas) | |||
| Linha 1: | Linha 1: | ||
| − | ''' SCC-603 - Algoritmos e Estruturas de Dados II ''' [[http://sistemas2.usp.br/jupiterweb/obterDisciplina?sgldis=SCC0603&nomdis= ementa]] | + | ''' SCC-603 --- Algoritmos e Estruturas de Dados II --- 1º Semestre 2012''' [[http://sistemas2.usp.br/jupiterweb/obterDisciplina?sgldis=SCC0603&nomdis= ementa]] |
'''Professora:''' Rosane Minghim (rminghim at icmc.usp.br) | '''Professora:''' Rosane Minghim (rminghim at icmc.usp.br) | ||
| − | Horário de atendimento: | + | 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 19:00 às 21:00 | + | Horário de atendimento: <span style="color:green">Segunda-feira, 19:00 às 21:00</span> |
| − | Sala: | + | Sala: 3-009 |
| − | |||
| − | |||
| − | |||
| − | |||
| Linha 23: | Linha 19: | ||
== Avisos == | == 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) | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | 03/07 | ||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | === 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 | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # O | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Cronograma e Critérios de Avaliação == | == Cronograma e Critérios de Avaliação == | ||
| − | + | [[Media:(Novo)Cronograma.pdf|Cronograma e Avaliação]] | |
== Material Didático == | == Material Didático == | ||
| − | # [[Media: | + | # [[Media: Grafos1_Rosane_2012.pdf|Arquivo 01 - Introdução a Grafos (Revisado)]] |
| − | # [[Media: | + | # [[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: | + | # [[Media:scc603-2012-04_organizacao_de_arquivos.pdf|Arquivo 04 - Organização de Arquivos (Revisado)]] |
| − | # [[Media:Arquivo 05 - Fundamentos de Arquivos. | + | # [[Media:scc603-2012-05_fundamentos_de_arquivos.pdf|Arquivo 05 - Fundamentos de Arquivos (Revisado)]] |
| − | # [[Media: | + | # [[Media:scc603-2012-fundamentos_exemplos.tar.gz|Fundamentos de Arquivos: Códigos-exemplo (complementar)]] |
| − | # [[Media: | + | # [[Media:scc603-2012-06_armazenamento_secundario-1.pdf|Arquivo 06 - Armazenamento Secundário, parte 1 (Revisado)]] |
| − | # [[Media: | + | # [[Media:scc603-2012-07_armazenamento_secundario-2.pdf|Arquivo 07 - Armazenamento secundário, parte 2 (Revisado)]] |
| − | # [[Media:Arquivo | + | # [[Media:scc603-2012-08_processamento_cosequencial.pdf|Arquivo 08 - Processamento Cosequencial (Revisado)]] |
| − | + | # [[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 207: | Linha 62: | ||
== Trabalhos == | == Trabalhos == | ||
| − | + | 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: | + | # [[Media:scc603_2012-1_lista1.pdf|Lista de Exercícios 1]] |
| − | # [[Media: | + | # [[Media:scc603_2012-1_lista2.pdf|Lista de Exercícios 2]] |
| − | # [[Media: | + | # [[Media:scc603_2012-1_lista3.pdf|Lista de Exercícios 3]] |
| − | # [[Media: | + | # [[Media:scc603_2012-1_lista4.pdf|Lista de Exercícios 4]] |
| − | # [[Media: | + | # [[Media:scc603_2012-1_lista5.pdf|Lista 5 - Processamento Cosequencial]] |
| − | # [[Media: | + | # [[Media:scc603_2012-1_lista6.pdf|Lista 6 - Estruturas de Arquivos]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Notas == | == Notas == | ||
| − | + | # [[Media:(Novo) p2.rar|Notas P2]] | |
| − | + | # [[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. | ||
| + | * 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 |
| − | Link: http:// | + | * 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
Índice
Avisos
- Notas P2
- Notas P3
- Notas e média de prova
- 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
Material Didático
- Arquivo 01 - Introdução a Grafos (Revisado)
- Arquivo 02 - Grafos Algoritmos (Revisado)
- Grafos - Caminhos (complementar)
- Arquivo 03 - Grafos Caminhos Mínimos
- Arquivo 04 - Organização de Arquivos (Revisado)
- Arquivo 05 - Fundamentos de Arquivos (Revisado)
- Fundamentos de Arquivos: Códigos-exemplo (complementar)
- Arquivo 06 - Armazenamento Secundário, parte 1 (Revisado)
- Arquivo 07 - Armazenamento secundário, parte 2 (Revisado)
- Arquivo 08 - Processamento Cosequencial (Revisado)
- Arquivo 09 - Índices - Cap. 5
- Arquivo 11 - Árvores B, parte 1
- Arquivo 12 - Árvores B, parte 2
- Arquivo 13 - Árvores B, parte 3
- Arquivo 14 - Árvores B, parte 4
- Arquivo 15 - Árvores B+
- 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.
- Cuidado com a memória!
- Trabalho 3 - Índices
- Trabalho 4 - Árvore B
Exercícios de Aula
Listas de Exercícios
- Lista de Exercícios 1
- Lista de Exercícios 2
- Lista de Exercícios 3
- Lista de Exercícios 4
- Lista 5 - Processamento Cosequencial
- Lista 6 - Estruturas de Arquivos
Notas
- 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.
- Autor: William Douglas.
- 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/
