Coloración de Grafos

Un grafo es un conjunto de objetos llamados vértices y una selección de pares de vértices unidos gráficamente por líneas llamadas aristas. Típicamente, un grafo se representa mediante una serie de puntos o circulos (los vértices) conectados por líneas (las aristas).

El problema de coloración de grafos se ha estudiado durante varias décadas, lamentablemente, el problema de coloración de grafos arbitrario con el menor número conocido de colores es un problema que se clasifica entre los llamados “NP-COMPLETOS” para los cuales, las únicas soluciones conocidas consisten en probar todas las posibilidades. Realizado esto a través de métodos y algoritmos informáticos representaría un tiempo de ejecución de T(n₂).

El problema básicamente consiste en colorear los vértices de los grafos con el menor número de colores posibles. La única regla es que no pueden quedar coloreados 2 vértices unidos por una arista con el mismo color. De este modo, para resolver este problema del modo “ávido” o en otras palabras empírico, se procede a colorear el primer vértice, luego se examinan la lista de los no coloreados y se verifica si no hay una arista que lo una con un vértice que ya tenga asignado el nuevo color, si tal arista no existe, se le asigna el nuevo color al vértice.

Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas por ejemplo, Dibujo computacional y en todas las áreas de Ingeniería. Como caso práctico podemos incluir el descrito en el libro “ESTRUCTURA DE DATOS Y ALGORITMOS” de Alfred V. AHO, acerca de un modelo matemático que simplificaría el diseño de un semáforo para una intersección complicada de 5 calles. El programa o algoritmo debe estar diseñado para recibir como entradas cada uno de los giros de autos posibles.

Visto de este modo existen 13 giros de autos permisibles que son los siguientes:
ED, EC, EB, EA, DC, DB, DA, BA, BD, BC, AD, AC, AB.

Diseñaremos un grafo cuyos vértices representen los giros posibles y uniremos por las aristas cada giro no permitido evitando una colisión vehicular. Luego procedemos a la coloración del grafo del modo descrito anteriormente. Un procedimiento realizado ávidamente nos podría conducir a un resultado similar a este:

De este modo determinamos que cada color representa una serie de posibles giros de vehículos que podrían circular libremente sin el temor de impactar con otros posibles giros. Esta es un ejemplo práctico de una aplicación cotidiana en campos de ingeniería; Sin embargo esta estructura puede ser implementada en muchos más campos profesionales y matemáticos.

Referencias:

• http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos#Aplicaciones
• Libro "Estructura de Datos" de Alfred V. Aho, John E. Hopcroft, Jefrey D. Ullman
  

Apuntadores

Los apuntadores son una herramienta muy poderosa de programación que consiste es apuntar hacia la dirección de memoria en la cual esta almacenada una variable específica. Las direcciones en memoria se describen como valores hexadecimales.

Generalmente cuando se trabaja con apuntadores se utiliza una técnica llamada “referenciación”; Esta consiste determinar la dirección de memoria de una variable. Para dar un ejemplo de esto, C++ y C utilizan el operador ”&” aplicado a la variable de la que se desea obtener la dirección. Su sintaxis sería similar a esta:

Int x = 50;
Cout << ”La dirección de x es: ” << &x

Este código imprime un valor del estilo “0x4fffd34”. Este valor puede variar durante cada ejecución del programa, debido a que el programa puede reservar distintos espacios de memoria durante cada ejecución.

Al igual que una variable normal, un apuntador direcciona hacia direcciones de memoria con un determinado tipo de datos. Por lo cual, si el apuntador esta declarado como tipo Entero y este direccionase a una dirección de memoria que almacena un tipo Float, esto nos llevaría a un error similar al de asignar un tipo de datos diferente a una variable definida con otro tipo.

Referencia:

http://gilberto2112.brinkster.net/programaconkarel/administrador/Mis_Archivos_GRB/apuntadores.pdf

Algoritmos Recursivos

Los algoritmos recursivos son algoritmos que se encuentran encapsulados dentro de una función y generalmente necesitan ser llamados a si mismos dentro de la misma función para la resolución de un problema especifico. En otras palabras una función recursiva es aquella que contiene invocaciones a si misma.

Los algoritmos recursivos cuentan como mínimo con 2 partes básicas:

1. Caso Base: Es un caso donde se encuentra una solución al problema sin necesidad de recurrir nuevamente al llamado de la función (recursión).


2. Parte Recursiva: Brinda una solución al problema cada vez más cercana a la esperada; Sin embargo, necesita un nuevo llamado a la función para determinar otra posible solución.

La recursividad es una herramienta poderosa y a la vez peligrosa. Sin duda alguna la única ventaja que ofrece comparada a la iteración, es el ahorro de código, ya que es más sencillo volver a llamar una función ya creada que programar detalladamente el ciclo de repetición que le dará solución a un problema específico; Sin embargo solo se recomienda utilizar este tipo de algoritmo cuando utiliza pocos parámetros, variables e invocaciones.

Es importante mencionar que el diseño de un algoritmo de iteración llevará más trabajo para el programador; Sin embargo se puede contar que al final será un código más rápido, seguro y estable.

Ejemplo de los 2 Codigos:

El código a continuación mostrado representa los algoritmos de iteración y recursión de un préstamo, donde se utiliza la variable m para representar el monto, x para la tasa de interés y n el numero de periodos a calcular.

ITERATIVO


public float capital(float m, int n, float x)
{
if (n == 0)
{ return m; }
else
{
x = x / 100;
for (int b = n; b > 0; b--)
{m = m + (x * m);}
} return m;
}


RECURSIVO


public float capital(float m, int n, float x)
{

if (n == 0)
{ return m; }
else
{ return capital(m, n - 1, x) * (1 + (x/100)); }
}


REFERENCIAS:

http://www.programacionfacil.com/estructura_datos_csharp:transformacion_algoritmos_recursivos.htm
http://www.slideshare.net/demogorgon/algoritmos-recursivos
http://www.elcodigo.net/tutoriales/jsavanzado/jsavanzado4.html#punto3

Algoritmo Schönhage – Strassen

Es un Algoritmo que agiliza la multiplicación de números enteros de gran tamaño. Este algoritmo consiste en multiplicar los elementos de la cantidad 1 por los de la cantidad 2, al igual que se haría en la multiplicación normal. A los valores resultantes no se les aplica la operación de carga de la cantidad, dejando los valores así como resultan de la operación. Por ejm:

3 2 5
X 3 1 8

______________
24 16 40
3 2 5
9 6 15

_______________
9 9 41 21 40

A este primer resultado se le conoce como convolución lineal o acíclico. Una vez hecha la primera operación. Continuamos con la segunda parte que es la parte innovadora de este algoritmo. Esto consiste en dejar el elemento de la derecha y trasladar al número siguiente el elemento de la izquierda. Por ejm de 40 dejamos el 0 y trasladamos el cuatro al 21 iterando esta misma operación hasta realizarla al último número resultante. Este proceso es casi similar al original realizado en la multiplicación original. La diferencia radica en que el elemento de la izquierda lo sumamos al valor resultante directamente después de la suma realizada; En cantidades pequeñas esta diferencia no parece ser tan significativa; Pero en cantidades de números enteros realmente grandes, este algoritmo simplifica y agiliza considerablemente la operación. Terminando la operación quedaría de la siguiente manera:
9 9 41 21 40
= 10 3 3 5 0


Referencias:

http://es.wikipedia.org/wiki/Volker_Strassen
http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm

Volker Strassen

Es un brillante matemático alemán quien además destacó en otros campos como ser la filosofía, la física entre otros. Sin embargo; Sus estudios han venido a revolucionar el campo de la informática por sus importantes aportes al análisis de algoritmos.

Cuenta con un doctorado en Matemáticas el cual obtuvo en la universidad de Göttingen en el año de 1962 y entonces ocupó un puesto en el departamento de Estadística de la universidad de Berkeley, California.

En 1969 Strassen dirigió sus investigaciones hacia el análisis de Algoritmos, entre sus principales estudios y aportes a la matemática y la algoritmia podemos mencionar los siguientes:

• 
  
  Ley de Strassen del logaritmo Iterado. Este refiere a la función repetida de la función logaritmo sobre su argumento para encontrar valores iguales o menores a 1 y se representa Ln *(x). Esta función es utilizada en la informática para “Logaritmo Binario Iterado” que repite la función logaritmo en base 2. Este estudio fue citado y presentado ampliamente en el congreso Internacional de Matemáticos. Estas expresiones aplicando logaritmos iterados son aplicados en análisis de algoritmos como por Ejm. “Triangulación de Delaunay” , grafos y arboles.
  


• 
  
  El Algoritmo de Strassen. Volker Strassen sostuvo que la forma estándar de multiplicación de matrices no era óptima y en su intento de demostrarlo creo el método conocido como “Logaritmo de Strassen”. Este es ligeramente más rápido que el método estándar de multiplicación matricial; No obstante es más lento que el más rápido conocido.

Introduccion General

Hola a todos, mi nombre es Alejandro Henriquez y actualmente estudio la Ingenieria en Sistemas en la universidad Ceutec Honduras, el proposito de este blog es recopilar la informacion asignada, investigada y desarrollada de la asignatura "Estructura de Datos". Espero este blog pueda ser de utilidad a muchas mas personas y a traves de el desarrollar una estructura de informacion personal con la que siempre pueda contar como referencia.