Estrutura de Dados II
Horário
Terça e Quinta, às 18:30 @ LABCOMP-03
Slack
Todo material de aula será postado no Slack. Para ingressar, clique aqui.
Objetivo
Introduzir os técnicas avançadas para armazenamento e manipulação de dados.
Ementa
Ordenação de dados; Árvores; Tabelas;
Bibliografia
- WIRTH, N. Algoritmos e estruturas de dados. Rio de Janeiro: Prentice Hall do Brasil, 1989
- VELOSO, P., SANTOS, C. S., AZEREDO, P. A., FURTADO, A. L. Estruturas de dados. 3.ed. Rio de Janeiro: Campus, 1985
Material extra
- Balanced binary search trees - AVL trees, 2-3 trees, B trees
- Algorithms Behind Modern Storage Systems
- Blist: uma implementação de B+ tree em Python
- Fast Algorithms for Sorting and Searching Strings
Avaliação
- Exercícios em sala: 3.5 pontos (0.5pt cada exercício)
- Prova do primeiro bimestre: 5.5 pontos
- Seminário: 5 pontos
- Projeto de disciplina (PD): 6 pontos
- Atividade extra (AE): 1 ponto
Seminário
O seminário é uma apresentação de tópicos não abordados na disciplina, como por exemplo:
- Arvore B (remoção)
- Arvore B* (inserção e busca)
- Acesso concorrente em Arvore B* (inserção e busca)
- Hashing (funções de transformação, colisões & listas encadeadas, endereçamento aberto)
O seminário é em dupla e pode ser feito usando slides ou o quadro com piloto e apagador. Cada apresentação deve conter:
- Introdução do tópico
- Exemplo prático
- Exercícios para serem resolvidos em sala
Até no máximo 3 dias corridos antes da apresentação, a dupla deve enviar para o slack um artigo científico que aborde o tema que será apresentado. Todos os alunos que não apresentarem devem fazer o resumo do artigo enviado (em dupla). O resumo deve ter no mínimo uma folha, e deve ser entregue (impresso) ao fim do seminário correspondente para o professor. Não serão aceitos resumos entregues fora do prazo.
Pontuação do seminário:
- Apresentação do seminário: 3.00
- Entrega dos resumos: 2.00 (ou .50 por resumo)
- A dupla que não enviar o artigo para o slack até o prazo estipulado, será penalizada com 1 ponto do seminário. Nesse caso, Nesse caso, os alunos se beneficiam do 0.50 automaticamente.
Projeto de disciplina (PD)
O projeto de disciplina consiste em identificar como as estruturas de dados estudadas em sala são utilizadas em implementações de projetos de software reais.
Os alunos devem investigar que potenciais projetos de software fazem uso de alguma das estruturas de dados, identificar os trechos de código que fazem uso das estruturas, e entender as decisões que levaram ao uso dessa estrutura (pq foi usado x ao invés de y?). Como atividade bonus, os alunos que conseguirem modificar o código para utilização de outra estrutura de dados (ou para otimizar uma estrutura já existente), receberão 2 pontos extras.
Depois de fazer a investigação, os alunos precisam preparar uma apresentação contendo: o nome do projeto, o local em que o projeto está disponível, os nomes das classes, métodos, trechos de código, etc, que fazem uso das estruturas, uma discussão sobre pq as estruturas estão sendo empregadas, e, caso tenha sido feito, quais foram as alterações realizadas no código. A apresentação deve durar no máximo 15 minutos. Terá penalidade de 1 ponto para quem estourar o tempo (ENSAIEM!).
Atividade Extra (AE)
Alunos interessados em fazer a atividade extra devem entrar em contato com o professor, avisando o interesse, até o dia 20/11. As instruções da atividade extra será passada para o aluno interessado. A atividade extra é individual.
Nota final
Soma de todas as atividades dividido por dois.
Cronograma
Passível de alterações.
| # | Data | Conteúdo de Aula |
| 1 | 28/08 | Apresentação da disciplina, Revisão de conceitos |
| 2 | 30/08 | Árvores e Árvores Binárias |
| 3 | 04/09 | Árvores Binárias (cont) |
| 3 | 06/09 | Exercício em sala |
| 5 | 11/09 | Árvores AVL |
| 6 | 13/09 | Exercício em sala |
| 7 | 18/09 | NAO TEREMOS AULA |
| 8 | 20/09 | NAO TEREMOS AULA |
| 8 | 25/09 | Árvore B |
| 9 | 27/09 | Exercício em sala |
| 10 | 02/10 | Árvore 2-3 & Árvore Trie (Definição das equipes do seminário) |
| 11 | 04/10 | Exercício em sala |
| 12 | 09/10 | Árvore B+ |
| 12 | 11/10 | Exercício em sala |
| 13 | 16/10 | NAO TIVEMOS AULA |
| 14 | 18/10 | Árvore Radix |
| 15 | 23/10 | Exercício em sala |
| 16 | 25/10 | Árvore Ternária de busca |
| 17 | 30/10 | Exercício em sala |
| 17 | 01/11 | Prova |
| 18 | 06/11 | Seminário 1 |
| 19 | 08/11 | NAO TEREMOS AULA |
| 20 | 13/11 | Seminário 2 |
| 21 | 15/11 | FERIADO |
| 22 | 20/11 | Seminario 3 & entrega da AE |
| 23 | 22/11 | Seminário 4 |
| 24 | 27/11 | Acompanhamento das atividades |
| 25 | 29/11 | Acompanhamento das atividades |
| 26 | 04/12 | NAO TEREMOS AULA |
| 27 | 06/12 | NAO TEREMOS AULA |
| 28 | 11/12 | Acompanhamento das atividades |
| 29 | 13/12 | Acompanhamento das atividades |
| 30 | 18/12 | Acompanhamento das atividades |
| 31 | 20/12 | Apresentação do PD |
Entrega atrasada
Entregas de trabalhos após o prazo serão aceitas mas os pontos referentes não serão contabilizados.
Política de plágio
Todos os trabalhos (a não ser que indicados explicitamentes) devem ser feitos de forma individual. O que você entregar deve ser fruto do seu trabalho. Alunos são permitidos e encorajados para discutir os trabalhos e projetos com outros alunos. Alunos não são permitidos copiar solução ou parte de solução de colegas. Na presença de plágio, os alunos envolvidos não receberão pontos da atividade em questão.
Pontuação extra
Dado a existência da atividade extra (AE), qualquer pontuação extra não será possível.