Teoria da Computação

Publicado 10/12/2020, 9:16:17 PM, última modificação 10/12/2020, 9:23:20 PM

Ementa: Linguagens regulares, livres e sensíveis a contexto. Autômatos. Máquina de Turing. Computabilidade. Problema da parada. Classes de Problemas P, NP, NP-Completo e NP-Difícil. 

Código da disciplina: PPGCC01

Carga-horária: 60 horas

Obrigatória? Sim

Créditos: 4

Bibliografia:

  • SIPSER, Michael. Introdução à teoria da computação. São Paulo, SP: Thomson Learning, 2006. 459p. ISBN 9788522104994.

  • MENEZES, Paulo Blauth. Linguagens formais e autômatos. 6. ed. Porto Alegre: Bookman, 2011. 256 p. ISBN 9788577807659.

  • HOPCROFT, John E.; ULLMAN, Jeffrey D.; MOTWANI, Rajeev. Introduction to automata theory, languages, and computation. 3rd. ed. Boston, MA: Addison Wesley, 2007. 535p. ISBN 0321455363.

  • Martin, John. C. Introduction to Languages and the Theory of Computation, 4th ed. New York, NY, EUA: McGraw Hill, 2011, 436p, ISBN 9780073191461.

  • VIEIRA, Newton José. Introdução aos fundamentos da computação: linguagens e máquinas. São Paulo, SP: Cengage Learning, 2014, 319p. ISBN 8522105081.

  • JARGAS, Aurélio Marinho. Expressões regulares: uma abordagem divertida. 4a. ed. São Paulo: Novatec, 2012,  23p. ISBN 9788575222126.

  • MOORE, Christopher; MERTENS, Stephan. The Nature of Computation. 1 a . ed. New York, NY, EUA: Oxford, 2011, 985p. ISBN 9780199233212.

  • RODGER, Susan H.; FINLEY, Thomas W. JFLAP: An Interactive Formal Languages and Automata Package. 1a ed., Sudbury, MA, EUA: Jones and Barlett, 2006, 192p. ISBN 9780763738341.