Dublin Core
Title
Análisis experimental de algoritmos de aproximación aleatorizados para conteo en autómatas
Subject
Algoritmos aleatorizados
Complejidad computacional
Autómatas
Análisis experimental de algoritmos
620
Ingeniería
Description
Tesis (Magíster en Ciencias de la Ingeniería)--Pontificia Universidad Católica de Chile, 2023
Esta tesis analiza el rendimiento de algoritmos para el problema #NFA, que consiste en contar la cantidad de palabras aceptadas, de un largo dado, en autómatas finitas no deterministas (NFAs). Este trabajo contiene la primera implementación y análisis empírico del algoritmo de aproximación aleatorizado propuesto por Arenas et al. (2021). Este estudio utiliza una metodología experimental para evaluar el algoritmo en tres familias diferentes de NFAs, incluyendo el modelo de Tabakov-Vardi de NFAs aleatorios.Los resultados muestran que el algoritmo de Arenas et al. no logra superar en eficiencia a los algoritmos tradicionales de determinización, incluso con relajaciones en sus parámetros. Esto sugiere que, aunque el algoritmo presenta una complejidad polinomial teórica, en la realidad no resulta efectivo para situaciones realistas, caracterizándolo como un posible algoritmo galáctico (Lipton & Regan, 2013). Asimismo, la tesis recomienda direcciones de investigación futuras. Esto incluye el desarrollo de métodos alternativos para generar NFAs aleatorios y la mejora de la eficacia en las subrutinas de muestreo de los algoritmos de aproximación aleatorizados. De esta forma, el estudio abre nuevos caminos tanto en el desarrollo de algoritmos para el problema #NFA como en las metodologías de evaluación de estos.
Creator
Rodríguez Reveco, Ricardo Raúl
Date
2024-01-30T14:03:44Z
2024-01-30T14:03:44Z
2023
Contributor
Arenas Saavedra, Marcelo Alejandro
Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Rights
acceso abierto
Format
xv, 106 páginas
application/pdf
Language
es
Type
tesis de maestría
Identifier
https://repositorio.uc.cl/handle/11534/81052