Please use this identifier to cite or link to this item:
https://rinacional.tecnm.mx/jspui/handle/TecNM/5779| Title: | Programa simulador de una máquina de Turing no determinista |
| Authors: | ALCUDIA CHAGALA, LORENA |
| Issue Date: | 2012-11-01 |
| Publisher: | 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 |
| Appears in Collections: | Maestría en Ciencias de la Computación |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Programa simulador de una máquina de Turing no determinista.pdf | TESIS | 3.02 MB | Adobe PDF | View/Open |
This item is protected by original copyright |
This item is licensed under a Creative Commons License
