Menu:

Estruturas de Dados II


Horário: segundas e sextas, de 20:00h às 22:00h

Local: sala 204, 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.si.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

O Trabalho da disciplina será feito em grupos de 3 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-SI-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. 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 Local Entrega
17/02/2014 Apresentação da disciplina Sala H-204
21/02/2014 Organização de Programas em Java Lab II (Sala E-320)
24/02/2014 Orientação a Objetos em Java Sala H-204
28/02/2014 SEM AULA --
03/03/2014 SEM AULA -- CARNAVAL --
07/03/2014 SEM AULA -- CARNAVAL --
10/03/2014 Conceito de Arquivos
Leitura: Why File Structures?
 Sala H-204
14/03/2014 Tutorial sobre manipulação de arquivos Lab II (Sala E-320)
17/03/2014 Arquivos Sequenciais
Atualização em Lote
JUnit 		Sala H-204
21/03/2014 Arquivo para exercício do BalanceLine
Casos de Teste BalanceLine		 Lab II (Sala E-320)
24/03/2014 Intercalação de Arquivos Sequenciais
Classificação Externa: geração de partições classificadas
Arquivo com os casos de teste em Java 		Sala H-204 Exercício do Slide 55 (até 20h)
28/03/2014 Exercício de Geração de Partições Classificadas (ver arquivo base da aula anterior) Lab II (Sala E-320)
31/03/2014 Classificação Externa: intercalação
Arquivo com os casos de teste em Java para o exercício de intercalação
Arquivos de Acesso Direto: hashing
Tutorial sobre manipulação de arquivos de acesso randômico		 Sala H-204 Exercício BalanceLine (até 20h)
04/04/2014 Hashing (continuação) Sala H-204
07/04/2014 Hashing (continuação) Sala H-204 Exercício Geração Partições Classificadas (até 20h)
11/04/2014 Hashing (continuação) Lab II (Sala E-320)
14/04/2014 AULA Exercício Intercalação (até 20h)
18/04/2014 SEM AULA -- SEMANA SANTA
21/04/2014 SEM AULA -- TIRADENTES
25/04/2014 PROVA 1 Sala H-204
28/04/2014 TRABALHO - PARTE 1 Sala H-204
02/05/2014 SEM AULA -- DIA DO TRABALHO
05/05/2014 VISTA DE PROVA Sala E-326
09/05/2014 Arquivos Indexados: Árvore B Sala H-204
12/05/2014 Árvore B (continuação)
Árvores usadas no testes
Esqueleto da implementação 		Sala H-204
16/05/2014 Implementação Árvore B Lab II (Sala E-320)
19/05/2014 Árvore B+ Sala H-204
23/05/2014 Implementação Árvore B+
Árvores usadas no testes
Esqueleto da implementação 		Lab II (Sala E-320)
26/05/2014 Arquivos indexados por chaves secundárias
30/05/2014 SEM AULA
02/06/2014 Plantão de dúvidas Sala E-326
06/06/2014 TRABALHO - PARTE 2
09/06/2014 PROVA 2
13/06/2014 SEM AULA -- IPAW Implementação árvore B (até 20h)
16/06/2014 VISTA DE PROVA
20/06/2014 SEM AULA -- CORPUS CHRISTI
23/06/2014 SEM AULA -- JOGO DO BRASIL
27/06/2014 VS