MC448 - Análise de Algoritmos I

Conteúdo desta página

Avisos Importantes

• [10/07/2013] Divulgadas as Notas do Exame Final. Os exames estarão disponíveis para consulta no dia 30/07/2013, às 17h (vide regras para o uso do horário de atendimento).
• [21/06/2013] Divulgado o esboço do exame com a distribuição das questões. Favor consultar a planilha de notas, aba “exame”, para verificar qual a nota que será atribuída para cada questão, caso o aluno indique no exame que a questão não deva ser corrigida, usando neste caso notas previamente obtidas durante o semestre, conforme especificado no rodapé de cada questão. Se um aluno com direito a fazer o exame decidir não realizá-lo, será considerado que ele optou por receber as notas previamente obtidas no semetre para todas as questões do exame. Apenas alunos cuja coluna “Situação” da planilha de notas for igual a “exame” devem/podem realizar o exame.
• [21/06/2013] Divulgadas as Notas da Quarta Prova. atendimento). As provas estarão disponíveis para consulta no horário de atendimento do dia 25/06/2013, último do semestre (vide regras para o uso do horário de atendimento).
• [22/05/2013] Divulgadas as Notas da Terceira Prova. As provas estarão disponíveis para consulta nos horários de atendimento dos dias 28/05/2013 e 04/06/2013 (vide regras para o uso do horário de atendimento).
• [24/04/2013] Divulgadas as Notas da Segunda Prova. As provas estarão disponíveis para consulta nos horários de atendimento dos dias 30/04/2013 e 07/05/2013 (vide regras para o uso do horário de atendimento).
• [27/03/2013] Divulgadas as Notas da Primeira Prova. As provas estarão disponíveis para consulta nos horários de atendimento dos dias 02 e 09 de abril de 2013 (vide regras para o uso do horário de atendimento).
• [05/12/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

Terças-feiras, das 17h às 18h, na sala 23 do IC-1.

Importante:

• O atendimento deve ser confirmado, com no mínimo 24h e no máximo 48h 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

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

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. 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.
6. Todas as provas e o exame serão realizados na sala 85 do IC, com início às 17h.
7. Após corrigidas, as provas estarão disponíveis para consulta apenas nos dias e horários divulgados junto com as notas das provas.

Notas

Consulte as notas aqui.

Datas Importantes

• 26/03/2013 (terça-feira): Primeira prova (P1).
• 23/04/2013 (terça-feira): Segunda prova (P2).
• 21/05/2013 (terça-feira): Terceira prova (P3).
• 18/06/2013 (terça-feira): Quarta prova (P4).
• 10/07/2013 (quarta-feira): Exame (E).

Todas as notas serão divulgadas em até 15 dias após a realização das provas e do exame.