CI089 - Complexidade Computacional

Segundo semestre de 2003

Ementa -- Bibliografia -- Provas -- Listas -- Aulas -- Frequência -- Notas -- Links-- Temas para seminário

Ementa:

Máquinas de Turing e elementos de computabilidade.
A classe de complexidade P.
A classe NP e NP-completude.
Complexidade de Espaço.

Objetivos:

A compreensão das limitações do modelo computacional e da dificuldade inerente de se resolver poblemas computacionais algoritmicamente.

Carga horária: 60 Créditos: 4 Responsável: Jair.

Bibliografia básica:

C. H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, Readymg, 1994.
J.E. Hopcroft and J.D. Ullman, Introduction to automata theory, languages, and Computation, Addison-Wesley, Reading, Mass., 1979. (ou sua versão moderna: Hopcroft, Ullman, Motwani, Introducao a Teoria de Automatos, Linguagens e Computacao, Ed. Campus)

Bibliografia complementar:

M.R. Garey and D.S. Johnson, Computers and intractability :a guide to the theory of NP-completeness, San Francisco, W.H. Freeman, 1979.
A.V. Aho, J.E. Hopcroft, and J.D. Ullman, The Desing and Analysis of Computer Algorithms, Addison-Wesley, Reading, 1975.
T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to algorithms, The MIT Press, McGraw-Hill Book Company.
T.A. Sudkamp, Languages and Machines, Addison-Wesley.

Sistema de avaliação

Média aritmética de duas provas dá a média de provas. A média final é a media ponderada da média das provas (peso 2) com a média das listas (peso 1).
Tendo 75% de freqüência, o aluno com nota maior ou igual a 70 estará aprovado.
Tendo 75% de freqüência, o aluno com nota maior ou igual a 40 e menor do que 70 estará habilidato a fazer a prova final.
Em qualquer outro caso o aluno estará reprovado e será indicado se houve ou não infreqüência.
O aluno que fizer a prova final estará aprovado apenas se a média aritmética da prova final e da média final for maior ou igual a 50.
Seminário é obrigatório para alunos de mestrado. A nota entra na média como nota de lista.

Calendário de provas

Computação paralela
Criptografia Oliver
Complexidade de informação Murilo
Hierarquia polinomial
Complexidade de Espaço

Calendário de provas

Prova 1: 04/11/2003, terça as 17:20hs na PC08
Prova 2: 12/12/2003, sexta no auditório da informática
Final : 17/02/2004, terça, na PC08
2a. Chamada : 05/02/2004, quinta

Não haverá aulas em:

20 e 22/01 de 2004

Listas de exercícios

Links

Electronic Colloquium on Computational Complexity.
Fundamentals of Computing, Leonid Levin.
Introduction to Complexity Theory, Two sets of Lecture Notes, Oded Goldreich
Computational Complexity of Games and Puzzles
Computational complexity theory and Computability From Wikipedia, the free encyclopedia.
Personal WWW pages of complexity people

P versus NPClay Mathematics Institute
The Complexity Zoo

Tópicos das aulas

Aula 01 - 16/09 - Motivação.

Aula 02 - 18/09 - "revisao": Problemas x Algoritmos, notação assintotica, algoritmos polinomiais.

Aula 03 - 23/09 - Maquinas de Turing (informalmente); aceite de lingugens, cálculo de funções, MT k-fitas, MT k-dimensional e MT com fita infinita nos dois sentidos. Definicçõa formal de MT k-fitas.

Aula 04 - 25/09 - MT, exemplos, simplificacoes.

Aula 05 - 30/09 - RAM.

Aula 06 - 02/10 - RAM x MT

Aula 07 - 07/10 - MT x RAM; MT universal.

Aula 08 - 09/10 - MT Universal; decidibilidade.

Aula 09 - 14/10 - Problemas indecidiveis: argumento de contagem; linguagem universal

Aula 10 - 16/10 - O problema da parada.

Aula 11 - 21/10 - {M|L(M) vazio} nao e rec. enum. Teorema de Rice.

Aula 12 - 23/10 - Redutibilidade.

Aula 13 - 28/10 - não houve aula.

Aula 14 - 30/10 - alguns ajustes. Complexidade de tempo de M.T.

Aula 15 - 04/11 - PROVA

Aula 16 - 06/11 - Linear speed up. Classes de complexidade.

Aula 17 - 11/11 - A classe P.

Aula 18 - 13/11 - MT nao-deterministica.

Aula 19 - 18/11 - A classe NP.

Aula 20 - 20/11 - A classe NP, verificadores polinomiais; co-NP.

Aula 21 - 25/11 - PxNP; Reducao polinomial. CLIQUE reduz a SAT.

Aula 22 - 27/11 - NP-completude.

Aula 23 - 02/12 - SAT é NP-completo.

Aula 24 - 04/12 - SAT é NP-completo.

Aula 25 - 09/12 - SAT é NP-completo; 3-SAT é NP-completo.

Aula 26 - 11/12 - Complexidade e espaço.

Aula 26 - 12/12 - PROVA

RECESSO 14/12/03 - 18/01/2004

Aula 27 - 27/01 - Seminário 1: Compleixdade de informação, Murilo.

Aula 28 - 29/01 - Seminario 2: Criptografia, Oliver.

Aula 29 - 04/02 - Seminario 3: Complexidade de espaço, Pedro.

Aula 30 - 06/02 - Seminario 4: Indecidibilidade em lógica, Tiago.

September 2003 October 2003 November 2003 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 4 5 6 1 2 3 4 1 7 8 9 10 11 12 13 5 6 7 8 9 10 11 2 3 4 5 6 7 8 14 15 16 17 18 19 20 12 13 14 15 16 17 18 9 10 11 12 13 14 15 21 22 23 24 25 26 27 19 20 21 22 23 24 25 16 17 18 19 20 21 22 28 29 30 26 27 28 29 30 31 23 24 25 26 27 28 29 December 2003 January 2004 February 2004 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 4 5 6 1 2 3 1 2 3 4 5 6 7 7 8 9 10 11 12 13 4 5 6 7 8 9 10 8 9 10 11 12 13 14 14 15 16 17 18 19 20 11 12 13 14 15 16 17 15 16 17 18 19 20 21 21 22 23 24 25 26 27 18 19 20 21 22 23 24 22 23 24 25 26 27 28 28 29 30 31 25 26 27 28 29 30 31 29

Freqüência: