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

Empecemos por el principio, la definición de Teoría de la Computacion en wikipedia y de este índice de contenidos que me parece más que razonable como punto de partida.

  1. Introducción a Teoría de la Computación
  2. Lenguajes formales.
    1. Alfabetos, palabras, lenguajes, operaciones sobre lenguajes (concatenación, reverso, estrella), morfismos, sistemas de reescritura.
  3. Autómatas finitos.
    Autómatas finitos deterministas, autómatas finitos indeterministas, autómatas finitos con lambda-transiciones, equivalencia entre modelos de autómatas, operaciones sobre autómatas, minimización de autómatas.
  4. Gramáticas incontextuales.
    Gramàticas incontextuales, lenguaje generado por una gramática, árbol de derivación, ambigüidad, operaciones sobre gramáticas, depuración de gramáticas.
  5. Expresiones regulares.
    Expresiones regulares, equivalencia con autómatas y Lema de Arden, operaciones sobre expresiones regulares.
  6. Autómatas con pila.
    Autómatas con pila indeterministas y su equivalencia con lenguajes incontextuales, autómatas con pila deterministas, autómatas con pila de aceptación única y su equivalencia con lenguajes incontextuales no ambiguos, operaciones de cierre, jerarquía de Chomsky.
  7. No regularidad y no incontextualidad.
    Demostraciones de no regularidad por repetición de estado y por transformaciones que preservan la regularidad. Demostraciones de no incontextualidad por repetición de variable.
  8. Máquinas de Turing.
    Máquinas de Turing deterministas, extensiones indeterministas o con varias cintas, equivalencia de máquinas de Turing y algoritmos de alto nivel.
  9. Decidibilidad, semi-decidibilidad, computabilidad.
    Lenguajes decidibles, lenguajes semi-decidibles, funciones computables, operaciones de cierre, teorema del complementario, teorema de proyección, conexiones entre semi-decidibilidad y computabilidad.
  10. No decidibilidad, no semi-decidibilidad, no computabilidad.
    El lenguaje K, K es semi-decidible pero no decidible, reducciones para demostrar no decidibilitdad y no semi-decidibilidad, equivalencia entre no semi-decidibilidad y no computabilidad.
  11. Problemas naturales indecidibles.
    Accesibilidad de palabras por reescritura, PCP, intersección no vacía y ambigüidad de gramáticas incontextuales, 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>