MATRICES DISPERSA

Matrices Dispersas

En álgebra lineal numérica una matriz dispersa o matriz rala o matriz hueca es una matriz de gran tamaño en la que la mayor parte de sus elementos son cero.1
Con matrices de gran tamaño los métodos tradicionales para almacenar la matriz en la memoria de una computadora o para la resolución de sistemas de ecuaciones lineales necesitan una gran cantidad de memoria y de tiempo de proceso. Se han diseñado algoritmos específicos para estos fines cuando las matrices son dispersas.

Matrices dispersas

forma de representación

 Formato CRS

 Un vector de punto flotante de tamaño k en el que se almacenan los valores de los coeficientes.

 Otro vector de tamaño k en el que se almacenan los números de columna de los elementos distintos de cero.

 Un vector de tamaño n+1 siendo n la cantidad de filas de la matriz, en el cual se almacena la posición de la primera ocurrencia de cada fila Las matrices dispersas son ampliamente usadas en la computación científica, especialmente en la optimización a gran escala, análisis estructural y de circuitos, dinámica de fluidos computacionales y en general en solución numérica de ecuaciones diferenciales parciales; otras áreas de interés en donde se pueden aplicar la representación dispersa son la teoría de grafos, teoría de redes, la combinatoria, los métodos numéricos, entre otros. 

Ejemplo : Este video no tiene lucro para esta pagina

Para mayor información sigueme en:

CIBERGRAFIA

- haz click aqui para ver de donde se saco la informacion

Algoritmo Enearios

Árboles Enearios

Al igual que en los TDAs estudiados con anterioridad, la forma de implementar un árbol n-ario dependerá del problema a resolver y de la capacidad del diseñador.

No obstante, existen 3 Implementaciones básicas:

- Implementación matricial. El árbol se representa en un vector de enteros, donde cada componente contiene el índice de su nodo padre.
- Implementación con listas. Se representa mediante un vector de listas. Cada índice de las componentes del vector se asocia con un nodo del árbol, y cada componente es una lista con los Hijos del nodo.
- Implementación con celdas enlazadas. Cada nodo del árbol es una celda enlazada con un puntero a su padre, a su hijo izquierda y a su hermano derecha.
- El tipo Nodo del árbol es entero.
- La relación padre-hijo se representa en un vector P, donde P[i] indica cuál es el nodo padre de i. Si el nodo no tiene padre (es la raíz), P[i] tomará valor -1.
- Las etiquetas de los nodos se representan en otro vector de etiquetas.

Esta implementación es relativamente sencilla y con bajo coste de memoria. Facilita las operaciones de acceso a los ancestros de un nodo (eficiencia O(log(n)) para viajar desde un nodo hoja hasta la raíz), pero resulta difícil gestionar operaciones con los hijos (conocer la altura, determinar los hijos, establecer hijo izquierda y hermano derecha...)
árbol eneario

árbol enario en piramide

Un Arbol se denomina Piramide si el valor del nodo padre es igual a la suma de los valores de los nodos hijos. Excepto para las hojas

Ejemplo: Este video no tiene lucro para esta pagina

Para mayor información sigueme en:

CIBERGRAFIA

- haz click aqui para ver de donde se saco la informacion

Algoritmo kruskal

Algoritmo kruskal

árbol de coste total mínimo/máximo

Joseph B. KruskalJoseph B. Kruskal investigador del Math Center (Bell-Labs), que en 1956 descubrió su algoritmo para la resolución del problema del Árbol de coste total mínimo (minimum spanning tree - MST) también llamado árbol recubridor euclídeo mínimo. Este problema es un problema típico de optimización combinatoria, que fue considerado originalmente por Otakar Boruvka (1926) mientras estudiaba la necesidad de electrificación rural en el sur de Moravia en Checoslovaquia.

El objetivo del algoritmo de Kruskal es construir un árbol (subgrafo sin ciclos) formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.

Un árbol (spanning tree) de un grafo es un subgrafo que contiene todos sus vértices o nodos. Un grafo puede tener múltiples árboles. Por ejemplo, un grafo completo de cuatro nodos (todos relacionados con todos) tendría 16 árboles.

La aplicación típica de este problema es el diseño de redes telefónicas. Una empresa con diferentes oficinas, trata de trazar líneas de teléfono para conectarlas unas con otras. La compañía telefónica le ofrece esta interconexión, pero ofrece tarifas diferentes o costes por conectar cada par de oficinas. Cómo conectar entonces las oficinas al mínimo coste total.

La formulación del MST también ha sido aplicada para hallar soluciones en diversas áreas (diseño de redes de transporte, diseño de redes de telecomunicaciones - TV por cable, sistemas distribuidos, interpretación de datos climatológicos, visión artificial - análisis de imágenes - extracción de rasgos de parentesco, análisis de clusters y búsqueda de superestructuras de quasar, plegamiento de proteínas, reconocimiento de células cancerosas, y otros)

Árbol de Expansión

Dado un grafo conexo, no dirigido G. Un árbol de expansión es un árbol compuesto por todos los vértices y algunas (posiblemente todas) de las 

Ejemplo: Este video no tiene lucro para esta pagina

Para mayor información sigueme en:

CIBERGRAFIA

- haz click aqui para ver de donde se saco la informacion

Grafos Particulares

Grafos Particulares

COMPLETO Un grafo no dirigido G= es COMPLETO si existe arista entre todo par de vértices de V. Sea n=|V|, el número de aristas de un grafo completo no dirigido es exactamente |E|=n. (n-1)/2. Si se trata de un grafo dirigido entonces |E|=n. (n-1). 

GRAFOS EULERIANOS Se dice que un grafo no dirigido G= es EULERIANO si existe un camino cerrado, propio, simple (no se repiten aristas) pero no necesariamente elemental que incluye todas las aristas de G. Los siguientes lemas permiten determinar si un grafo dado es euleriano: Lema 1: Un grafo no dirigido y conexo es euleriano si y sólo si el grado de todo vértice es par. Lema 2: Un grafo dirigido y fuertemente conexo es euleriano si y sólo si el grado de todo vértice es cero. Averiguar si un grafo no dirigido y conexo es euleriano tiene un coste de θ(n), si se supone conocido el grado de cada vértice; gracias al lema 1 basta con recorrer el conjunto de vértices y comprobar si el grado de cada uno de ellos es par o no lo es. 

GRAFOS HAMILTONIANOS Un grafo no dirigido G= es HAMILTONIANO si existe un camino cerrado y elemental (no se repiten vértices) que contiene todos los vértices de G. Si existe, el camino se llama circuito hamiltoniano. Anàlisi i Disseny d’Algorismes – ADA Grafos FIB – UPC, curs 2007/2008 María Teresa Abad 6 Departament Llenguatges i Sistemes Informàtics En este caso no existe ninguna propiedad que permita determinar la existencia del camino por lo que averiguar si existe tiene el mismo coste que calcular directamente el camino (es un problema NP-C). La forma habitual de resolverlo es aplicar el esquema de Vuelta Atrás que va construyendo todos los caminos posibles y, para cada uno de ellos, comprueba si cumple la condición de hamiltoniano.

Ejemplo: Este vídeo no tiene lucro para esta pagina

Para mayor información sigueme en:

CIBERGRAFIA

- haz click aqui para ver de donde se saco la informacion

Algoritmo Prim

Algoritmo Prim

El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.

En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.

El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP

Algunos trabajos han comparado la eficiencia entre los algoritmos de Kruskal y de Prim:

Sea a es el número de arcos y n el número de nodos. El algoritmo de Kruskal requiere un tiempo que está en O(a log n). Para un grafo denso, a tiende a n(n-1)/2, por lo que el algoritmo requiere un tiempo que está en O(n^2 log n), y el algoritmo de Prim puede ser mejor O(n^2). En un grafo disperso, a tiende a n-1, por lo que el algoritmo de Kruskal requiere un tiempo que está en O(n log n) y el algoritmo de Prim es menos eficiente. Sin embargo, si el algoritmo de Prim se implementa con montículos, el tiempo requerido por este algoritmo está, como el de Kruskal, en O(a log n).

Si a es aproximadamente igual a n (grafo con pocos arcos) conviene usar Kruskal

Si a es aproximadamente igual a n^2 (grafo denso) conviene usar Prim

En cualquier caso, la complejidad del algoritmo de Kruskal depende de la técnica de ordenación empleada. El algoritmo de Prim requiere más memoria que el algoritmo de Kruskal. Ambos algoritmos son relativamente fáciles de paralelizar. Puede encontrar más información en:

Ejemplo : Este video no tiene fines de licro para esta pagina

Para mayor información sigueme en:

CIBERGRAFIA

- haz click aqui para ver de donde se saco la informacion

Algoritmo De Floyd-Warshall

Algoritmo De Floyd-Warshall

El algoritmo de Floyd-Warshall compara todos los posibles caminos a través del grafo entre cada par de vértices. El algoritmo es capaz de hacer esto con sólo V^3 comparaciones (esto es notable considerando que puede haber hasta V^2 aristas en el grafo, y que cada combinación de aristas se prueba). Lo hace mejorando paulatinamente una estimación del camino más corto entre dos vértices, hasta que se sabe que la estimación es óptima.

Algoritmo:

Dado un grafo G(V,A) se puede aplicar el algoritmo de Floyd para resolver el problema de encontrar el camino más corto de todos los vértices entre sí.

Inicio
Armar la matriz de adyacencia F, teniendo en cuenta que F(i,j)=0 si i = j (diagonal principal es 0). Además dónde no exista camino se debe indicar con infinito.
Para k desde 1 hasta n
    Para i desde 1 hasta n
        Para j desde 1 hasta n
          F[i,j]=min(F[i,j], F[i,k] + F[k,j])
       Fin para j
   Fin para i
Fin para k

En la k-esima vuelta F[i, j] contendrá el valor del camino más corto que una al vértice i con el j tal que dicho camino no pase por un vértice con número mayor que k.
La matriz resultante es la de los mínimos caminos entre cada nodo. Si se quiere saber cual es dicho camino, se debe armar un árbol a medida tomando como numero de nodo a k cada vez que se detecta que hubo una optimización.
Debido a su triple ciclo anidado es obviamente O(N^3).

imagen :

Ejemplo : En esta pagina no tiene lucros con este vídeo

Para mayor información sigueme en:

CIBERGRAFIA

- haz click aqui para ver de donde se saco la informacion

ÁRBOL B+

ÁRBOL B+

• Los árboles-B+ se han convertido en la técnica mas utilizada para la organización de archivos indizados. La principal característica de estos arboles es que todas las claves se encuentran en las hojas y por lo tanto cualquier camino desde la raíz hasta alguna de las claves tienen la misma longitud. 
• Todas las claves se encuentran en las hojas.
• Cualquier cambio desde la raiz hasta la clave tiene la misma longitud.
• Ocupa mas espacio que un árbol B porque hay duplicidad en llaves.
• Cada pagina excepto la raiz continua entre N y 2N elementos.
• Las claves de las paguinas de raiz en interiores se utilizan como indices

- Ejemplo: 

Ejemplo de un árbol B+

  Para mayor información sigueme en:

CIBERGRAFIA

- haz click aqui para ver de donde se saco la informacion

ÁRBOL B

ÁRBOL B

1. Definición: Los B-árboles sugieron en 1972 creados por R.Bayer y E.McCreight.El problema original comienza con la necesidad de mantener índices en almacenamiento externo para acceso a bases de datos,es decir,con el grave problema de la lentitud de estos dispositivos se pretende aprovechar la gran capacidad de almacenamiento para mantener una cantidad de información muy alta organizada de forma que el acceso a una clave sea lo más rápido posible.
2. Se utilizan para manejar archivos que contienen gran cantidad de informacion .
3. Se utiliza como metodo de busqueda externa
4. Cada nodo o (pagina) es un arbol b de orden N contiene 2 N claves como maximo y n claves como minimo
5. fueron propuestos por banyer mccreght en 1970 
6. Cada (pagina) tiene 2 N  hijos como maximo y N+1 hijos como minimos exepto la pagina de raiz que puede tener como minimo una clave y por consiguiente dos hijos
7. La pagina se almacena en dispositivos secundarios la pagina de raiza en Miria principal 
8. Las paginas hojas estan todas al mismo nivel  

Ejemplo de insertado de un árbol B:

Ejemlo de un arbol B inserción :



Ejemplo de un árbol B retiro:

Para mayor información sigueme en:

CIBERGRAFIA

- haz click aqui para ver de donde se saco la informacion