Objetivos
O
aluno ao término da disciplina deverá ser capaz de:
1. Conhecer e utilizar as técnicas
fundamentais para avaliar a complexidade de algoritmos.
2. Conhecer e diferenciar as
estruturas de dados: listas, filas, pilhas, conjuntos, árvores.
3. Manipular estas estruturas de
dados por meio de algoritmos.
4. Selecionar e construir estruturas
de dados adequadas para aplicações específicas, bem como modelar estas
aplicações.
5. Aplicar algoritmos de ordenação e
de pesquisa na solução de problemas.

Ementa
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. Discussão, análise e
raciocínio sobre a complexidade de algoritmos e implementações
correspondentes.

Conteúdo
1) DESEMPENHO DE ALGORITMOS
1.1. Complexidade de algoritmos
-1.1.1 Contagem de operações
-1.1.2 Notação O, Omega
e Theta
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
2.3. Conjuntos
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. Tries

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
|
06 / 10 / 2020
|
T1 – parte 2
|
27 / 10 / 2020
|
T2
|
01 e 03 / 12 / 2020
|
G2
|
10 / 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.
|