Menu:

Estruturas de Dados


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

Local: Sala 215

Sala de aula virtual da disciplina: usaremos o Google Classroom para as discussões e entrega de tarefas e trabalhos da disciplina. É necessário ter uma conta no ID UFF. O código para inscrição na sala de aula do Google Classroom está na lista de chamada. A sala de aula no Google Classroom será usada também para divulgar avisos gerais e para dúvidas.

Importante: todos os alunos devem se inscrever no Google Classroom (os alunos para os quais eu possuo o endereço de email do ID UFF receberam convite – nesse caso basta aceitar o convite). Para se inscrever, clique no símbolo de “+” no canto superior direito da página, e selecione a opção “Participar da Turma”. O código de inscrição na turma está na lista de presença.

Monitoria

Vitor Augusto Bastos Pinheiro.

Horários de atendimento: SEG 14-16h; TER 14-16h; SEX 09-13h.

Ementa

Avaliação

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

P1 = Prova sem consulta

P2 = Prova sem consulta

T = Trabalho

Média = ((P1 * 2) + (P2 * 2) + T ) / 5

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

VERIFICAÇÃO SUPLEMENTAR:
(Presença >= 75%) E (4 <= Média < 6)

Será aprovado na VS o aluno que tirar nota maior ou igual a 6.

REPROVADO: caso contrário

Exercícios no Google Classroom

Diversos exercícios serão disponibilizadas durante o curso. Todos terão data de entrega marcada no Google Classroom. Durante a resolução dos exercícios, os alunos podem usar comentários de uma tarefa específica para tirar dúvidas no Google Classroom. Espera-se que os alunos façam uso do compilador C para verificar a corretude das suas respostas. Alunos que entregarem os exercícios no prazo e corretos podem ser aprovados direto caso tenham ficado com média entre 5,5 e 5,9. Da mesma forma, terão direto à VS caso tenham ficado com média entre 3,5 e 3,9.

Duplas

O Trabalho e os exercícios da disciplina serão feitos em duplas. As duplas são flexíveis e podem mudar a cada exercício. Observar apenas o limite máximo de 2 participantes.

IMPORTANTE: os exercícios devem ser entregues por todos os membros da dupla, SEMPRE. O nome do arquivo zip deve ser a concatenação do nome da dupla, separados por um traço (-). Exemplo: suponha a seguinte dupla Fábio Santos e João Felipe da Silva. O nome do arquivo zip a ser entregue em cada tarefa é FabioSantos-JoaoFelipedaSilva.zip. Note que os nomes são ordenados alfabeticamente.

Trabalho

O trabalho consistirá de um sistema de gerenciamento de um cardápio de pizzaria, usando uma Árvore B+. Seu programa deve receber como entrada os seguintes parâmetros:

O catálogo inicial deve ser salvo em dois arquivos binários usando a estrutura de uma Árvore B+ (um arquivo para o índice, outro para os dados).

Seu programa deve ser capaz de distinguir entre as informações principais consideradas chaves primárias (nesse caso, o código da pizza) e as informações subordinadas (nome da pizza, categoria e preço). A Árvore B+ deve ser armazenada em disco.

TAMANHOS e TIPOS DE DADOS:

As seguintes operações devem ser implementadas nesse trabalho:

IMPORTANTE: É obrigatório usar o projeto fornecido pela professora (disponível no Google Classroom), que contém o esqueleto das funções a serem implementadas. Esse projeto contém testes automatizados que serão usados como apoio para a correção do trabalho. Note que, independente dos testes automatizados, seu programa deve ter uma função principal que permita o acesso às funcionalidades mencionadas acima (inserção, exclusão, busca, etc.).

Listas de Exercícios

As listas de exercícios abaixo são sugeridas para auxiliar no estudo e fixação da matéria.

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 sem documentação (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.

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Introduction to algorithms, McGraw-Hill, 2009.

Celes, W., Cerqueira, R., Rangel, J.L. Introdução a Estruturas de Dados, Campus, 1a Edição, 2004.

Kernighan, B.W.,Ritchie, D.M. C: a linguagem de programação (Padrão ANSI), Campus, Segunda Edição, 1990.

Bibliografia Complementar

Tenenbaum, A.M., Langsam, Y., Augenstein, M.J. Estruturas de Dados Usando C, Pearson, Primeira Edição, 1995.

Ramakrishnan, R. Database Management Systems, McGraw Hill, Third Edition, 2003.

Ferramentas

Para programação em C, recomendo o CLion. É possível solicitar uma licença grátis para estudante no site da Jetbrains.

Para ajudar na identificação de memory leak, vocês podem usar as seguintes ferramentas:

Cronograma

Data Atividade
20/03/2019 Apresentação da Disciplina
22/03/2019 Revisão de C
Esqueleto do código de manipulação de listas encadeadas
27/03/2019 Revisão de Pilhas e Filas em C
Código em C de manipulação de pilhas usando vetores
29/03/2019 Árvores e Árvores Binárias
Implementação de Árvore Binária
03/04/2019 Árvores Binárias de Busca
05/04/2019 Árvores AVL
10/04/2019 Aula de laboratório cancelada devido às chuvas e falta de energia no Campus. Façam os exercícios colocados no Google Classroom no tópico “Aula de Laboratório”.
12/04/2019 Grafos
17/04/2019 Aula de Laboratório (Lab. 306)
19/04/2019 FERIADO
24/04/2019 Arquivos
Tutorial de Acesso a Arquivos em C
26/04/2019 Arquivos Binários (continuação da aula anterior)
Ordenação de Arquivos
Insertion Sort em Memória e em Disco para Ordenar Arquivos
01/05/2019 FERIADO
03/05/2019 Ordenação Externa de Arquivos: Geração de Partições Classificadas
Implementação de Classificação Interna
08/05/2019 Geração de Partições Classificadas (continuação)
10/05/2019 Ordenação Externa de Arquivos: Intercalação de Partições Classificadas
Implementação de Intercalação
15/05/2019 Aula de Dúvidas
17/05/2019 Árvore B
Implementação de Busca e Inserção em Árvore B em memória
22/05/2019 PROVA 1
24/05/2019 Exercícios no Laboratório
29/05/2019 Árvore B+
31/05/2019 Aula no Laboratório
05/06/2019 Vista de Prova + Laboratório
07/06/2019 Tabelas Hash. Tratamento de colisão por encadeamento exterior.
Implementação Básica de Tabela Hash em memória (Essa implementação não trata colisões)
Implementação de Tabela Hash em memória com tratamento de colisões por Encadeamento Exterior
12/06/2019 Exercícios no Laboratório
14/06/2019 Exercícios no Laboratório
19/06/2019 Continuação de Tabelas Hash. Tratamento de colisão por encadeamento interior e Endereçamento Aberto.
Implementação de Tabela Hash em memória com tratamento de colisões por Encadeamento Interior
Implementação de Tabela Hash em memória com tratamento de colisões por Endereçamento Aberto
21/06/2019 FERIADO
26/06/2019 Continuação de Tabelas Hash. Tratamento de colisão por endereçamento aberto
Implementação de Tabela Hash em memória com tratamento de colisões por Endereçamento Aberto
28/06/2019 Heap
Implementação em memória
Implementação em disco
Essa aula não foi ministrada presencialmente. O vídeo da aula está disponível no Google Classroom.
03/07/2019 SEM AULA – Exercícios de Revisão para a prova estão disponíveis no Google Classroom.
05/07/2019 PROVA 2
10/07/2019 SEGUNDA CHAMADA
12/07/2019 VISTA DE PROVA
17/07/2019 VS
19/07/2019 VISTA DE PROVA