Algoritmos e Estruturas de Dados I

oliveira(AT)inf.pucrs.br

Na universidade de Yale (e em muitos outros lugares) existem reports que podem servir de inspiração para os seus relatórios. Eu acho estes aqui, aqui e aqui legais. Alguns destes relatórios tem uma página de apresentação que não é necessária para nossa disciplina.

E aqui tem uma checklist pra você saber se está indo por um bom caminho.

• Uma micro-classe para desenvolver pilhas está aqui.

• Uma micro-classe para desenvolver listas baseadas em vetores.

• Uma micro-classe para desenvolver listas encadeadas.

• Uma micro-classe para desenvolver árvores genéricas está aqui.

Objetivos

O cumprimento da disciplina busca dar ao aluno, ao final do semestre, condições de:

• Conhecer e utilizar as técnicas fundamentais para avaliar a complexidade de algoritmos.
• Conhecer e diferenciar as estruturas de dados: listas, filas, pilhas, conjuntos, árvores.
• Manipular estas estruturas de dados por meio de algoritmos.
• Selecionar e construir estruturas de dados adequadas para aplicações específicas, bem como modelar estas aplicações.
• 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.

Programa

1. Desempenho de algoritmos
   1. Contagem de operações
   2. Notações O, Omega e Theta
2. Estruturas lineares
   1. Estruturas contíguas X Estruturas encadeadas
   2. Coleções e suas operações de acesso
      1. Listas
      2. Pilhas
      3. Filas
   3. Conjuntos

3. Classificação e pesquisa

   1. Pesquisa sequencial X pesquisa binária
   2. Classificação de dados
      1. Mergesort
      2. Quicksort

4. Árvores

   1. Definições e representação
   2. Árvores genéricas
   3. Árvores binárias de pesquisa
   4. Operações: caminhamento, pesquisa, inserção, remoção
   5. Árvores balanceadas e sua eficiência
   6. Tries

Avaliação

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

Materiais

1. Materiais da disciplina: 

   1. Notações estão aqui e uma lista de exercícios sobre notações e contagem de operações está aqui.
   2. Uma micro-classe para desenvolver listas encadeadas está aqui.
   3. Uma micro-classe para desenvolver árvores genéricas está aqui.
   4. Uma lista de exercícios sobre pesquisa e ordenação está aqui.
   5. Uma lista de exercícios sobre pilhas/listas/etc está aqui.
   6. Material para aula prática sobre árvores binárias de pesquisa:
      • A lista de exercícios está aqui.
      • Uma micro-classe para árvores binárias de pesquisa está aqui
   7. Métodos de ordenação estão aqui. 

2. Introdução à análise de algoritmos

   1. Material sobre somas (bem legal), na Universidade do Tennessee (Knoxville) .
   2. Somas na Univ. da California (Davis) .
   3. Um material ótimo chamado A Gentle Introduction to Algorithm Complexity Analysis. Muito bom, e você pode mandar um mail para o autor (Dionysis Zindros) agradecendo!
   4. Material sobre análise de algoritmos em Cprogramming.com.
   5. Notação O() na Wikipedia.
   6. A grande tabela sobre notação O(). 

3. Pilhas, listas e filas

   1. Uma ótima apresentação de Princeton sobre o comportamento e implementação de pilhas, listas e outras estruturas similares. 

4. Árvores

   1. Um site que possui animações de operações em árvores binárias, AVL e B-trees: aqui .
   2. Um site bem legal com os algoritmos sobre árvores está aqui.
   3. Material simples mas interessante sobre árvores está aqui.
   4. Alguns tutoriais ótimos sobre arvores binárias, árvores AVL e árvores de Andersson estão aqui. O site original não existe mais, mas o archive.org manteve um espelho. Aproveite!!

5. Ordenação e pesquisa de dados

   1. Um otimo texto sobre hashing sendo usado em criptografia no Unixwiz.
   2. Animações de algoritmos de ordenação
   3. Uma animação que inclui algoritmos paralelos no RIT.
   4. Algoritmos de ordenação na Wikipedia.
   5. Algoritmos de ordenação dançantes !!
   6. Uma coleção de algoritmos, incluindo ordenação. 

6. What papers should everyone read?

7. Um pouco de tudo:

   1. Um Wikibook inteiro sobre algoritmos.

   2. Aulas em video na Universidade da California at Berkeley

   3. Um livro ótimo está aqui.

   4. Uma série de aulas do MIT (em inglês), sobre vários tópicos da disciplina e outros assuntos.

   5. Este livro é muito bom! Leia com calma e cuidado!!
   6. Um catálogo de cursos sobre algoritmos na Universidade de Pittsburgh. Fonte de outros links!
   7. Recursão, explicada em um material de Stanford. Leia tudo!!
   8. Estruturas de dados e algoritmos na McGill .Bem legal!!
   9. Design and Analysis na Universidade de Kent.
   10. Algoritmos do Skiena. 

Bibliografia:

Livros texto

• 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.

Livros complementares

• 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.