Grafos

Grafos

Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole. Un grafo simple está formado por dos conjuntos:

-Un conjunto V de puntos llamados vértices o nodos.

-Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados.
De una manera más informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos.En un grafo simple entre dos nodos sólo hay un arco. Si hay más de un arco hablamos de un multigrafo. Si los arcos se pueden recorrer en una en una dirección concreta pero no en la contraria lo llamamos grafo dirigido o dígrafo y los arcos son entonces aristas, si los arcos salen y llegan al mismo punto formando un bucle el grafo resultante se llama pseudografo.

Aristas

Una arista corresponde a una relación entre dos vértices de un grafo.

Para caracterizar un grafo G son suficientes únicamente el conjunto de todas sus aristas, comúnmente denotado con la letra E, junto con el conjunto de sus vértices, denotado por V. Así, dicho grafo se puede representar como G(V,E), o bien G = (V,E).

Un vértice es incidente a una arista si pertenece a ésta, o en otras palabras, si está conectado a otro vértice  a través de ella.

Ejemplo:

Grafo dirigido y no dirigido

Un grafo en el cual toda arista es dirigida se denominará «digrafo» o bien «grafo dirigido». Un grafo dirigido o dígrafo consiste de un conjunto de vértices V y un conjunto de arcos A.

Un grafo en el cual todas las aristas son no dirigidas se denominará «grafo no dirigido». El grafo no dirigido es aquel que no tiene sentido su arista. Un grafo no dirigido G representa elementos, y una arista (v, w) representa una incompatibilidad entre los elementos v y w.

Pseudo Grafo

Un pseudografo es un grafo que está facultado para tener aristas múltiples; es decir, aristas que relacionan los mismos nodos. De esta forma, dos nodos pueden estar conectados por más de una arista. Formalmente, un multigrafo G es un par ordenado G:=(V, E) donde:

-V es un conjunto de vértices o nodos

-E es un multiconjunto de pares no ordenados de nodos, llamados aristas o líneas.

Grafos Bipartitos

Un grafo bipartito se denomina al grafo cuyos vértices se pueden separar en dos subconjuntos disjuntos V1(G) y V2(G) y las líneas siempre unen vértices de un subconjunto con vértices de otro subconjunto.

Además se tiene que:

-V1(G) U V2(G) = V(G).

-La intersección de V1(G) y V2(G) es vacío.

-Para todos los puntos x1, x2 en V1(G) y para todos los puntos y1, y2 en V2(G) , no existe línea alguna x = (x1,x2) , ni x = (y1,y2).

Para mayor informacion sobre grafos consultat la siguiente pagina:

http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos

Arboles

Arbol

Un árbol es una estructura de datos dinámica no lineal  y homogénea en el que cada elemento puede tener varios elementos posteriores y solamente un elemento anterior. Es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos, de los cuales uno es conocido como raíz , además se crea una relación de parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc.

Un árbol es una estructura que está compuesta por un dato y varios árboles. Dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente, es decir un nodo cualquiera puede ser considerado como la raíz de una árbol completo.

En relación con otros nodos:

*Nodo Padre: Nodo que contiene un puntero al nodo actual. En un árbol un nodo solo puede tener un nodo padre.. X es padre de Y sí y solo sí el nodo X apunta a Y, tambien se dice que X es antecesor de Y.

*Nodo Hijo: Cualquiera de los nodos apuntados por uno de los nodos del aŕbol. Un nodo puede tener varios hijos.. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. Tambien se dice que X es descenciente directo de Y.

*Hermano: Dos nodos serán hermanos si son descencientes directos de un mismo nodo.

En cuanto a la posición dentro del árbol:

*Nodo Raíz: Es el único nodo del árbol que no tiene padre. Este es el nodo que usaremos para referirnos al árbol.

*Nodo Hoja: Nodo que no tiene hijos. Se llama hoja o terminal a aquellos nodos que no tienen ramificaciones ( hijos ).

*Nodo Interior: Es un nodo que no es raíz ni hoja.

*Orden: Es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc. Podríamos decir que nuestro árbol de ejemplo es de orden tres.

*Grado: El número de hijos que tiene el elemento con más hijos dentro del árbol.

*Nivel: Se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero, el de sus hijos uno y asi sucesivamente.

*Rama: Es el camino desde el nodo raíz a una hoja.

*Altura: La altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, tambien podemos  hablar de altura de ramas, el máximo número de nodos que hay que recorrer para llegar de la raíz a una de las hojas.

*Peso: Es el número de nodos del árbol sin contar la raíz.

*Camino: Es una consecuencia de nodos, en el que dos nodos consecutivos cualesquiera son padre e hijo.

*Longitud de camino: Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente.

Arboles Binarios

un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos .Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.

Tipos de arboles binarios:

*Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.

*Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.

*Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas  están a la misma profundidad.

*A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.

Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos . Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

Aqui les dejo un video informativo sobre los arboles:

 

Fuente:

http://blog.unab.cl/maxbecerrabustamante/arboles/

http://es.wikipedia.org/wiki/%C3%81rbol_binario

 

 

Tablas de dispersión y punteros

Puntero:

Es una variable que referencia una región de memoria; es una variable cuyo valor es una dirección de memoria. Si se tiene una variable ‘ p ‘ de tipo puntero que contiene una dirección de memoria en la que se encuentra almacenado un valor ‘ v ‘ se dice que ‘ p ‘ apunta a ‘ v ‘. El programador utilizará punteros para guardar datos en memoria en muchas ocasiones, de la forma que se describe a continuación.

Aqui les dejo un video para mas informacion sobre punteros:

 

Tablas de dispersión:

Las tablas de dispersión, o simplemente tablas hash, son estructuras de datos que se usan en aplicaciones que manejan una secuencia de elementos, de tal forma que cada elemento tiene asociado un valor clave, que es un número entero positivo perteneciente a un rango de valores,
relativamente pequeño. En estas organizaciones, cada uno de los elementos ha de tener una clave que identifica de manera única al elemento. Por ejemplo, el campo número de cuenta del conjunto de alumnos de la Universidad Iberoamericana puede considerarse un campo clave para organizar la información relativa al alumnado de la universidad ya que el número de cuenta es único. Hay una relación única (uno a uno) entre el campo y el registro alumno. Podemos suponer que no existen, simultáneamente, dos registros con el mismo número de cuenta.

Las tablas de dispersión son estructuras de datos que tienen como finalidad realizar la búsqueda o eliminación de un registro con una complejidad constante. La organización ideal de una tabla es aquella en la cual el campo clave de los elementos se corresponde directamente con el índice de la tabla.

Ejemplo:

 

Para mayor informacion cosultar las siguientes paginas:

http://www.ie.uia.mx/acad/atortole/progra2/hash.html

http://es.wikipedia.org/wiki/Tabla_hash

http://es.wikipedia.org/wiki/Puntero_(inform%C3%A1tica)

 

 

Listas enlazadas, pilas y colas

Colas:

Las colas no son más que listas lineales de información a las cuales se accede de un modo determinado siendo el de tipo (FIFO) lo que quiere decir que el primer dato en entrar es también el primer dato en salir, en las colas no se permite el acceso aleatorio a ningún elemento concreto, las inserciones para las colas se hacen al final de la lista.

Hay que tener en cuenta que las operaciones de recuperación es destructiva de la cola, si no es almacenado en otro lugar se destruye. Las colas se utilizan principalmente en las simulaciones, planificación de sucesos, y los procesos de entrada salida con buffer.

Las colas circulares:

No son mas que una variante de las anteriores y su diferencia es que mientras que en las colas lineales es necesario parar el programa cuando se alcanza el limite del array en las circulares, la cola está llena solo cuando el índice de almacenamiento y el índice de recuperación son iguales, en otro caso la cola aun tiene espacio para almacenar más datos. Su utilización más común es en los sistemas operativos en los que la cola circular mantiene la información que se lee de archivo y que se escribe en archivo, aplicaciones de tiempo real, etc.

Pilas:

Una pila es lo contrario de una cola, ya que su acceso es de tipo LIFO, el último que entra es el primero que sale, imaginar un montón de libros unos encima de otros y que para acceder al segundo por arriba primero es necesario coger el primero, su utilización principal es para el software de sistemas, compiladores, interpretes.

Las dos operaciones básicas, son las de almacenamiento y la de recuperación, que se llaman push y pop, para implementar una pila se necesitan las dos operaciones mencionadas con anterioridad y una zona de memoria para utilizarla como pila, se puede utilizar un array, o una zona asignada mediante asignación dinámica de memoria. Al igual que en las colas, la función de recuperación elimina el valor de la lista, y si este no se almacena en algún lugar, este se destruye.

La variable top es el índice de la siguiente posición libre de la pila. Cuando se implementan estas funciones, lo más importante es evitar el  esbordamiento de la pila por los dos extremos, si top=0 la pila esta vacía y si top >que la ultima posición de almacenamiento la pila está llena.

Listas enlazadas:

Al contrario que las pilas y las colas las listas enlazadas pueden acceder a una zona de memoria de forma aleatoria, ya que cada trozo de información lleva un enlace al siguiente elemento de la cadena. Una lista enlazada requiere una estructura de datos compleja, al contrario que las colas o las pilas, que pueden operar con elementos simples o complejos, además una operación de  ecuperación en una lista enlazada no elimina ni destruye el elemento de la lista. Para poder eliminar un elemento de una lista es necesario utilizar una operación especifica de eliminación.

Las listas enlazadas se utilizan principalmente para dos propósitos, crear arrays de un tamaño desconocido en memoria, y los archivos de almacenamiento en disco para bases de datos, las listas enlazadas permiten insertar y eliminar nuevos elementos.

Listas simplemente enlazadas:

Una lista  simplemente enlazada necesita que cada elemento contenga un enlace con el siguiente elemento, cada elemento consiste
en una estructura de campos de información  a punteros de enlace.

Existen dos formas de construir una lista simplemente enlazada , la primera es añadir un nuevo elemento al principio o al final de la lista, la otra añade los elementos en un punto especifico de la lista.

Si la lista ya esta ordenada, es conveniente mantenerla así, insertando los nuevos elementos en su lugar apropiado para lo cual se explora la lista de forma secuencial hasta encontrar el lugar apropiado, la nueva dirección se inserta en ese punto y los enlaces se vuelven a colocar como sea necesario.

Listas doblemente enlazadas:

Las listas doblemente enlazadas consisten en datos y enlaces tanto al elemento siguiente como al elemento anterior. Con lo que se consiguen dos grandes ventajas, primero la lista se puede leer en cualquier dirección, la segunda es que se pueden leer los enlaces hacia delante como hacia atrás, con lo que si un enlace resulta no valido se puede reconstruir utilizando el otro enlace.

Como en las listas simplemente enlazadas, las doblemente enlazadas pueden contener una función que almacene cada elemento en una posición especifica de la lista a medida que esta se construye, en lugar de colocar cada elemento al final de la lista.

Para mayor informacion consultar las siguientes paginas:

http://www.lcc.uma.es/~pscp/doc/colas.doc

http://es.wikipedia.org/wiki/Lista_(inform%C3%A1tica)

Ordenacion por insercion

El algoritmo de ordenación por el método de inserción directa es un algoritmo relativamente sencillo y se comporta razonablemente bien en gran cantidad de situaciones.

Completa la tripleta de los algoritmos de ordenación más básicos y de orden de complejidad cuadrático, junto con SelectionSort y BubbleSort.

Se basa en intentar construir una lista ordenada en el interior del array a ordenar.

De estos tres algoritmos es el que mejor resultado da a efectos prácticos. Realiza una cantidad de comparaciones bastante equilibrada con respecto a los intercambios, y tiene un par de características que lo hacen aventajar a los otros dos en la mayor parte de las situaciones.

Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterio claro de comparación, tal que dados dos elementos nos diga si están en orden o no.

Ejemplo:

 

Ordenacion por seleccion

Se basa en realizar varias pasadas, intentando encontrar en cada una de ellas el elemento que según el criterio de ordenación es mínimo y colocándolo posteriormente en su sitio.

No suele dar resultados buenos si se compara con otros métodos de ordenación. Realiza una enorme cantidad de comparaciones muy pocos intercambios. Eso hace que su utilización se restrinja en general a dos situaciones: o bien necesitamos un algoritmo sencillito para ordenar unos pocos datos y cogemos éste mismo que no está mal y es facil de recordar, o bien tenemos una situación en la cual escribir en el array es mucho más gravoso que leer.

Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterio claro de comparación, tal que dados dos elementos nos diga si están en orden o no.

Les dejo un video para mayor informacion:

Ordenamiento de burbuja

El algoritmo de ordenación por el método de la burbuja, también conocido como intercambio directo, es uno de los más simples que se conocen.

Se basa en una serie de intercambios entre elementos adyacentes. Esos intercambios dan la impresíón de que cada elemento va ascendiendo a través del array acercándose cada vez más a su posición final, recordando a cómo ascienden las burbujas de gas en un líquido.

A efectos prácticos, el algoritmo de la burbuja no es adecuado prácticamente para ninguna situación, ya que realiza muchas comparaciones y muchos intercambios. Los hay similares que se comportan bastante mejor. Su interés es más bien teórico, ya que sirve para establecer comparativas con otros métodos y extraer conclusiones teóricas.

Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterio claro de comparación, tal que dados dos elementos nos diga si están en orden o no.

Aqui les dejo un video para mayor informacion:

 

Ordenamiento de Shell

El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga «pasos más grandes» hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.

Ejemplo:

Aqui les dejo un video para mayor informacion:

Ordenamiento Rápido

Este algoritmo esta basado en la tecnica divide y vencerás, lo que hace este algoritmo es dividir recurvisamente el vector en partes iguales, indicando un elemento de inicio, fin y un pivote que nos permitira segmentar nuestra lista. Una vez dividida, lo que hace, es dejar todos los mayores que el pivote a su derecha y todos los menores a su izquierda. Al finalizar el algoritmo, nuestros elementos estan ordenados, asi crearemos arreglos mas pequeños para ordenar estos.

Ejemplo:

Aqui les dejo un video para mayor informacion:

Algoritmos de ordenamiento

Los algoritmos de ordenamiento nos permite, como su nombre lo dice, ordenar.Estos nos serviran para ordenar vectores o matrices con valores asignados aleatoriamente.

El ordenamiento se efectúa con base en el  valor de  algún campo en un registro y su propósito principal es el  de facilitar las búsquedas de los miembros del conjunto  ordenado.

El ordenar un grupo de  datos  significa mover los datos o sus  referencias para que queden en una secuencia tal que represente  un orden, el cual puede ser numérico, alfabético o  incluso alfanumérico, ascendente o descendente.

Algunos tipos de ordenamientos son:

Ordenamiento de burbuja

Ordenamiento por monticulo

Ordenamiento por inserción

Ordenamiento por mezcla

Ordenamiento rapido

Ordenamiento por seleccion

Ordenamiento de shell