INF1010 – Estrutura de dados Avançadas Turma 3WA (2020.1)

Aulas são ministradas na PUC-Rio 15h-17h Segundas e Quartas no ~~Lab-A (Labgrad)~~ zoom.

Objetivo da Disciplina:

Apresentar as técnicas básicas de organização de dados, possibilitando a construção de algoritmos eficientes em memória primária ou secundária.
Praticar a implementação de estruturas de dados e a avaliação da eficiência de algoritmos complexos
Ao final do curso o aluno deve ser capaz de desenvolver programas de computador eficazes e eficientes para a solução de problemas complexos.

Material das Aulas:

Aula 00 – Apresentação da Disciplina (vídeo)
Aula 01 – Revisão C – Ponteiros, Alocação, Recursão, Estruturas (vídeos)
Aula 02 – Revisão C – Vetores de Ponteiros, Busca em Vetores, Módulos, TAD (vídeos)
Aula 03 – Revisão de Estruturas de Dados – Listas Encadeadas (vídeos)
Aula 04 – Revisão de Estruturas de Dados – Pilhas
Aula 05 – Revisão de Estruturas de Dados – Filas
Aula 06 – Árvores e Árvores Binárias
Aula 07 – Árvores Binárias de Busca
Aula 08 – Árvores AVL
Aula 09 – Complexidade de Algoritmos
Aula 10 – Árvores Rubro Negras
Aula 11 – Árvores B
Aula 12 – Árvores 2-3
Aula 13 – Tabelas de Dispersão
Aula 14 – Filas de Prioridades, Heaps e Heapsort
Aula 15 – Conjuntos e Mapas de Bits
Aula 16 – Partições Dinâmicas de Conjuntos (União e Busca)
Aula 17 – Árvores Trie e Patricia
Aula 18 – Grafos e Buscas
Aula 19 – Caminho mais Curto
Aula 20 – Árvore Geradora Mínima

Leitura Complementar:

8 Common Data Structures every Programmer must know – Artigo apresenta todas as estruturas que veremos no curso.

Ementa do Curso:

1) Parte 1 – Revisão
- Ponteiros, Alocação, Recursão, Estruturas
- Vetores de Ponteiros, Busca em Vetores, Módulos, TAD
- Listas Encadeadas
- Pilha
- Fila
- Complexidade de Algoritmos
2) Parte 2 – Árvores
- Árvores n-árias
- Árvores Binárias
- Árvores Binárias de Busca
- Árvores AVL
- Árvores rubro-negras
- Árvores B
- Árvores 2-3
3) Parte 3 – Hash e Heap
- Tabelas de Dispersão (hashtables)
- Filas de prioridades, Heaps e Heapsort
- Conjuntos, Mapas de bits
- Partições dinâmicas (União e Busca)
4) Parte 4 – Grafos
- Introdução à Grafos
- Percursos, Busca em Profundidade e em Largura
- Busca A*
- Busca Dijkstra
- Árvore Geradora Mínima Kruskal

Cronograma:

Data	Planejado
04/mar	Apresentação da Disciplina, Revisão, Ponteiros, Alocação, Recursão, Estruturas
09/mar	VetorPonteiros, BuscaVetor, Modulos, TAD
11/mar	Listas Encadeadas
16/mar	Pilha
18/mar	Fila
23/mar	Árvores
25/mar	Complexidade de Algoritmos
30/mar	Árvores Binárias; Árvores Binárias de Busca
01/abr	Árvores AVL
06/abr	Revisão - Entrega de trabalho 1
08/abr	P1
13/abr	Árvores N-árias; Árvores 2-3
15/abr	Árvores vermelho-negras
20/abr	Feriado/Recesso (Recesso de São Jorge)
22/abr	Árvores B
27/abr	Árvores B (de ordem 3)
29/abr	Tabelas Hash
04/mai	introdução a heaps de prioridades
06/mai	heaps e heapsort
11/mai	Conjuntos, Mapas de bits
13/mai	Partições dinâmicas
18/mai	Revisão - Entrega de trabalho 2
20/mai	P2
25/mai	Introdução à Grafo, percursos, Busca em Profundidade e em Largura
27/mai	Lab Grafos
01/jun	A*
03/jun	Lab Grafos
08/jun	Dijkstra
10/jun	Lab Grafos
15/jun	Kruskal
17/jun	Lab Grafos
22/jun	Revisão - Entrega de trabalho 3
24/jun	P3
29/jun	(Não haverá aula)
01/jul	P4
06/jul	(Não haverá aula)

Bibliografia:

Celes, W., Cerqueira, R., Rangel, J.L., Introdução a Estruturas de Dados – Uma introdução com técnicas de programação em C, Ed. Campus, 2004.
Horowitz. E.; Sahni, S.; Anderson-Freed, S. Fundamentals of Data Structures in C, 2nd edition. Silicon Press, 2008.
Kruse, R.; Tondo, C.; Leung, B.; Mogalla, S.; Data Structures and Program Design in C, 2nd edition. Pearson, 1996.
Moraes, C.; Estruturas De Dados E Algoritmos: Uma Abordagem Didática, Ed. Futura, 2003
Rocha, A.; Estruturas De Dados E Algoritmos Em C, 3ª Edição, Ed. FCA, 2014
Edelweiss, N.; Galante, R.; Estruturas de Dados, Ed. Bookman, 1ª edição, 2008
Kernighan, B.W., Ritchie, D.M., C – A Linguagem de Programação – Padrão ANSI, Ed. Campus, 1989.