Menu:

Estruturas de Dados II


Horário: quartas e sextas, de 7h às 9h

Local: Sala 206

Grupo da disciplina: usaremos um grupo fechado do Facebook para as discussões da disciplina. Inscrevam-se em https://www.facebook.com/groups/ed2.2015.1/. Esse grupo será usado também para divulgar avisos gerais.
(importante: todos os alunos devem se cadastrar nesse grupo – o grupo é fechado, então nada que for postado nele aparecerá na sua linha do tempo do Facebook)

Monitoria

Monitor: Lucas B. P. de Oliveira (TER 16-18h, QUA 16-18h, QUI 09-13h)

Avaliação

A avaliação da disciplina é composta de duas provas (P1 e P2) e um trabalho (T). A média será calculada da seguinte forma:

P1 = Prova sem consulta

P2 = Prova sem consulta

T = (Participação + 2 x Trabalho) / 3

Média das Provas = (P1 + P2) / 2

Caso Média das Provas >= 4

Média = (P1 + P2 + T) / 3

Caso contrário:

Média = Média das Provas

Obs.: Vale notar que o uso da nota T não é opcional para quem fica com Média das Provas >= 4. Então, caso a nota T seja baixa, a Média será afetada mesmo que a Média das Provas seja alta.

APROVADO

(Presença >= 75%) E (Média >= 6)

VERIFICAÇÃO SUPLEMENTAR

(Presença >= 75%) E (4 <= Média < 6)

Será aprovado na VS se tirar nota maior ou igual a 6.

REPROVADO

Caso contrário

Participação

O item PARTICIPAÇÃO é incorporado à nota do trabalho. Cada exercício passado em sala vale um ponto de participação. Todos os grupos que entregarem o exercício na data correta ganham o ponto. Ao final, será feita uma proporção. O grupo que tem mais pontos fica com 10 em Participação. Os demais ganham nota proporcional.

Grupos

Os Trabalhos e exercícios da disciplina serão feitos em grupos de 4 a 5 participantes, que devem ser constituídos na primeira semana de aula e ter a mesma formação até o final do curso. Entreguem por e-mail (assunto: ED2-Grupo) o número da matrícula e o nome completo de cada participante do grupo.

Ao final do curso, cada membro do grupo será solicitado a indicar, sob o seu ponto de vista, o percentual de participação de cada membro do grupo (inclusive de sí próprio) nas atividades relacionadas ao trabalho e aos exercícios. Esta informação será utilizada na distribuição das notas. Desta forma, empenhe-se desde o início de forma pró-ativa.

Trabalho

Implementar um gerenciador de dados que seja capaz de fazer as seguintes tarefas:

  1. Permitir que o usuário especifique a estrutura das tabelas que deseja armazenar (nome da tabela, conjunto de atributos e tipo de cada atributo). Em gerenciadores de dados, essas informações normalmente ficam armazenadas numa estrutura chamada catálogo.
  2. Permitir que o usuário insira registros nas tabelas (usuário escolhe a tabela e o sistema pergunta valores para os atributos da tabela
  3. Permitir que o usuário faça consultas sobre os registros de uma determinada tabela. Usuário escolhe o nome da tabela e um ou mais atributos (não necessariamente os atributos chave da tabela). O usuário passa as condições de seleção de cada um dos atributos (exemplo: codigo > 30 e data = “05/10/2010”).
  4. Permitir que o usuário exclua registros de uma tabela. A seleção dos registros a serem excluídos será feita da mesma forma explicada no item 3.
  5. Permitir que o usuário modifique o valor de um determinado atributo de uma determinada tabela. O usuário escolhe a tabela, o atributo e os critérios de seleção da tupla a ser modificada, fornecendo o valor da chave.

O trabalho deve ser implementado com tabelas hash com encadeamento exterior. O catálogo pode utilizar outra forma de armazenamento, à escolha do grupo.

Relatório: o relatório a ser entregue deve descrever a implementação, dificuldades encontradas e deve ter um manual de uso do sistema.

Código fonte: deve ser entregue, juntamente com instruções de instalação.

O trabalho será apresentado em dois momentos distintos (ver seção Cronograma). Na primeira apresentação é esperado que o grupo mostre o andamento atual do trabalho. É esperado que já exista algum resultado concreto. Pelo menos o catálogo já deve estar implementado e funcionando. Em outras palavras, o item 1 acima deve estar pronto e funcionando.

A segunda apresentação será a apresentação final, onde os grupos devem mostrar os resultados obtidos no trabalho.

Ambas as apresentações serão feitas na forma de uma demostração do trabalho em funcionamento. Alunos devem estar preparados para responder sobre detalhes do código.

ATENÇÃO: No dia da apresentação final, o gerenciador de dados já deve estar com os seguintes dados cadastrados em uma tabela chamada PESSOA, com os atributos COD (inteiro), NOME (string de tamanho 10) e IDADE (inteiro).

O atraso na entrega do Trabalho terá uma multa de um ponto por dia.

Presença

De acordo com o Regulamento dos Cursos de Graduação, a presença mínima necessária para aprovação é de 75% das aulas (Art. 96) e não há abono de faltas (Art. 103).

Bibliografia

Ferraz, I. N. Programação com Arquivos. Editora Manole Ltda. Barueri, 2003.

Szwarcfiter, J., Markenzon, L. Estruturas de Dados e Seus Algoritmos. Editora LTC, 3a. edição, 2010.

Santos, Clesio S. e Azeredo, Paulo A. Tabelas: Organização e Pesquisa. Série de Livros Didáticos, Número 10. Ed. Sagra Luzzatto, 2001.

Smith, Peter D. e Barnes, G. Michael. Files & Databases: An Introduction. Addison Wesley Series in Computer Science,1987.

Listas de Exercícios

Lista 1 - Arquivos Sequenciais

Lista 2 - Tabelas Hash

Lista 3 - Árvores B, B+, Tries

Lista 4 - Indexação por chaves secundárias

Cronograma

Data Atividade Entrega
11/03/2015 Apresentação da disciplina
13/03/2015 Conceito de Arquivos
Leitura: Why File Structures?
Tutorial sobre manipulação de arquivos
18/03/2015 Conceito de Arquivos (continuação)
20/03/2015 Intercalação
Esqueleto da Implementação
25/03/2015 Geração de Partições Classificadas
Esqueleto da Implementação
27/03/2015 Intercalação
Esqueleto da Implementação
01/04/2015 Implementação da Intercalação Ótima
03/04/2015 FERIADO
08/04/2015 Apresentação Parte 1 do Trabalho
10/04/2015 Arquivos de Acesso Direto: hashing
Tutorial sobre manipulação de arquivos de acesso randômico
15/04/2015 Encadeamento Exterior
Esqueleto da Implementação
17/04/2015 Implementação de Hash com Encadeamento Exterior
22/04/2015 Encadeamento Interior, Endereçamento Aberto e Tabelas Extensíveis
24/04/2015 Implementação de Hash com Encadeamento Interior
29/04/2015 Implementação de Hash com Encadeamento Interior
01/05/2015 FERIADO
06/05/2015 PROVA 1
08/05/2015 Arquivos Indexados: Árvore B
13/05/2015 Implementação de Árvore B
Árvores de Teste
15/05/2015 Vista de Prova
20/05/2015 Arquivos Indexados: Árvore B+
Implementação de Árvore B+
Árvores de Teste
22/05/2015 Implementação de Árvore B+ (continuação)
27/05/2015 AULA
29/05/2015 SEM AULA - SIGMOD
03/06/2015 SEM AULA - SIGMOD
05/06/2015 FERIADO
10/06/2015 SEM AULA (força maior)
12/06/2015 Arquivos indexados por chaves secundárias
17/06/2015 Apresentação do Trabalho - grupos G2, G5, G1 (sala 512) Código Fonte e Relatório
19/06/2015 Apresentação do Trabalho - grupos G3, G7, G4 (sala 512)
24/06/2015 AULA
26/06/2015 PROVA 2
01/07/2015 Vista de Prova
03/07/2015 VS
08/07/2015 Vista de VS