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 aqui 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. :(

Consulte o cronograma.

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 = ( P1 + 2 * P2 + 2 * MT)/5

Materiais

  1. Materiais da disciplina: 
  2. Material para aulas práticas sobre heaps: aqui.
  3. Material para aulas práticas sobre grafos:  
  4. Um pouco de tudo:
    1. Uma série de aulas do MIT (em inglês), sobre vários tópicos da disciplina e outros assuntos.
    2. Um catálogo de cursos sobre algoritmos na Universidade de Pittsburgh. Fonte de outros links!
    3. Um livro inteiro sobre recursão.
    4. Recursão, explicada em um material de Stanford. Leia tudo!!
    5. Estruturas de dados e algoritmos na McGill. Bem legal!!
    6. Design and Analysis na Universidade de Kent.
    7. Algoritmos do Skiena.
    8. Aulas em video na Universidade da California at Berkeley 
    9. What papers should everyone read? 
    10. Siga no Twitter: CompSciFact 
    11. Um Wikibook inteiro sobre algoritmos.  
    12. Um livro ótimo está aqui.
    13. Caso você tenha dificuldade ao 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. 
  5. Uma análise muito legal do processo de construção de um heap para o heapsort .
  6. Grafos
    1. Vocabulário de grafos na Wikipedia.
    2. Uma introdução muito legal da USP.
    3. Algoritmos, grafos e labirintos.
    4. Uma apresentação sobre grafos feita pelo Paul van Dooren (Univ. Católica de Louvain).
    5. Outra apresentação (em português) feita pelo Antonio Loureiro (UFMG).
    6. Este livro é muito bom! Leia com calma e cuidado!!
    7. Tutoriais sobre teoria dos grafos na Univ. do Tenessee (Martin).
    8. Um livro inteiro on-line: Bondy & Murty. Contém aplicações, mas este é um livro de Matemática, não de Informática. Também é meio antigo, então pode não ser a melhor escolha do mundo... procure livros mais interessantes no catálogo da biblioteca!
 

Bibliografia:

Livros texto

Livros complementares