Objetivos
O
aluno ao término da disciplina deverá ser capaz de:
1. Conhecer e diferenciar as
estruturas de dados: listas, filas, pilhas, árvores.
2. Manipular estruturas de dados por
meio de algoritmos.
3. Selecionar e construir estruturas
de dados adequadas para aplicações específicas, bem como modelar estas
aplicações utilizando a noção de orientação a objetos.
4. Aplicar algoritmos de ordenação e
de pesquisa na solução de problemas usando abordagem orientada a objetos.
5. Compreender conceitos básicos
relacionados a complexidade e análise de algoritmos.

Ementa
Estudo de complexidade, análise e classificação
de algoritmos utilizando notação assintótica. Construção e raciocínio sobre
diferentes algoritmos e implementações para estruturas de dados lineares e
hierárquicas: listas, filas, pilhas e árvores. Exame da adequação destes
algoritmos na solução de diversas classes de problemas. Construção de
algoritmos e implementações para problemas de ordenação e pesquisa.

Conteúdo
1) DESEMPENHO DE ALGORITMOS
1.1. Noções de complexidade
-1.1.1 Contagem de operações
-1.1.2 Notação O()
2) ESTRUTURAS LINEARES
2.1. Estruturas contíguas X Estruturas
encadeadas
2.2. Coleções e suas operações de acesso
-2.2.1 Listas
-2.2.2 Pilhas
-2.2.3 Filas
3) CLASSIFICAÇÃO E PESQUISA
3.1. Pesquisa sequencial X pesquisa binária
3.2. Classificação de dados
-3.2.1 Insertion Sort
-3.2.2 Mergesort
-3.2.3 Quicksort
-3.2.4 Limite inferior para ordenação por
comparações O( n log(n) )
-3.2.5 Algoritmos que não são baseados em
comparação
4) ÁRVORES
4.1. Definições e representação
4.2. Árvores genéricas
4.3. Árvores binárias de pesquisa
4.4. Operações: caminhamento, pesquisa, inserção, remoção
4.5. Árvores balanceadas e sua eficiência
4.6. Heaps
(com vetores) e heapsort

Bibliografia
Básica
·
CORMEN, T. H. Algoritmos – teoria e prática. 3ª
ed., Rio de Janeiro: Elsevier-Campus, 2012.
·
ELLIS, H.; SAHNI, S.; RAJASEKARAN, S. Computer algorithms. Silicon Press, 2007.
·
GOODRICH, M. T.; TAMASSIA,
R. Estruturas de dados e
algoritmos em Java. 5ª ed., Porto Alegre: Bookman, 2013.
Complementar
·
AHO, A. V. Foundations
of computer science. New York: Computer Science Press, 1998.
·
GERSTING, J. L. Fundamentos matemáticos para ciência
da computação: um tratamento moderno de matemática discreta. 5. ed.,
Rio de Janeiro: LTC, 2004.
·
LEVITIN, A. Introduction
to the design and analysis of algorithms. Boston:
Addison-Wesley, 2003.
·
MCALLISTER, W. Data structures and algorithms using Java. 1 ed., Boston:
Jones and Bartlett, 2009.
·
RAWLINS, G. J. E. Compared to what? An introduction to the analysis of algorithms.
New York: Computer Science Press,
1992.
Recursos WEB
·
https://eternallyconfuzzled.com/andersson-trees-c-a-balanced-binary-search-tree-using-split-and-skew
|
|

Critérios de Avaliação
G1 = (T1 +
T2) / 2
Quanto ao T1: Trabalho
prático, extraclasse, abordando, geralmente, os conteúdos relacionados com as
unidades 1 e 2, mas pode envolver também os conteúdos da unidade 3.
Quanto ao T2: Trabalho
prático, extraclasse, abordando, geralmente, os conteúdos relacionados com a unidade
4.
OBS. 1:
Será estimulada a pesquisa de alguns conteúdos extraclasse e que serão
posteriormente avaliados.
OBS. 2: O grau mínimo
em G1 para realizar G2 é 4.0.

Datas das Avaliações
T1 – parte 1
|
07 / 10 / 2020
|
T1 – parte 2
|
28 / 10 / 2020
|
T2
|
07 / 12 / 2020
|
G2
|
14 / 12 / 2020
|

Comentários, dúvidas, sugestões, envie um mail para isabel.manssour
at pucrs dot br

Última alteração em 07 de agosto de 2020.
|