La teoría de autómatas es una rama de la teoría de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolve

r. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces de reconocer. También son de gran utilidad en la teoría de la complejidad computacional.

Temas a conocer:

1. Comenzamos con un estudio de los autómatas finitos y los lenguajes que pueden definir (los llamados “lenguajes regulares”. Los temas incluyen autómatas deterministas y no deterministas, expresiones regulares y la equivalencia de estos mecanismos que definen el lenguaje.

También examinamos las propiedades de cierre de los lenguajes regularesConsideramos las propiedades de decisión de los lenguajes regulares. Finalmente, vemos el lema de bombeo para los lenguajes regulares, una forma de probar que ciertos lenguajes no son lenguajes regulares.

• 2. Nuestro segundo tema son las gramáticas libres de contexto y sus idiomas. Aprendemos sobre los árboles de análisis y seguimos un patrón similar al de los autómatas finitos: propiedades de cierre, propiedades de decisión y un lema de bombeo para lenguajes libres de contexto. También presentamos el autómata pushdown, cuya versión no determinista es equivalente en poder de definición del lenguaje a las gramáticas libres de contexto.

A continuación, presentamos la máquina de Turing, una especie de autómata que puede definir todos los lenguajes que razonablemente se puede decir que son definibles por cualquier tipo de dispositivo informático (los llamados “lenguajes recursivamente enumerables”). Aprenderemos cómo los “problemas” (preguntas matemáticas) pueden expresarse como lenguajes. Eso nos permite definir problemas como “decidibles” si su lenguaje puede ser definido por una máquina de Turing e “indecidibles” si no. Veremos algunos problemas básicos indecidibles, por ejemplo, es indecidible si la intersección de dos lenguajes libres de contexto está vacía.

• 3. Por último, examinamos la teoría de los problemas intratables. Estos son problemas que, si bien son decidibles, casi con certeza no tienen un algoritmo que se ejecute en el tiempo menos que alguna función exponencial del tamaño de su entrada. Nos enfrentamos a los problemas NP-completos, una gran clase de problemas intratables. Esta clase incluye muchos de los problemas combinatorios difíciles que se ha asumido durante décadas o incluso siglos que requieren tiempo exponencial, y aprendemos que ninguno o todos estos problemas tienen algoritmos de tiempo polinomial. Un ejemplo común de un problema NP-completo es SAT, la pregunta de si una expresión booleana tiene una asignación de verdad a sus variables que hace que la expresión en sí sea verdadera.

¿Qué es edX?

EdX es un proveedor de educación en línea que ofrece cursos en línea, conocidos popularmente como MOOC o Massive Open Online Courses, de las mejores universidades y otras instituciones de todo el mundo.

---

Únete al canal oficial de CardBiss para más Cursos GRATIS

Unirme en Telegram

---

Actualmente, edX cuenta con un catálogo de más de 2650 cursos en línea creados por estos socios.

Los cursos de EdX consisten en conferencias en video pregrabadas que puede ver en un horario semanal o cuando sea conveniente para usted.

También tienen lecturas, foros de discusión de estudiantes, tareas / asignaciones y pruebas o exámenes en línea.

¿Cómo me registro al curso?

Antes de que te registres en un curso debes saber que para poder unirte a un curso en edX existen dos modalidades, la de pago y gratuita.

Cada una con sus ventajas y desventajas que te listamos a continuación:

Si quieres un certificado de finalización y acceso a las evaluaciones y exámenes te recomendamos elegir la opción de paga, si por el contrario deseas o obtenerlo de manera gratuita puedes elegir la opción de auditoria (sin certificado), puedes tomar la siguiente imagen como referencia:

Si quieres acceder al curso de manera completamente gratuita puedes hacerlo dando clic al botón de abajo.

Recuerda que no existe una fecha limite o cupones de descuento, aun así, debes darte prisa.

Para obtener el curso da clic en el siguiente botón: