Análise e Complexidade de Algoritmos

Plano de Ensino

• Carga Horária: 45h
• Aulas Previstas: 15

Objetivos

Objetivo Geral

Capacitar os alunos a avaliar os principais modelos de computação, permitindo que estes analisem as noções e as limitações dos conceitos de computabilidade e de eficiência computacional.

Objetivos Específicos

1. Analisar e produzir provas em sistemas formais.
2. Analisar definições de linguagens e suas propriedades.
3. Desenvolver expressões regulares, gramáticas e autômatos como reconhecedores de linguagens.
4. Analisar e correlacionar os conceitos de computabilidade, decidibilidade e redutibilidade.
5. Identificar problemas decidíveis e indecidíveis.
6. Analisar a complexidade de tempo de algoritmos e suas classes de complexidade.
7. Julgar qual a estrutura de dados mais adequada à solução de um determinado problema com base em suas características de complexidade.
8. Desenvolver algoritmos utilizando técnicas de projeto de algoritmos de dividir-e-conquistar, programação dinâmica, e algoritmos gulosos.
9. Analisar a complexidade de espaço de algoritmos.
10. Avaliar e aplicar estratégias para lidar com problemas intratáveis.

Ementa

Lógica de programação; Construção de Algoritmos; Complexidade de Algoritmos; Algoritmos de Busca e Ordenação; Recursividade; Estruturas de Dados; Árvores; Grafos; Linguagens Formais e Autômatos; Tipos de Linguagem e seus Reconhecedores.

Referências Bibliográficas

1. Michael Sipser. “Introduction to the Theory of Computation.” 3rd ed. Cengage Learning. 2013.
2. John C. Martin. “Introduction to Languagens and the Theory of Computation.” 4th ed. McGraw-Hill. 2011.
3. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. “Introduction to Algorithms.” 3rd ed. The MIT Press. 2009.