Menu:

Estruturas de Dados II


Horário: quartas e sextas, de 07:00h às 09:00h

Local: sala 302 (quartas), sala 202 (sextas)

Grupo da disciplina: usaremos um grupo fechado do Facebook para as discussões da disciplina. Inscrevam-se em https://www.facebook.com/groups/ed2.2014.2/. 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: Rafael Machado (detalhes do contato dele estão no nosso grupo do Facebook)

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 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 interior. O tamanho da tabela deve ser 23. 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. 80, §14).

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
06/08/2014 Apresentação da disciplina
08/08/2014 Conceito de Arquivos
Leitura: Why File Structures?
13/08/2014 Tutorial sobre manipulação de arquivos
15/08/2014 Arquivos Sequenciais
Atualização em Lote
JUnit
Arquivo para exercício do BalanceLine
Casos de Teste BalanceLine 		Exercício Conta-Corrente (17/08, via Interagir)
20/08/2014 Balance Line (continuação)
22/08/2014 Intercalação de Arquivos Sequenciais Exercício Balance Line (24/08, via Interagir)
27/08/2014 Classificação Externa: geração de partições classificadas
Arquivo com os casos de teste em Java
29/08/2014 Implementação da geração de partições classificadas
03/09/2014 Classificação Externa: intercalação
Arquivo com os casos de teste em Java para o exercício de intercalação
05/09/2014 Exercício de Intercalação Exercício Geração de Partições Classificadas (07/09, via Interagir)
10/09/2014 Apresentação do Trabalho (Parte 1)
12/09/2014 Arquivos de Acesso Direto: hashing
Tutorial sobre manipulação de arquivos de acesso randômico 		Exercício de Intercalação (14/09, via Interagir)
Parte 1 do Trabalho (14/09, via Interagir)
17/09/2014 Hashing (continuação)
Esqueleto da Implementação de hashing com encadeamento exterior
19/09/2014 Hashing (continuação)
24/09/2014 Hashing (continuação)
26/09/2014 Esqueleto da Implementação de hashing com encadeamento interior
01/10/2014 Revisão para a prova
03/10/2014 PROVA 1
08/10/2014 SEM AULA - SBBD
10/10/2014 SEM AULA - SBBD
15/10/2014 SEM AULA - Dia do Professor
17/10/2014 SEM AULA - Agenda Acadêmica
22/10/2014 Vista de Prova
24/10/2014 Arquivos Indexados: Árvore B
29/10/2014 Árvore B (continuação), Árvore B+
31/10/2014 Implementação Árvore B+
Árvores usadas no testes
05/11/2014 Implementação árvore B+ (continuação)
07/11/2014 Apresentação do Trabalho Relatório + Código Fonte
12/11/2014 Arquivos indexados por chaves secundárias
14/11/2014 PROVA 2
19/11/2014 Vista da P2 (sala 512)
21/11/2014 SEM AULA - RECESSO
26/11/2014 VS
28/11/2014 SEM AULA
03/12/2014 Vista de VS