Algoritmos e Programação III 

Pegue aqui o segundo trabalho.

E aqui os casos de teste.

Materiais sobre grafos:

Materiais para a aula prática sobre árvores:

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 no texto como se fosse uma explicação para o algoritmo geralmente recebem notas ruins.

Objetivos

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

Ementa

Formalização dos conceitos sobre complexidade e análise de algoritmos utilizando notação assintótica. Descrição da classificação de algoritmos quanto à complexidade e a utilização de contagem de passos para a análise da complexidade de algoritmos. Estudo e análise da complexidade dos algoritmos de pesquisa, ordenação e hashing. Introdução do conceito de classes de problemas. Estudo dos tipos abstratos de dados não-lineares árvore e grafo e sua implementação como objetos. Modelagem e solução de problemas utilizando árvores e grafos.

Programa

  1. Introdução à análise de algoritmos
    1. Ordem de crescimento
    2. Notações Assintóticas
      1. Notação O
      2. Notação Theta
      3. Notação Omega
    3. Tipos de algoritmos: logarítmico, linear, quadrático, exponencial e outros
  2. Ordenação, pesquisa de dados e “hashing”
  3. Pesquisa sequencial e binária
    1. Hashing
    2. Método simples de ordenação
    3. Quicksort
    4. Heaps e heapsort
  4. Árvores
    1. Definições básicas
    2. Representação
    3. Árvores Genéricas, Binárias e de Pesquisa
    4. Caminhamentos: infixado, pré-fixado, pós-fixado
    5. Operações: pesquisa, inserção, remoção
    6. Balanceamento
    7. Aplicações
  5. 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+P2+P3+T1+T2)/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 lista de exercícios sobre árvores binárias está aqui.
    3. Uma lista de exercícios sobre árvores binárias de pesquisa está aqui.
    4. Grafos estão aqui e uma lista de exercícios está aqui.
    5. Métodos de ordenação estão aqui.
     
  2. Aulas em video na Universidade da California at Berkeley
  3. What papers should everyone read? 
  4. Siga no Twitter: CompSciFact 
  5. Um Wikibook inteiro sobre algoritmos. 
  6. Um livro ótimo está aqui. 
  7. E outro livro muito legal está aqui. 
  8. Caso você tenha dificuldade ao escrever os trabalhos:
    1. Dicas sobre o uso de pseudo-código estão aqui, 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. 
    Recomendamos os itens listados em Writing Texts and Abstracts, especialmente as dicas de Schulzrinne e a apresentação de Peyton-Jones. 
  9. Introdução à análise de algoritmos
    1. Material sobre somas (bem legal), na Universidade do Tennessee (Knoxville).
    2. Material sobre análise de algoritmos em Cprogramming.com.
    3. Explicações legais sobre notação O() na Universidade de Wisconsin (Madison).
    4. Notação O() na Wikipedia.
    5. Somas na Univ. da California (Davis).
    6. Problemas P e NP na Univ. da California (Los Angeles).
    7. Mais P e NP na Univ. da California (Irvine).
    8. A reportagem de capa da Communications of the ACM de setembro de 2009, que trata dos últimos resultados sobre P e NP. 
     
  10. 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 legal de algoritmos de ordenação na Univ. de British Columbia. Outra 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.
     
  11. Á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.
     
  12. Grafos
    1. Vocabulário de grafos na Wikipedia e na Univ. do Colorado (Denver).
    2. Algoritmos, grafos e Labirintos.
    3. Mais sobre teoria dos grafos na Wikipedia.
    4. Tutoriais sobre teoria dos grafos na Univ. do Tenessee (Martin).
    5. Faça este teste sobre grafos.
    6. Algoritmos básicos na Worcester Polytechnic.
    7. Repositório de algoritmos na Univ. de Osnabruck.
    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!
     
  13. 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. Estruturas de dados e algoritmos na McGill. Bem legal!!
    4. Design and Analysis na Universidade de Kent.
    5. Catálogo de Algoritmos, do Skiena, em Stony Brook. 

Bibliografia:

Livros texto

Livros complementares

De volta para minha página.

[PUCRS]

[Faculdade de Informática]

[Pós-Graduação em Informática]