Una introducción básica

La Programación Matemática como rama de la Matemática Aplicada ha estudiado (desde mediados del siglo XX) problemas de decisión en los que se deben determinar acciones que optimicen un determinado objetivo (optimización).
El elemento clave con el que se sirve la programación matemática para verificar el método científico es el modelo matemático. Los modelos matemáticos son abstracciones simplificadas de sistemas reales que destacan las relaciones e interacciones principales entre las entidades del sistema estudiado1. Para elaborar dichos modelos, la programación matemática se nutre de resultados del álgebra, del análisis matemático, del cálculo numérico, de la geometría, de la topología, etc. El proceso de modelización debe verificar el método científico tal como puede observarse en el siguiente diagrama:
metodocientifico Dentro de los modelos, los problemas de optimización que se intentan resolver suelen tener la siguiente forma: min\{f(x) : x \in S\} es decir, encontrar si existe un elemento (o todos los elementos) donde la función objetivo f alcance su valor mínimo (o máximo), siendo el conjunto S el de las soluciones factibles. Las búsquedas de dichas soluciones puede concluir con uno de los siguientes resultados:

  • Problema no factible: No hay ninguna solución factible, es decir, que el conjunto S=\{\emptyset\}
  • Problema no acotado: Cuando no se determina que siempre se encontrará una solución mejor, que haga tender a infinito (positivo o negativo) la función objetivo.
  • Problema con óptimo: Cuando se encuentra al menos una solución que satisface el la función objetivo siendo un mínimo (o máximo) global.

Según las características de las variables e inecuaciones (restricciones) de cada modelo, la programación matemática puede dividirse en varias ramas, como la programación lineal (cuando la función objetivo es lineal), y la no lineal. Por otro lado, cuando la variable a estudiar es entera2 (o natural) se habla de Programación Entera (lineal o no lineal). Otra rama de interés es la Optimización Combinatoria, que intenta resolver problemas caracterizados por tener un número finito (pero muy grande en general) de posibles soluciones.
Son muchas las herramientas y técnicas que asisten a la programación matemática para intentar abordar estos problemas.
Todo algoritmo utilizado para resolver un problema posee un orden de complejidad estudiado por la Teoría de la Complejidad Algorítmica. Este orden de complejidad estudia la mayor número de “pasos” que deberá ejecutar el algoritmo para resolver el problema en función del tamaño de la entrada de datos al algoritmo. Por tanto es importante no el hecho de conocer en sí la cantidad de pasos que utilizará para cada tamaño de instancia (o entrada), sino el orden de crecimiento de la cantidad de pasos que realizará el algoritmo. Este orden de crecimiento se describe con la llamada notación “O”. Por ejemplo, para un orden de crecimiento cuadrático, se denotará O(). El orden de complejidad nos dará una pauta de cuán tratable es un problema, para ilustrar las connotaciones del crecimiento del orden de complejidad se adjunta la siguiente tabla que muestra para distintos órdenes de complejidad, como crecen según el tamaño de la entrada al algoritmo:

cuadroorden

Si un problema admite una solución con un algoritmo de orden polinomial, se dice que pertenece a la clase P. Los problemas con un orden mayor al polinomial se conocen como NP (no polinomiales). Muchos de los problemas que estudia la programación matemática pertenecen a la clase NP3.
Los algoritmos genéticos (o de forma más general, la programación evolutiva) son algoritmos que se inspiran en la evolución biológica para buscar soluciones en espacios de estados. La gran mayoría de los problemas que busca solucionar la inteligencia artificial son problemas complejos de búsqueda en espacios de estados muy grandes. Si bien son algoritmos de búsqueda, se han utilizado (casi exclusivamente) en problemas de optimización combinatoria para problemas NP. Tienen la característica de ser altamente paralelizables4, lo que lo diferencia de muchos de los mecanismos de resolución clásicos de programación matemática, que esencialmente son soluciones secuenciales poco paralelizables.
MapReduce es un aporte5 introducido con la aparición de las bases de datos NoSQL y la necesidad de manejar grandes volúmenes de datos cada vez más complejos (con un orden mucho mayor de relaciones que las bases de datos más tradicionales). Este mecanismo de naturaleza funcional permite paralelizar problemas sobre distintos tipos de clusters estableciendo un marco de trabajo estándar para desarrollar trabajos altamente paralelizables.
Una vez introducidos los conceptos claves del trabajo, se pueden enumerar los objetivos del mismo:

  1. Construir una máquina o framework para correr algoritmos genéticos sobre MapReduce maximizando el nivel de paralelismo.
  2. Una vez logrado el primer objetivo, se procederá a estudiar la complejidad de los algoritmos dentro de este nuevo marco.
  3. Se estudiarán alternativas de paralelismo, contando con los desarrollos ya aportados sobre poblaciones.
  4. Se estudiarán las analogías (evaluadas y no evaluadas aún) con la biología, desde el punto de vista del alto paralelismo alcanzado.
  5. Se tratarán modelos de gran complejidad para optimizar la generación de energía eléctrica térmica e hídrica en la República Argentina.

Notas
1 Algunos de los modelos proceden directamente de la realidad, pero muchos otros son planteos de otras ramas de la ciencia, como la Teoría de Juegos, la teoría de grafos, la teoría de la decisión, la bioinformática, etc.
2 Ecuaciones deofánticas.
3 Uno de los problemas abiertos de la ciencia de la computación más interesantes es determinar si P = NP.
4 Esto quiere decir que pueden ser resueltos en paralelo de manera eficiente por varios procesadores al mismo tiempo.
5 Inicialmente concebido por Google.

Anuncios

2 pensamientos en “Una introducción básica

    • Muchas gracias! Tiene razón! Ya actualicé. Corregido. Es lo que necesito, correcciones, lecturas críticas, sopapos, etc…. Lo que estoy usando es latex, un viejo amor de la era de estudiante… Algo a veces críptico que te salva muchas veces. Acá en wordpress está nativo, por ejemplo para poner conjunto vacío lo que tiene que escribir en la entrada es $ l a t e x \ e m p t y s e t $ \emptyset

Deje un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s