Algoritmos e Estruturas de Dados I

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.

Objetivos

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

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. Ótimo: o missing semester do MIT com muitos conhecimentos úteis está aqui

  2. Materiais da disciplina: 

    1. Algoritmos e contagem de operações wiki youtube google
    2. Notação assintótica, O, Omega, Theta wiki youtube google
    3. Notação assintótica, crescimento de funções e teste do limite wiki youtube google
    4. TADs e pilhas contíguas wiki youtube google
    5. Uso de encadeamento e referências wiki youtube google
    6. Pilhas com encadeamento + calculadora wiki youtube google
    7. Prática de pilhas wiki youtube google
    8. Filas contíguas circulares wiki youtube google
    9. Filas simplesmente encadeadas wiki youtube google
    10. Filas duplamente encadeadas wiki youtube google
    11. Listas contíguas e encadeadas wiki youtube google
    12. Pesquisa: sequencial e binária wiki youtube google
    13. Árvores binárias e n-árias: introdução e vocabulário wiki youtube google
    14. Árvores binárias e n-árias: representação wiki youtube google
    15. Árvores n-árias: listar, pesquisar, inserir, destruir wiki youtube google
    16. Árvores bin. de pesquisa: listar, pesquisar, inserir wiki youtube google
    17. Árvores bin. de pesquisa: remover wiki youtube google
    18. Prática de árvores wiki youtube google
    19. Classificação: mergesort wiki youtube google
    20. Classificação: quicksort wiki youtube google

    21. Notações estão aqui e uma lista de exercícios sobre notações e contagem de operações está aqui.

    22. Uma micro-classe para desenvolver listas encadeadas está aqui.
    23. Uma micro-classe para desenvolver árvores genéricas está aqui.
    24. Uma lista de exercícios sobre pesquisa e ordenação está aqui.
    25. Uma lista de exercícios sobre pilhas/listas/etc está aqui.
    26. 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
    27. Métodos de ordenação estão aqui
  3. 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(). 
  4. Pilhas, listas e filas

    1. Uma ótima apresentação de Princeton sobre o comportamento e implementação de pilhas, listas e outras estruturas similares. 
  5. Á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!!
  6. 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. 
  7. What papers should everyone read?

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

Livros complementares