MC448 - Projeto e Análise de Algoritmos I
Segundo semestre de 2009
Prof. Orlando Lee (Sala 04 - Prédio IC01)
Conteúdo desta página
Avisos importantes
Veja as notas das provas aqui.
- 23/12: Médias finais disponíveis.
- 17/12: ATENÇÃO! O Exame será dia 22/12 às 10h na Sala CB01. O Exame será aplicado pelo Prof. Sandro Rigo. O Exame cobrirá toda a matéria vista na disciplina.
- 14/12: notas e médias finais disponíveis. Revisão da prova será amanhã 14/12 às 10:30h até 11:00h em minha sala (sala 4 IC01). Não haverá revisão das outras provas.
- 24/11: dia 1/12 haverá um teste baseado nas listas 9,10 e 11. O teste não tem valor nenhum na média final.
- 24/11: listas de exercícios 9, 10 e 11 disponíveis.
- 12/11: notas da segunda prova disponíveis.
- 27/10: Atualizei a Lista 6 com exercícios sobre algoritmos lineares de ordenação.
- 24/10: Havia um erro de digitação no algoritmo MinimoMultiplicações nos slides de programação dinâmica. Consertado. Modifiquei um pouco os slides de algoritmos gulosos.
- 22/10: Lista de exercícios 7 e 8 disponíveis!
- 09/10: Lista de exercícios 6 disponível!
- 05/10: notas da primeira prova aqui. Revisão até o dia 15/10 na minha sala no horário de atendimento.
- 16/09: no dia 17/09 (quinta-feira) passarei um teste consistindo de exercícios (nível de dificuldade semelhante a uma questão da prova) para os alunos resolverem em sala. O teste não tem valor nenhum na média final.
- 14/09: Lista de exercícios 4 e 5 disponíveis!
- 8/09: atualizei os slides de projeto por indução incluindo um pouco mais de explicação de como inserir um novo prédio em um skyline.
- 31/08: listas de exercícios disponibilizadas!
- 18/08: algumas informações sobre a gripe H1N1 estão aqui. Informações atualizadas sobre a doença podem ser encontradas nos sites do CECOM (UNICAMP) e do Ministério da Saúde.
- 17/08: IMPORTANTE! Consulte esta seção freqüentemente ao longo do semestre!
Horário das aulas e atendimento
- Aulas
- terça, 10-12h, sala CB16.
- quinta, 10-12h, sala CB14.
- Atendimento: quinta-feira, 18h às 19h na sala 4 do IC01
Observações:
- se passados 15 minutos do horário de início do
atendimento, não houver nenhum aluno presente,
o atendimento fica automaticamente cancelado.
- não haverá atendimento em semana de prova.
Objetivos
O que será visto no curso:
- Conceito de medida de desempenho assintótico de um algoritmo
- Como medir o desempenho de um algoritmo de forma abstrata
- Projeto de algoritmos eficientes e elegantes para vários
problemas computacionais básicos
- Prova de correção de algoritmos iterativos e seus invariantes
- Natureza recursiva de vários problemas e como explorá-la para projetar
algoritmos eficientes
- Vários algoritmos e técnicas para problemas de natureza computacional
Programa da disciplina
- Algoritmos, modelos de computação, análise de complexidade
- Somas, crescimento de funções e análise assintótica
- Recorrências e métodos de resolução
- Divisão-e-conquista
- Indução matemática e projeto de algoritmos por indução
- Invariantes de algoritmos iterativos
- Algoritmos de ordenação: selection, insertion e bubble sort
- Algoritmos de ordenação: heapsort
- Filas de prioridade
- Algoritmos de ordenação: mergesort e quicksort
- Cota inferior de ordenação
- Algoritmos lineares para ordenação
- Algoritmos de seleção (order statistics)
- Programação dinâmica
- Algoritmos gulosos
- Análise amortizada
- Estrutura de dados para conjuntos disjuntos
- Grafos: conceitos, busca em largura e busca em profundidade
- Grafos: ordenação topológica
- Grafos: conexidade forte
- Grafos: árvore geradora mínima
- Grafos: caminhos mínimos
Listas de Exercícios
Durante o semestre serão disponibilizados várias listas de exercícios. A entrega destes não será cobrada.
Material didático
O material didático (slides) que será usado neste curso foi preparado pelo professor Cid Carvalho de Souza e por Cândida Nunes da Silva. O que disponibilizarei aqui será basicamente o mesmo com algumas adaptações, modificações e erros introduzidos por mim.
Deixo claro que o material serve principalmente como guia e de nenhum modo deve ser usado como única fonte de estudos. Para isso, deve-se consultar a bibliografia.
Os slides estão em arquivos no formato PDF com 4 slides por página.
Avaliação
A avaliação se baseará em três provas P1.
Denote por P1, P2, e P3 as notas das provas.
A média do semestre M será calculada da seguinte forma:
M = (3*P1 + 3*P2 + 4*P3)/ 10 .
Observações:
- Não haverá provas substitutivas.
- Todas as provas do curso serão realizadas sem consulta.
- Qualquer tipo de fraude detectada durante ou depois de uma prova acarretará
em média final igual a zero para todos os envolvidos sem prejuízo de outras sanções regimentais.
Datas importantes
- Para se inteirar dos feriados, prazos etc,
consulte o
calendário da DAC de 2009.
- 18/08: início das aulas.
- 22/09: primeira prova
- 24/09: Congresso de Iniciação Científica - não haverá aula.
- 29/09 e 1/10: Semana de Comemoração dos 40 anos de Computação - não haverá aulas.
- 20/10: Reunião de Avaliação de Cursos - não haverá aula.
- 29/10: segunda prova
- 10/12: terceira prova
- 22/12: Exame
Referências Bibliográficas
O Livro-texto do curso é a referência [2,3,4]. A referência [1] será usada em alguns tópicos e para elaboração de exercícios.
[Livro-texto]
U. Manber, Introduction to Algorithms: A Creative
Approach, Addison-Wesley,
1989.
As seguintes referências são equivalentes.
A referência [4] é a primeira edição do livro.
A segunda edição possui versões em inglês [3] e português [2].
Verifique a equivalência de
capítulos entre as edições
(material preparado pelo Prof.
Zanoni Dias).
[Livro-texto]
T. Cormen, C. Leiserson, R. Rivest,
C. Stein, Algoritmos - Teoria e
Prática, 2002.
T. Cormen, C. Leiserson,
R. Rivest, C. Stein, Introduction to
Algorithms, McGraw-Hill,
2001.
-
T. Cormen, C. Leiserson,
R. Rivest, Introduction to
Algorithms , McGraw-Hill, 1990.
Um mapeamento dos tópicos cobertos em sala de aula com os
Capítulos dos livros-texto é mostrado na tabela abaixo:
| Assunto |
Cormen (referências [2]/[3])(capítulo/seção) |
Manber (capítulo/seção) |
| Crescimento de funções |
3 |
3.1, 3.2 |
| Somas |
Apêndice A |
3.4 |
| Fórmulas de Recorrência |
4 |
3.5, 3.6 |
| Fundamentos Básicos |
Apêndice B, 10 e 21 (21.1 a 21.3) |
4 |
| Indução Matemática |
|
2 e 5 |
| Ordenação |
6, 7 e 8 |
6.1 a 6.4 |
| Estatísticas de Ordem |
9 |
6.5 |
| Busca Binária |
|
6.1 a 6.3 |
| Algoritmos Gulosos |
161 a 163 |
6.6 |
| Programação dinâmica |
15 |
5.10 |
| Análise amortizada |
17 |
|
| Estruturas de dados para conjuntos disjuntos |
21 |
4.5 |
| Algoritmos básicos em Grafos |
22.1 a 22.4 |
7.3 a 7.4 |
| Árvore Geradora Mínima |
23 |
7.6 |
| Caminhos Mínimos |
24.1 a 24.3 e 25.1 a 25.2 |
7.5, 7.7 e 7.8 |
Aqui você encontrará uma errata
da versão em português (referência [2]) do livro do Cormen,
Leiserson, Rivest e Stein (referência [3]), preparada pelos
Professores João
Meidanis e Zanoni Dias com
auxílio de alunos que cursaram esta disciplina anteriormente.
A página oficial do MIT Press contendo a
errata da referência [3] pode ser encontrada
aqui.
Além destes livros, existem nas
bibliotecas da UNICAMP outras excelentes obras sobre os
assuntos que serão referenciados na sala de aula. Dentre
estas, destacamos as seguintes referências:
G. Brassard e P. Bratley,
Algorithmics: theory and
practice, Prentice-Hall,
1995.
N. Ziviani, Projeto de Algoritmos - 2a edição, Thomson, 2004. 
A. Aho, J. Hopcroft,
J. Ullman, The Design and Analysis of
Computer Algorithms, Addison-Wesley,
1974. 
D. E. Knuth, The Art of Computer Programming, Addison-Wesley, 1974. 
J. L. Szwarcfiter,
Grafos e Algoritmos Computacionais
Editora Campus, 1984.