1 2 3 4 5

Sobre Matemáticas y Programación

Walter Mora F.
Escuela de Matemática - Instituto Tecnológico de Costa Rica
wmora@itcr.ac.cr

Resumen

Se hace una descripción de cómo se usan las matemáticas en la solución de algunos problemas de graficación por computadora, usando elementos de Algebra Lineal y matemáticas generales. Se presentan las implementaciones en Java de los ejemplos.

Introducción

En este trabajo vamos a abordar algunas ideas matemáticas para resolver algunos problemas de implementación en el contexto de manejo de gráficos por computadora. Muchas de las ideas provienen del Algebra Lineal en general. En esencia se intenta mostrar como algunas tareas de programación pueden convertirse en un campo adecuado para trabajar en 'matemática aplicada'. La solución de problemas de gráficos requiere habilidades de programación y algoritmos eficientes. En los problemas que se presentan, se muestra la parte matemática que resuelve el problema y la solución de algunos problemas de índole puramente computacional. Los mejores algoritmos para las tareas usuales de programación de gráficos se pueden encontrar en los libros dedicados a la graficación por computadora (Computer Graphics). Una bibliografía básica se puede obtener al final de este trabajo.

Algoritmos eficientes

Desde el punto de vista de las matemáticas, muchas veces importa solo la validez teórica de un resultado y no su eficiencia práctica. Pero en el mundo de los cálculos por computadora, importa el número de operaciones para llevar a cabo una tarea.

Por ejemplo, en el contexto de las matrices A(BC) = (AB)C. Es decir, da lo mismo hacer el producto A(BC) que el producto (AB)C. El resultado es el mismo. Desde el punto de vista de la computación estos cálculos pueden ser muy distintos en términos de esfuerzo computacional. En efecto, si calculamos solamente el número de multiplicaciones que requiere cada una de estos productos de matrices, podemos obtener resultados dramáticamente distintos!

Si tenemos las matrices A_m×n = (a_ij) y B_n×k = (b_ij) entonces, si denotamos la fila i-ésima de A con

F_i = (a_i1,^..., a_in) y la columna j-ésima de B con C^j = (b_1j,^..., b_nj) entonces

AB = $\displaystyle \sum_{i=1}^{m}$ $\displaystyle \sum_{j=1}^{k}$ F_i^.C^j = $\displaystyle \sum_{i=1}^{m}$ $\displaystyle \left(\vphantom{\sum_{j=1}^k \left(\sum_{h=1}^n a_{ih}b_{hj}\right) }\right.$ $\displaystyle \sum_{j=1}^{k}$ $\displaystyle \left(\vphantom{\sum_{h=1}^n a_{ih}b_{hj}}\right.$ $\displaystyle \sum_{h=1}^{n}$ a_ihb_hj $\displaystyle \left.\vphantom{\sum_{h=1}^n a_{ih}b_{hj}}\right)$ $\displaystyle \left.\vphantom{\sum_{j=1}^k \left(\sum_{h=1}^n a_{ih}b_{hj}\right) }\right)$

de donde, para hacer la multiplicación A_m×nB_n×k se requieren m^.k^.n multiplicaciones (no estamos contando sumas).

Así, la multiplicación A_10×100B_100×5 requiere 5000 multiplicaciones mientras que B_100×5C_5×50 requiere 25000 multiplicaciones, finalmente

(A_10×100B_100×5)C_5×50 requiere 5 000 + 2 500 = 7 500 multiplicaciones
A_10×100(B_100×5C_5×50) requiere 25 000 + 50 000 = 75 000 multiplicaciones

Así, aunque (AB)C = A(BC), computacionalmente es mejor calcular (AB)C en este caso, pues requiere 67 500 multiplicaciones menos!

Una discusión detallada de este tópico se puede ver en [Cormen]

1 2 3 4 5

Revista Virtual, Matemática Educación e Internet.
Derechos Reservados.