MC448 - Análise de Algoritmos I
Turma B
Segundo Semestre de 2006
Conteúdo desta página:
Notícias de Última Hora
- [17/12/2006] Divulgadas as notas do exame e as médias
finais (veja aqui)
- [28/11/2006] Divulgado o resultado da avaliação
didática (veja aqui)
- [27/11/2006] Divulgadas as notas da segunda prova (veja aqui)
- [09/11/2006] Divulgada lista de exercícios sobre "Todos Caminhos
Mínimos" (veja aqui)
- [08/11/2006] Divulgada lista de exercícios sobre "Caminhos
Mínimos" (veja aqui)
- [31/10/2006] Divulgada lista de exercícios sobre
"Estruturas de dados para conjuntos disjuntos" (veja aqui)
- [25/10/2006] Divulgada lista de exercícios sobre
"Árvore Geradora Mínima" (veja aqui)
- [19/10/2006] Divulgada lista de exercícios sobre
"Algoritmo Elementares em Grafos" (veja aqui)
- [09/10/2006] Divulgada lista de exercícios sobre
"Algoritmos Gulosos" (veja aqui)
- [03/10/2006] Divulgada lista de exercícios sobre
"Programação Dinâmica" (veja aqui)
- [26/09/2006] Divulgada lista de exercícios sobre
"Estatísticas de Ordem" (veja aqui)
- [23/09/2006] Divulgadas as notas da primeira prova (veja aqui)
- [13/09/2006] Divulgada lista de exercícios sobre "Limite
Inferior para Ordenação" e "Ordenação em
Tempo Linear" e lista complementar sobre "Algoritmos de
Ordenação" (veja aqui)
- [09/09/2006] Divulgadas as notas do segundo teste (veja aqui)
- [08/09/2006] Divulgada lista de exercícios sobre
"Algoritmos de Ordenação" (veja aqui)
- [29/08/2006] Divulgada lista de exercícios sobre
"Algoritmos por Indução" e listas complementares sobre
"Indução Matemática" e "Relações de
Recorrência" (veja aqui)
- [26/08/2006] Divulgadas as notas do primeiro teste (veja aqui)
- [16/08/2006] Divulgada a primeira lista complementar de
exercícios (veja aqui)
- [14/08/2006] Divulgadas as primeiras listas de exercícios
(veja aqui)
- [02/08/2006] Início das aulas.
Docente:
Dias, Horários e Local das Aulas
Segundas às 21h e quartas às 19h na sala CB08.
Dias, Horários e Local de
Atendimento
Quartas-feiras, das 18h às 19h, no CB08.
Não haverá horário de atendimento na semana de
prova, teste ou exame
Programa:
- Introdução à Análise de Algoritmos
- Indução Matemática
- Complexidade de Algoritmos.
- Relações de Recorrência
- Construção de Algortimos por Indução
- Algoritmos de Ordenação
- Limite Inferior para Ordenação
- Estatísticas de Ordem
- Estruturas de Dados para Conjuntos Disjuntos.
- Programação Dinaâmica
- Análise Amortizada
- Algoritmos em Grafos
Referências Bibliográficas
[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.
[Livro-texto]
T. Cormen, C. Leiserson, R. Rivest,
C. Stein, Algoritmos - Teoria e
Prática, 2002.
Errata
T. Cormen, C. Leiserson,
R. Rivest, C. Stein, Introduction to
Algorithms, McGraw-Hill,
2001.
Errata
-
T. Cormen, C. Leiserson,
R. Rivest, Introduction to
Algorithms , McGraw-Hill,
1990.
Outras referências
recomendadas:
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, Addison-Wesley, 1974.
Material Didático:
O material didático abaixo foi preparado pelo professor Cid Carvalho de Souza
especialmente para esta disciplina.
Transparências (4 por página):
Uma cópia deste material pode ser encontrada no Xerox da
Dança (com a Mara).
Avaliação:
A avaliação será baseada nas notas de duas
provas e de quatro testes denotados respectivamente por P1,
P2, T1, T2, T3 e T4.
As provas terão 2 horas de duração e
cobrirão toda a matéria. Os teste terão 30
minutos de duração e serão realizados no
final das aulas previamente marcadas (veja datas abaixo). Os testes
serão fortemente baseados nos exercícios das listas
divulgadas até uma semana antes da data do teste.
A média do semestre M
será calculada da seguinte forma:
- Calcule: T = (T1 + T2 + T3 + T4)/4
- Calcule: M = (2*P1 + 2*P2 + T)/5
Se M < 5.0, o aluno deverá fazer o exame. Sendo
E a nota do exame, o
cálculo da média final da
disciplina (MF) será feito da seguinte forma:
- Se o aluno não compareceu ao exame
então MF = M.
-
Caso contrário, MF = (M + E)/2
Se (MF ≥ 5.0) então o aluno APROVOU-SE. Caso contrário,
ele REPROVOU-SE.
Observações:
- Não haverá provas ou testes substitutivos.
- Todas as provas, os testes e o exame serão realizados sem
consulta.
- Qualquer tentativa de fraude nas provas, nos testes ou no exame
implicará em média final do semestre MF = 0
(ZERO) para todos os envolvidos, sem prejuízo de outras
sanções.
- Não será cobrada presença em sala de
aula. Todos os alunos receberão 100% de presença,
independente da nota final obtida (não será atribuido o
conceito "Reprovado por Falta" em nenhum caso).
Datas Importantes:
-
Calendário oficial da DAC: Visite esta página para
saber quais as datas de desistência de matrícula em
disciplina e dos períodos sem atividades.
- 02/08/2006: Início das aulas.
- 23/08/2006: Primeiro teste (T1).
- 06/09/2006: Segundo teste (T2).
- 20/09/2006: Primeira prova (P1).
- 18/10/2006: Terceiro teste (T3).
- 01/11/2006: Quarto teste (T4).
- 22/11/2006: Segunda prova (P2).
- 13/12/2006: Exame (E).