Programa de Verão 2010 do LNCC

Introdução a Teoria da Complexidade Computacional Clássica

Data Início: 18/1/2010
Data Fim: 22/1/2010
Carga Horária: 07:30horas
Horário: segunda - terça - quarta - quinta - sexta   de 15:00hs às 16:30hs
Local: Auditorio A


Professores

Emmanuel Felix Lopes da Silva - TRF 3ª e 5ª Regiões - EFLSILVA@trf3.jus.br

Fábio Borges de Oliveira - Laboratório Nacional de Computação Científica - borges@lncc.br

Objetivos:
A Teoria da Complexidade Computacional Clássica surge na década de 60 do século passado a partir dos esforços dos pesquisadores em Ciência da Computacão, visando estudar não só se um determinado problema é resolvível computacionalmente mas também, caso seja, quais recursos computacionais são necessários a sua solução. O objetivo deste curso é apresentar uma visão panorâmica da área, com um enfoque intuitivo e conceitual. Definimos precisamente a noção intuitiva de algoritmo, em seguida expomos algumas das mais destacadas classes de complexidade tais como: P, NP, co-NP, PSPACE e EXP, abordando a questão da completude. Seguimos, apresentando os algoritmos de aproximação e probabílisticos. Finalizamos com uma breve exposição de algumas aplicações práticas da teoria, notadamente em criptografia e problemas de otimização.

Ementa:
1. Noções de computabilidade;
2. Medidas de complexidade;
3. As classes de complexidade P, NP e co-NP;
4. NP-completude;
5. As classes PSPACE e EXP;
6. PS-completude;
7. Algoritmos de aproximação e probabilísticos;
8. Computação paralela;
9. Aplicações da teoria da complexidade clássica: criptografia, problemas de otimização.

Bibliografia
1) Computational Complexity, Christos H. Papadimitriou – Addison Wesley, 1994.
2) Introduction to the Theory of Computation, second edition, Michael Sipser – Thomson,
2006.