MC438 - Análise de Algoritmos I

Aulas e Atendimento

• As aulas serão às segundas-feiras 21h00 às 23h00 e quartas-feiras 19h00 às 21h00.
• Os atendimentos serão marcados pelo docente e anunciados em classe.

Aulas de Exercícios e Atendimento pelo Monitor

• Haverá algumas aulas de exercícios que serão dadas pelo Monitor (PED: Fábio P. Selmi-Dei).
• As aulas de exercícios e os atendimentos dados pelo Monitor serão às terças e quintas-feiras de 17h00 às 19h00 na sala PB-07.

Avaliação

Haverá três provas (P1, P2, P3) nas datas indicadas ao final deste documento. Cada prova será em classe e terá duração de 120 minutos. A média final será a média ponderada de P1, P2 e P3 com pesos iguais a 1, 2, 3, respectivamente. Não serão ministradas provas antecipadas nem substitutivas.

Aviso: Qualquer tentativa de cola ou fraude, detetada durante uma prova ou posteriormente, acarretará nota zero naquela prova para todos os implicados, além das sansões regimentais, a critério do docente.

Tabela de Notas está disponível aqui.

Tópicos Selecionados para o Exame

• Prova 1 - Uma questão entre os dois tópicos abaixo:
  Crescimento de Funções: C1 e M2
  Indução Matemática: M3

• Prova 2 - Duas questões entre os três tópicos:
  Recorrência: C4
  Estrutura de Dados: C11, C13 e C22 (22.1, 22.2, 22.3)
  Algoritmos por indução: M5

• Prova 3 - Uma questão de cada tópico:
  Algoritmos de Ordenação: C7 (7.1, 7.2, 7.3, 7.4), C8 (8.1, 8.2), C9, C10 (10.1), M6 (6.1, 6.2, 6.3, 6.4, 6.5)
  Grafos: C23, C24, C25 (25.1, 25.2) e M7 (7.1, 7.3, 7.4, 7.5, 7.6, 7.10)

Avisos sobre atendimento:

• Professor: dia 19/11/2003, das 18h as 20h na sala de aula (IC-85).
• Monitor: dia 25/11/2003, véspera do exame, das 17h as 19h na sala PB-07.

Exercícios

Listas de exercícios serão atribuídas ao longo do semestre. Além de servir para maior fixação do material apresentado em classe, o conteúdo dos exercícios é considerado parte integrante do material visto e será assumido como parte da matéria coberta. Como as listas não farão parte da avaliação, suas soluções não serão coletadas. Os alunos são encorajados a resolver todos os exercícios individualmente e, só posteriormente, realizar discussão em grupo. Quaisquer dificuldades devem ser prontamente discutidas com o Professor ou com o Monitor nos horários de atendimentos. Dúvidas não sanadas geram mais dúvidas.

Tópicos a serem cobertos

Tópicos previstos (outros poderão ser acrescentados aqui ao longo do semestre):

• Revisão de técnicas de demonstração.
• Revisão de indução.: veja capítulo 3 de [1]. (Veja também Notas de Aula - Indução.)
  • Princípio da indução fraca, forte e reversa
  • Conceitos e exemplos
• Classes de funções: veja bibliografia [2].
• Modelos, reduções e projeto por indução.
  • Modelos computacionais.
  • Reduções entre problemas: conceito e suas aplicações para estabelecimento de quotas inferiores e superiores, com exemplos (Veja Notas de Aula - Reduções.)
  • Projeto de algoritmos por indução
• Somatórios e relações de recorrência: veja capítulo 3 de [1] e capítulos 3 e 4 de [2].
  • Breve revisão de somatórios mais frequentemente usados
  • Definição da função lg* n
  • Relações de recorrência: conceito, técnicas de solução e teorema master
  • Exemplos
  • Union-find (e análise usando lg* n).
• Revisão de estruturas de dados: veja capítulo 4 de [1], capítulos 11, 13, 22 de [2] e também [9].
  • Leitura individual: vetores, listas ligadas, pilhas, filas
  • Árvores balanceadas de busca (binária e B)
  • Heap (inclusive algoritmo linear para construção)
• Ordenação e estatísticas de ordem: veja capítulo 6 de [1] e capítulos 7, 8, 9, 10 de [2].
  • Complemente seu estudo bibliográfico com a visualização de animações de algoritmos de ordenação:
    • No ASTRAL o projeto Sort.exe (para MS-Windows) contém diversos algoritmos.
    • Nesta página de Applets há animações também interessantes.
    • Se você quiser uma fonte extensiva de animações de algoritmos (não só de ordenação) visite CCAA.
• Algoritmos em Grafos: veja capítulo 7 de [1] e capítulos 23 a 27 de [2].
  • Representação de grafos
  • Busca em largura e em profundidade
  • Ordenação topológica
  • Caminhos mínimos
  • Árvores geradoras mínimas
  • Problemas de fluxos
  • Casamentos máximos
  • Exemplos
• Paradigmas de projeto de algoritmos: veja capítulos 3, 4, e 5 de [3].
  • Paradigma de Divisão e Conquista
    • Exemplos
  • Paradigma de Programação Dinâmica
    • Exemplos
  • Paradigma Guloso
    • Exemplos

Slides de algumas aulas ou notas sobre tópicos específicos poderão ser disponibilizados aqui. (Verifique esta página regularmente.)

Referências Bibliográficas

1. [Livro-texto] U. Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley, 478pgs.
   
   Os seguintes dois livros são equivalentes: [3.] é em Inglês e [2.] é sua tradução para Português.
2. [Livro-texto] T. Cormen, C. Leiserson, R. Rivest, C. Stein, Algoritmos - Teoria e Prática (tradução da 2ª Ed. Americana), 2002, 936 pgs.
3. T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, McGraw-Hill, 1180 pgs.
   
   Outras referências recomendadas:
4. G. Brassard e P. Bratley, Algorithmics: theory and practice, Prentice-Hall, 524 pgs.
5. D. F. Stubbs, N. W. Webre, Data Structures with Abstract Data Types and Pascal, Brooks/Cole, 480pgs.

Datas importantes