Análisis experimental de algoritmos de aproximación aleatorizados para conteo en autómatas

Simple item page
dc.catalogadorpva
dc.contributor.advisorArenas Saavedra, Marcelo Alejandro
dc.contributor.authorRodríguez Reveco, Ricardo Raúl
dc.contributor.otherPontificia Universidad Católica de Chile. Escuela de Ingeniería
dc.date.accessioned2024-01-30T14:03:44Z
dc.date.available2024-01-30T14:03:44Z
dc.date.issued2023
dc.descriptionTesis (Magíster en Ciencias de la Ingeniería)--Pontificia Universidad Católica de Chile, 2023
dc.description.abstractEsta 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.
dc.fechaingreso.objetodigital2024-01-30
dc.format.extentxv, 106 páginas
dc.fuente.origenSRIA
dc.identifier.doi10.7764/TesisUC/ING/81052
dc.identifier.urihttps://doi.org/10.7764/TesisUC/ING/81052
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/81052
dc.information.autorucEscuela de Ingeniería; Arenas Saavedra, Marcelo Alejandro; 0000-0003-3678-1868; 81488
dc.information.autorucEscuela de Ingeniería; Rodríguez Reveco, Ricardo Raúl; S/I; 233091
dc.language.isoes
dc.nota.accesoContenido completo
dc.rightsacceso abierto
dc.subjectAlgoritmos aleatorizadoses_ES
dc.subjectComplejidad computacionales_ES
dc.subjectAutómatases_ES
dc.subjectAnálisis experimental de algoritmoses_ES
dc.subject.ddc620
dc.subject.deweyIngenieríaes_ES
dc.titleAnálisis experimental de algoritmos de aproximación aleatorizados para conteo en autómatases_ES
dc.typetesis de maestría
sipa.codpersvinculados81488
sipa.codpersvinculados233091
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TESIS_RRodríguez_Firma Final.pdf
Size:
628.58 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.98 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
3.01 Tesis magíster