Moodle: Clique aqui para o EAD
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:
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.