Métodos de Monte Carlo para problemas de conteo.

Abstract

Este proyecto presenta un análisis comparativo entre dos métodos probabilísticos del tipo Monte Carlo aplicados a problemas de conteo combinatorio de alta complejidad computacional: el algoritmo HyperLogLog y las Cadenas de Markov Monte Carlo. El objetivo principal fue evaluar su precisión, escalabilidad y eficiencia en la resolución de dos problemas: el cálculo de la complejidad de Kolmogorov mediante máquinas de Turing y el problema del recorrido del caballo en tableros de ajedrez. HyperLogLog es una técnica diseñada para estimar la cantidad de elementos únicos en grandes volúmenes de datos utilizando poca memoria. Por su parte, MCMC permite muestrear eficientemente sobre espacios de soluciones complejos mediante simulaciones estocásticas. Ambos métodos fueron adaptados a los problemas propuestos y validados frente a valores de referencia obtenidos de la literatura. Los resultados mostraron que HyperLogLog fue más eficaz en el análisis de secuencias binarias, alcanzando errores inferiores al 1% y demostrando buena estabilidad en escenarios de baja complejidad. Además, presentó una eficiencia relativa por unidad de error aproximadamente 3,6 veces mayor que MCMC, lo que lo convierte en la mejor opción para este tipo de problemas cuando se busca precisión final con bajo uso de memoria. En contraste, MCMC fue más adecuado para el recorrido del caballo, especialmente en tableros grandes como el de 8×8, donde HyperLogLog resultó inviable. Para el caso del tablero 6 × 6, MCMC mostró una ventaja significativa, con un speed-up efectivo alrededor de 167 veces superior al de HyperLogLog, lo que indica un aprovechamiento computacional mucho más eficiente en este contexto. Ambos métodos presentaron un bajo consumo de memoria. El desarrollo incluyó la implementación completa de los algoritmos, la generación de escenarios de prueba y la evaluación empírica de métricas como el error relativo y la escalabilidad. También se documentaron dificultades encontradas, como problemas de convergencia, desafíos en la calibración de parámetros y restricciones de recursos. Este trabajo contribuye al estudio y aplicación de métodos probabilísticos en contextos de conteo complejo, y sienta las bases para futuras investigaciones que busquen mejorar su precisión, optimización y aplicabilidad en otras áreas de la computación.