MC448 - Análise de Algoritmos I
Turma #
Primeiro Semestre de 2013
Conteúdo desta página:
Avisos Importantes
- [05/12/2012] Site da disciplina no ar.
Docente:
Dias, Horários e Local de
Atendimento
Terças-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.
- 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, se não houver alunos, o 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.
- Não haverá atendimento de dúvidas por email.
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 quatro
provas denotadas respectivamente
por P1, P2, P3 e P4. Cada prova
terá duração de 1h e será composta de duas questões.
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
Prova 2:
- Construção de Algoritmos por Indução
- Divisão e Conquista
- Algoritmos de Ordenação
- Limite Inferior para Ordenação
Prova 3:
- Ordenação em Tempo Linear
- Estatísticas de Ordem
- Programação Dinâmica
- Algoritmos Gulosos
Prova 4:
- 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:
- N = (P1 + P2 + P3 + P4)/4
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).
- O exame terá duração de 2h e será composto por 4 questões, sendo
que cada questão cobrirá um tópico de uma das provas.
- Todas as provas e o exame serão realizados na sala 85 do IC, com
início às 17h.
- Após corrigidas, as provas estarão disponíveis para consulta
apenas nos dias e horários divulgados junto com as notas das provas.
Datas Importantes: