Evaluación probabilística de problemas #P-Completos mediante el método de Montecarlo y su implementación concurrente

Ponente(s): Luis Daniel Ramos Lopez, María Guadalupe Rodríguez Sánchez

En esta plática se presenta un método numérico probabilístico para estimar soluciones de problemas #P-Completos, mediante el uso del método de Montecarlo. Se describe una generalización del algoritmo, junto con una implementación concurrente en C++ que aprovecha bibliotecas estándar y funciones intrínsecas del procesador para generar instancias aleatorias de manera eficiente, además del uso de hilos a nivel de usuario. Finalmente, se mostrarán comparaciones de tiempos de ejecución y precisión de las estimaciones frente a algoritmos clásicos como búsqueda con retroceso o programación dinámica, destacando la escalabilidad y las limitaciones del método propuesto.