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
·
GOODRICH, M. T.; TAMASSIA, R.; MOUNT, D. Data
Structures and Algorithms in C++. 2nd ed., Wiley, 2011.
·
AHO, A. V. Foundations
of computer science. New York: Computer Science Press, 1998.
·
SEDGEWICK, R. Algorithms in C. 3rd Ed,
vol 1. Addison-Wesley, 1998-2002.
·
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
·
http://user.it.uu.se/~arnea/ps/simp.pdf
|
|
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
|
08 / 04 / 2021
|
T1 – parte 2
|
20 / 05 / 2021
|
T2
|
08 / 07 / 2021
|
G2
|
15 / 07 / 2021
|
Comentários, dúvidas, sugestões, envie um mail para isabel.manssour
at pucrs dot br
Última alteração em 25 de fevereiro de 2021.
|