MC548 - Análise de Algoritmos II

Turma # - Primeiro Semestre de 2013

Conteúdo desta página


Avisos Importantes


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:


Programa


Referências Bibliográficas

A seguir encontra-se a bibliografia de base desta disciplina com alguns comentários visando auxiliá-lo na escola dos livros a serem pesquisadas durante os seus estudos. Note que, além destes livros, existem nas bibliotecas da UNICAMP outras boas referências sobre os assuntos que serão vistos em sala de aula.

  1. T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein. Introduction to Algorithms (Third Edition). The MIT Press, 2009.
    Comentário: Livro básico de análise de algoritmos.
  2. T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein. Algoritmos - Teoria e Prática. Editora Campus, 2002.
    Comentário: Versão em português, da segunda versão da referência anterior.
  3. U. Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.
    Comentário: O capítulo 10 trata exclusivamente sobre reduções entre problemas e é uma ótima referência para o curso. O mesmo pode ser dito a respeito do capítulo 11 sobre NP-completude.
  4. C. H. Papadimitriou e K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc., 1982.
    Comentário: Uma boa fonte de referência na parte de NP-completude, principalmente para explicar as técnicas de branch-and-bound e apresentar os conceitos básicos de algoritmos aproximados.
  5. E. Horowitz e S. Sahni. Fundamentals of Computer Algorithms. Computer Science Press, 1978.
    Comentário: Outra boa fonte de referência para NP-completude, algoritmos aproximados, algoritmos de branch-and-bound e backtracking.
  6. M. Garey e D. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, 1979.
    Comentário: Referência clássica sobre a Teoria da Complexidade.
  7. P. J. de Rezende e J. Stolfi. Fundamentos de geometria computacional. Universidade Federal de Pernambuco, Departamento de Informatica, 1994. IX Escola de Computação, Recife, 24 a 31 de julho de 1994.
    Comentário: Uma boa leitura sobre reduções entre problemas (parte inicial do curso).
  8. M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.
    Comentário: Este livro é muito bem escrito e aborda de forma bem mais aprofundada vários tópicos que são vistos na disciplina.
  9. H.R. Lewis e C.H. Papadimitriou. Elementos de Teoria da Computação. Bookman. 2a edição, 2000.
    Comentário: No mesmo nível do livro acima, porém em português.
  10. M.C. Goldbarg e H.P.L. Luna. Otimização Combinatória e Programação Linear: modelos e algoritmos. Editora Campus, 2000.
    Comentário: Uma boa fonte de consulta em português sobre formulação de problemas usando PLI.
  11. N. Ziviani. Projeto de Algoritmos com implementações em Pascal e C (3a edição). Thomson, 2010.
    Comentário: Um livro recente em português sobre algoritmos. O Capítulo 9 é uma boa referência complementar.

Material Didático


Listas de Exercícios


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:

Prova 2:

Prova 3:

Prova 4:

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:

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

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