Teoría de la computación. Incluye CD

Tipo: Libro impreso / Print book

Tamaño / Size: 21 x 27.5 cm

Páginas / Pages: 246

Resumen / Summary:

Autor / Author: Jorge Eduardo Carrión Viramontes
Editorial / Publisher: Limusa (Noriega Editores)
Entrega / Delivery : Nacional / International
Envio desde / Ships from: Colombia
Condición / Condition: Nuevo / New

Tabla de contenido / Table of contents:

Prólogo

1. Conceptos básicos Símbolo
Alfabeto
Cadenas
Operaciones con cadenas Lenguajes
Operaciones con lenguajes Preguntas

2. Lenguajes regulares
Definición
Expresiones regulares
Teoremas sobre expresiones regulares
Análisis léxico
Preguntas

3. Autómatas finitos deterministas
Diagramas de transiciones
Autómata finito determinista
AFD complemento
Autómatas equivalentes
AFD mínimo equivalente
Máquina de Moore
Máquina de Mealy
Transductor determinista

4. Autómatas finitos no deterministas
Definición
Transiciones épsilon
Equivalencia entre AFN con y sin transiciones épsilon
Criterios de simplificación
Autómatas finitos generalizados
Ejemplo práctico
Preguntas

5. Autómatas finitos y expresiones regulares
Construcción de autómatas
Obtención de expresiones regulares
Simplificación de AFNG
Preguntas

6. Gramáticas regulares
Definición de gramática
Construcción de gramáticas
Obtención de expresiones regulares
Gramáticas regulares reversas
Propiedades de las gramáticas regulares
Preguntas

7. Gramáticas libres del contexto
Definición de gramática libre del contexto
Árboles de derivación
Ambigüedad
Pruebas de corrección y completez
Depuración de gramáticas independientes del contexto
Forma normal de Chomsky
Algoritmo de CYK (Cocke, Younger y Kasami)
Forma normal de Greibach
Preguntas

8. Lenguajes libres del contexto
Lenguajes no regulares
Propiedades de los LIC
Construcción de GIe
Análisis sintáctico Gramáticas LL(k)
Gramáticas LR(k)
Preguntas

9. Autómatas de pila
Autómatas de pila determinista
Autómatas de pila no determinista
Autómatas de pila condicionada
APD complemento
Construcción de un APN a partir de una GlC
Construcción de las GlC
Preguntas

10. Máquinas de Turing
La máquina de Turing
Funciones Turing-computables
Reconocimiento de lenguajes con máquinas de Turing
Variantes de las máquinas de Turing
Máquinas de Turing básicas
Máquinas de Turing compuestas
Máquina universal de Turing
Preguntas

11. Gramáticas no restringidas
Lenguajes decidibles
Gramáticas sensibles al contexto
Gramáticas no restringidas
Toda MT puede simularse por alguna
GNR Jerarquía de Chomsky
Lenguajes enumerables
La máquina de Turing como enumerador
Preguntas

12. Resolubilidad
Definición
Reformulación de problemas
Propiedades de los lenguajes decidibles
Problema de detención
Diagonalización
Reducibilidad
Preguntas

13. Computabiiidad
Funciones iniciales
Construcciones primitivas
Funciones recursivas primitivas
Funciones características
Funciones u-recursivas
Funciones parciales
Funciones recursivas parciales
Incomputabilidad
Preguntas

14. Complejidad
Complejidad de los algoritmos
Complejidad temporal de las máquinas de Turing
Complejidad de los problemas
Tasas de crecimiento
Intratabilidad
Cálculos de tiempo polinomial
Problemas de decisión
Teorema de Cook
Comentarios finales

Preguntas
A. Glosario de términos
B. Solución a los problemas planteados

Ver todas las reseñas