Conteúdo desta página
Docente
Zanoni Dias
Sala: 23 (IC-1)
Email: zanoni@ic.unicamp.br
Dias e Horários das Aulas e Atendimentos pelo Professor
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.
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.
- Complemente seu estudo bibliográfico com a visualização de animações de algoritmos de ordenação:
- 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
- Paradigma de Divisão e Conquista
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] Introduction to Algorithms: A Creative Approach U. Manber Addison-Wesley, 1989. |
| [2] |  |
[Livro-texto] Algoritmos - Teoria e Prática T. Cormen, C. Leiserson, R. Rivest, C. Stein Editora Campus, 2002. Errata |
| [3] |  |
Introduction to Algorithms T. Cormen, C. Leiserson, R. Rivest, C. Stein McGraw-Hill, 2001. Errata |
Obs: As referências [2] e [3] são equivalentes: a primeira é a versão em Português da segunda (em Inglês).
Outras referências recomendadas:
| [4] |  |
Algorithmics: theory and practice G. Brassard e P. Bratley Prentice-Hall, 1995. |
| [5] |  |
Data Structures with Abstract Data Types and Pascal D. F. Stubbs, N. W. Webre Brooks/Cole, 1989. |
Listas de 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 nos horários de atendimentos. Dúvidas não sanadas geram mais dúvidas.
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.
Tópicos Selecionados para o Exame
As cinco questões do exame serão divididas da seguinte forma:
- 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)
Legenda:
C = Capítulo do Cormen
M = Capítulo do Manber
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.
Notas
Consulte as notas aqui.
Datas Importantes
- 30/07/2003: Início das aulas.
- 03/09/2003: Primeira prova.
- 06/10/2003: Segunda prova.
- 10/11/2003: Terceira prova.
- 10/11/2003: Último dia de aula.
- 26/11/2003: Exame.