MC448 - Análise de Algoritmos I

Conteúdo desta página

Avisos Importantes

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

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

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

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

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

Recomenda-se o estudo do programa da disciplina através do material didático preparado pelo professor Cid Carvalho de Souza especialmente para esta disciplina (slides em formato PDF).

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:

• N = (2*P1 + 3*P2)/5

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:

1. Não haverá provas ou exame substitutivos.
2. As provas e o exame serão realizados sem consulta a qualquer material.
3. 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.
4. 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).
5. As provas e o exame serão realizados das 9:30h às 11:30h na sala 85 (auditório) do IC-1.

Notas

Consulte as notas aqui.

Datas Importantes

• 21/09/2012: Primeira prova (P1).
• 23/11/2012: Segunda prova (P2).
• 14/12/2012: Exame (E).