MO417 - Complexidade de Algoritmos I

Prof. Pedro J. de Rezende
Segundo Semestre de 2012

Novidades Recentes

• Aqui serão colocados avisos importantes. Consulte esta página regularmente.
• As notas da P2 e os Conceitos Finais estão disponíveis. [20121116]
• As notas da P1 estão disponíveis. [20120923]
• Os Slides das aulas serão colocados online a cada semana. Veja links na tabela de Tópicos abaixo. [20120804]
• Várias listas de exercícios já estão disponíveis. Pode começar a trabalhar neles. [20120804]
• A seção "Material Didático" reflete da melhor forma possível o que estudar, onde estudar e quais listas de exercícios correspondem a que tópicos. [20120804]
• Observe cuidadosamente o calendário de atividades (aulas e provas) abaixo. [20120804]
• Nos dias de provas, cheguem à sala de aula às 15:50 para que a prova possa ser iniciada pontualmente às 16:00 hs. pois ela não poderá ser estendida além de 18:00 hs. Peço que a distribuição de alunos pela sala seja antecipadamente preparada de modo a maximizar a distância mínima entre pares de alunos. [20120804]
• Se, erroneamente, você está com a impressão de que classes de complexidade é um tema simples que será esgotado nesta disciplina, não deixe de consultar Important Complexity Classes ou melhor ainda Complexity Zoo e também Compendium [20120801]
• Procure conseguir um exemplar dos livros recomentados desde a primeira semana de aulas. [20120801]

• Prof. Pedro J. de Rezende [MO417]
• Sala IC-29, http://www.ic.unicamp.br/~rezende, (19) 3521-5860,

• As aulas serão às segundas quartas-feiras 16h00-18h00, na sala IC-322.
• Horários de atendimento:
  • o professor atenderá :
• na sala de aulas, logo após as aulas, sempre que a aula terminar antes de 18h00;
• na sala IC-29, às segundas-feiras de 18h05 às 19h00.
• O atendimento imediatamente anterior a cada prova fica, desde já, revogado! I.é., procurem estudar com antecedência para as avaliações.

  Tópicos a serem cobertos
A Ementa da disciplina consiste dos seguintes tópicos:

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

Listas de Exercícios

Listas de exercícios serão atribuídas ao longo do semestre. Além de servir para maior fixação do material apresentado em classe, o conteúdo dos exercícios é considerado parte integrante do material visto e será assumido como parte da matéria coberta. Como as listas não farão parte da avaliação, suas soluções não serão coletadas. Os alunos são encorajados a resolver todos os exercícios individualmente e, só posteriormente, realizar discussão em grupo. Quaisquer dificuldades devem ser prontamente discutidas com o Professor nos horários de atendimentos. Dúvidas não sanadas geram mais dúvidas.

Material Didático: Slides das Aulas, Recomendações de Leitura e Listas de Exercícios

É imperativo ressaltar que não se estuda pelos slides! Eles devem servir apenas como um guia de estudo para orientar na identificações dos tópicos dos livros textos que devem ser profundamente estudados.

Note que nem tudo o que está contido nesses slides foi visto em classe, mas também há tópicos vistos em classe que não estão contido nesses slides (podemos usar lousa!). Portanto, compareça às aulas, guie-se por suas anotações e por esses slides, mas estude pelos livros recomendados. ([1], [2] e [3] indicam o primeiro (Cormen), o segundo (Manber) e o terceiro (Brassard) livros das Referências Bibliográficas abaixo.)

As listas de exercícios já indicadas nesta página poderão ser revistas/acrescidas à medida que cada tópico for sendo coberto. Visite esta página assiduamente.

Os arquivos contendo os slides serão acessíveis a partir de links na tabela abaixo, oportunamente.

Avaliação e Critérios para Aprovação

A avaliação desta disciplina consistirá de duas provas (P1, P2) nas datas indicadas ao final deste documento. Cada prova será em classe e terá duração de 120 minutos. As notas serão entre 0,0 e 10,0 e a média será mapeada para conceitos conforme descrito abaixo.

A Média das Provas (MP) será a média ponderada de P1 e P2 com pesos iguais a 1 e 2, respectivamente. Não serão ministradas provas antecipadas nem substitutivas. Situações excepcionais (a critério do professor) serão tratadas como tal.

O Conceito Final (CF) será obtido pelo mapeamento:
Se MP em [9.0, 10.0], CF=A; se MP em [7.5, 9.0), CF=B; se MP em [6.0, 7.5), CF=C; se MP em [0.0, 6.0), CF=D.

Aviso: Qualquer tentativa de cola ou fraude, detectada durante uma prova ou posteriormente, acarretará nota zero naquela prova para todos os implicados, além das sansões regimentais previstas.

Aqui está a Tabelas de Notas.

Referências Bibliográficas

Os livros principais são [1], [2], e [3]. Os demais são complementares.

1. T. Cormen, C. Leiserson, R. Rivest, C. Stein, Algoritmos - Teoria e Prática (tradução da 2ª Ed. Americana), Ed. Campus (2002).

2. U. Manber, Algorithms: A Creative Approach, Addison-Wesley (1989).

3. G. Brassard e P. Bratley, Algorithmics: Theory and Practice, Prentice-Hall.
4. J. Kleinberg e E. Tardos, Algorithm Design, Addison Wesley, (2005).
5. A. Aho, J. Hopcroft, e J. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley (1974).
6. N. Ziviani Projeto de Algoritmos com Implementações em Pascal e C, Pioneira Thomson Learning, 2ª. edição, (2004).
7. J. Szwarcfiter, Algoritmos em Grafos, Editora Campus (1987).
8. J. Szwarcfiter e L. Markenson, Estruturas de Dados e seus Algoritmos, LTC Editora (1994).
9. C. H. Papadimitriou e K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc.,1982.
10. M. Garey e D. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, 1979.
11. 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.
    
12. M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.
13. H.R. Lewis e C.H. Papadimitriou. Elementos de Teoria da Computação. Bookman. 2a edição, 2000.
    
14. D. E. Knuth, The Art of Computer Programming, vol. I: Fundamental Algorithms Addison-Wesley, 1997.

Datas importantes