1. Repositorio Institucional del Tecnológico Nacional de México (RI - TecNM)
2. Tesis de Posgrado
3. Tamaulipas
4. Instituto Tecnológico de Ciudad Madero
5. Tesis
6. Tesis de Maestría
7. Maestría en Ciencias de la Computación

Titre:	Programa simulador de una máquina de Turing no determinista
Auteur(s):	ALCUDIA CHAGALA, LORENA
Date de publication:	2012-11-01
Editeur:	Tecnológico Nacional de México
metadata.dc.publisher.tecnm:	Instituto Tecnológico de Ciudad Madero
Description:	Actualmente podemos resolver una gran cantidad de problemas mediante el uso de la programación; sin embargo, ¿cómo podemos saber cuál es la mejor manera de resolverlos?, y más aún ¿cómo saber si nuestra solución es buena? Para dar respuesta a estas interrogantes, recurrimos al análisis de la complejidad y nos adentramos a la teoría de la complejidad computacional, definida como la rama de la teoría de la computación que estudia (de manera teórica) los recursos requeridos en el proceso de cómputo de un algoritmo para resolver un problema. Tales recursos son el tiempo (número y tipo de pasos de ejecución de un algoritmo) y el espacio (cantidad de memoria utilizada para la solución de un problema). En este trabajo se plantea la problemática en la resolución de problemas con máquinas de Turing, ya que en la literatura se explican problemas bastante rudimentarios, con lo cual imaginarse problemas complejos con máquinas de Turing, resulta ser muy complicado. Para el entendimiento de problemas complejos se desarrolló una herramienta de simulación de máquinas de Turing, esta herramienta permite resolver problemas NP-completos. El programa de simulación se presenta en dos versiones, en la versión 1 las reglas de transición de la máquina de Turing de un problema en cuestión se introducen por archivos de texto y en la versión 2 las reglas de transición son introducidas mediante un editor de autómatas. Para probar el funcionamiento de la herramienta de simulación se experimentó con el problema del circuito Hamiltoniano y el problema de Partición. En base a la experimentación realizada con los problemas de decisión anteriores se obtuvo una herramienta capáz de resolver problemas complejos, permitiendo la introducción de reglas de transición de manera modular, y facilitando al usuario mediante la introducción de reglas abreviadas la generación autómatica en un 80% de las reglas de transición pertenecientes a un problema NP-completo.
metadata.dc.type:	info:eu-repo/semantics/masterThesis
Collection(s) :	Maestría en Ciencias de la Computación

Ce document est protégé par copyright Voir la licence

Ce document est autorisé sous une licence de type Licence Creative Commons