Diferencias

Muestra las diferencias entre dos versiones de la página.

Enlace a la vista de comparación

materias:computabilidadcomplejidad [2016/09/13 06:13]
frank.valencia [Información Básica]
materias:computabilidadcomplejidad [2016/09/13 06:26] (actual)
frank.valencia [Descripción del Curso]
Línea 12: Línea 12:
 El curso comienza con un contexto motivador que describe el origen de computación y su relación estrecha con la lógica matemática.  El curso cubre  tres modelos fundamentales de computación y sus correspondientes lenguajes formales: Máquinas de estado finito y lenguajes regulares, máquinas de pila y lenguajes incontextuales, máquinas de Turing y lenguajes recursivos. Se estudiará la expresividad de estos modelos y sus limitaciones absolutas: En particular, se mostrará formalmente que hay problemas que no pueden ser solucionados (decididos) por ninguna máquina de Turing (el más expresivos de todos los modelos computacionales), lo cual implica que no pueden ser solucionados por ningún algoritmo de acuerdo a la tesis fundamental de Turing (también estudiada en el curso).  El curso comienza con un contexto motivador que describe el origen de computación y su relación estrecha con la lógica matemática.  El curso cubre  tres modelos fundamentales de computación y sus correspondientes lenguajes formales: Máquinas de estado finito y lenguajes regulares, máquinas de pila y lenguajes incontextuales, máquinas de Turing y lenguajes recursivos. Se estudiará la expresividad de estos modelos y sus limitaciones absolutas: En particular, se mostrará formalmente que hay problemas que no pueden ser solucionados (decididos) por ninguna máquina de Turing (el más expresivos de todos los modelos computacionales), lo cual implica que no pueden ser solucionados por ningún algoritmo de acuerdo a la tesis fundamental de Turing (también estudiada en el curso). 
  
-Por otro lado también se estudiarán y clasificarán, de acuerdo a su complejidad espacial y temporal inherente, problemas fundamentales que sí pueden ser decididos por una máquina de Turing. Este estudio cubre temas para el análisis de complejidad especial de algoritmos y estructuras de datos como también clases fundamentales de problemas que pueden ser solucionadas en tiempo polinomial de una manera determinista (P), no determinista (NP), en tiempo exponencial de manera determinista (EXP), y con espacio polinomial de manera determinista (EXP).+Por otro lado también se estudiarán y clasificarán, de acuerdo a su complejidad espacial y temporal inherente, problemas fundamentales que sí pueden ser decididos por una máquina de Turing. Este estudio cubre el análisis de complejidad de algoritmos y estructuras de datos,  como también clases fundamentales de problemas que pueden ser solucionadas en tiempo polinomial de una manera determinista (P), no determinista (NP), en tiempo exponencial de manera determinista (EXP), y con espacio polinomial de manera determinista (EXP).
  
  
 
materias/computabilidadcomplejidad.txt · Última modificación: 2016/09/13 06:26 por frank.valencia
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki