Algoritmos probabilÍsticos

Abstract

Este documento contiene el informe del seminario de grado titulado “Algoritmos probabilísticos” desarrollado en el marco de las actividades del grupo de estudio y desarrollo investigativo en matemática aplicada, en la línea de matemática computacional. Inicialmente se presentan algunos ejemplos de este tipo de algoritmos para después mostrar las diferentes clases de algoritmos probabilísticos que se conocen: Algoritmos de las Vegas y algoritmos de Monte Carlo; se ilustran algunos ejemplos de cada una de estas clases y se analiza la probabilidad de que estos algoritmos siempre encuentren una respuesta correcta, así como la probabilidad de error y el tiempo de complejidad de tales algoritmos. Finalmente, se formaliza el concepto de algoritmo probabilístico, utilizando para ello el modelo de computación teórico conocido como máquina de Turing no determinística con algunas características especiales, algunos de los temas desarrollados en el seminario de grado se han complementado con ejemplos, tablas y gráficas para una mayor facilidad en su comprensión.