Algoritmos e Estruturas de Dados I 

Profa. Isabel Harb Manssour, Turma 127 (2LM 4LM)

 

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.

../Imagens/emban15.png (1469 bytes)

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.

../Imagens/emban15.png (1469 bytes)

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

../Imagens/emban15.png (1469 bytes)

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

·       http://www.eternallyconfuzzled.com

../Imagens/emban15.png (1469 bytes)

Critérios de Avaliação

G1 = (P1 + 2*P2 + 2*MT) / 5

Quanto à P1: Prova escrita, abordando, geralmente, os conteúdos relacionados com as unidades 1 e 2, mas pode envolver também os conteúdos da unidade 3.

Quanto à P2: Prova escrita, abordando todas as unidades.

Quanto à PS: Esta prova escrita será aplicada somente para os alunos que não puderam comparecer nas provas P1 ou P2, sendo que o conteúdo contempla todas as unidades.

Quanto ao MT: Corresponde a média dos trabalhos do semestre, podendo permitir pesos diferentes entre os trabalhos.

OBS. 1: Será estimulada a pesquisa de alguns conteúdos extraclasse e que serão posteriormente avaliados.
OBS. 2: 75% de presença é necessário para aprovação (tanto em G1 como em G2) e o grau mínimo em G1 para realizar G2 é 4.0.

../Imagens/emban15.png (1469 bytes)

Datas das Avaliações

P1

06 / 05 / 2019

P2

01 / 07 / 2019

PS

03 / 07 / 2019

T1

24 / 04 / 2019

T2

20 / 05 / 2019

T3

19-24 / 06 / 2019

G2

10 / 07 / 2019

../Imagens/emban15.png (1469 bytes)

../Imagens/E-MAIL.JPG (3237 bytes) Comentários, dúvidas, sugestões, envie um mail para isabel.manssour at pucrs dot br

../Imagens/emban15.png (1469 bytes)

 Última alteração em 25 de fevereiro de 2019.