Algoritmo para problema de “Casamiento Estable”

Aunque el problema es conocido como “casamiento estable” (y se soluciona pensando en esta idea), su utilidad es muy amplia y se puede aplicar a una basta gama de problemas actuales. Este problema fue estudiado por primera vez hace ya unos 50 años por Gale y Shapley, con el fin de seleccionar de la manera más óptima y justa a candidatos que postulan a las diferentes universidades. Parece bastante simple la idea, pero veamos un ejemplo que más o menos ilustra las complicaciones del problema: Supongamos que existen n empresas y n candidatos para trabajar (si, nadie quedará sin empleo esta vez), cada empresa necesita tan sólo 1 empleado y vamos a suponer que todos los candidatos postulan a todas las empresas. Seguir leyendo…

¿Cómo trabaja un Algoritmo Genético Simple?

Para hacer una verdadera introducción a los “algoritmos genéticos” probablemente necesitaríamos escribir un libro y no un artículo como este. Intentaremos explicar de dónde viene el nombre algoritmo genético, qué es lo que son, qué +tipos de problemas resuelven, cómo trabajan, qué ventajas y qué desventajas tienen.. Concluiremos con un ejemplo simple de un algoritmo genético (en pseudolenguaje) explicado con lujo de detalles.

¿Por qué Algoritmo Genético?

Un algoritmo genético es básicamente una técnica de búsqueda basada en la teoría de evolución de Darwin. Esta técnica intenta imitar los mecanismos de selección natural, de acuerdo a los cuáles los individuos más aptos de una población son los que sobreviven, pues son capaces de adaptarse más fácilmente a los cambios que se producen en su entorno. En la actualidad se sabe que éstos cambios se efectúan a nivel genético (por esto es el nombre que se le da al algoritmo) y que los atributos más deseables (los que permiten una mejor adaptación en el entorno) son los que se transmiten a los descendientes cuando un individuo se reproduce sexualmente.


Seguir leyendo…

Construyendo Obras de Arte Fractal

¿Qué es un fractal?, ¿cómo se clasifican según sus propiedades?, ¿cómo se construye un fractal?, ¿existe sólo una forma de hacerlo?…. No conozco ningún científico que no se maraville con los fractales, aquellas obras de arte cuya forma y colorido dependen de un patrón dado por una función matemática. El primer concepto de fractal fue propuesto por el matemático Benoît Mandelbrot (1924-2010) en su libro “¿Cuánto mide la costa de Gran Bretaña?” publicado en 1967.

Arte-Fractal Maldenbrot


Seguir leyendo…

Modelamiento del “Juego de la Vida de Conway” mediante Pseudolenguaje

Para comprender lo que realmente es el “juego de la vida”, debemos entender primero lo que es un autómata celular simple, entender las reglas del juego, conocer algunas aplicaciones de este y cómo funciona, para finalmente modelarlo.. en este mismo órden:

¿Qué es un Autómata Celular?

No existe una definición formal de autómata celular (A.C.), sin embargo, la definición que utilizaremos es bastante general y se ajusta al problema que abordamos. Un autómata celular es un modelo matemático para un sistema dinámico que evoluciona en pasos discretos. Es adecuado para modelar sistemas naturales que puedan ser descritos como una colección masiva de objetos simples que interactúen localmente unos con otros mediante reglas que definen el comportamiento del autómata. Seguir leyendo…

Programa algebraico de Multiplicación Veloz o Algoritmo de Karatsuba

Imaginemos que tenemos 2 números a,b con una cantidad muy grande de dí­gitos. Debido a las limitaciones de nuestro sistema computacional, no es posible multiplicar directamente y obtener el resultado a*b, es decir, un programa simple como
Leer más…