Menu:

Estruturas de Dados II


Horário: sextas, de 14:00h às 18:00h

Local: sala 401, bloco H

Grupo da disciplina: usaremos um grupo fechado do Facebook para as discussões da disciplina. Inscrevam-se em https://www.facebook.com/groups/ed2.cc.2014.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: Matheus Corrêa matheus_cxp@hotmail.com

Horário de Atendimento da monitoria:

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 OU falta em P1 OU falta em P2:

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 que entregarem o exercício na data correta ganham o ponto. Ao final, será feita uma proporção. O aluno que tem mais pontos fica com 10 em Participação. Os demais ganham nota proporcional.

Grupos

As atividades da Avaliação 3 (T) serão feitas 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-CC-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 à Avaliação 3. 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. 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). Vale notar que segundo o mesmo regulamento, nenhuma falta será abonada (Art. 80, §15).

Avaliação de Aprendizagem em Caráter Excepcional

De acordo com o Regulamento dos Cursos de Graduação, não será permitida a Avaliação de Aprendizagem em Caráter Excepcional (i.e., 2ª chamada), com exceção dos casos citados no Art. 87, de acordo com os procedimentos do Art. 88.

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
21/02/2014 Apresentação da disciplina
Conceito de Arquivos
Tutorial sobre manipulação de arquivos
Leitura: Why File Structures?
28/02/2014 SEM AULA Exercício do slide 50 (até 14h)
07/03/2014 SEM AULA -- CARNAVAL
14/03/2014 Arquivos Sequenciais
Atualização em Lote
JUnit
Casos de Tese para exercício do BalanceLine
Arquivo para exercício do BalanceLine

Intercalação de Arquivos Sequenciais 		Exercício do slide 55 (até 14h)
21/03/2014 Classificação Externa: geração de partições classificadas
Arquivo com os casos de teste em Java para o exercício de geração de partições classificadas

Classificação Externa: intercalação
Arquivo com os casos de teste em Java para o exercício de intercalação 		Exercício BalanceLine (até 22/03 às 23:59h)
28/04/2014 Arquivos de Acesso Direto: hashing
Tutorial sobre manipulação de arquivos de acesso randômico		 Exercício geração de partições classificadas (até 29/03 às 23:59h)
04/04/2014 especificação dos testes
Esqueleto da implementação		 Exercício de Intercalação (até 05/04 às 23:59h)
11/04/2014 PROVA 1 TRABALHO - PARTE 1
18/04/2014 SEM AULA -- SEMANA SANTA
25/04/2014 Arquivos Indexados: Árvore B
VISTA DE PROVA
02/05/2014 SEM AULA -- RECESSO DIA DO TRABALHO
09/05/2014 Esqueleto da implementação
Árvores usadas no testes
16/05/2014 Árvore B+
Árvores usadas no testes
Esqueleto da implementação
23/05/2014 Arquivos indexados por chaves secundárias Exercício Árvore B (até dia 25/05 à meia noite)
30/05/2014 PROVA 2
06/06/2014 VISTA DE PROVA, sala 326, bloco E
13/06/2014 SEM AULA -- IPAW Entrega do trabalho, até dia 14/06 às 23:55h
20/06/2014 SEM AULA -- CORPUS CHRISTI
27/06/2014 VS