Algebra lineal y computacion PDF

Preview

Summary

investigacion realizada sobre Algebra lineal y la computación ...

Description

Universidad Autónoma de Baja California Sur.

Ingeniería en desarrollo de software. . Álgebra lineal.

Álgebra lineal y la Computación.

Tercer semestre.

Jennifer Lopez Urquidez.

Nelson Eduardo Olachea Urias.

La Paz, B.C.S. A 18 de agosto de 2018.

Introducción. En el presente trabajo se habla del algebra lineal y computación como concepto, la relación que tienen estos dos, y sus aplicaciones en el mundo de la informática, ya que estos dos conceptos se relación muy estrechamente. El cuerpo de este documento contiene información con relación en los videojuegos, buscadores de información (más específicamente google), seguridad informática, criptografía y el algoritmo de flujo máximo en las redes de transporte de elementos. Álgebra lineal, esta materia tomo importancia en la computación debido a la cantidad de operaciones que se requieren en este ámbito. El manejo de imágenes, y digitalización de todo tipo de información requiere de vectores y el grupo de vectores que forman matrices, justo lo que explica el álgebra lineal. El álgebra lineal una rama de las matemáticas que proporciona conocimientos para resolver problemas de aplicaciones en la vida real e ingeniería, ya que ayuda a convertir ciertos fenómenos en modelos lineales para poder manejarlos, graficarlos y resolverlos de una forma más fácil. A simple vista puede no parecer que estén tan relacionadas, sin embargo el trabajo detrás lleva un largo proceso de estudio y aplicación del algebra lineal.

Algebra lineal. Podemos entender como algebra a la rama de las matemáticas que engloba las operaciones aritméticas a través de signos, letras y números. Lineal define todo lo referente a una línea o una sucesión, en este ámbito la idea de lineal hace referencia a aquello que cuenta con consecuencias proporcionales a una causa. De modo que el álgebra lineal es una rama de las matemáticas que estudia conceptos como: vectores, matrices, sistemas de ecuaciones lineales, espacios vectoriales, y sus transformaciones lineales. Alrededor de 1840 se desarrolló esta rama gracias a las aportaciones de Hermann Grassmann y William Rowan Hamilton. El álgebra lineal tiene una amplia variedad de aplicaciones en diferentes ramas como por ejemplo: administración, economía, ciencias sociales, ingeniería, física, biología, entre otros.

Computación. La palabra computación proviene del latín computatĭo, computatiōnis, que deriva del verbo computāre, cuyo significado es ‘enumerar cantidades’. Computación, en este sentido, designa la acción y efecto de computar, realizar una cuenta, un cálculo matemático. De allí que antiguamente computación fuese un término usado para referirse a los cálculos realizados por una persona con un instrumento utilizado para tal fin (como por ejemplo el ábaco) o sin él. Computación se refiere a la tecnología diseñada para el manejo automático de la información mediante el uso computadoras, entiéndase como información al conjunto organizado de datos. En este sentido, la computación es también un área de conocimiento constituida por disciplinas relativas a las ciencias y la tecnología, para el estudio, desde el punto de vista teórico y práctico, de los fundamentos del procesamiento automático de datos, y su desarrollo, implementación y aplicación en sistemas informáticos.

Relación. La computación convive de manera muy cercana con las matemáticas, se utiliza en una gran cantidad de procesos, llevan una estrecha relación. Sin embargo, específicamente en el área de álgebra lineal en relación con la computación se utiliza en diversos tipos de problemáticas, se utiliza en desarrollo de algunas aplicaciones (videojuegos, diseños y modelado de gráficos en 2D y 3d y en la escala de imágenes, etc.) lo que se hace en estas cuando se cambia la vista, en la rotación de cámaras o incluso el movimiento de la imagen es una

transformación lineal, conceptos que se aprenden en espacios vectoriales en algebra línea, entre otras. El álgebra lineal se aplica en la Informática en el ejemplo más claro, Google, que a través de vectores, matrices y cálculos matemáticos se manejan los conceptos de las búsquedas para la muestra de resultados. El álgebra lineal también es aplicada en la seguridad informática en el campo de criptografía para transformar el texto en otra estructura diferente, irreconocible a simple vista.

Google. Existen muchas aplicaciones del algebra lineal en la programación, por ejemplo en los buscadores, siendo Google el más completo y desarrollado. Google es una compañía de la industria del internet, software, hardware y tecnología, que tiene como principal producto un motor de búsqueda que permite encontrar información de un determinado tema y arroja un sinfín de páginas web, videos e imágenes. Esto no es por arte de magia, google tiene un largo proceso detrás que incluye inteligencia artificial, donde rastrean (recolectan) información y de esa misma página sigue los enlaces que lleva a otras. Centrándonos en el álgebra lineal, la facilidad con la que google muestra los resultados se debe al algoritmo de Larry Page, llamado “PageRank”, que se basa en la teoría de grafos. El conjunto de páginas web de internet es un grafo dirigido (dígrafo), de modo que cada página web es un nodo y estas están relacionadas, ya que estas mismas se enlazan entre sí y por ello reciben votos. Si a la página en cuestión la citan muchas páginas y/o páginas importantes recibe más votos, por tanto se posicionan mejor en el buscador.

La importancia ‘xj’ de la página ‘Pj’ es proporcional a la suma de las importancias de las páginas que enlazan con ‘Pj’.

Después se crea una matriz (M) de adyacencia con los valores del dígrafo, para t finalizar con cálculos algebraicos que implica ecuaciones como: M ∙ x= λ∙ x Donde: λ=constantede proporcionalidad ↔ un valor propio de M t

x= ( x 1 , x 2 ,… , x n ) vector de importancias

de las paginas web ↔un vector propio de M t (asociado a λ)

Después de aplican otros teoremas que entran en matemáticas aplicadas. Todo esto da un valor de importancia a la página web, lo cual lo coloca en una buena posición en la ordenación de páginas mostradas por google o todo lo contrario. Sin embargo, no sirve de nada el dígrafo, ni las matrices, ni los cálculos, si la información relacionada con las páginas no es almacenada para ser consultado después, a este proceso se le conoce como indexación. Para finalizar el tema del PageRank, anexo una breve descripción de lo que es este sistema (traducido): “Suponemos que la página A tiene páginas T1 ... Tn que lo señalan (es decir, son citas). El parámetro d es un factor de amortiguación que se puede establecer entre 0 y 1. Por lo general, establecemos d a 0,85. Hay más detalles sobre d en la siguiente sección. También C (A) se define como el número de enlaces que salen de la página A. El PageRank de una página A se da de la siguiente manera: PR (A) = (1-d) + d (PR (T1) / C (T1) + ... + PR (Tn) / C (Tn)) Tenga en cuenta que los PageRank forman una distribución de probabilidad sobre las páginas web, por lo que la suma de los PageRank de todas las páginas web será uno.”

Videojuegos. A pesar de que la mayoría de personas creen que el desarrollo de videojuegos es sencillo, no podrían estar más equivocados, el desarrollo de videojuegos implica un cumulo de aplicaciones de matemáticas tanto como geometría, algebra lineal, trigonometría, entre otros. Desde los antiguos juegos en 2D, se utilizan conceptos del algebra lineal, en especial para representar el punto en el que se encuentran los objetos y el movimiento de esos mismos. Ahora los videojuegos tienen más cálculos que antes, desde la llegada de los famosos juegos en 3D. Un vector es una forma matemática de representar un punto. Un vector puede tener dos dimensiones y si se le añade otro componente se convierte en un vector tridimensional, generalmente sus componentes son llamados X, Y y Z. Los vectores hacen posible colocar un objeto en un determinado punto, esto hace posible que los objetos puedan interactuar entre sí, porque se conoce el punto exacto de cada uno y puede compararse si estos pueden interactuar o no.

Otro ejemplo simple que involucra nodos y gráficos es un mapa de algunas ciudades y las carreteras entre ellas (o un mapa subterráneo). Cada ciudad es un nodo, generalmente dibujado como una burbuja circular. Cada camino es un borde, y conecta dos nodos (ciudades), estos se dibujan generalmente como líneas rectas. Toda la colección de nodos y aristas (ciudades y caminos) se llama un gráfico. A veces hay un camino de una sola dirección, llamado borde dirigido, y le dibujamos una flecha para mostrar en qué dirección puede viajar a lo largo de él. Para complicar un poco más las cosas, a veces se agrega algo llamado “costo” a cada borde. La idea de un costo es que indica cuánto costaría viajar por ese borde.

Procesamiento de imágenes. El procesamiento digital de imágenes no se limita solamente a retocar o cambiar el tamaño de las imágenes capturadas, su uso se extiende a muchos campos de la ciencia y la tecnología. Algunos de los campos más importantes son: la medicina, la detección remota, la transmisión y codificación de datos, la robótica, la visión artificial, el reconocimiento de patrones, la industria cinematográfica, procesamiento de imágenes obtenidas de microscopios y la restauración y enfocado de imágenes. Ejemplos del procesamiento digital de imágenes usando herramientas del álgebra lineal son: traslación, rotación, sesgado, escalado, uso de las curvas de Bézier, reflexión y ajustes de canal, brillo y contraste. Otras operaciones más complejas como filtros, requieren la combinación del álgebra lineal con otras herramientas matemáticas. Una imagen puede ser representada como una matriz de m x n, repleta de pequeños elementos (conocidos como pixeles). Al asignar un número a cada color, la matriz se convierte en una matriz numérica. Los filtros se aplican a las imágenes digitales para mejorar la calidad o hacer más rápida la búsqueda de información. Por ejemplo: suavizar la imagen, reducir la cantidad de variaciones de intensidad entre cada pixel (es decir, no

cambiar bruscamente de color entre una celda de la matriz y otra); eliminar ruido, cambiar la intensidad de los pixeles; detectar bordes, detectar bordes donde se produce el cambio brusco de intensidad; realzar bordes, destacar los bordes que se encuentran en la imagen. Cada operación se realiza directamente en los valores de la matriz. El ajuste de brillo implica cambiar el porcentaje de luminiscencia y oscuridad de un color.

Donde: m mn corresponde a un vector ( r , g , b ) correspondiente ala imagen. p es el parametro de ajuste de brillo , cuyo valor va de−100 a 100.

¿ la matriz C correspode a la imagen con el . Invertir colores (negativo): Esta operación se trata de transformar cada RGB a su negativo.

La rotación de una imagen viene dada por una transformación lineal en la que las coordenadas del punto imagen son expresadas en términos de las del punto original a través de ecuaciones.

{

1

( ) ( )( ) 1

x ax + by x → 1 = ab x 1= cd y y y cx+dy

Seguridad informática. El álgebra lineal se puede implementar incluso en un protocolo de comunicación segura a nivel de alcance de datos del protocolo IPv6. En esta aplicación se implementan conceptos como los que se relacionaron con el desarrollo del algoritmo de Google. Esta aplicación del algebra lineal en la informática fue expuesta en “ekoparty” (conferencia de seguridad de Argentina). En este caso plantearon una doble transformación de dominios para luego hacer el análisis. Primero cambiaron al dominio de los grafos, es decir, convirtieron toda la captura de red en un grafo donde las relaciones del mismo pueden tener un peso, dependiendo de la cantidad y el tipo de tráfico generado entre los nodos. Luego, a partir del grafo construyen una matriz, en este caso la matriz laplaciana (un tipo de matriz similar a la de adyacencia), la cual aporta información relevante de un grafo. Dentro de los cálculos que hacían estaban los valores y vectores propios de la matriz (también conocidos como eigenvalores y eigenvectores) para luego aplicar algoritmos de Spectral Clustering y encontrar patrones.

Criptografía. La criptografía trata de proteger la comunicación con datos delicados por medio de la encriptación de datos (transformar los datos a una forma ilegible), esto también implica descifrar el mensaje. El sistema de cifrado Hill implica el uso de matrices como el sistema de cifrado para encriptar el mensaje. Lo primero es tener una matriz invertible (A; que será la matriz de claves) y transformar el mensaje a una secuencia de números, dando a cada carácter un valor especifico, una vez hecho esto, se forma una matriz (B) mediante la agrupación de los números en columnas de acuerdo al orden de la matriz de claves (la cantidad de números de cada columna debe ser igual al orden de la matriz). Después se multiplica la matriz de claves (A) por la matriz B, obteniendo como resultado otra matriz (C), la cual es la matriz cifrada. C=A∗B

Por ultimo para descifrar el mensaje se multiplica la matriz inversa de A por C.

Algoritmo de flujo máximo. Este algoritmo se usa para planificar rutas aéreas, solucionar problemas de logística o crear redes de comunicaciones. En 2010, el Instituto tecnológico de Massachusetts (MIT) junto con la Universidad de Yale y la Universidad del Sur de California, lograron una mejora en este algoritmo en los 10 años anteriores a este. De la forma más simple puede decirse que este algoritmo se utiliza para calcular la cantidad máxima de elementos que pueden pasar de un extremo a otro de una red, teniendo en cuenta las limitaciones de la capacidad de los enlaces de esa red. Esos elementos son por ejemplo, los paquetes de datos que viajan a través de Internet o las cajas de mercancías que se trasladan por las carreteras. En estos casos las limitaciones en los enlaces se refieren a la velocidad de la conexión a Internet o a la velocidad media del tráfico en las carreteras en hora pico. La manera de representar una red de comunicaciones es mediante un grafo. En el problema de flujo máximo, uno de los vértices en el grafo es conocido como “fuente” (un nodo que no tiene arista entrante) y otro es designado “sumidero” (un nodo que no tiene aristas salientes) Cada una de las aristas tiene una capacidad, es decir, una cantidad finita de elementos que pueden pasar por ellas. El problema consiste en determinar la máxima capacidad de flujo que puede ingresar a través de la fuente y salir por el nodo de destino. El procedimiento para obtener el flujo máximo de una red consiste en seleccionar cualquier trayectoria de la fuente al destino y asignar el flujo máximo posible en esa trayectoria. Y hacer esto repetidas veces, ya que en cada una de ellas solo se considera un camino a través del grafo. Sin embargo, la mejora introducida por este equipo permite seleccionar, de una manera más inteligente, el orden en que estos caminos son explorados para reducir el tiempo en que se resuelve el problema. Su innovación consiste en representar el grafo como una matriz, en la que a cada nodo del grafo se le asigna una fila y una columna de la matriz. El número donde una fila y una columna coinciden representa la cantidad de cosas que pueden ser transferidas entre dos nodos. Una fila de una matriz también se puede interpretar como una ecuación matemática. Las herramientas del álgebra lineal permiten la solución simultánea de todas las ecuaciones creadas por todas las filas de una matriz. Si se modifican los números de la matriz en repetidas ocasiones, se modifican las ecuaciones y los investigadores pueden evaluar eficazmente todo el grafo a la vez. Este enfoque resulta ser más eficiente que probar caminos uno por uno.

En el mundo real estos grafos modelan redes de transporte y comunicación. Pero para este equipo, las posibilidades de aplicaciones prácticas del nuevo algoritmo van mucho más allá, desde el análisis de circuitos hasta el alineamiento de secuencias de ADN, pasando por el procesamiento digital de imágenes, entre otras.

Bibliografía: Perez, J., Gardey, A. (2017). Definición de algebra lineal. Recuperado de: https://definicion.de/algebra-lineal/ Computación (2016). Disponible en: https://www.significados.com/computacion/ Oktac, A., Trigueros, M. (2010). ¿Cómo se aprenden los conceptos de algebra lineal? Recuperado de: https://dialnet.unirioja.es/servlet/articulo?codigo=4065021 Algebra lineal (s.f). EcuRed. Disponible en https://www.ecured.cu/ %C3%81lgebra_lineal Madelayne, A. (2012). Relacionemos algebra lineal con la informática. Disponible en: https://tecinfo5.wordpress.com/2012/02/20/relacionemos-el-algebra-lineal-conla-tecnologia-en-informatica-4/ Garcia, J. (2002). Algebra lineal tras los buscadores de internet. Recuperado de: https://www.cs.buap.mx/~fjrobles/buscap.pdf D’Andrea, C. (2012). El álgebra lineal detrás de Google. Recuperado de: http://www.ub.edu/arcades/2012_07_29_google_corrientes.pdf Brin, S., Page, L. (s.f). The Anatomy of a Large-Scale Hypertextual Web Search Engine. Recuperado de: http://infolab.stanford.edu/~backrub/google.html Goodman, D. (2000). The Use of Mathematics in Computer Game. Recuperado de: https://nrich.maths.org/1374?/ Anibal. (2016). El álgebra lineal y el procesamiento digital de imágenes. Disponible en: https://www.nibcode.com/es/blog/12/algebra-lineal-y-el-procesamiento-digitalde-imagenes-parte-I Baños, M. (2014). Procesamiento de imágenes con matrices. Disponible en: https://prezi.com/mmciwfr-jpfh/procesamiento-de-imagenes-con-matrices/ Gutiérrez, C. (2017). De la teoría a la realidad: algebra lineal aplicada a la seguridad informática. Disponible en: https://www.welivesecurity.com/laes/2017/10/03/algebra-lineal-aplicada-seguridad-informatica/ Kevin. (2014). La criptografía y el álgebra lineal. Recuperado de: https://www.nibcode.com/es/blog/7/criptografia-y-algebra-lineal Higueras, E. (2010). Importante mejora de uno de los algoritmos básicos de la informática. Disponible en: https://www.tendencias21.net/Importante-mejora-deuno-de-los-algoritmos-basicos-de-la-informatica_a4893.html...