Conteúdo desta página:

• Docente
• Alunos Matriculados
• 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

Docente:

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

Alunos Matriculados:

Lista de alunos matriculados na disciplina de acordo com a DAC.

Dias, Horários e Local das Aulas:

Segundas e quartas das 8h às 10h, na sala IC-85.

Dia, Horário e Local de Atendimento:

Segundas-feiras, das 17:30h às 18:30h, na sala 23 (IC-1).
Importante: não haverá atendimento em semana de prova.

Material Didático:

Trasparências sobre NP-Completude (formato ps e pdf), elaboradas pelo professor Cid Carvalo de Souza [3].

Aula final: "Tratamento Algorítmico de Problemas NP-Difíceis" (aula elaborada e ministrada pelo professor Cid Carvalho de Souza no exame para professor titular em agosto de 2005).

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 e R.L.Rivest. Introduction to Algorithms. McGraw-Hill, 1990.
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. C. H. Papadimitriou e K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc.,1982.
5. E. Horowitz e S. Sahni. Fundamentals of Computer Algorithms. Computer Science Press, 1978.
6. M. Garey e D. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, 1979.
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.
8. M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.
9. H.R. Lewis e C.H. Papadimitriou. Elementos de Teoria da Computação. Bookman. 2a edição, 2000.
10. M.C. Goldbarg e H.P.L. Luna. Otimização Combinatória e Programação Linear: modelos e algoritmos. Editora Campus, 2000.
11. N. Ziviani. Projeto de Algoritmos com implementações em Pascal e C. 2a edição. Thomson, 2003.
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 da lista e a data de 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 praticamente, 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. Atrinuiçã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+2*P1+3*P2+4*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. Todos os alunos receberão 100% de presença, independente do conceito final obtido (não será atribuido o conceito "Reprovado por Falta" em nenhum caso).

Datas Importantes:

• 03/08/2005: início das aulas.
• 12/09/2005: primeira prova (P1).
• 17/10/2005: segunda prova (P2).
• 30/11/2005: 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é uma semana após as datas das provas e da entrega das listas de exercícios.