Matemáticas en la informática (V): Interpolación polinómica

Seguro que no habías pensado antes en una canción como en una función

Voy a contar una pequeña historia. Estábamos en clase de análisis matemático aburridos mirando a la pantalla del ordenador pensando en como hacer la práctica del día. La práctica consistía en la interpolación polinómica y la verdad es que no teníamos muchas ganas de trabajar.
El profesor se dió cuenta y en lugar de reprocharnos nuestra actitud, nos contó una aplicación sobre lo que trabajabamos. Un alumno de la universidad, ya en su proyecto final de carrera, había creado una aplicación para encontrar canciones al ponerle un fragmento. Nosotros pensamos, bien, bueno, es una aplicación interesante, como Shazam. Cuando preguntó si alguien sabía como funcionaba, obviamente la respuesta que obtuvo fue silencio (los alumnos no es que participasemos mucho de todos modos). Así que procedió a explicarlo. La aplicación interpretaba el sonido como una función, realizaba una interpolación de esa función y buscaba en su base de datos la que más se aproximase. Resultó que era un método bastante bueno para ese problema, como todo tenía sus fallos pero no dejaba de resultar interesante. Algo en lo que nunca habíamos pensado y que despertó nuestra atención, nos hizo pensar en si nosotros seríamos capaces de sacarle alguna funcionalidad al tratamiento de las funciones, alguno ya pensaba en hacerse rico y todo...


Tras esta historia introductoria voy a hablar de que es la interpolación polinómica. En esencia es encontrar un polinomio que pase por un conjunto de puntos dados o aproximarse a otra función

Aquí tenemos un ejemplo de interpolación polinómica de la función tangente

Como ya he dicho al principio, este campo tiene muchas aplicaciones en la informática, si piensas en algo que pueda venir descrito por una función, puedes aplicarlo. Como en el tratamiento de imagenes, en la animación... En la animación se me vienen a la cabeza ejemplos más claros, como que un objeto se mueva, cambie de tamaño, rote, etc. Con la interpolación se crea un efecto de transición y da la sensación de que las cosas cambian en el tiempo.


Con esta última entrada doy por finalizadas mis entradas sobre álgebra, espero que hayan sido interesantes. Un saludo.

Leer más

Matemáticas en la informática(IV): Grafos

¿Sabías que esto de aquí es un grafo?

En esta entrada voy a hablar de los grafos.Para empezar, ¿qué es un grafo? Una breve definición: "un conjunto de nodos unidos por enlaces llamados aristas, que permiten representar relaciones binarias entre elementos de un conjunto"

Hay un montón de conceptos relacionados con los grafos, pero, ¿cómo surgió todo esto? Bueno, vamos a remontarnos en la historia para encontrar su origen.

Los siete puentes del problema

Todo comenzó con el planteamiento para resolver un problema, el problema de los puentes de Königsberg(actualmente Kaliningrado). Esta ciudad era famosa por sus siete puentes, que unen los margenes del rio Pregel con dos de sus islas. El problema planteaba lo siguiente, ¿es posible recorrer todos los puentes pasando una sola vez por cada uno y regresar al mismo punto donde se comenzó?
El matemático suizo Leonhard Euler se propuso resolver el problema, con lo que dio inicio a la teoria de grafos. Concluyo que el problema no tenía solución, puesto que no era posible regresar al punto de inicio sin pasar por alguno de los puentes mas de una vez.


Ya hemos aprendido un poco más sobre los grafos, pero,¿donde podemos verlos en algún campo relacionado con la informática? Bien, aqui tenemos un ejemplo muy ilustrativo, una red de ordenadores, que pueden constituirse con distintas topologías físicas.

Topologías físicas de red

En el caso de las comunicaciones, se buscan siempre grafos completos, que sean completamente conexos, para que en el caso de que falle un nodo los demás puedan seguir funcionando y comunicándose con los otros sin problemas.

También podemos decir que un grafo es una estructura de datos abstracta, que se utiliza para representar un programa, generalmente en lenguajes orientados a objetos. Pero sobre este tema ya avanzaremos más en el próximo trimestre, cuando avancemos en la abstracción de datos, que aún no somos expertos en la materia. Con todo eso dicho, espero que haya resultado interesante aprender sobre los grafos y que empecemos a pensar en la de grafos que nos rodean en el día a día.

Leer más

Matemáticas en la informática(III): Elementos gráficos

Esto requiere de cálculos que no entiendo ni de lejos...

El mundo de la animación hoy en día va de la mano de la informática y de las matemáticas, como vemos en la foto que encabeza esta entrada, los elementos gráficos necesitan de complejos algoritmos capaces de expresar en operaciones matemáticas lo que se intenta dibujar por pantalla.

Un Homer Simpson un tanto cutre

Para dibujar eso por pantalla, mira la operación tan "sencilla" que es necesaria:

x(t) = ((-11/8 sin(17/11-8 t)-3/4 sin(11/7-6 t)-9/10 sin(17/11-5 t)+349/9 sin(t+11/7)+17/12 sin(2 t+8/5)+288/41 sin(3 t+8/5)+69/10 sin(4 t+8/5)+8/5 sin(7 t+13/8)+4/7 sin(9 t+28/17)+4/7 sin(10 t+19/11)+1051/8) theta(39 pi-t) theta(t-35 pi)+(-3/4 sin(11/7-5 t)-54 sin(11/7-t)+237/8 sin(2 t+11/7)+52/11 sin(3 t+33/7)+38/9 sin(4 t+11/7)+249/2) theta(35 pi-t) theta(t-31 pi)+(-16/9 sin(14/9-5 t)-5/2 sin(14/9-3 t)+781/8 sin(t+33/7)+291/11 sin(2 t+11/7)+23/7 sin(4 t+11/7)+18/19 sin(6 t+11/7)+2/5 sin(7 t+61/13)+24/23 sin(8 t+14/9)+1/27 sin(9 t+5/11)+4/11 sin(10 t+11/7)+1/75 sin(11 t+5/8)+1411/7) theta(31 pi-t) theta(t-27 pi)+(-7/11 sin(13/10-13 t)+3003/16 sin(t+33/7)+612/5 sin(2 t+11/7)+542/11 sin(3 t+47/10)+137/7 sin(4 t+51/11)+53/7 sin(5 t+17/11)+23/12 sin(6 t+41/9)+94/11 sin(7 t+51/11)+81/11 sin(8 t+41/9)+53/12 sin(9 t+23/5)+73/21 sin(10 t+13/9)+15/7 sin(11 t+6/5)+37/7 sin(12 t+7/5)+5/9 sin(14 t+27/7)+36/7 sin(15 t+9/2)+68/23 sin(16 t+48/11)+14/9 sin(17 t+32/7)+1999/9) theta(27 pi-t) theta(t-23 pi)+(1692/19 sin(t+29/19)+522/5 sin(2 t+16/11)+767/12 sin(3 t+59/13)+256/11 sin(4 t+31/7)+101/5 sin(5 t+48/11)+163/8 sin(6 t+43/10)+74/11 sin(7 t+49/12)+35/4 sin(8 t+41/10)+22/15 sin(9 t+29/14)+43/10 sin(10 t+4)+16/7 sin(11 t+6/5)+11/21 sin(12 t+55/14)+3/4 sin(13 t+37/10)+13/10 sin(14 t+27/7)+2383/6) theta(23 pi-t) theta(t-19 pi)+(-1/9 sin(7/5-10 t)-2/9 sin(11/9-6 t)+20/11 sin(t+16/15)+7/13 sin(2 t+15/4)+56/13 sin(3 t+25/9)+1/6 sin(4 t+56/15)+5/16 sin(5 t+19/8)+2/5 sin(7 t+5/16)+5/12 sin(8 t+17/5)+1/4 sin(9 t+3)+1181/4) theta(19 pi-t) theta(t-15 pi)+(-1/6 sin(8/11-5 t)+5/8 sin(t+6/5)+13/5 sin(2 t+45/14)+10/3 sin(3 t+7/2)+13/10 sin(4 t+24/25)+1/6 sin(6 t+9/5)+1/4 sin(7 t+37/13)+1/8 sin(8 t+13/4)+1/9 sin(9 t+7/9)+2/9 sin(10 t+63/25)+1/10 sin(11 t+1/9)+4137/8) theta(15 pi-t) theta(t-11 pi)+(-17/13 sin(6/5-12 t)-15/7 sin(25/26-11 t)-13/7 sin(3/14-10 t)-25/7 sin(9/13-6 t)-329/3 sin(8/17-t)+871/8 sin(2 t+2)+513/14 sin(3 t+5/4)+110/9 sin(4 t+3/8)+43/8 sin(5 t+1/5)+43/13 sin(7 t+42/11)+49/16 sin(8 t+11/13)+11/5 sin(9 t+2/7)+5/7 sin(13 t+42/13)+1729/4) theta(11 pi-t) theta(t-7 pi)+(427/5 sin(t+91/45)+3/11 sin(2 t+7/2)+5656/11) theta(7 pi-t) theta(t-3 pi)+(-10/9 sin(7/10-4 t)-7/13 sin(5/6-3 t)-732/7 sin(4/7-t)+63/31 sin(2 t+1/47)+27/16 sin(5 t+11/4)+3700/11) theta(3 pi-t) theta(t+pi)) theta(sqrt(sgn(sin(t/2))))
y(t) = ((-4/11 sin(7/5-10 t)-11/16 sin(14/13-7 t)-481/11 sin(17/11-4 t)-78/7 sin(26/17-3 t)+219/11 sin(t+11/7)+15/7 sin(2 t+18/11)+69/11 sin(5 t+11/7)+31/12 sin(6 t+47/10)+5/8 sin(8 t+19/12)+10/9 sin(9 t+17/11)+5365/11) theta(39 pi-t) theta(t-35 pi)+(-75/13 sin(14/9-4 t)-132/5 sin(11/7-2 t)-83 sin(11/7-t)+1/7 sin(3 t+47/10)+1/8 sin(5 t+14/11)+18332/21) theta(35 pi-t) theta(t-31 pi)+(191/3 sin(t+33/7)+364/9 sin(2 t+33/7)+43/22 sin(3 t+14/3)+158/21 sin(4 t+33/7)+1/4 sin(5 t+74/17)+121/30 sin(6 t+47/10)+1/9 sin(7 t+17/6)+25/11 sin(8 t+61/13)+1/6 sin(9 t+40/9)+7/6 sin(10 t+47/10)+1/14 sin(11 t+55/28)+7435/8) theta(31 pi-t) theta(t-27 pi)+(-4/7 sin(14/9-13 t)+2839/8 sin(t+47/10)+893/6 sin(2 t+61/13)+526/11 sin(3 t+8/5)+802/15 sin(4 t+47/10)+181/36 sin(5 t+13/3)+2089/87 sin(6 t+14/3)+29/8 sin(7 t+69/16)+125/12 sin(8 t+47/10)+4/5 sin(9 t+53/12)+93/47 sin(10 t+61/13)+3/10 sin(11 t+9/7)+13/5 sin(12 t+14/3)+41/21 sin(14 t+22/5)+4/5 sin(15 t+22/5)+14/5 sin(16 t+50/11)+17/7 sin(17 t+40/9)+4180/7) theta(27 pi-t) theta(t-23 pi)+(-7/4 sin(8/11-14 t)-37/13 sin(3/2-12 t)+2345/11 sin(t+32/21)+632/23 sin(2 t+14/3)+29/6 sin(3 t+31/21)+245/11 sin(4 t+5/4)+193/16 sin(5 t+7/5)+19/2 sin(6 t+32/7)+19/5 sin(7 t+17/9)+334/23 sin(8 t+35/8)+11/3 sin(9 t+21/11)+106/15 sin(10 t+22/5)+52/15 sin(11 t+19/12)+7/2 sin(13 t+16/13)+12506/41) theta(23 pi-t) theta(t-19 pi)+(-3/7 sin(1/10-9 t)-1/8 sin(5/14-5 t)-9/8 sin(26/17-2 t)+18/7 sin(t+14/11)+249/50 sin(3 t+37/8)+3/13 sin(4 t+19/9)+2/5 sin(6 t+65/16)+9/17 sin(7 t+1/4)+5/16 sin(8 t+44/13)+2/9 sin(10 t+29/10)+6689/12) theta(19 pi-t) theta(t-15 pi)+(-1/27 sin(1-11 t)-1/6 sin(4/11-10 t)-1/5 sin(2/11-9 t)-7/20 sin(1/2-5 t)-51/14 sin(29/28-3 t)+23/7 sin(t+18/5)+25/9 sin(2 t+53/12)+3/2 sin(4 t+41/15)+1/5 sin(6 t+36/11)+1/12 sin(7 t+14/3)+3/10 sin(8 t+19/9)+3845/7) theta(15 pi-t) theta(t-11 pi)+(-8/7 sin(1/3-13 t)-9/13 sin(4/5-11 t)-32/19 sin(17/12-9 t)-11/6 sin(9/13-8 t)-169/15 sin(8/17-3 t)+917/8 sin(t+55/12)+669/10 sin(2 t+4/13)+122/11 sin(4 t+49/24)+31/9 sin(5 t+1/8)+25/9 sin(6 t+6/7)+43/10 sin(7 t+1/21)+18/19 sin(10 t+9/13)+2/9 sin(12 t+31/15)+1309/5) theta(11 pi-t) theta(t-7 pi)+(-267/38 sin(3/10-2 t)+625/8 sin(t+62/17)+8083/14) theta(7 pi-t) theta(t-3 pi)+(1370/13 sin(t+25/6)+41/21 sin(2 t+205/51)+11/16 sin(3 t+8/13)+9/13 sin(4 t+26/9)+6/5 sin(5 t+11/14)+2251/4) theta(3 pi-t) theta(t+pi)) theta(sqrt(sgn(sin(t/2))))

Ahora imagínate tener que calcular tú todo eso, pero no para ese dibujo tan sencillo, pongamos por ejemplo una escena de una película de animación 3D con muchos elementos visuales, muy detallados. Sería un infierno.

Es por ello que las matemáticas tienen un papel tan importante hoy en día en la animación, son imprescindibles para los complejos software de modelado y para los renderizados que se realizan. Sin ellos, no existiría la "magia" de las peliculas de animación.

Leer más

Matemáticas en la informática(II): Criptografía

Hay que cifrarlo todo muy bien, que nadie nos espie

Bueno, en esta entrada vamos a hablar de la criptografía, algo muy importante en la informática y en las comunicaciones en general. Los matemáticos y los informáticos colaboran hoy en día para hacer cifrados cada vez mejores. Vamos a ver un poco el sistema criptográfico RSA.

RSA

"RSA (Rivest, Shamir y Adleman, sus creadores) es un sistema criptográfico de clave pública desarrollado en 1977. Es el primer y más utilizado algoritmo de este tipo y es válido tanto para cifrar como para firmar digitalmente."

¿Cómo funciona?

Los mensajes enviados se representan mediante números, y el funcionamiento se basa en el producto, conocido, de dos números primos grandes elegidos al azar y mantenidos en secreto.

Para mas información, pinchar aqui.


¿Que utilidad tiene esto?

Hoy en día utilizamos el ordenador para prácticamente todo, consultar información, intercambiar mensajes, fotos, etc. Hay que pararse a pensar en un momento que pasaría si alguien se hiciese con nuestra información mas sensible, como nuestras cuentas bancarias, nuestras contraseñas... Eso a una escala global sería terrible, las comunicaciones serían un caos.

Hay muchos mas algoritmos que no he tratado en esta entrada pero creo que como introducción a la criptografía está bien. Nos vemos en la próxima entrada.

Leer más

Matemáticas en la informática (I): Álgebra de Boole

George Boole. Sin el trabajo de este señor no estarías leyendo esto

En esta entrada voy a tratar una de las bases matemáticas de la informática, ya que sin comprenderla no podríamos entender la informática tal y como lo hacemos hoy en día. Hablo del álgebra de Boole.

Para aquellos que desconozcan de lo que hablo, aquí pongo una breve definición, sacada de wikipedia:

El álgebra de Boole es un sistema matemático centrado en los valores cero y uno (falso y verdadero).En el álgebra de Boole se definen varias operaciones lógicas(AND,OR,NOT.XOR) con las que podemos realizar todo tipo de operaciones.

¿Para que sirve todo esto? Bueno, espero que la siguiente imagen resulte mas ilustrativa de lo que voy a decir

Puertas lógicas de circuitos

El álgebra de Boole se encuentra presente en los circuitos de un ordenador, es lo que le permite interpretar la información, todo ello gracias a los transistores, que pueden dar esos dos valores lógicos de los que hablamos antes (0 y 1) gracias a distintos niveles de voltaje (se suele hablar de que 0 voltios es el 0 lógico y que un valor distinto de 0 voltios es el 1 lógico).

Además de eso, ¿qué podemos hacer con el álgebra de Boole? Podemos expresar predicados, que es algo que no hemos llegado aún a cubrir en la asignatura. Un ejemplo de esto sería algo como:

p="Si llueve"
q="llevare paraguas"
"Si llueve, llevaré paraguas" Esa frase se podría expresar de la forma pq
"No llueve"    Esta sería ~p

Y de este modo se pueden interpretar muchas mas proposiciones de forma lógica, lo cual es útil en el mundo de la informática, pues utilizamos operaciones lógicas al programar.

Con esto doy por finalizado este primer acercamiento a las matemáticas en la informática, en la próxima entrada, veremos la criptografía.

Leer más

Matemáticas en la informática

Todo esto son matemáticas, aunque en un principio no lo parezca...

Bueno, escribo esta entrada para dar inicio a las entradas que van a formar parte de la asignatura de Álgebra y Matemática discreta. En esta serie de entradas voy a intentar cubrir aspectos de la informática que necesitan de las matemáticas para existir. Hay un montón de casos que se extienden mas allá, como la criptografía, el álgebra de Boole... hasta los movimientos del ratón tienen una base matemática detrás.

Leer más