PONTIFÍCIA UNIVERSIDADE CATÓLICA DE GOIÁS
PRÓ-REITORIA DE GRADUAÇÃO
DEPARTAMENTO DE COMPUTAÇÃO
PLANO DE ENSINO
Disciplina: Estrutura de Dados II
Curso: Engenharia de Computação/ Ciência da computação
Professor: Pedro Araújo Valle
Código
Nº de Créditos
Pré-requisitos:
CMP1099
06
CMP1054
Co-requisito
EMENTA
Estudo de algoritmos de pesquisa e ordenação, tabelas hash e algoritmos e grafos.
OBJETIVOS GERAIS
•
•
•
•
Estudar e comparar algoritmos de ordenação mais conhecidos;
Estimar e comparar tempos de execução de algoritmos;
Dominar o conhecimento de organização de tabelas hash e seu uso para acesso a dados;
Compreender estrutura de grafos e seu uso em algoritmos clássicos.
OBJETIVOS ESPECÍFICOS
O aluno deverá ser capaz de:
• Identificar e aplicar os algoritmos de ordenação mais adequados e eficientes, conforme o problema
apresentado;
• Implementar tabelas hash utilizando o a função hash que melhor se encaixa no problema;
• Escolher o algoritmo de grafo de acordo com a necessidade apresentada.
CONTEÚDO PROGRAMÁTICO
•
•
•
•
•
•
Algoritmos de ordenação e pesquisa
Estimativas de tempo de execução de programas
Tabelas Hash
Conceitos básicos e terminologia de Grafos
Aplicações de grafos na solução de problemas clássicos: Árvore geradora mínima, Caminho mais
curto, Matching, Coloração, Caixeiro Viajante, Roteamento de Veículos, Coleta de lixo e entrega
de correspondências, etc.
Representações de grafos no computador
METODOLOGIA
•
•
•
Aulas expositivas;
Formação de grupos para discussão e definições de problemas;
Estudo dirigido – resolução de exercícios em classe.
AVALIAÇÃO
A nota final, NF, da disciplina será resultante da média ponderada de dois conjuntos de
notas, N1 e N2, conforme a expressão NF = 0,4·N1+ 0,6·N2, sendo que tanto N1 quanto N2 serão
compostos por no mínimo duas notas resultantes de duas avaliações individuais com todo o
conteúdo do período correspondente. Serão aplicados pequenos testes em sala ou trabalhos, cuja
soma de suas notas irão compor N1 e N2, sendo que a Avaliação Interdisciplinar (AI) é uma das
avaliações previstas para compor N2.
A frequência será computada em cada encontro através de chamada feita durante as aulas
e pela Atividade Externa à Disciplina (AED).
Será considerado aprovado na disciplina o aluno que obtiver a frequência mínima de 75%
e Nota Final igual ou superior a cinco.
ATIVIDADE EXTERNA À DISCIPLINA
•
•
Pesquisa sobre aplicações práticas de grafos (6h);
Implementação de algoritmo para cadastramento de grafos (vértices, arestas, pesos) em lista de
adjacências e também em matriz de adjacências (6h).
BIBLIOGRAFIA BÁSICA
1. CORMEN, Thomas H. et al. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro: Campus, 2012.
2. DROZDEK, Adam. Estruturas de dados e algoritmos em C++. São Paulo: Cengage Learning,
2002.
3. ZIVIANI, Nivio. Projeto de algoritmos com implementações em Java e C++. São Paulo: Cengage
Learning, 2006.
BIBLIOGRAFIA COMPLEMENTAR
1. AHO Alfred V.; HPCROFT John E.; ULLMAN, Jefrey D. Data structure and algorithms. Ney
2.
3.
4.
5.
York: Addison-Wesley, 1983.
BRASS, P. Advanced data structures. Cambridge: Cambridge University Press, 2008.
SEDGEWICK, Robert. Algorithms. 4. ed. San Francisco: Addison-Wesley, 2010.
SHAFER, Clifford A. Data structures and algorithm analysis in C++. 1. ed. Nrew York: Dover
Publications, 2011.
SZWARCFITER, Jayme L. Estruturas de dados e seus algoritmos. 3. ed. Rio de Janeiro: LTC,
2010.
CRONOGRAMA
04/02 – Apresentação do programa e entrega do plano de ensino.
05/02 – Algoritmo Insertion Sort e tempo de execução.
09/02 – Notação assintótica.
11/02 – Notações assintóticas: limite superior (O), limites inferior e superior (θ), limite inferior
(Ω).
12/02 – Exercícios de fixação.
19/02 – Implementação do Insertion Sort e execução com quantidades crescentes de valores.
23/02 – Algoritmo Bubblesort.
25/02 – Exercícios de fixação.
26/02 – Algoritmo Merge sort.
02/03 – Algoritmo Heapsort.
04/03 – Exercícios de fixação.
05/03 – Algoritmo Quicksort.
09/03 – Considerações sobre a técnica “dividir para conquistar”. Comparação entre os diversos
algoritmos
11/03 – Exercício de fixação.
12/03 – 1ª avaliação N1.
16/03 – Implementação de alguns algoritmos utilizando técnicas para medição do tempo de
execução.
18/03 – Resolução da prova.
19/03 – Implementação de alguns algoritmos utilizando técnicas para contagem das execuções de
cada instrução.
23/03 – Tabelas Hash.
25/03 – Tratamento de colisões por encadeamento.
26/03 – Exercícios de fixação.
30/03 – Endereçamento aberto, função hash: métodos da divisão e da multiplicação.
01/04 – Sondagem linear. Exercícios.
06/04 – Sondagem quadrática. Exercícios.
08/04 – Função hash duplo. Exercícios.
09/04 – Revisão. Exercícios de fixação.
13/04 – 2ª avaliação N1.
15/04 – Introdução aos grafos, representação: listas de adjacência e matriz de adjacência.
16/04 – Resolução da prova.
22/04 – Busca primeiro em largura – BFS.
23/04 – Impressão de percurso – PRINT_PATH.
27/04 – Exercícios de fixação.
29/04 – Busca primeiro em profundidade.
30/04 – Exercícios de fixação.
04/05 – 1ª avaliação N2.
06/05 – Grafos ponderados.
07/05 – Resolução da prova.
11/05 – Classificação de grafos. Conceitos de elementos de grafos.
13/05 – Exercícios de fixação.
14/05 – Avaliação Interdisciplinar – AI.
18/05 – Árvores geradoras mínimas.
20/05 – Algoritmos de Kruskal e Prim.
21/05 – Exercícios de fixação.
25/05 – Caminhos mínimos de fonte única.
27/05 – Algoritmo de Bellman-Ford.
28/05 – Algoritmo de Dijkstra.
01/06 – Exercícios de fixação.
03/06 – Caminhos mínimos de todos os pares.
08/06 – Algoritmo de Floyd-Warshall.
10/06 – Fluxo máximo: Ford-Fulkerson.
11/06 – Implementações de alguns algoritmos.
15/06 – Revisão. Exercícios de fixação.
17/06 – 2ª avaliação N2.
18/06 – Entrega de notas e resultados.
MATERIAL DE APOIO
Softwares diversos e internet.