Algoritmos e Estruturas de Dados II

Algoritmos e Estruturas de Dados II

oliveira(AT)inf.pucrs.br

Critérios de correção para os trabalhos.

Os trabalhos tem a forma de ARTIGOS (pegue um exemplo). Artigos que incluírem o código do programa e mal dão alguma explicação para o algoritmo geralmente recebem notas que não são legais. :(

Aqui tem um template para relatórios no Overleaf.

Caso você tenha dificuldade na hora de escrever os trabalhos:

  1. Dicas sobre o uso de pseudo-código estão aqui e aqui.

  2. Também temos o livro do Zobel na biblioteca. Use-o!!

  3. Um repositório de links existe na Iowa State. 

  4. Recomendamos os itens listados em Writing Texts and Abstracts, especialmente as dicas de Schulzrinne e a apresentação de Peyton-Jones. 

E aqui o texto explicando o método para encontrar as funções para algoritmos desconhecidos. Este não é um trabalho da nossa disciplina, está aqui apenas para leitura!

Objetivos

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

  1. Conhecer estruturas de dados avançadas: filas de prioridades, mapas e conjuntos;

  2. Conhecer grafos, suas formas de representação e seus algoritmos mais importantes;

  3. Indicar as estruturas de dados que melhor se adaptam para a solução de um determinado problema;

  4. Analisar e selecionar o algoritmo mais eficiente para a solução de um determinado problema.

Ementa

Projeto e análise de algoritmos e estruturas de dados avançadas: filas com prioridade, heaps, tabelas de hash, mapas, dicionários, conjuntos e grafos. Discussão, análise e raciocínio sobre a complexidade de algoritmos e implementações correspondentes.

Programa

  1. Revisão de complexidade

  2. Estruturas avançadas

    1. Filas de prioridade

    2. Tabelas de espalhamento (hashing)

    3. Conjuntos

    4. Aplicações: dicionários

    5. Aplicações: quadtrees

    6. Aplicações: codificação de Huffman

    7. Aplicações: árvores B

  3. Grafos

    1. Definições básicas

    2. Representação e implementação

    3. Grafos ponderados

    4. Caminhamentos: largura e profundidade

    5. Operações sobre grafos

      1. Detecção de Ciclos e Ordenação Topológica

      2. Detecção de Componentes

      3. Árvores de cobertura mínima

      4. Caminhos Mínimos: Dijkstra e Floyd

      5. Fluxos

    6. Caminho crítico

    7. Aplicações

Avaliação

G1 = ( 3 * ( P1 + P2 ) + 2 * ( T1 + T2 ) / 10

Materiais

  1. O livro excelente do Sedgewick com praticamente todos os conteúdos de Algoritmos I e Algoritmos II está aqui e aqui, com texto, slides e vídeos.

  2. Este livro é muito bom! Leia com calma e cuidado!!

  3. Os materiais do livro do Sedgewick (que é muito bom!!!) estão aqui.

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

  5. Ótimo: o missing semester do MIT com muitos conhecimentos úteis está aqui

  6. Notação O wiki youtube google

  7. Análise de algoritmos quicksort mergesort wiki youtube google
  8. Heap sift-up sift-down wiki youtube google
  9. Análise do heapsort wiki youtube google
  10. Pesquisa sequencial e pesquisa binária tabelas hash wiki youtube google
  11. Dicionários Union Find wiki youtube google
  12. Tries compressed tries wiki youtube google
  13. Bloom filter Árvore B wiki youtube google
  14. Codificação de Huffman wiki youtube google
  15. Quadtrees wiki youtube google
  16. Grafos: introdução vocabulário exemplos wiki youtube google
  17. Matrizes de adjacência listas de adjacência wiki youtube google
  18. Dicionários wiki youtube google
  19. Caminhamento em grafos wiki youtube google
  20. Detecção de ciclos e problema da planilha wiki youtube google
  21. Organização topológica wiki youtube google
  22. MST Prim Kruskal wiki youtube google
  23. Algoritmo de Dijkstra wiki youtube google
  24. Algoritmo de caminho crítico wiki youtube google
  25. Algoritmo de Ford-Fulkerson wiki youtube google

  26. Algoritmo de Floyd-Warshal wiki youtube google

  27. Material para aulas práticas sobre heaps: aqui.

  28. Applets mostrando o funcionamento de várias estruturas vistas em aula: aqui.

  29. Material para aulas práticas sobre grafos:

  30. Primeira parte da matéria:

  31. Uma análise muito legal do processo de construção de um heap para o heapsort .

  32. Grafos

Bibliografia:

Livros texto

Livros complementares