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. Material para aulas práticas sobre heaps: aqui.

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

  3. Material para aulas práticas sobre grafos:

  4. Primeira parte da matéria:

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

  6. Grafos

Bibliografia:

Livros texto

Livros complementares