|
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
·
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
|
05 / 04 / 2021
|
|
T1 – parte 2
|
19 / 05 / 2021
|
|
T2
|
07 / 07 / 2021
|
|
G2
|
14 / 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.
|