Aprender Computación: Roadmap (Computación 0)


Hace pocas fechas vi un video sobre Computación Cuántica que despertó mi interés de una manera brutal Sin embargo, mi nivel en la teoría de computación creo que no es suficiente, así que he decidido, como con matemáticas, estudiarla desde cero.

Antes de nada, quiero compartiros el genial video del que hablo:

Ahora, creo que es momento de iniciar con un índice de contenidos, que me servirá de guía pero que, al mismo tiempo, será un documento vivo:

Roadmap sobre Teoría de Computación

WARNING: Este roadmap es un documento vivo que variará con el tiempo, en tanto mejore mi comprensión y avance en la materia.. v0.0.3.

  1. ¿Qué es una teoría científica?
  2. Introducción a Teoría de la Computación
    1. ¿Que son máquinas abstractas y que tienen que ver en ello las gramáticas formales?
    2. Introducción técnica a máquinas abstractas.
    3. Conceptos: automatismo y autonomía
    4. Jerarquía: Estructura de máquinas y gramáticas
    5. Esquema: Relación entre máquinas y gramáticas
    6. ¿Cual es el sentido de las máquinas abstractas?
  3. Lenguajes formales.
    1. ¿Qué son los lenguajes formales?
    2. Alfabetos y Gramáticas
    3. Jerarquía de Chomsky
  4. Lenguajes Regulares
  5. Expresiones regulares.
  6. Gramáticas
    1. Gramáticas Formales
    2. Gramáticas Regulares
  7. Autómatas
    1. Autómatas finitos.
      1. Autómatas finitos deterministas
      2. Autómatas finitos indeterministas
      3. Autómatas finitos con lambda-transiciones.
      4. Equivalencia entre modelos de autómatas
      5. Operaciones sobre autómatas
      6. Minimización de autómatas.
  8. Autómatas con pila.
    1. Autómatas con pila indeterministas y su equivalencia con lenguajes incontextuales
    2. Autómatas con pila deterministas,
    3. Autómatas con pila de aceptación única y su equivalencia con lenguajes incontextuales no ambiguos
    4. Operaciones de cierre
    5. Jerarquía de Chomsky.
  9. No regularidad y no incontextualidad.
    1. Demostraciones de no regularidad por repetición de estado y por transformaciones que preservan la regularidad.
    2. Demostraciones de no incontextualidad por repetición de variable.
  10. Máquinas de Turing.
    1. Máquinas de Turing deterministas.
    2. Extensiones deterministas o con varias cintas
    3. Equivalencia de máquinas de Turing y algoritmos de alto nivel.
  11. Decidibilidad, semi-decidibilidad, computabilidad.
    1. Lenguajes decidibles
    2. Lenguajes semi-decidibles
    3. Funciones computables
    4. Operaciones de cierre
    5. Teorema del complementario
    6. Teorema de proyección
    7. Conexiones entre semi-decidibilidad y computabilidad.
  12. No decidibilidad, no semi-decidibilidad, no computabilidad.
    1. El lenguaje K, K es semi-decidible pero no decidible.
    2. Reducciones para demostrar no decidibilitdad y no semi-decidibilidad.
    3. Equivalencia entre no semi-decidibilidad y no computabilidad.
  13. Problemas naturales indecidibles.
    1. Accesibilidad de palabras por reescritura.
    2. PCP, intersección no vacía y ambigüidad de gramáticas incontextuales
    3. Universalidad de gramáticas incontextuales y satisfactibilidad de lógica de palabras.

Obviamente esto no incluye computación cuántica, ¡ya llegaremos a ello!


Quizá te interese leer más sobre Computación

Dejar una Respuesta

XHTML: Usted puede usar las siguientes etiquetas: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>