Estruturas de Dados

Informações Gerais

Nesta disciplina aprende-se as técnicas clássicas para a eficiente manipulação de dados em programas de computador. Na regulamentação desta disciplina você pode acessar as informações oficiais sobre ela, incluindo justificativa, objetivos, ementa e bibliografia.

Os assuntos das aulas, juntamente com as datas de cada encontro da disciplina, estão no plano de atividades. Se você desejar alguma alteração nas datas, por favor me comunique o quanto antes!

As aulas da disciplina não seguirão nenhum livro de forma exata, mas, àqueles que desejarem uma sugestão de livro para estudar, eu recomendo o muito bom Estruturas de Dados e Seus Algoritmos, de Jayme Szwarcfiter e Lilian Markenzon, que contém todo o conteúdo que veremos e o apresenta em nível adequado a esta disciplina. Um livro mais avançado, mais abrangente e que também contempla a disciplina posterior de Construção e Análise de Algoritmos, é o Algoritmos, de Cormen, Leiserson, Rivest e Stein.

A minha sugestão para a obtenção de um bom desempenho na disciplina é (1) acompanhar as aulas com atenção, tirando dúvidas o quanto antes, e (2) fazer os exercícios com regularidade. Caso você possua uma dúvida no horário da aula, o ideal é tirá-la na própria ocasião, para que os demais alunos também se beneficiem das explicações. Esteja, porém, à vontade para me contactar fora das aulas.

Média das APs	≥ 7	7 > média ≥ 4	< 4
Situação	Aprovado	AF	Reprovado

Plano de Atividades

Esta é uma disciplina de 4 créditos, e portanto ela possui (4/2)*16 = 32 encontros planejados, dos quais 27 são Aulas, 4 são Avaliações Parciais e 1 é reservado aos Encontros Universitários. Adicionalmente, poderá ser realizada também uma Avaliação Final. Na tabela a seguir estão as datas e descrições de cada encontro (observe que a solução de cada prova, exceto a AF, será apresentada na última meia-hora da própria data de aplicação).

A disciplina está dividida em 4 partes:

A parte 1 é uma introdução e motivação da disciplina: nela são apresentados 2 problemas evidentemente relevantes, que são então discutidos e resolvidos por meio de programas de computador, ao mesmo tempo em que são introduzidas as estruturas de Pilha e Fila. Essa parte intencionalmente ilustra a aplicabilidade do conteúdo da disciplina, já que para alguns dos outros tópicos não haverá tempo para a discussão de uma aplicação específica. A apresentação de programas concretos para resolver os problemas também é um foco dessa parte, ilustrando a viabilidade da implementação de cada um dos assuntos que serão vistos.
Na parte 2 são introduzidas as listas encadeadas, que são então utilizadas na implementação de vários Tipos Abstratos de Dados, culminando com mais uma representação e mais um problema envolvendo grafos. Por fim, complementando o foco em programação da primeira metade da disciplina, é introduzida a análise de complexidade assintótica de algoritmos, a qual é então aplicada aos algoritmos vistos até ali.
A parte 3 aprofunda o estudo sobre Dicionários, introduzindo a Busca Binária, as Árvores Binárias de Busca, as Árvores AVL e as Tabelas de Dispersão.
A parte 4 apresenta o último Tipo Abstrato de Dados da disciplina, a Fila de Prioridades, cujo gancho é finalmente aproveitado para a discussão do Problema de Ordenação, por meio de dois algoritmos assintoticamente ótimos.

Aula	Data	Descrição
01	18/08	Introdução à Disciplina; O Problema da Avaliação de Expressões Aritméticas.
	21/08	Semana Acadêmica da Computação
	25/08	Semana Acadêmica da Computação
02	28/08	Pilhas e Implementação via Vetor
03	01/09	Programa para Avaliação de Expressões Aritméticas
04	04/09	O Problema das Distâncias em um Grafo Não-Ponderado; Matrizes de Adjacência.
05	08/09	Filas e Implementação via Vetor
06	11/09	Programa para Cálculo de Distâncias em Grafo Não-Ponderado
*	15/09	AP1 e Solução da Prova
07	18/09	Listas Encadeadas e Implementação de Pilhas e Filas
08	22/09	Deques e implementação via Lista Duplamente Encadeada
09	25/09	Conjuntos Dinâmicos Simples e Implementação via Lista Simplesmente Encadeada
10	29/09	Conjuntos Dinâmicos Refinados e Implementação via Lista Duplamente Encadeada
11	02/10	Grafos e Implementação via Listas de Adjacências
12	06/10	Ordenação Topológica de Grafos Direcionados Acíclicos
13	09/10	Introdução às Notações Assintóticas O, Ω e Θ
14	13/10	Complexidade Assintótica de Algoritmos e Análise dos Algoritmos Anteriores
*	16/10	AP2 e Solução da Prova
15	20/10	Busca Binária e uso na Implementação de Dicionários
16	23/10	Árvores Binárias de Busca e uso na Implementação de Dicionários
17	27/10	Remoção e Percursos em Árvores Binárias de Busca
18	30/10	Árvores AVL – Parte 1 / 2
19	03/11	Árvores AVL – Parte 2 / 2
20	06/11	Tabelas de Dispersão ("hash tables") – Parte 1 / 3
*	10/11	Encontros Universitários 2017
21	13/11	Tabelas de Dispersão ("hash tables") – Parte 2 / 3
22	17/11	Tabelas de Dispersão ("hash tables") – Parte 3 / 3
*	20/11	AP3 e Solução da Prova
23	24/11	Filas de Prioridades e Montes ("heaps") Binários
24	27/11	Algoritmos para Montes Binários
25	01/12	Construção de Montes em Tempo Linear e Ordenação por Monte ("heapsort")
26	04/12	Ordenação por Entrelaçamento ("Mergesort")
27	08/12	Implementação e Otimizações no Entrelaçamento
*	11/12	AP4 e Solução da Prova
	15/12	Notas da AP4
*	18/12	AF
	22/12	Notas da AF

Para fins de registro, também é possível acessar a versão inicial do plano acima.

Estruturas de Dados – 2017.2

Avisos

Informações Gerais

Regras

Plano de Atividades