Plano de ensino

Análise e Complexidade de Algoritmos

Mestrado Profissional em Computação Aplicada — 2020/1

Esta disciplina é uma introdução aos modelos de computação, computabilidade e complexidade. Ela tenta apresentar uma visão da ciência da computação para além dos computadores. Isto é, a ciência da computação como um conjunto de ferramentas matemáticas para entender sistemas complexos.

Início
Encerramento
Local
Ifes, Campus Serra
Ambiente virtual
Acessar disciplina

Aviso Devido à pandemia de COVID-19, e seguindo as diretrizes do Ifes, esta disciplina será ministrada remotamente.

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.