Conteúdo desta página:

• Notícias de Última Hora
• Docente
• Dias, Horários e Local das Aulas
• Dia, Horário e Local de Atendimento
• Material Didático
• Ementa
• Bibliografia
• Avaliação
• Datas importantes
• Notas
• Avaliação Didática
• Listas de Exercícios

Notícias de Última Hora:

• [02/12/2011] Divulgadas as notas da terceira prova e da décima lista de exercícios, assim como os conceitos finais.
• [02/12/2011] Divulgado o resultado da avaliação didática.
• [24/11/2011] Divulgadas as notas da nona lista de exercícios.
• [23/11/2011] Divulgada a décima lista de exercícios (entregar dia 30/11/2011).
• [18/11/2011] Divulgadas as notas da oitava lista de exercícios.
• [16/11/2011] Divulgada a nona lista de exercícios (entregar dia 23/11/2011).
• [08/11/2011] Divulgadas as notas da sétima lista de exercícios.
• [07/11/2011] Divulgada a oitava lista de exercícios (entregar dia 16/11/2011).
• [26/10/2011] Divulgada a sétima lista de exercícios (entregar dia 07/11/2011).
• [21/10/2011] Divulgadas as notas da segunda prova e da sexta lista de exercícios.
• [05/10/2011] Divulgadas as notas da quinta lista de exercícios.
• [03/10/2011] Divulgada a sexta lista de exercícios (entregar dia 19/10/2011).
• [21/09/2011] Divulgada a quinta lista de exercícios (entregar dia 03/10/2011).
• [13/09/2011] Divulgadas as notas da primeira prova e da quarta lista de exercícios.
• [02/09/2011] Divulgadas as notas da segunda e terceira listas de exercícios.
• [31/08/2011] Divulgada a quarta lista de exercícios (entregar dia 12/09/2011).
• [21/08/2011] Divulgadas as notas da primeira lista de exercícios.
• [17/08/2011] Divulgada a terceira lista de exercícios (entregar dia 31/08/2011).
• [17/08/2011] Divulgada a segunda lista de exercícios (entregar dia 24/08/2011).
• [02/08/2011] Divulgada a primeira lista de exercícios (entregar dia 10/08/2011).
• [30/07/2011] Site da disciplina no ar.

Docente:

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

Dias, Horários e Local das Aulas:

Segundas e quartas, das 14h às 16h, na sala 322 do IC-3.

Dia, Horário e Local de Atendimento:

Segundas-feiras, das 16h às 17h, na sala 23 (IC-1).


Importante: não haverá atendimento em semana de prova. O horário de atendimento será encerrado caso não haja procura até às 16:30h.

Material Didático:

Transparências utilizadas nas aulas (4 slides por página):

• Introdução
• Crescimento de funções
• Recorrências
• Ordenação
• Ordenação em tempo linear
• Estatísticas de ordem
• Projeto de algoritmos por indução
• Programação dinâmica
• Algoritmos gulosos
• Representação e buscas em grafos
• Árvore geradora mínima
• Caminhos mínimos
• NP-Completude

Ementa:

• Modelos de computação e ferramentas/notação para análise de algoritmos.
• Indução matemática e projeto de algoritmos.
• Algoritmos gulosos.
• Programação dinâmica.
• Divisão e conquista.
• Algoritmos para ordenação e seleção.
• Algoritmos para problemas básicos em grafos.
• Reduções e NP-completude.

Bibliografia:

1. T.H. Cormen, C.E. Leiserson, R.L. Rivest e C. Stein. Introduction to Algorithms. The MIT Press, 3rd edition (2009)
2. U. Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley (1989)
3. C. C. de Souza. Teoria da Complexidade: Notas de Aula (2005)
4. N. Ziviani. Projeto de Algoritmos com Implementações em Pascal e C. Thomson, 3a edição (2010)
5. C. H. Papadimitriou e K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc. (1982)
6. E. Horowitz e S. Sahni. Fundamentals of Computer Algorithms. Computer Science Press (1978)
7. M. Garey e D. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman (1979)
8. P. J. de Rezende e J. Stolfi. Fundamentos de geometria computacional. IX Escola de Computação, Universidade Federal de Pernambuco. Departamento de Informatica (1994)
9. M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company (1997)
10. H.R. Lewis e C.H. Papadimitriou. Elementos de Teoria da Computação. Bookman, 2a edição (2000)
11. M.C. Goldbarg e H.P.L. Luna. Otimização Combinatória e Programação Linear: modelos e algoritmos. Editora Campus (2000)
12. A. Aho, J. Hopcroft e J. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley (1974)
13. D. E. Knuth, The Art of Computer Programming, vol. I: Fundamental Algorithms Addison-Wesley (1997)

Avaliação:

A avaliação será baseada nas notas de três provas e de listas de exercícios denotadas respectivamente por P1, P2, P3 e E.

Haverá, no mínimo, um intervalo de 5 dias entre a divulgação de uma lista de exercícios e a data de sua entrega (que será sempre num dia de aula). As listas deverão ser entregues no começo da aula. Não serão aceitas listas entregues fora do prazo (tolerância máxima de 30 minutos). Apesar de discussões em grupo serem incentivadas nesta disciplina, a redação das respostas das listas deverá ser feita individualmente. Só serão aceitas listas escritas a mão, com letra legível. As listas poderão ser entregues incompletas, mas cada exercício entregue deve estar completamente resolvido. O número de listas de exercícios durante o curso, assim como o número de exercícios por lista, deverá variar entre 5 e 15. Serão atribuídas notas as listas de exercícios. Idealmente todos os exercícios serão corrigidos. Na prática, a critério exclusivo do docente, poderão ser utilizados outras formas para atribuir notas as listas, por exemplo:

1. Atribuição de nota máxima para quem entregou e zero para quem não entregou.
2. Atribuição de uma nota proporcional ao número de exercícios entregues.
3. Correção de um (ou mais) exercícios escolhido(s) aleatoriamente. Neste caso o mesmo sub-conjunto de exercícios será considerado para todos os alunos. Caso o exercício escolhido não tiver sido entregue será atribuida nota zero.
4. Uma combinação destes ou de outros métodos.

A nota E será calculada como a média aritmética simples entre todas as listas de exercícios do semestre.

A média do semestre M será calculada da seguinte forma:

M = (1*E + 3*P1 + 3*P2 + 3*P3)/10

O conceito final será atribuído da seguinte forma:
1. A: se M ≥ 8.5
2. B: se 7.0 ≤ M < 8.5
3. C: se 5.0 ≤ M < 7.0
4. D: se M < 5.0

Observações:

1. Não haverá provas substitutivas.
2. Todas as provas serão realizados sem consulta.
3. Qualquer tentativa de fraude nas provas ou nas listas de exercícios implicará em média do semestre ZERO para todos os envolvidos, sem prejuízo de outras sanções.
4. Não será cobrada presença em sala de aula.

Datas Importantes:

• 03/08/2011: Primeiro dia de aula.
• 12/09/2011: Primeira Prova (P1)
• 19/10/2011: Segunda Prova (P2)
• 30/11/2011: Terceira Prova (P3)

Observações:

1. Visite a página do Calendário oficial da DAC para saber quais as datas de alteração de matrícula, de trancamento de disciplinas e dos períodos sem atividade.
2. Todas as notas serão divulgadas em até duas semanas após as datas das provas e das entregas das listas de exercícios.