¿Estás estudiando computación o programación y quieres entender mejor cómo funcionan los lenguajes, autómatas y máquinas de Turing? Entonces este libro gratuito es para ti.
En Facialix te compartimos “Teoría de la Computación: Lenguajes Formales, Computabilidad y Complejidad”, un libro en español que podrás descargar sin costo y usar como apoyo para tus estudios universitarios o aprendizaje independiente.
Escrito por Gonzalo Navarro, profesor del Departamento de Ciencias de la Computación de la Universidad de Chile, este libro explica de forma clara temas clave de la teoría computacional y los acompaña con ejercicios y proyectos.
Contenido del libro
El libro está dividido en seis grandes módulos, cada uno con sus respectivos temas, ejercicios, preguntas y proyectos:
1. Conceptos Básicos
- Inducción estructural
- Conjuntos, relaciones y funciones
- Cardinalidad
- Alfabetos, cadenas y lenguajes
- Especificación finita de lenguajes
2. Lenguajes Regulares
- Expresiones regulares
- Autómatas finitos deterministas y no deterministas
- Conversión entre autómatas y expresiones
- Propiedades de clausura
- Lema de bombeo
- Ejercicios, preguntas y proyectos
3. Lenguajes Libres del Contexto
- Gramáticas libres del contexto
- Autómatas de pila
- Conversión entre gramáticas y autómatas
- Parsing, determinismo
- Ejercicios, preguntas y proyectos
4. Máquinas de Turing y la Tesis de Church
- Máquinas de Turing (simples, de múltiples cintas, no deterministas)
- Máquina universal
- Tesis de Church
- Gramáticas dependientes del contexto
- Ejercicios, preguntas y proyectos
5. Computabilidad
- Problema de la detención
- Problemas indecidibles
- Reducción y demostraciones
- Ejercicios, preguntas y proyectos
6. Complejidad Computacional
- Tiempo de cómputo
- Clases P y NP
- Problemas NP-completos
- Jerarquía de complejidad
- Ejercicios, preguntas y proyectos
El contenido está enfocado en conceptos fundamentales que todo estudiante de informática debe conocer. Además, está disponible bajo una licencia Creative Commons, lo que permite su distribución gratuita siempre que no se modifique ni se utilice con fines comerciales.
Información del libro
- Título: Teoría de la Computación (Lenguajes Formales, Computabilidad y Complejidad)
- Autor: Gonzalo Navarro
- Categoría: Teoría de la Computación
- Licencia: Creative Commons BY-NC-ND 2.5
- Idioma: Español