Automatas
Páginas: 54 (13265 palabras)
Publicado: 30 de octubre de 2012
Desarrollo de Temario Teoría de la Computación
TEORIA DE LA COMPUTACION
1.1 Autómatas, computabilidad y complejidad.
1.2 Nociones matemáticas.
1.2.1 Conjuntos
1.2.2 Funciones y Relaciones
1.2.3 Cadenas y Lenguajes
1.3 Inducción matemática.
2 Lenguajes regulares.
2.1 Autómatas finitos
2.1.1 Autómatas finitos determinísticos.
2.1.2 Autómatas finitos Nodeterminísticos
2.2 Expresiones regulares.
2.3 Lenguajes no regulares.
3 Lenguajes libres de
3.1 Gramáticas libres de contexto. contexto.
3.2 Árboles de derivación.
3.3 Formas normales de Chomsky.
3.4 Formas normales de Greibach.
3.5 Eliminación de Factores Comunes izquierdos.
3.6 Eliminación de recursividad izquierda.
3.7 Eliminación de la ambigüedad.
3.8Autómatas Push-Down.
3.9 Lenguajes no regulares.
4 Máquina de Turing.
4.1 Definición formal de una máquina de Turing.
4.2 Construcción modular de una máquina de Turing.
4.3 Lenguajes aceptados por la MT.
4.4 Variantes de una máquina de Turing.
4.5 Problemas de Hilbert.
5 Decibilidad
5.1 Lenguajes Decidibles.
5.2 El problema de Halting.
5.3Decibilidad de Teorías Lógicas.
6 Reducibilidad
6.1 Problemas insolubles para la teoría de lenguajes
6.2 Un problema simple insoluble
6.3 Reducibilidad de Turing
1.1 Autómatas, Computabilidad y complejidad.
Autómata.
Un autómata es un sistema secuencial, aunque en ocasiones la palabra es utilizada
también para referirse a un robot y puede definirse como un equipoelectrónico programable en lenguaje informático diseñado para controlar en tiempo real y en ambiente industrial procesos secuenciales. Sin embargo la rápida evolución de los autómatas hace que esta definición no esté cerrada.
Un autómata programable se puede considerar como un sistema basado en un micro
procesador siendo sus partes fundamentales la Unidad Central de Procesos (CPU) la memoria y elsistema de entradas y salidas (E/S) por lo que realiza control interno y externo del autómata y la interpretación de las instrucciones del programa. Se describen tres tipos de autómatas que reconocen tipos diferentes de lenguajes los autómatas finitos, autómatas a pila y maquinas de Turing.
Computabilidad.
Es la parte de la computación que estudia los problemas decisión y pueden serresueltos con un algoritmo o la misma máquina de Turing. Por lo que es llevar acabo registros que pueden ser realizados por humanos para ser automatizados y estar libres de errores.
Consiste en ser capaz de encontrar la representación adecuada para la descripción de un problema o fenómeno se dice que un algoritmo es una manera formal y sistemática de representar la descripción de un proceso.Complejidad.
Es la cualidad de lo que está compuesto diversos elementos la complejidad tiende a ser utilizada para caracterizar algo con muchas partes que forman un conjunto intrincado.
La palabra proviene del latín complectere que significa trenzar, enlazar al agregado prefijo “com” añade el sentido de la dualidad de dos elementos opuestos que se enlazan íntimamente pero sin anular su dualidady esta es una noción utilizada en filosofía y epistemología y varía según el área del conocimiento.
1.2 Nociones Matemáticas.
1.2.1 Conjuntos
El concepto de conjunto es de fundamental importancia en las matemáticas modernas. Muchos matemáticos creen que es posible expresar todas las matemáticas con un lenguaje de teoría de conjuntos. Otra aplicación de la teoría de conjuntosla encontramos con el modelado e investigación de operaciones en las ciencias computacionales.
Los conjuntos fueron por primera vez formalmente estudiados por G. Cantor. Después de esto la teoría de conjuntos se ha convertido en un área muy bien establecida de matemáticas, contradicciones o paradojas que encontramos en dicha teoría. Eventualmente, los más sofisticados acercamientos al trabajo...
TEORIA DE LA COMPUTACION
1.1 Autómatas, computabilidad y complejidad.
1.2 Nociones matemáticas.
1.2.1 Conjuntos
1.2.2 Funciones y Relaciones
1.2.3 Cadenas y Lenguajes
1.3 Inducción matemática.
2 Lenguajes regulares.
2.1 Autómatas finitos
2.1.1 Autómatas finitos determinísticos.
2.1.2 Autómatas finitos Nodeterminísticos
2.2 Expresiones regulares.
2.3 Lenguajes no regulares.
3 Lenguajes libres de
3.1 Gramáticas libres de contexto. contexto.
3.2 Árboles de derivación.
3.3 Formas normales de Chomsky.
3.4 Formas normales de Greibach.
3.5 Eliminación de Factores Comunes izquierdos.
3.6 Eliminación de recursividad izquierda.
3.7 Eliminación de la ambigüedad.
3.8Autómatas Push-Down.
3.9 Lenguajes no regulares.
4 Máquina de Turing.
4.1 Definición formal de una máquina de Turing.
4.2 Construcción modular de una máquina de Turing.
4.3 Lenguajes aceptados por la MT.
4.4 Variantes de una máquina de Turing.
4.5 Problemas de Hilbert.
5 Decibilidad
5.1 Lenguajes Decidibles.
5.2 El problema de Halting.
5.3Decibilidad de Teorías Lógicas.
6 Reducibilidad
6.1 Problemas insolubles para la teoría de lenguajes
6.2 Un problema simple insoluble
6.3 Reducibilidad de Turing
1.1 Autómatas, Computabilidad y complejidad.
Autómata.
Un autómata es un sistema secuencial, aunque en ocasiones la palabra es utilizada
también para referirse a un robot y puede definirse como un equipoelectrónico programable en lenguaje informático diseñado para controlar en tiempo real y en ambiente industrial procesos secuenciales. Sin embargo la rápida evolución de los autómatas hace que esta definición no esté cerrada.
Un autómata programable se puede considerar como un sistema basado en un micro
procesador siendo sus partes fundamentales la Unidad Central de Procesos (CPU) la memoria y elsistema de entradas y salidas (E/S) por lo que realiza control interno y externo del autómata y la interpretación de las instrucciones del programa. Se describen tres tipos de autómatas que reconocen tipos diferentes de lenguajes los autómatas finitos, autómatas a pila y maquinas de Turing.
Computabilidad.
Es la parte de la computación que estudia los problemas decisión y pueden serresueltos con un algoritmo o la misma máquina de Turing. Por lo que es llevar acabo registros que pueden ser realizados por humanos para ser automatizados y estar libres de errores.
Consiste en ser capaz de encontrar la representación adecuada para la descripción de un problema o fenómeno se dice que un algoritmo es una manera formal y sistemática de representar la descripción de un proceso.Complejidad.
Es la cualidad de lo que está compuesto diversos elementos la complejidad tiende a ser utilizada para caracterizar algo con muchas partes que forman un conjunto intrincado.
La palabra proviene del latín complectere que significa trenzar, enlazar al agregado prefijo “com” añade el sentido de la dualidad de dos elementos opuestos que se enlazan íntimamente pero sin anular su dualidady esta es una noción utilizada en filosofía y epistemología y varía según el área del conocimiento.
1.2 Nociones Matemáticas.
1.2.1 Conjuntos
El concepto de conjunto es de fundamental importancia en las matemáticas modernas. Muchos matemáticos creen que es posible expresar todas las matemáticas con un lenguaje de teoría de conjuntos. Otra aplicación de la teoría de conjuntosla encontramos con el modelado e investigación de operaciones en las ciencias computacionales.
Los conjuntos fueron por primera vez formalmente estudiados por G. Cantor. Después de esto la teoría de conjuntos se ha convertido en un área muy bien establecida de matemáticas, contradicciones o paradojas que encontramos en dicha teoría. Eventualmente, los más sofisticados acercamientos al trabajo...
Leer documento completo
Regístrate para leer el documento completo.