MC448 - Análise de Algoritmos I

Conteúdo desta página

Avisos Importantes

• [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

Zanoni Dias
Sala: 23 (IC-1)
Email: zanoni@ic.unicamp.br

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

[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
[4]		Introduction to Algorithms T. Cormen, C. Leiserson, R. Rivest McGraw-Hill, 1990.

Obs: As referências [2], [3] e [4] 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.

Outras referências recomendadas:

[5]		Algorithmics: theory and practice G. Brassard e P. Bratley Prentice-Hall, 1995.
[6]		Projeto de Algoritmos - 2a edição N. Ziviani Thomson, 2004.
[7]		The Design and Analysis of Computer Algorithms A. Aho, J. Hopcroft, J. Ullman Addison-Wesley, 1974.
[8]		The Art of Computer Programming D. E. Knuth Addison-Wesley, 1974.
[9]		Grafos e Algoritmos Computacionais J. L. Szwarcfiter Addison-Wesley, 1974.

Listas de Exercícios

• Introdução à Análise de Algoritmos:
  • [4] 1.1-3, 1.2-1, 1.2-2
• Indução Matemática:
  • [1] 2.1, 2.3, 2.12, 2.18, 2.26
• Complexidade de Algoritmos:
  • [4] 2.1-1, 2.1-2, 2.1-4
• Relações de Recorrência:
  • [4] 4.1-1, 4.1-2, 4.1-6, 4.2-1, 4.2-2, 4.2-3, 4.2-4, 4.2-5, 4.3-1, 4.3-2, 4.3-3
• Construção de algoritmos por indução:
  • [1] 5.5, 5.11, 5.12, 5.14, 5.15, 5.25a
• Algoritmos de ordenação:
  • [4] 7.1.1, 7.1-4, 7.1-5, 7.2-1, 7.2-3, 7.3-1, 7.4-1, 7.4-2 ([2] 6.4-3)
  • [4] 8.1-1, 8.1-2, 8.2-1 ([2] 7.2-2), 8.2-2 ([2] 7.3-2), 8.3-2, 8.4-4 ([2] 7.4-5)
• Limite inferior para ordenação e ordenação em tempo linear:
  • [4] 9.1-1, 9.2-1, 9.2-2, 9.2-3, 9.2-5 ([2] 8.2-4), 9.3-4, 9.4-1 ([2] 8.4-2), 9.4-2 ([2] 8.4-3)
• Estatística de ordem:
  • [4] 10.1-1, 10.3-1, 10-3.3, 10.3-5, 10.3-8
• Programação Dinâmica:
  • [4] 16.1-2 ([2] 15.2-2), 16.3-2 ([2] 15.4-2), 16.3-3 ([2] 15.4-3), 16.3-4 ([2] 15.4-4), 16.3-5 ([2] 15.4-5), 16-3 ([2] 15-3)
• Algoritmos Gulosos:
  • [4] 17.1-3 ([2] 16.1-4), 17.2-4, 17.2-5, 17.3-2, 17.3-7, 17-1
• Algoritmos elementares em grafos:
  • [4] 23.1-1, 23.1-5, 23.1-6, 23.2-2, 23.2-3, 23.2-6, 23.3-9 ([2] 22.3-11), 23.4-3, 23.4-5, 23.5-1
• Árvore geradora mínima:
  • [4] 24.1-1, 24.1-5, 24.2-2, 24.2-3, 24.2-4, 24.2-5, 24.2-8 ([2] 23.2-7)
• Estruturas de dados para conjuntos disjuntos:
  • [4] 22.1-3, 22.2-2, 22.3-2, 22.3-3
• Caminhos Mínimos:
  • [4] 25.2-2 ([2] 24.3-2), 25.2-3 ([2] 24.3-3), 25.2-4 ([2] 24.3-4), 25.2-5 ([2] 24.3-6), 25.2-6 ([2] 24.3-7), 25.3-3 ([2] 24.1-3), 25.3-4 ([2] 24.1-4), 25.4-3 ([2] 24.2-3)
• Todos Caminhos Mínimos:
  • [4] 26.2-5 ([2] 25.2-6), 26-1

Listas Complementares

• Lista 1 - Complexidade de Algoritmos
• Lista 2 - Indução Matemática
• Lista 3 - Relações de Recorrência
• Lista 4 - Algoritmos de Ordenação

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):

• Formato PDF
• Formato PS

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:

1. Calcule: T = (T1 + T2 + T3 + T4)/4
2. 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:

1. Se o aluno não compareceu ao exame então MF = M.

2. Caso contrário, MF = (M + E)/2

MF ≥ 5.0

APROVOU-SE

REPROVOU-SE

Observações:

1. Não haverá provas ou testes substitutivos.
2. Todas as provas, os testes e o exame serão realizados sem consulta.
3. 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.
4. 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).

Notas

Consulte as notas aqui.

Datas Importantes

• 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).

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.