Menu:

Estruturas de Dados II


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

Local: Sala 237 (quartas) e Sala 239 (sextas)

Lista: http://groups.google.com.br/group/ed2-uff-2011-2
(importante: todos os alunos devem se cadastrar nessa lista)

Monitoria

Monitor: Carlos Henrique henriquezplay@hotmail.com

Horário de Atendimento: SEG 11-13h, TER 08-09h, QUA 11-13h, QUI 08-09h, SEX 09-11h

Avaliação

Média = (2 x Prova1 + 2 x Prova2 + Participação + 2 x Trabalho) / 7

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.

Grupos

As atividades da disciplina (exceto as provas) 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 - 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 si próprio) no resultado final dos trabalhos. Esta informação será utilizada na distribuição das notas. Desta forma, se empenhe desde o início de forma pró-ativa.

Participação

Na maioria das aulas serão fornecidos exercícios para serem feitos em grupo durante a aula ou em casa. Os grupos serão convidados a se voluntariar para apresentar as suas soluções. A participação nessas atividades será considerada na composição da média final (item Participação). A nota de participação é calculada da seguinte forma: cada apresentação feita por um grupo vale 1 ponto. Uma tarefa só pode ser apresentada por um único grupo. Nas apresentações será sempre dada prioridade para os grupos que têm menos pontos. Ao final do semestre, o grupo que tiver mais pontos terá nota 10. A nota dos demais grupos será calculada proporcionalmente. Notem que existe também um “grupo invisível”. Se nenhum grupo se voluntariar para apresentar uma determinada tarefa, o grupo invisível ganha mais um ponto. A pontuação do grupo invisível é calculada da seguinte forma: número de pontos do grupo que tem mais pontos somado ao número de tarefas que não foram apresentadas por nenhum grupo. Isso significa que se ninguém entregar alguma tarefa, nenhum grupo ficará com 10 na nota de participação, pois a partir deste momento o grupo que tem mais pontos é o grupo invisível, e a pontuação dele sempre cresce.

A entrega das listas de exercícios também valem ponto de participação para o grupo. A diferença é que cada lista entregue no prazo, e com respostas corretas, vale um ponto, independente de outro grupo também ter entregue a lista. Listas entregues fora do prazo, ou com respostas incorretas, não ganham ponto.

Exemplo: suponha que o grupo X tem 5 pontos, e o grupo Y tem 2 pontos. Todas as tarefas foram apresentadas, então o grupo invisível também tem 5 pontos. A nota do grupo X é 10, e a do grupo Y é 4. Numa outra situação, suponha que o grupo X tem 5 pontos, e o grupo Y tem 2 pontos. No entanto, 2 tarefas não foram apresentadas. Desta forma, o grupo invisível tem 7 pontos (= 5 + 2). A nota do grupo X é 7,1 e a do grupo Y é 2,9.

Trabalho

Implementar um sistema de controle de empregados e seus dependentes. O sistema deve ser capaz de realizar as seguintes tarefas:

  1. Permitir que o usuário cadastre empregados. Cada empregado tem os seguintes atributos: código, nome, idade, salário.
  2. Permitir que o usuário cadastre dependentes dos empregados. Cada dependente tem os seguintes atributos: código, nome, idade, código do empregado de quem ele é dependente. A tela de cadastro, no entanto, não deve pedir para o usuário informar o código do empregado, e sim o nome. O sistema deve encontrar seu código automaticamente.
  3. Permitir que o usuário faça consultas sobre os dados do sistema (ver detalhes abaixo).
  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.

As seguintes consultas são obrigatórias:

  1. Encontrar um empregado que tenha um determinado nome (exemplo: nome=JOANA)
  2. Encontrar um empregado que tenha idade maior que um determinado valor (exemplo: idade > 20)
  3. Encontrar um empregado que tenha mais do que um determinado número de dependentes (exemplo: empregado com mais de 2 dependentes)
  4. Encontrar os nomes dos dependentes de um determinado empregado
  5. Encontrar um dependente que tenha um determinado nome
  6. Encontrar um dependente que tenha idade menor do que um determinado valor (exemplo: idade < 5)

As consultas devem ser parametrizadas, ou seja, o usuário informa o valor que quer usar como parâmetro em cada tipo de consulta. Além das consultas acima, o sistema deve também permitir outros 5 tipos de consulta, no mínimo.

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á entregue em duas etapas (ver seção Cronograma). Na primeira entrega é esperado que já exista algum resultado concreto. Pelo menos a interface já deve estar pronta e funcionando.

A segunda etapa consista de entrega e apresentação do trabalho completo, onde os grupos devem mostrar os resultados obtidos no trabalho.

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

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

Auto-Avaliação

Ao final da disciplina, cada componente do grupo deverá me enviar, de forma anônima, o percentual de participação de cada membro do grupo no trabalho e nas atividades realizadas durante o curso em grupo (listas de exercícios, tarefas de aula, DOJOs, etc). Os componentes que não enviarem assumem que o que foi informado pelos colegas está correto. Estes percentuais serão consolidados e aplicados sobre as notas de participação e sobre a nota do trabalho. Desta forma, dois componente de um mesmo grupo podem ficar com notas diferentes no trabalho e na participação.

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

Veja as datas de entrega das listas no cronograma da disciplina.

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
10/08/2011 Apresentação da disciplina
Leitura: Why File Structures?
12/08/2011 Conceito de Arquivos
17/08/2011 Tutorial sobre manipulação de arquivos
19/08/2011 Arquivos Sequenciais
Atualização em Lote
Material de Apoio: Tutorial JUnit. Atenção: usem JUnit 4
24/08/2011 DOJO Balance Line
26/08/2011 DOJO:
31/08/2011 Intercalação de Arquivos Sequenciais
02/09/2011 Classificação Externa: geração de partições classificadas
07/09/2011 FERIADO
09/09/2011 Classificação Externa: intercalação Lista 1
14/09/2011 DOJO
16/09/2011 Arquivos de Acesso Direto: hashing
Tutorial sobre manipulação de arquivos de acesso randômico
21/09/2011 Não houve aula
23/09/2011 Hashing (continuação)
28/09/2011 Hashing (continuação)
30/09/2011 PROVA 1
05/10/2011 Sem aula - SBBD
07/10/2011 Sem aula - SBBD
12/10/2011 FERIADO
14/10/2011 Vista de Prova (sala 326 - Bloco E) Lista 2 + Código-fonte da 1a parte do Trabalho
19/10/2011 Sem aula - Agenda Acadêmica
21/10/2011 Sem aula - Agenda Acadêmica
26/10/2011 Aula prática
28/10/2011 FERIADO
02/11/2011 FERIADO
04/11/2011 Aula prática (continuação)
09/11/2011 Arquivos Indexados: Árvore B
11/11/2011 (continuação) Arquivos Indexados (Árvore B+)
16/11/2011 Aula prática Lista 3
18/11/2011 Aula prática (continuação)
23/11/2011 Arquivos Indexados por chaves secundárias
25/11/2011 PROVA 2 Lista 4
30/11/2011 Apresentação do Trabalho: G6, G8, G5, G4 Código-fonte e relatório
02/12/2011 Apresentação do Trabalho: G3, G1, G9, G2 Código-fonte e relatório
07/12/2010 Vista de Prova
09/12/2011 Sem aula
14/12/2011 VS - sala 233 do bloco D, aplicada pelo Prof. Leonardo Murta. Levar carteira de identidade, que será exigida para a realização da prova
16/12/2011 Vista de Prova + Entrega das notas