Biblioteca Matrix

Hace dos años, cuando cursaba Estructuras de Datos, desarrollé una biblioteca de clases, que permitía declarar matrices en C++ y calcular operaciones típicas, como el determinante o la inversa. Apliqué los conocimientos de  2º de Bachillerato para construir las operaciones, pero era imposible trabajar con matrices grandes.

El año pasado estudié nuevas formas de calcular las mismas operaciones, pero logrando una eficiencia mucho mayor gracias al método de Gauss, que agiliza los cálculos del determinante, la inversa y la solución de un sistema lineal. Y estos algoritmos los he implementado como mejora de la matriz que diseñé en un principio, dando lugar a la que he llamado Biblioteca Matrix 2. La podéis descargar en el siguiente enlace:


Está escrita en C++ y es compatible con g++ (Linux/Windows) y Visual Studio. Comprende el código fuente, el Makefile para g++/MinGW, el proyecto VisualStudio, la biblioteca compilada para Windows con MinGW y la documentación HTML de Doxygen. Espero que os sea de utilidad, y si alguien encuentra algún bug, le ruego que me lo haga saber.

Comentarios

Publicar un comentario

Entradas populares de este blog

Algoritmo de relleno

Imagen
Esta historia parte de un pequeño proyecto de antaño en el que intenté implementar la herramienta de relleno de Paint o Photoshop. Estamos hablando de un algoritmo de relleno por difusión : el objetivo es pasar por todos los puntos no coloreados partiendo de uno arbitrario y la solución se antojaba sencilla: un algoritmo de  backtracking .  Estuve cerca de lograrlo pero cuando la superficie a rellenar era medianamente grande, el programa se colgaba por desbordamiento de pila . El problema es que, al tratarse de una función recursiva , con cada paso que daba había que guardar en la pila el punto anterior, y si el espacio es grande podemos estar hablando de miles o millones de pasos. Esta información se guarda en la pila de llamadas , una zona de memoria especialmente rápida... y pequeña. La solución es muy fácil: convertir la función recursiva en iterativa , y guardar cada punto a explorar dentro de un contenedor de pila ( QStack en la biblioteca Qt), cuyos datos se a
Leer más

Problema de las N reinas

Imagen
El problema de las ocho reinas es un juego que consiste en colocar ocho reinas en un ajedrez sin que se amenacen entre sí. La solución a este problema se encuentra con un algoritmo de backtracking , que consiste en asignar una fila a cada reina, y progresivamente colocar cada reina en una posición diferente. Si una reina es amenazada en cualquier casilla de su fila, la retiramos y colocamos la reina anterior en otra posición. El programa termina cuando se ha conseguido colocar a todas las reinas en posiciones seguras. Aquí dejo una propuesta dinámica para N reinas, en lenguaje C: >>  Descargar reinas.c  << Mejorando el algoritmo Tiempo después de publicar originalmente este post, estudié que éste es realmente un problema de satisfacción de restricciones . Resolver un problema NP completo puede costarnos mucho tiempo, ya que el espacio de búsqueda crece enormemente respecto al tamaño del problema. La aproximación por backtracking  "a pelo&quo
Leer más

Cifrado de Vernam

Imagen
El cifrado de Vernam es un algoritmo de encriptación en flujo , es decir, consiste en combinar cada uno de los bits del mensaje con otro bit que actúa como clave de cifrado. Numerosos protocolos criptográficos, como el sistema WEP que utilizan nuestros routers o el A5/1 que se usa en las redes de teléfonos móviles, están basados en el cifrado de Vernam. Este procedimiento requiere, a diferencia de los sistemas de encriptación por bloques, una clave que sea tan larga como el mensaje . Entonces necesitamos alguna forma de obtener una clave pseudoaleatoria que pueda tener una longitud muy larga, y variable. Una forma de conseguir una clave fiable con facilidad, es utilizar un LFSR (Linear Feedback Shift Register), o Registro de Desplazamiento con Retroalimentación lineal. No nos asustemos por ese nombre, es lo más fácil del mundo: Fuente: Wikipedia . Un registro de desplazamiento es un conjunto de bits que tienen la capacidad de moverse a través de las celdas en las que
Leer más