Grafos

Grafo

es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).

Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).

Definiciones

Un grafo G es un par ordenado G = (V,E), donde:V es un conjunto de vértices o nodos, y
E es un conjunto de arcos o aristas, que relacionan estos nodos.

Normalmente V suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos. Se llama orden de G a su número de vértices, V .

Lazos o bucles
Un lazo o bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.

Grafo no dirigido

Un grafo no dirigido o grafo propiamente dicho es un grafo G = (V,E) donde:

es un conjunto de pares no ordenados de elementos de .
Un par no ordenado es un conjunto de la forma {a,b}, de manera que {a,b} = {b,a}. Para los grafos, estos conjuntos pertenecen al conjunto potencia de V de cardinalidad 2, el cual se denota por .

Grafo dirigido

Un grafo dirigido o digrafo es un grafo G = (V,E) donde:

es un conjunto de pares ordenados de elementos de .
Dada una arista (a,b), a es su nodo inicial y b su nodo final.
Por definición, los grafos dirigidos no contienen bucles.

Pseudografo

Un pseudografo es un grafo G = (V,E) donde:

es un conjunto de pares no ordenados de elementos de .
Es decir, un pseudografo es un grafo no dirigido que acepta bucles en .

Pseudografo dirigido

Un pseudografo dirigido es un grafo G = (V,E) donde:

es un conjunto de pares ordenados y etiquetados de elementos de
Es decir, un pseudografo dirigido es un grafo dirigido que acepta bucles en .

Propiedades

Adyacencia: dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.
Incidencia: una arista es incidente a un vértice si ésta lo une a otro.
Ponderación: corresponde a una función que a cada arista le asocia un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo. Esto se usa mucho para problemas de optimización, como el del vendedor viajero o del camino más corto.
Etiquetado: distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto.

Ejemplos

La imagen es una representación del siguiente grafo:
V:={1,2,3,4,5,6}
E:={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}

El hecho que el vértice 1 sea adyacente con el vértice 2 puede ser denotado como 1 ~ 2.
En la Teoría de las categorías una categoría puede ser considerada como un multigrafo dirigido, con los objetos como vértices y los morfismos como aristas dirigidas.
En ciencias de la computación los grafos dirigidos son usados para representar máquinas de estado finito y algunas otras estructuras discretas.
Una relación binaria R en un conjunto X es un grafo dirigido simple. Dos vértices a, b en X están conectados por una arista dirigida ab si aRb.

Ordenamiento Binario

La búsqueda binaria consiste en emplear "divide y vencerás" para, dividiendo el problema por la mitad, dirigirse a la izquierda o derecha dependiendo de la comparación de la palabra a encontrar con el elemento del medio, y así sucesivamente, hasta encontrar la palabra a buscar. Tened en cuenta que la implementación más sencilla del algoritmo supone invocar recursivamente al método buscar (search).

Se pide: Codificar el método search que realiza la búsqeda binaria. Se puede descargar un esqueleto de esta clase aquí BinarySearch.java.

public void int compareTo(String a)
Dados dos String:
String cadena1
String cadena2

El método compareTo funciona de la siguiente forma: cadena1.compareTo(cadena2)

devuelve un número negativo si cadena1 < cadena2
devuelve un número positivo si cadena1 > cadena2
devuelve 0 si cadena1 = cadena2

ordenamiento con árbol binario es un algoritmo de ordenamiento, el cual ordena sus elementos haciendo uso de un árbol binario de búsqueda. Se basa en ir construyendo poco a poco el árbol binario introduciendo cada uno de los elementos, los cuales quedarán ya ordenados. Después, se obtiene la lista de los elementos ordenados recorriendo el árbol en inorden.

Complejidad:
Insertar elementos en un árbol binario de búsqueda tiene una complejidad O(log n). Entonces, agregar n elementos a un árbol cualquiera da como resultado una complejidad O(n log n). Además, recorrer los elementos del árbol en inorden tiene complejidad O(n).

Características:
Tiene un buen rendimiento.
Es estable (no cambia el orden relativo de elementos iguales).
No requiere espacio de almacenamiento extra.
Puede ordenar listas tal cual las recibe.

Estructuras de datos "Matrices"

Matrices

•Dos estructuras de datos fundamentales son las conocidas
como: matriz (o array) y registro (o estructura).

• Son de uso frecuente, por lo que son elementos
imprescindibles en la programación de muchos problemas.
• Por ejemplo, las notas correspondientes a las distintas
evaluaciones realizadas a cada uno de los alumnos de un
determinado curso forman una matriz, y la ficha que contiene
los datos personales de cada uno de estos alumnos es un
ejemplo de registro (o estructura).





Matrices

Una matriz (array en inglés) es un conjunto de elementos
contiguos, todos del mismo tipo, que comparten un nombre
común y a los que es posible acceder mediante la posición
(índice) que ocupa cada uno de ellos en la matriz, como un
vector o una matriz en Álgebra.
Esta disposición permitirá escribir código más simple, ya que
será posible establecer bucles en los que se recorra los
elementos de una matriz mediante el número de índice.
A las matrices de una dimensión se les suele llamar también
vectores o listas, y a las matrices de dos dimensiones, tablas.




Declaración de matrices


La declaración de una matriz especifica el nombre de la
matriz, el número de elementos de la misma y el tipo de éstos:
donde:
• variable es el nombre de la matriz.
• dimension es una lista de expresiones numéricas, separadas por comas y que definen las dimensiones de la matriz. Esta lista puede ser de la forma:
[inferior To] superior [, ...
• tipo define el tipo de la variable (Integer, Long, String, etc.)

Ejemplos de declaración de matrices


Lista o vector de 60 enteros, indexados del 0 al 59:

Dim temp(59) As Integer

Lista o vector de 60 enteros, indexados del 1 al 60:

Dim temp(1 To 60) As Integer

Lista o vector de 60 cadenas de caracteres de longitud fija 40:

Dim temp(1 To 60) As String * 40

Tabla de 10 * 10 elementos de tipo Double:

Dim a(9,9) As Double
Dim a(1 To 10, 1 To 10) As Double
Dim a(-5 To 4, 2001 To 2010) As Double

Ejemplo de manipulación de matrices


Const n = 12
Dim A(1 to n) As Double ´matriz de n elementos
Dim i As Integer
´Bucle For para Rellenar la matriz “a” con datos.
For i = 1 To n
A(i) = InputBox(“Introduce el elemento” & i & “ de A”)
Next i
´Bucle For para Visualizar la matriz con Print
For i = 1 To n
MsgBox A(i)
Next i

Matrices dinámicas

Una matriz dinámica, a diferencia de las anteriores, puede ser
redimensionada en cualquier momento de la ejecución del programa.

Para crear una matriz dinámica, primero hay que declararla como si
fuera una matriz estática (con Dim), pero sin darle dimensión.

Para reasignar dinámicamente el número de elementos se utiliza la
sentencia ReDim. No es posible cambiar el número de dimensiones
de la misma, sólo los tamaños de cada dimensión.

Cada vez que se ejecuta ReDim, todos los valores previamente
almacenados se pierden.

Para cambiar el tamaño conservando los valores hay que utilizar la
palabra clave Preserve, en cuyo caso no es posible cambiar el/los
índice/s inferior/es, sólo el superior.

Funciones de Dispersión

Funciones de Dispersión

Consiste en la elección de una clave, para el buen funcionamiento de la estructura, debe cumplir las siguientes características:

• Ser una función sencilla y por tanto rápida.
• Distribuir uniformemente los elementos en el espacio de almacenamiento
• Evitar en lo posible la aparición de sinónimos
• Para dos claves muy similares, generar posiciones distantes.

En primer lugar, obtenemos un numero a partir de la clave alfanumérica utilizada y luego hacemos la operación modulo N sobre ese numero. Así obtendremos una posición donde almacenar nuestro elemento. Hay que cuenta que N (el tamaño de la tabla) ha de ser un número primo.
El código seria: prívate static int Hash1(String Clave)

{

int valor = Clave.charAt(0);

int tam = Clave.length();

for (int i = 1; i <>

valor += Character.getNumericValue( Clave.charAt(i)); }

return (valor % N);

}

Método de la División

Es la función de dispersión clásica para claves enteras.
Consiste en tomar el resto de la división de la clave por el número de entradas de la tabla (B).
Código: x = x % B;
Como ventajas citar que es una función fácil de calcular y que se puede utilizar para tablas de cualquier tamaño, aunque se recomienda elegir B con cuidado.
Como inconvenientes podemos citar que el rango de valores es limitado.

Suma de ASCII

Es la función de dispersión clásica para claves de tipo cadena. Consiste en sumar los valores ASCII de la clave.
Ejemplo: “HOLA” => (‘H’+’O’+’L’+’A’) % B

Funciones de Dispercion

Consiste en la elección de una clave, para el buen funcionamiento de la estructura, debe cumplir las siguientes características:
• Ser una función sencilla y por tanto rápida.
• Distribuir uniformemente los elementos en el espacio de almacenamiento
• Evitar en lo posible la aparición de sinónimos Para dos claves muy similares, generar posiciones distantes

En primer lugar, obtenemos un numero a partir de la clave alfanumérica utilizada y luego hacemos la operación modulo N sobre ese numero. Así obtendremos una posición donde almacenar nuestro elemento. Hay que cuenta que N (el tamaño de la tabla) ha de ser un número primo.

El código seria:

prívate static int Hash1(String Clave) {
int valor = Clave.charAt(0);
int tam = Clave.length();
for (int i = 1; i <>
valor += Character.getNumericValue( Clave.charAt(i));
}
return (valor % N);
}


Método de la División :


-Es la función de dispersión clásica para claves enteras.
-Consiste en tomar el resto de la división de la clave por el número de entradas de la tabla (B).
-Código: x = x % B;
-Como ventajas citar que es una función fácil de calcular y que se puede utilizar para tablas de cualquier tamaño, aunque se recomienda elegir B con cuidado.
-Como inconvenientes podemos citar que el rango de valores es limitado.

Suma de ASCII:


Es la función de dispersión clásica para claves de tipo cadena. Consiste en sumar los valores ASCII de la clave.

Ejemplo: “HOLA” => (‘H’+’O’+’L’+’A’) % B
Codigo:
for (int i=0; i x = (x + clave.charAt(i)) % B;
}

Como ventajas citar que es una función fácil de implementar y que se ejecuta con rapidez.
Como inconvenientes podemos citar que no distribuye bien las claves si el tamaño de la tabla es grande, ya que las claves se van a situar en la
parte superior de la tabla.

Quicksort

Quicksort el ordenamiento rápido

El método de ordenamiento Quick Sort es actualmente el más eficiente y veloz de los métodos de ordenación interna.


Este método es una mejora sustancial del método de intercambio directo y recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor C.A. Hoare lo bautizó así.
es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos). Fue desarrollada por C. Antony R. Hoare en 1960.

Descripción del algoritmo

Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.

La idea central de este algoritmo consiste en los siguiente:Se toma un elemento x de una posición cualquiera del arreglo.Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x.Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta de x en el arreglo.

Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.

Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido

Analisis del algoritmo:

Estabilidad: No es estable.
Requerimientos de Memoria: No requiere memoria adicional en su forma recursiva. En su forma iterativa la necesita para la pila.

Ventajas:

Muy rápido.
No requiere memoria adicional.

Desventajas:

Implementación un poco más complicada.
Recursividad (utiliza muchos recursos).
Mucha diferencia entre el peor y el mejor caso.

Ejemplo:

}El elemento divisor será el 6:
}5 - 3 - 7 - 6 - 2 - 1 - 4
} p
}Comparamos con el 5 por la izquierda y el 4 por la derecha con el pivote.
}5 - 3 - 7 - 6 - 2 - 1 - 4
}i p j
}5 es menor que 6 y 4 NO es mayor que 6. Avanzamos la i, y la j queda donde está.
}
}5 - 3 - 7 - 6 - 2 - 1 - 4
} i p j
}3 es menor que 6 y 4 NO es mayor que 6. Avanzamos la i, y la j queda donde está.
}
}5 - 3 - 7 - 6 - 2 - 1 - 4
} i p j
}7 NO es menor que 6 y 4 NO es mayor que 6.
}
}5 - 3 - 7 - 6 - 2 - 1 - 4
} i p j

Ordenamiento Shell

Es un algoritmo de ordenamiento. El método se denomina Shell en honor de su inventor Donald Shell. Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso. Un cambio menor presentado en el libro de V. Pratt produce una implementación con un rendimiento de O(nlog2 n) en el peor caso. Esto es mejor que las O(n2) comparaciones requeridas por algoritmos simples pero peor que el óptimo O(n log n). Aunque es fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy difícil analizar su tiempo de ejecución.

El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:

El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.

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.


Implementacion:

public static void shellSort(int[] a) {
for ( int increment = a.length / 2;
increment > 0;
increment = (increment == 2 ? 1 : (int) Math.round(increment / 2.2))) {
for (int i = increment; i <>
for (int j = i; j >= increment && a[j - increment] > a[j]; j -= increment) {
int temp = a[j];
a[j] = a[j - increment];
a[j - increment] = temp;
}
}
}
}