Introducción a la teoría de autómatas, lenguajes y computaci
Libros / Revistas

Introducción a la teoría de autómatas, lenguajes y computaci

La teoría de autómatas es el estudio de dispositivos de cálculo abstractos, es decir, de las “máquinas”. Antes de que existieran las computadoras, en la década de los años treinta, A. Turing estudió una máquina abstracta que tenía todas las capacidades de las computadoras de hoy día, al menos en lo que respecta a lo que podían calcular. El objetivo de Turing era describir de forma precisa los límites entre lo que una máquina de cálculo podía y no podía hacer; estas conclusiones no sólo se aplican a las máquinas abstractas de Turing, sino a todas las máquinas reales actuales.

En las décadas de los años cuarenta y cincuenta, una serie de investigadores estudiaron las máquinas más simples, las cuales todavía hoy denominamos “autómatas finitos”. Originalmente, estos autómatas se propusieron para modelar el funcionamiento del cerebro y, posteriormente, resultaron extremadamente útiles para muchos otros propósitos, como veremos en la Sección 1.1. También a finales de la década de los cincuenta, el lingüista N. Chomsky inició el estudio de las “gramáticas” formales. Aunque no son máquinas estrictamente, estas gramáticas están estrechamente relacionadas con los automátas abstractos y sirven actualmente como base de algunos importantes componentes de software, entre los que se incluyen componentes de los compiladores.

En 1969, S. Cook amplió el estudio realizado por Turing sobre lo que se podía y no se podía calcular. Cook fue capaz de separar aquellos problemas que se podían resolver de forma eficiente mediante computadora de aquellos problemas que, en principio, pueden resolverse, pero que en la práctica consumen tanto tiempo que las computadoras resultan inútiles para todo excepto para casos muy simples del problema. Este último tipo de problemas se denominan “insolubles” o “NP-difíciles”. Es extremadamente improbable que incluso la mejora de carácter exponencial en la velocidad de cálculo que el hardware de computadora ha experimentado (“Ley de Moore”) tenga un impacto significativo sobre nuestra capacidad para resolver casos complejos de problemas insolubles.

Contenido:

1. Introducción a los autómatas
2. Autómatas finitos
3. Lenguajes y expresiones regulares
4. Propiedades de los lenguajes regulares
5. Lenguajes y gramáticas independientes del contexto
6. Autómatas a pila
7. Propiedades de los lenguajes independientes del contexto
8. Introducción a las máquinas de Turing
9. Indecidibilidad
10. Problemas intratables
11. Otras clases de problemas
Índice

Información del Libro:

Autores:
John E. Hopcroft, Rajeev Motwani y Jeffrey D. Ullman
Edición: 3ra
Editorial: Pearson
Número de Páginas: 458 páginas
Formato: pdf

Descarga el Libro

Si lo que encontraste en este Post te sirvió , no te olvides de agradecérselo al Uploader ;
Tu comentario y agradecimiento es su única recompensa y estimulo para seguir compartiendo.
Estadísticas
Creado 03.09.2015 a las 01:59 hs
Categoría Libros / Revistas
  • 1
    Medallas
  • 0
    Favoritos
  • 1142
    Visitas
  • 4.5/10
    LPDLW score
  • 6
    Votantes
  • 43
    Puntos
  • 0
    Seguidores
  • 0
    Recomendado
Comentarios
4
Cargando comentarios espera un momento...

Para poder comentar necesitas ser un usuario registrado , ¡ Registrarme Ahora !. O.. ya tienes usuario? Logueate!
Creado por    klifor
Ver perfil de klifor klifor
Hombre Full User  Mensaje
964 21 19
Medallas ganadas por este Post
1
Punteadores
Tags
Posts relacionados
Mas Post de     klifor
Términos y condiciones
Privacidad
Report - DMCA
Contacto
LoPeorDeLaWeb  © 2014 - 2024
Carga   0.692    Mls  
Basado en  PHPost 
Diseño de Kmario19
Adaptado por  jor51 
LoPeorDeLaWeb utiliza cookies. Lea nuestra Política de Privacidad para obtener más información. Para eliminar este mensaje, haga clic en el siguiente botón: Acepto el uso de cookies