MC448 - Análise de Algoritmos I
Turma #
Segundo Semestre de 2012
Conteúdo desta página:
Notícias de Última Hora
- [14/12/2012] Divulgadas
as notas da Prova de
Proficiência.
- [27/11/2012] O último horário de atendimento do semestre será
realizado no dia 04/12/2012 (terça-feira), das 17h às 18h, na sala 23
do IC. Interessados no atendimento, segundo
as regras pré-estabelecidas para os
atendimentos, devem entrar em contato com o professor no dia
anterior, confirmando o interesse no atendimento.
- [24/11/2012] Divulgadas as notas da segunda
prova. As provas estarão disponíveis para consulta no dia 27 de
novembro de 2012 (terça-feira), das 17h às 18h, na sala 23 do
IC.
- [22/09/2012] Divulgadas as notas da primeira
prova. As provas estarão disponíveis para consulta nos horários
de atendimento dos dias 26 de setembro e 03 de outubro de 2012.
- [31/07/2012] Site da disciplina no ar.
Docente:
Dias, Horários e Local de
Atendimento
Quartas-feiras, das 17h às 18h, na sala 23 do IC-1.
Importante:
- O atendimento deve ser confirmado com 24h de antecedência, por
email. Você deve enviar uma mensagem com o subject/assunto "[MC448]
Horário de Atendimento" confirmando sua intenção de usar o
horário de atendimento no horário acima (único
disponível). Você receberá um email confirmando o
atendimento.
- Só serão atendidos alunos que confirmarem o atendimento, de
acordo com a regra acima.
- Alunos que confirmarem o interesse pelo horário de atendimento,
mas não comparecerem ao mesmo terão um desconto de 1,0 (um)
ponto na média (M) da disciplina.
- Se você confirmou o interesse pelo horário de atendimento,
você deve comparecer a sala indicada até no máximo às
17:30h. Após este horário será aplicada a regra acima e o
horário de atendimento será encerrado.
- Se não houver nenhum atendimento confirmado, o horário
estará cancelado.
- Não haverá horário de atendimento na semana
das provas ou do 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
- Divisão e Conquista
- Algoritmos de Ordenação
- Limite Inferior para Ordenação
- Ordenação em Tempo Linear
- Estatísticas de Ordem
- Programação Dinâmica
- Algoritmos Gulosos
- Noções Básica de Grafos
- Buscas em Grafos
- Ordenação Topológica
- Árvore Geradora Mínima
- Caminhos Mínimos
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.
Material Didático:
Avaliação:
A avaliação será baseada nas notas de duas provas
denotadas respectivamente por P1 e P2.
Os seguintes tópicos serão avaliado em cada uma das provas.
Prova 1:
- 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
- Divisão e Conquista
- Algoritmos de Ordenação
- Limite Inferior para Ordenação
Prova 2:
- Ordenação em Tempo Linear
- Estatísticas de Ordem
- Programação Dinâmica
- Algoritmos Gulosos
- Noções Básica de Grafos
- Buscas em Grafos
- Ordenação Topológica
- Árvore Geradora Mínima
- Caminhos Mínimos
A nota final antes do exame (N) será calculada usando a
seguinte fórmula:
Se 2.5 ≤ N < 5, o aluno terá direito a fazer o exame.
A nota final da disciplina (F) após o exame (E) será
calculada pela fórmula:
- F = min{5, (N + E)/2}, se 2.5 ≤ N < 5 e o aluno fez o exame
- F = N, caso contrário
Observações:
- Não haverá provas ou exame substitutivos.
- As provas e o exame serão realizados sem consulta a
qualquer material.
- Qualquer tentativa de fraude nas provas ou no exame resultará
em média do semestre N = 0 (zero) para todos os envolvidos, sem
prejuízo de outras sanções.
- De acordo com a fórmula acima, caso um aluno seja aprovado
após realizar o exame, sua nota final será igual a F=5 (cinco).
- As provas e o exame serão realizados das 9:30h às 11:30h na
sala 85 (auditório) do IC-1.
Datas Importantes:
- 21/09/2012: Primeira prova (P1).
- 23/11/2012: Segunda prova (P2).
- 14/12/2012: Exame (E).