MC538 - Análise de Algoritmos II

Of.: S-5 T:04 L:00 HS:04 SL:04 C:04

 

Pre-Req.: MC438

 

Ementa:

 

Algoritmos algébricos e para problemas da teria de números. Estruturas de dados avançadas. Autômatos finitos. Noções básicas de computabilidade e complexidade.

 

Programa:

 

  1. Algoritmos algébricos e para a problemas da teoria dos números
    1. Algoritmos para exponenciação e exponenciação modular
    2. Algoritmo de Euclides para o MDC: corretude e análise de pior caso. Algoritmos de Euclides estendido
    3. Teste de primalidade. Algoritmo de divisões sucessivas e algoritmo porbalístico baseado no teorema de Fermat (Miller-Rabin). Aplicações de criptografia ( método RSA)
    4. Algoritmos para multiplicação de matrizes: algoritmos cúbico e algoritmo de Strassen
    5. Transformada rápida de Fourier
  2. Estruturas de dados avançadas
    1. Estruturas para união de conjuntos disjuntos e sua análise
    2. Árvores binárias de busca auto-ajustáveis. Análise amortizada
  3. Autômatos finitos
    1. Alfabetos, cadeias e linguagens
    2. Autômatos finitos determinísticos e não-determinísticos. Linguagens regulares
    3. Expressões regulares e gramáticas regulares
    4. Aplicações de autômatos finitos
  4. Noções básicas de computabilidade e complexidade
    1. Máquinas de Turing e a tese de Church-Turing
    2. Problemas indecidíveis. O problema da parada. Diagonalização. Como mostrar que um problema é indecidível
    3. A hierarquia de complexidade. As classes P e NP. Problemas completos para uma classe. O teorema de Cook ( em alto nível apenas)
    4. Problemas e reduções fundamentais em NP-completude
    5. P-espaço e NP-espaço. O teorema de Savitch

 

Bibliografia:

 

T. Cormen, C.Leiserson e R. Rivest, Introduction to Algorithms, MIT Press, 1990

M. Sipser, Introduction to the Theory of Computation. PWS, 1997