Análisis asintotico

Ahora demostrare un ejemplo del ejercicio 2 del examen: Análisis asintotico. Esta fue la forma como respondí a la pregunta 2 del examen anterior.

2. Encuentre una función de complejidad asintotica f(n) así que la función g(n) definida experimentalmente por doce puntos en la siguiente tabla sea $\Omega f(n)$.

Justifique esto con una gráfica y discute la calidad de la cota obtenida.

n	g(n)	n	g(n)	n	g(n)
3	15	130	3,800	3,982	190,000
12	170	203	7,500	5,002	240,000
30	600	603	22,000	10,393	550,000
57	1,500	1,038	42,000	40,039	2,600,000

Primero noto que con los primeros 4 datos, f(n) podría ser n² porque 3² se aproxima a 15, 12² se aproxima 170, 30² se aproxima a 600 y 57² se aproxima a 1,500 pero al calcular los últimos, no:

3,982²= 15,856,324
5,002²= 25,020,004
10,393²= 108,014,449
40,039²= 1,603,121,251

Como la complejidad asintotica es mas importante a grandes instancias y n² crece demasiado rápido, probaremos con una función inferior pero que obviamente sea superior a n.

3,982^1.5= 251,276.5054
5,002^1.5= 353,765.5438
10,393^1.5= 1,059,525.4449
40,039^1.5= 8,011,702.8514

Demasiado, ahora con potencia 1.4:

3,982^1.4= 109,683.6155
5,002^1.4= 150,938.8936
10,393^1.4= 420,181.8590
40,039^1.4= 2,776,364.6813

Suficiente para mi, g(n)= n^1.4, ahora busquemos una cota inferior.

Sabemos que una cota inferior a g(n) puede ser f(n)= log n, pero no esta tan próxima a n^1.4, una mas inmediata seria n^1.35, así que la tomaremos y comparamos:

3,982^1.35= 72,466.4013
5,002^1.35= 98,592.5224
10,393^1.35= 264,606.3437
40,039^1.35= 1,634,377.4061

Los datos son inferiores a los de n^1.4, entonces f(n)= n^1.35 sera nuestra cota inferior u $\Omega f(n)$.

Vemos la gráfica:

Como pueden ver la linea roja representa nuestra función g(n) aproximada, la verde la cota inferior f(n) y la azul los datos experimentales de la tabla. La cota inferior resulto bastante buena ya que no nos fuimos hasta log n para hacerla inferior a la lineal n^1.4 sino a n^1.35 que se encuentra inmediatamente debajo de g(n).


Por ultimo me gustaría comentar sobre como realice esta entrada porque a alguien le podría servir en un futuro. Las potencias que se ven por el estilo de n^e, se realizan con una herramienta que ya viene incluida en los blogs que se llama superscript y subscript y se hacen escribiendo <sup> </sup> y <sub> </sub> respectivamente, mientras que los símbolos como $\Omega$ se hacen agregando al blog un gadget (código en java) para que reconozca escritura LaTeX, pero eso ya lo explique en esta entrada.

Por otro lado la gráfica la hice con un programa llamado gnuplot de descarga y uso gratuito, cuando lo descargue me incluyo un documento tutorial o guía para aprender a usarlo. Es un programa a base de linea de comando pero es muy potente.

Encriptacion RSA

Encriptacion: (Cifrado, codificación). La encriptación es el proceso para volver ilegible información considera importante. La información una vez encriptada sólo puede leerse aplicándole una clave.

Se trata de una medida de seguridad que es usada para almacenar o transferir información delicada que no debería ser accesible a terceros. Pueden ser contraseñas, numeros de tarjetas de crédito, conversaciones privadas, etc.

Acabo de leer hace poco sobre un método para encriptar información que es muy interesante, se creo en 1978 y se llama RSA, siglas de sus creadores: Rivest, Shamir y Adleman; se basa en la dificultad de factorizar números grandes en números primos, por ejemplo, resulta fácil multiplicar 2 números primos para obtener un tercero pero es difícil a partir del tercero obtener sus 2 factores primos. De hecho este es el mejor método de encriptacion que existe y lo usan bancos, instituciones gubernamentales, etc. Un banco de Monterrey, N.L. que usa este sistema proporcinado por RSA, The Security Division of EMC es Banorte:

Token Banorte

La mayoría de los números primos que se utilizan en la encriptacion RSA son de 250 dígitos o mas, esto es para obtener mayor seguridad pues es mas tardado factorizar un numero primo entre mas grande sea. Teóricamente cifras primas de 250 dígitos requieren millones de años para factorizar.

Como funciona exactamente

Resulta que:

$c \equiv m^{e} \ mod \ n$
$m \equiv c^{d} \ mod \ n$

Si y solo si
$n=pq$, p y q son números primos
$1 < e < \phi (n)$ y $gcd(e, \phi (n))=1$, con $\phi (n)=(p-1)(q-1)$
Y d cumple con $de \equiv 1 \ mod  \ n$
m seria un mensaje numerico y c su contra parte cifrada.
e seria la clave publica para encriptar y d la llave privada para desencriptar.
Nota: phi(n) es la función de Euler.

Procedimiento

1. Se buscan dos numeros p y q que sean primos.
2. Se obtienen n multiplicando p y q, y phi(n) multiplicando (p-1) y (q-1).
3. Se busca un numero e que no tenga divisores comunes con phi(n), y que divida a phi(n)+1 sin dejar residuo.
4. Se encuentra d con la division phi(n)+1 entre e.
5. Ahora ya tenemos todo y la llave publica sera (e, n) mientras que la privada es (d), como el resto de los numeros (p, q, phi(n)) no los vamos a necesitar, pueden destruirse para mayor seguridad.

Ejemplo

Supongamos que elegimos:

$p=11, \ q=23$, dos números primos pequeños ideales para nuestro ejemplo.
Entonces calculamos n: $n=pq=253,$
Calculamos phi(n): $\phi (n)=(p-1)(q-1)=(11-1)(23-1)=220$
Y e: $$1 < e < \phi (n)=220 \ y \ gcd(e, 220)=1$$.
Un numero que lo cumple es 13: $$1 < 13 < \phi (n)=220 \ y \ gcd(13, 220)=1$$
Ahora d es la division de phi(n)+1 entre e: $\frac{221}{13} =17$. Observamos que se cumple: $(17)(13) \equiv 1 \ mod  \ 253$, o que es lo mismo, phi(n)+1 puede ser dividido por e con residuo 0.

Comprobación:


Con el mensaje: 11
$c=11^{13} \ mod \ 253=132$
$m=132^{17} \ mod \ 253=11$


Otro ejemplo

Otro ejemplo con mayor claridad seria el siguiente:

$p=3, \ q=11$
$n=33$
$\phi n=(3-1)(11-1)=20$
$e=7$ porque cumple con 1 < 7 < 20 y gcd(7, 20)=1
$d=\frac{\phi (n)+1}{e}=\frac{21}{7} =3$

Comprobación:

Con el mensaje m=2

$c=m^{e} \ mod \ n=2^{7} \ mod \ 33=128 \ mod \ 33=29$
$m=c^{d} \ mod \ n=29^{3} \ mod \ 33=24389 \ mod \ 33=2$

Podemos observar que si introducimos el mensaje m=2 se encripta en c=29 y se puede desencriptar con la llave privada d. Ahora con nuestras llaves es posible encriptar y desencriptar cualquier mensaje numérico por mas largo que sea.

Nota que si vas a realizar operaciones de exponenciacion muy grandes, deberás de utilizar el algoritmo de potenciacion binaria para ahorrar operaciones.

Algunas formas para convertir un texto a numero es aplicando una llave numérica por partes o simplemente convirtiéndolo a valores ASCII (aunque esto no es tan seguro).

Mas información


http://www.rsa.com/
http://www.tagoror.com/enciclopedia/es/wikipedia/f/fu/funcion_phi_de_euler.html
http://boards5.melodysoft.com/canalingenio/la-funcion-phi-de-euler-225.html
http://neo.lcc.uma.es/evirtual/cdd/tutorial/presentacion/rsa.html

Ahora les mostrare el pseudocodigo que estoy haciendo, no esta terminado pero me da la idea de lo que voy a hacer para implementarlo.

/*Pseudocodigo para cifrar, metodo RSA*/

#include < stdio.h >
#include < time.h >
#define p long 47
#define q long 13
long p, q, n, h, e, d, m;
char M[4000];
long a[3], b[3], m[3], res;

n();
h();
e();
d();
string();
ps();
encrypt();
decrypt();
show-string();

main()
{
  n();
  h();
  e();
  d();
  put-string();
  ps(M)
  encrypt(m);
  decrypt(c);
  ps(m);
  show-string(M);
  getch();
}

n()
{
  //Elegir 2 primos (p y q)
  n=p*q;
}

h()
{
  //Funcion phi Euler
  h=(p-1)*(q-1);
}

e()
{
  //e  long fac[3];
  e=(5*h)/8;
  fac[0]=e;
  fac[1]=h;
  gcd();
  while (fac[1]!=1&&)
    {
      e++;
      gcd();
    }
}

d()
{
  //Algoritmo euclideano extendido para calcular
  //el modulo multiplicativo inverso de: e (mod h)
  a[1]=1;
  b[1]=0;
  m[1]=e;
  a[2]=0;
  b[2]=1;
  m[2]=h;
  res=e-(h*m[2]);
  while (m[2]!=1)
    {
      //Correr los valores
      a[0]=a[1];
      a[1]=a[2];
      b[0]=b[1];
      b[1]=b[2];
      m[0]=m[1];
      m[1]=m[2];
      //Calcular ultimos valores
      a[2]=a[0]-(a[1]*res);
      b[2]=b[0]-(b[1]*res);
      m[2]=m[0]-(m[1]*res);
    }
  d=a[2];
}

string()
{
  printf("Introduce el mensaje que quieras encriptar:\n");
  scanf("%s", M);
}

ps(char x)
{
  //Convertir cadena a numeros o viceversa
  if (isalfa(x))
    {
      m=tonumber(x);
      return m;
    }
  else
    {
      M=toalfa(x);
      return M;
    }
}

long encrypt(long)
{
  c=pow(m, e) mod n;
  return c;
}

long decrypt(long)
{
  m=pow(c, d) mod n;
  return m;
}

show-string()
{
  printf("%s", M);
}

gcd()
{
  //Algoritmo euclidiano
  fac[0]=e;
  fac[1]=h;
  fac[2]=fac[0]%fac[1];
  while (fac[2]!=0)
    {
      fac[0]=fac[1];
      fac[1]=fac[2];
      fac[2]=fac[0]%fac[1];
    }
}





Seguiré mejorando el pseudocodigo y mejorare la información aquí presente. Pueden darse una vuelta de vez en cuando para ver el avance. También agregare mas enlaces con información por si tienen dudas de como conseguir todos los números para las claves, se supone  que se utilizan ciertos métodos de factorizacion como el algoritmo euclideano que aprendimos la clase pasada en el salon pero por falta de tiempo no la mostrare aquí.

Actualización 18 Mayo 2010: He corregido unas cosas importantes y agregue un ejemplo mas.
Actualización 21 Mayo 2010: Utilizar algoritmo de potenciacion binaria para ahorrar operaciones.

Proyecto 5: Ciclo euleriano

El tema que yo elegí se llama ciclo euleriano, Euler se pronuncia "oil-er". A este tema también se le llama circuito euleriano, circuito de euler, tour euleriano o tour euler.

Definición

Un ciclo euleriano es un camino en un grafo G que comienza y termina en el mismo vértice, que incluye cada arista del grafo exactamente una vez y que puede tener vértices repetidos, es decir, un ciclo que incluye todas las aristas de E y que estas no se repitan.

Temas similares

Este tema esta extremada mente relacionado con el camino euleriano que trata sobre encontrar un camino en un grafo G de manera que se incluyan todas sus aristas sin repetirse, y también es comparado mas aun con el ciclo hamiltoniano que trata sobre un ciclo que incluye todos los vértices una sola vez.

Orígenes

Este acertijo surge con el problema de los 7 puentes de Königsberg (ciudad alemana del siglo XVIII situada sobre el río Praga) que fue resuelto por el matemático suizo Leonhard Euler en 1736 y publicado en un articulo titulado: Solutio problematis ad geometriam situs pertinentis (Solución de un problema relacionado con la geometría de posición).

El problema trata sobre atravesar los 7 puentes de la ciudad que conectaban 2 islas, una sola vez cada uno.

 Königsberg

http://staff.jccc.net/swilson/misc/images/koenigsberg_1910.jpg   

Los puentes son los caminos blancos sobre el río gris.

Euler resolvio el problema imaginando el territorio de las islas y el rio con un grafo conexo.

Para entender el problema de los 7 puentes de Königsberg, hay que imaginar que las aristas son los puentes y que los vértices son islas o territorios en la siguiente imagen.

Ahora hay que tratar de encontrar un ciclo que incluya todas las aristas de manera que en el trayecto no se repitan aristas.

...


Euler descubrió que esto es imposible de hacer en este grafo!, mas no fue el quien dio la demostración matemática sino que fue Carl Hierholzer hasta 1873.

Lo que Leonhard Euler dijo fue (en nuestros términos) que un ciclo euleriano en un grafo G existe si y solo si:

1. El grafo era conexo, es decir, hay por lo menos un camino para llegar a cualquier vértice y
2. El grado de todos los vértices de G es un numero par o dicho de otra manera, si no existe un solo vértice de grado impar.

Y como podemos observar, el grado de cada vértice en el grafo es un numero impar, de tal manera que ni siquiera se aproxima poseer un ciclo euleriano ya que si quisiéramos crearlo tendríamos que agregar o eliminar las tres arista del centro del grafo o agregarle 2 aristas.

Explicación

Podemos entender el argumento de Euler debido a que en un ciclo euleriano cuando pasamos a través de un vértice tenemos que tener 2 caminos (aristas) o cualquier otro numero par, esto es gra(e) mod 2 = 0, uno para llegar y el otro para partir o viceversa y completar el ciclo, de otro modo nos quedaríamos "atascados" en el mismo vértice o en su defecto jamas podríamos volver, de cualquier modo siempre nos faltaría 1 arista por recorrer para completar el ciclo.

Problema que se debe de resolver

Se puede decir que Euler resolvió el siguiente problema de decisión:
"Existe un trayecto que incluya todas las aristas sin repetirse, partiendo de un vértice v y regresando al mismo vértice v, en un grafo G?".

Sin su algoritmo para determinar este problema de decisión, tendríamos que realizar todos los trayectos posibles para determinar si existe algún ciclo euleriano y esto nos daría una complejidad asintótica O(n!), pero con las simples reglas de Euler obtenemos la complejidad O(n).

Ejemplo de ciclo euleriano

Es interesante observar que no importa cuan grande o complejo sea un grafo, si cumple con las 2 condiciones necesarias anteriores (1 y 2), este posee un ciclo euleriano.

En esta imagen el grafo es conexo además de que el grado de todos los vértices es un numero par.

Algoritmo del problema

Se pueden realizar varios algoritmos dependiendo de lo que se pretende resolver, por ejemplo, uno que resuelva el problema de decision: Existe un ciclo euleriano en un grafo G?, otro que resuelva el problema de decision: Cual es un ciclo euleriano en G?, e incluso un tercero que resuelva el problema de decisión: Cuales son todos los ciclos eulerianos en G? (una variante del anterior).

Ademas de que pueden existir variaciones del ciclo euleriano para resolver problemas de optimizacion como: Encuentra un ciclo euleriano de manera que se recorran ciertos vertices antes que otros, en este caso se podrian ponderar los vertices de acuerdo a la preferencia y optimizando el trayecto a recorrer para obtener el mejor ciclo posible.

Algoritmo de existencia

1. Para cada vértice en el grafo se analizara su grado (ignoramos los vecinos, es trivial).
2. Si alguno tiene un grado impar, se dirá que no existe un ciclo euleriano en el grafo y termina el algoritmo.
3. Si al final de analizar todos los vértices, nunca se dijo que no existía un ciclo euleriano, entonces se dice que si existe un ciclo euleriano.

Algoritmo de busqueda (cual es un ciclo euleriano?)

1. Iniciamos en un vértice al azar o elegido
2. Imaginamos una barrera que comienza a recorrer una arista elegida al azar.
3. La barrera se movera hasta que pueda llegar a un vértice con grado distinto a 1. La barrera almacenara en una pila cada arista del trayecto que recorrió, en orden. 
4. Nota: Esta barrera reservara un camino de llegada al vértice inicial, asegurando el ciclo.
5. La barrera cada vez que se mueve a una nueva posicion, eliminara las aristas recorridas.
6. Por otro lado imaginamos un viajero que recorrerá aristas al azar y que por supuesto no tiene acceso a las aristas eliminadas en el trayecto de la barrera.
7. Cada vez que se mueve el viajero a una arista vecina, guarda la arista recorrida en una lista o arreglo y elimina esa misma arista (para no volver a pasar por allí).
8. Cuando la barrera y el viajero no puedan moverse a ningun vertice vecino, se dice cual es el ciclo euleriano, mostrando primero la lista y luego la pila cuyos elementos aparecen en orden contrario a su introducción.

Nota: Probablemente exista un mejor método para encontrar un ciclo euleriano pero por falta de tiempo solo pensé en este algoritmo.

Complejidad computacional

En el algoritmo de existencia consideramos la instancia n como la cantidad de aristas en el grafo, en el paso 1 se sabe de un ciclo de n veces las operaciones que realizara dentro de este. En el segundo paso (que esta dentro del ciclo) se realiza la operación modular con 3 y la comparación con 0 para determinar si el grado es impar, estas son 2 operaciones (2n hasta ahora). Y en el tercer paso solo espera que termine el ciclo para decir que si existe un ciclo euleriano. En total fue:

$O(2n)$, como las constantes no importan es $O(n)$. El problema de existencia de un ciclo euleriano esta en P porque la complejidad O(n) es polinomial.

Pseudocodigo del algoritmo

Problema de decisión (existe un ciclo euleriano?)

#define num_de_vertices 4000

main()
 int i, grad[num_de_vertices];

 for (i=0;i<=size(grad[]);i++)
   if (grad[i]>1)

     if (grad[i]%3==0)
         puts No existe ciclo euleriano;
         goto end;
   else
     puts No existe ciclo euleriano;
end

Problema de decisión (cual es un ciclo euleriano?)

#define num_vertices 4000
int n, fin=0, turno=1, barrera, viajero, ver, aristas[400][400]; //aristas[][] no es mas que una matriz de adyacencia

main()
  read datafile; //Se encuentra la información del grafo
  ver= rand(0)%3;//Elegimos un vértice al "azar"
  barrera=ver;
  while (!fin)
    switch (turno) //Turnamos las funciones de barrera y viajero
      case 1:
           fbarrera();
           break;
      case 2:
           fviajero();
           break;
  if (detenerbarrera==true&&detenerviajero==true)
    print camino(); //Se terminan de turnar y muestran resultados
    print pila(); //en el orden correcto
end


fbarrera()
  if (gra(barrera)==0)//Si no tiene a donde ir, marca terminado
    detenerbarrera();
    fin=true;
  if (gra(barrera)==1)//Si solo existe un camino posible,se mueve
    pila(barrera); //Almacena el trayecto en que se movió
    barrera=vecino(barrera);//Aquí se mueve
    eliminar(barrera, vecino(barrera));//Se elimina ese camino //para no repetirlo
  turno++;
end 


fviajero()
  if (gra(viajero)==0) //Si no tiene a donde ir, marca terminado
    detenerviajero();
  camino(viajero);//Se alamacena el trayecto
  viajero=vecino(viajero);//Se mueve por una arista permitida
  eliminar(viajero, vecino(viajero));//Para no repetir aristas
  turno--;
end


vecino(int x)
  int i;
  for (i=0;i<=num_vertices;i++)
    if (aristas[x][j]==1)//Si existe una arista que incide en x, //se regresa el vértice al que lleva la arista
      return alpha(j);
end


eliminar(int t, int k)
  aristas[t][k]=null;//Al eliminar se asegura quitar la relacion
  aristas[k][t]=null;//en cualquier direccion
end


Análisis asintótico del algoritmo

Para el primer algoritmo en el peor caso es $O(n)$ porque:

Se asigna una constante (num_de_vertices). +1 paso
El for crea un ciclo donde la complejidad dependerá de los procesos dentro de este.
Se hacen dos comparaciones, grad[i]>1 y grad[i] mod 3==0, y una operación modular, mod 3. +3n pasos

Tenemos entonces O(3n+3) pero como las constantes no importan es O(n) y resulta polinomial.

En este mismo pseudocodigo en el mejor de los casos es O(1) esto es debido a que el primer vértice introducido puede ser de grado impar y por lo tanto eliminar la posibilidad del grafo en poseer un ciclo euleriano, entonces el caso promedio seria $O(\frac{1+(3n+1)}{2})$, como las constantes son triviales, sigue siendo $O(n)$.


Para el segundo algoritmo (de búsqueda) es $O(n)$ porque:

Declaramos una constante, num_vertices, y una variable, turno. +2 pasos
Asignamos un vertice al "azar". +2 pasos
Igualamos barrera y ver. +1 paso
Se intercambiaran el mando del programa fbarrera y fviajero por turnos, esto depende de que tan rapido encuentre el ciclo euleriano.

fbarrera va a comparar si termino de buscar el ciclo (1 operación), compara el grado del vértice actual (1 procedimiento si se almacena su grado). +2 pasos

Aquí viene lo interesante, si el grado de vértice es 1, la barrera puede avanzar y realizara las operaciones siguientes:

• Almacena su trayecto en la pila (1 operación), se cambia de posición (1 operación) a un nodo vecino que para encontrarlo se hace en aproximadamente n pasos dependiendo del grado del vértice actual (n operaciones aproximadamente), y elimina la arista que recorrió (2 operaciones). n+4 pasos
• Incrementa el turno. +1 paso

fviajero almacena su trayecto en un arreglo o lista, se mueve (1 operación) a un nodo vecino que para encontrarlo se hace en aproximadamente n pasos dependiendo el grado de vértice actual y se elimina la arista que recorrió (2 operaciones). n+3 pasos


El resultado es $O((t/2)(2n+9))$, donde t es la cantidad de veces que se turnaron.

Nota: En realidad la complejidad asintotica es menor que lo anterior pero no me meteré en detalles numéricos.

Al final las constantes se ignoran y nos quedamos con $O(n)$. El problema esta en P, tiempo polinomial.

Estructuras de datos utilizadas

Utilice arreglos unidimensionales en el primer pseudocodigo y arreglos unidimensionales, pilas y listas en el segundo.

Aplicaciones

Una aplicación del ciclo euleriano puede ser en la optimizacion de recorridos en mapas, por ejemplo si nos preguntaran si existe un camino para un viaje de turistas de manera que estos no recorran cualquiera de los caminos mas de una vez o en la versión extendida, cual es el mejor ciclo para los turistas recorriendo ciertos lugares antes que otros y sin pasar por los mismos caminos mas de una vez?.

También se me acaba de ocurrir que se puede aplicar en la determinación de flexibilidad en problemas de decisión en grandes instituciones o empresas, por ejemplo si se crea un modelo gráfico que simulara las opciones por las que puede optar una empresa con aristas y los estados finales al llevar a cabo lo optado con vértices, se podría conocer entonces el grado de flexibilidad en decisiones de cada estado dependiendo si existe un ciclo euleriano que permita volver al estado inicial por opciones distintas (aristas distintas), esto se vuelve mas real si permitimos la eliminación de opciones con el tiempo, es decir, eliminar aristas cada cierto tiempo, sea al azar o no.

Curiosidades

• Los 7 puentes de Königsberg fueron bombardeados y destruidos por los aliados en 1944 y solo 5 se reconstruyeron.
• La ciudad Königsberg fue renombrada Kalingraado y ahora es parte de Rusia.
• Ahora es posible visitar los puentes con un camino de Euler pero no con un ciclo de Euler. 
• El problema de los 7 puentes de Königsberg resuelto por L. Euler abrio paso a la topología, rama de las matemáticas que se encarga de estudiar propiedades de los objetos geométricos que tienen que ver con la posicion relativa entre puntos.

Fuentes

1 http://www.itl.nist.gov/div897/sqg/dads/HTML/eulercycle.html
2 http://www.economicexpert.com/a/Eulerian:path.htm
3 http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK4/NODE165.HTM
4 http://books.google.com.mx/books?id=7XUSn0IKQEgC&pg=PA502&lpg=PA502&dq=euler+cycle+applications&source=bl&ots=z6cFQPOS0e&sig=gCQCrKXT4T2ZWCFZLVtJ9k-juhk&hl=es&ei=x-DpS5DhHoyCtgOX3IX-Bw&sa=X&oi=book_result&ct=result&resnum=9&ved=0CFkQ6AEwCA#v=onepage&q&f=false
5 http://theoremoftheweek.wordpress.com/2009/09/29/theorem-8-eulerian-circuits/
6 http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/eulerTour.htm
7 http://mathworld.wolfram.com/EulerianCycle.html
8 http://mathforum.org/isaac/problems/bridges2.html
9 http://www.cs.sunysb.edu/~skiena/combinatorica/animations/euler.html
10 http://mathdl.maa.org/mathDL/46/?pa=content&sa=viewDocument&nodeId=1310&bodyId=1452 (explica cada párrafo de la demostración escrita por L. Euler)
11 http://math.dartmouth.edu/~euler/docs/originals/E053.pdf
12 http://www.iesezequielgonzalez.com/matematicas/grafos.htm
13 http://www.mathematische-basteleien.de/house.html
14 http://books.google.com.mx/books?id=aFDWuZZslUUC&printsec=frontcover&dq=CRC+concise+encyclopedia+of+mathematics&ei=f1z0S9qxLpTukgSM_YS8Bw&cd=1
15 http://books.google.com.mx/books?id=TrXd-gxPhVYC&printsec=frontcover&dq=The+algorithm+design+manual+2&ei=x1z0S9aPFJf4lASauI2uBw&cd=1
16 http://www.ual.es/~jlrodri/Topgen5/introduccion.html 



Comentario de auto evaluación


Creo que realice un buen trabajo con el reporte del blog, inclui todos los requisitos, agregue imagenes, trate de explicar de la manera mas simple posible, por otro lado mostré el algoritmo en que yo pensé para poder resolver el problema, y en algunas partes pedi la participacion del lector, estuvo muy completo e inclui 16 enlaces fuente al final para que los lectores encontraran mas información del tema.

Respecto a la presentacion, los primeros segundos al comenzar estaba algo nervioso pero despues se me fueron conforme pasaba el tiempo y me concentraba en la teoria, la cantidad de diapositivas para mostrar me parecio que se excedia en 2 para el tiempo de esta ocasion pero me las salte y las explique muy rapido, aun asi esas 2 diapositivas solo resaltaban el ejemplo posterior del algoritmo y fue mas facil que el publico entendiera la solución del problema de esta ultima forma. El diseno de la presentacion fue muy simple para mantener todo limpio, claro y conciso.

También hice al publico partícipe de la presentación y comente alguna curiosidad pequeña respecto al problema del ciclo euleriano al terminar. El tiempo que me tarde fue un poquito mas del limite acordado pero valieron la pena esos segundos extra para el publico.

Isomorfismo

Que es isomorfismo?

La propiedad de un grafo que indica que dicho grafo puede obtenerse de otro re etiquetando sus vértices.

Matemáticamente hablando:

G= (V, E) y G'= (V', E') son isomorfos $G\cong G'$ si existe una aplicación biyectiva f entre sus respectivos conjuntos de vértices V y V' que preserva sus adyacencias:

$$\forall v,w \in V,  v~w \Leftrightarrow f(v)~f(w)$$

La idea es simple, todos los vecinos que pertenecen a un vértice, también deben pertenecer al vértice del otro grafo.

Por ejemplo si el grafo G(1, 5) posee un vértice v cuyos vecinos son {a, b, c, d, e} y otro grafo M(1, 5) posee un vértice x cuyos vecinos también son {a, b, c, d, e}, entonces el vértice v es el mismo que el vértice x y los grafos G y M son los mismos a excepción por su ubicación en el espacio. Eso es isomorfismo, pero es mas claro verlo con un ejemplo:

En la imagen las posiciones de los vértices cambian al igual que algunas aristas, sin embargo todos los vértices conservan los mismos vecinos, entonces ambos grafos son isomorfos.



Fuentes


http://mate.cucei.udg.mx/matdis/5gra/5gra6.htm
http://web.udl.es/usuaris/p4088280/teaching/terminologia.pdf
http://mathworld.wolfram.com/GraphIsomorphismComplete.html

Prueba de escritura LaTeX

Prueba 1:

$$\int\int \frac{\sqrt{2x}^7\cos^3{8x}}{9-\sqrt{4x^2-672}}  dx$$ $$\LaTeX !$$

Acabo de agregar una función que me permite interpretar código LaTeX en el blog, la forma de hacer esto se describe fácilmente en esta mini guía. Aquí esta otra guía diferente que hace lo mismo (también proporciona el código javascript), eligan la que mas les guste.

Resumiendo el procedimiento: Copien el código que aparece en esa guía y agregenlo como gadget HTML/Javascript a su blog.

Ahora pueden escribir cualquier símbolo matemático entre 2 signos de dinero $.
Ejemplo: (signo dinero)codigo LaTeX(signo dinero)

Algunos otros ejemplos:

$$\exists \forall \wedge \vee \ni \bigcup \notin \nabla (\partial \int \hbar \prod \delta \mu \lambda \alpha \zeta \sqrt{\sum\gamma\eta}\ointH\Gamma)$$

Proyecto 4: Merge sort

El proyecto que elegimos mis compañeros y yo se trata de un algoritmo que ordena un arreglo con un método de división recursiva (merge sort u ordenamiento por mezcla).

Que hice yo:

Ayude a editar la presentación, cree un pseudocódigo, hice parte de la implementación interactiva y subí el documento a Internet.


Como me salio:

El diseño de la presentación fue correcto, limpio y ordenado, el pseudocódigo que hice no me convenció del todo porque lo  hice muy rápido casi sin pensarlo y tal vez debí de agregar mas detalles pero por otro lado esta bien mantenerlo simple y general para que el publico lo entienda rápidamente, y en cuanto a la implementación interactiva no estoy seguro de darle el orden correcto aunque de todas maneras se entienden los pasos del algoritmo.

Que podría mejorar:

Probablemente la longitud del pseudocódigo, en lugar de dejarlo sin detalles, crear el código en lenguaje C y por otro lado no dejar las cosas para ultima hora.

En qué aspectos estoy bien y en qué me hace falta mejorar:

Estoy bien al tomar el mando del equipo porque casi nadie tiene la iniciativa, también en cuanto al esfuerzo extra para hacer las cosas bien. Estoy mal en la falta de responsabilidad y en dejar todo a última hora ya que aunque quiera hacer un esfuerzo extra para mejorar las cosas, ya no alcanza el tiempo.

Ayudo a los demás o me apoyo en ellos:

Definitivamente ayudo a los demás, si hay tiempo les explico como funcionarían algunas cosas, si no hay tiempo les digo que después les explico para poder avanzar en cuanto al proyecto y que en cambio traten de leer un poco mas sobre el tema.
 
Quién se encarga de coordinar el trabajo:

En todos los equipos a los que he pertenecido, siempre soy yo el que coordino el trabajo, observo las capacidades y formo grupos mas pequeños, les pido que cada quien haga algo al igual que los demás, para que todos cooperemos al mismo tiempo (cuando se puede).

Qué papel tomo yo:

El que coordina a los demás y el que hace los códigos o pseudocódigos. Tomo mucha iniciativa y espero lo mismo de los demás aunque la mayoría de las veces no ocurra.

Reflexión personal:

Me falto ampliar el pseudocódigo porque iba a la carrera, siendo sincero no es que no administre mi tiempo si no que la organización con los demás miembros fue difícil, planeamos trabajar cosas juntos y acordamos fechas para reunirnos pero los horarios junto con la distancia nos impidió muchas cosas.

Links a los blogs:

Joel Ángel Escamilla Montemayor

Jorge Martínez Chavez 

Descargar:
Descargar
Visualizar 
  
Dinámica interactiva:
Applet Java

Proyecto 3: Calcular potencias elevadas

El problema que optamos para el proyecto 3 es el de calcular potencias elevadas.

Objetivo: Calcular una potencia elevada en el menor tiempo posible empleando algoritmo iterativo y/o recursivo

Que es recursion: Un algoritmo recursivo es aquel que realiza una llamada a una subrutina inherente a la misma, haciendo que los pasos o acciones dentro de esta, puedan ser repetidos sucesivamente hasta que una o varias variables pueda ser operada al convertirla en un dato conocido. Las propiedades de las subrutinas nos permiten expander su uso a una infinidad de programas, incluso a los mas complejos.

Un algoritmo recursivo se puede usar cuando se necesitan realizar las mismas acciones muchas veces, que aunque no es mas eficiente que el algoritmo iterativo, ahorra tiempo al implementarlo.

Como trabajamos como grupo: La organización no fue lo mejor en nuestro equipo, aunque con algo de esfuerzo hacia el final, pudimos terminar todo lo planeado. Creo que tome un papel importante dentro de este, ya que me fui viendo cada vez mas frecuente como el que iba liderando al equipo ya que asignaba actividades o corregía algunos trabajos.

Que fue mi contribución al trabajo: Realice ambos algoritmos (iterativo y recursivo), los 2 pseudocodigos los realice a partir de un código hecho por mi compañera en lenguaje C, que corregí previamente. Hice ademas las gráficas del análisis asintotico con el programa "gnuplot", la corrección de la introducción, la conclusión y las recomendaciones.
También la complejidad computacional, el análisis paso a paso solo del algoritmo iterativo y al igual que mi compañero, subí el documento PDF a Internet para mayor seguridad.

Que podría mejorar en el futuro: La creación de los pseudocódigos y la forma de organizarme individualmente y con mi equipo.

Links a los blogs:

Dora Nelly González Martínez

Joel Ángel Escamilla Montemayor

Jorge Martínez Chavez

Links del documento PDF:

Visualizar

Descargar

Proyecto 2: Árbol de expansión mínima

El problema que yo elegí es: Árbol de expansión mínima o minimum spanning tree (MST)

Objetivo:

Se pretende a partir de un grafo conexo, construir un árbol o subgrafo sin ciclos,  conteniendo todos los vértices del grafo inicial y con la suma de distancias o pesos mínimos posibles. Es decir, buscamos la expansión mínima.

Aplicaciones:

La aplicación de estos problemas se ubica en las redes de comunicación eléctrica, telefónica, carretera, ferroviaria, aérea, marítima, etc. En donde los nodos representan un consumo eléctrico, teléfonos aeropuertos, computadoras,etc

En 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).

Ejemplo, si la compañía de televisión por cable desea instalar en un vecindario sus cables pero estos solamente pueden recorrer por patrones o caminos específicos, seria útil saber cuales caminos son los mas cortos para así ahorrar la mayor cantidad de cable posible.

Otra aplicación es la de las redes de telecomunicación para optimizar las distancias recorridas y asi mismo el material utilizado. Una similar a esta última es utilizada en redes de información entre servidores y computadoras cliente, para disminuir la distancia, aumentar la velocidad de transmisión de información y reducir los costos.

Otra aplicación mas, aunque menos obvia es que el árbol de expansión  total mínima puede ser usado como solución aproximada al problema del viajante de comercio (traveling salesman problem), recuerde que encontrar la solución óptima a este problema es NP-Hard.

Representación:

Nuestro grafo tiene un numero de vértices, así como ramas o conexiones entre estos vértices, además tiene un numero representante de la distancia o expansión entre ambos vértices. Matemáticamente se expresa G(V, E) donde V = (v1, v2, … vn ) es un conjunto finito de vértices (nodos) y E = Eij en un conjunto finito de enlaces que representan la conexión entre los terminales o estaciones. Cada enlace tiene un número positivo real asociado denotado por W = Wij representando distancia, costo, etc.

http://www.people.vcu.edu/~gasmerom/MAT131/mst.html

Definido matemáticamente:

Ejemplo de instancia y solución optima:

El tránsito de Rusia esta planificando la construcción de una línea de sistemas de transito que conecte 7 zonas principales de la ciudad. (A, B, C, D, E, F, G). Donde los kilómetros entre ellas se representan son un numero en el arista correspondiente. Cada kilómetro de construcción le costara al tránsito 4 millones.

El transito desea acortar la distancia de traslación entre las 7 zonas pero asegurando no gastar demasiado del presupuesto. Es decir, desean optimizar la construcción por kilómetro recorrido.

Esto se ilustra como:

Teniendo en cuenta las distancias entre las zonas, se puede resolver de la siguiente manera.

	AD y CE son las aristas mas cortas, con peso 5, y AD se ha elegido arbitrariamente, por tanto se resalta.
	Sin embargo, ahora es CE la arista mas pequeña que no forma ciclos, con distancia 5, por lo que se resalta como segunda arista.
	La siguiente arista, DF con distancia 6, ha sido resaltada utilizando el mismo método.
	La siguientes aristas mas pequeñas son AB y BE, ambas con distancia 7. AB se elige arbitrariamente, y se resalta. La arista BD se resalta en rojo, porque formaría un ciclo ABD si se hubiera elegido.
	El proceso continúa marcando las aristas, BE con distancia 7. Muchas otras aristas se marcan en rojo en este paso: BC (formaría el ciclo BCE), DE (formaría el ciclo DEBA), y FE (formaría el ciclo FEBAD).
	Finalmente, el proceso termina con la arista EG de distancia 9, y se ha encontrado el árbol de expansión mínima.

El total de kilómetros obtenidos son 39 y el costo resultante es 156 millones.

Qué pasaría si se hubiera construido en lugar de la distancia BE, la distancia BC?

Respuesta: El costo aumentaría a 160 millones.

Formular un problema de decisión correspondiente:

Existe más de una forma de resolver la expansión mínima de un grafo G(V, E)?

Si, existen 4 algoritmos para su solución, estos son:

1.       Algoritmo de Kruskal

2.       Algoritmo de Prims

3.       Algoritmo de Boruvka

Con complejidad O(E log n)

4.       Algoritmo de Edmond

Con complejidad O(E log n) para un árbol esparcido y O(n²) para uno denso.

Este problema fue resuelto independientemente por Dijkstra (1959), Kruskal (1956) y Prim (1957) y la existencia de un algoritmo polinomial (que todos ellos demostraron) es una grata sorpresa, debido a que un grafo con N vértices puede llegar a contener N^N-2 subárboles T*.

La complejidad asintótica del algoritmo

El algoritmo de solución es NP duro?

Presentar un algoritmo para el problema de optimización

Algoritmo de Prim

Los pasos son:

1.      Se marca un nodo cualquiera, será el nodo de partida.

2.      Seleccionamos la arista de menor valor incidente en el nodo marcado anteriormente, y marcamos el otro nodo en el que incide.

3.      Repetir el paso 2 siempre que la arista elegida enlace un nodo marcado y otro que no lo esté.

4.      El proceso termina cuando tenemos todos los nodos del grafo marcados.

Ejemplo: Determinar el árbol de mínima expansión para el siguiente grafo:

·         Siguiendo el algoritmo de Prim, tenemos:

o    Elegimos, por ejemplo, el nodo 1 y lo marcamos.

o    Elegimos la arista con menor valor incidente en 1, la (1, 3) = 1 la marcamos y marcamos el otro nodo en el que incide, el 3.

o    Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (1, 2) = 3 la marcamos y marcamos el nodo no marcado, el 2.

o    Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (2, 5) = 5 la marcamos y marcamos el nodo no marcado, el 5.

o    Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 6) = 1 la marcamos y marcamos el nodo no marcado, el 6.

o    Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 7) = 2 la marcamos y marcamos el nodo no marcado, el 7.

o    Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 4) = 6 la marcamos y marcamos el nodo no marcado, el 4.

o    FIN. Finalizamos dado que tenemos marcados los 7 nodos del grafo.

o    Por tanto el árbol de mínima expansión resultante sería:

Aquí hay un pseudocódigo de Prim para resolverlo, y otro ejemplo de ejecución.

   JARNIK (Grafo G, nodo_fuente s)

       // Inicializamos todos los nodos del grafo. La distancia la ponemos a infinito y el padre de cada nodo a NULL

       // Encolamos, en una cola de prioridad donde la prioridad es la distancia, todas las parejas del grafo

       por cada u en V[G] hacer

           distancia[u] = INFINITO

           padre[u] = NULL

           Añadir(cola,<u,distancia[u]>)

       distancia[s]=0

       mientras cola != 0 do

           // OJO: Se entiende por mayor prioridad aquel nodo cuya distancia[u] es menor.

           u = extraer_minimo(cola) //devuelve el minimo y lo elimina de la cola.

           por cada v adyacente a 'u' hacer

               si ((v ∈ cola) && (distancia[v] > peso(u, v)) entonces

                   padre[v] = u

                   distancia[v] = peso(u, v)

                   Actualizar(cola,<v,distancia[v]>)

Imagen	Descripción	No visto	En el grafo	En el árbol
	Este es el grafo ponderado de partida. No es un árbol ya que requiere que no haya circuitos y en este grafo los hay. Los números cerca de las aristas indican el peso. Ninguna de las aristas está marcada, y el vértice D ha sido elegido arbitrariamente como el punto de partida.	C, G	A, B, E, F	D
	El segundo vértice es el más cercano a D: A está a 5 de distancia, B a 9, E a 15 y F a 6. De estos, 5 es el valor más pequeño, así que marcamos la arista DA.	C, G	B, E, F	A, D
	El próximo vértice a elegir es el más cercano a D o A. B está a 9 de distancia de D y a 7 de A, E está a 15, y F está a 6. 6 es el valor más pequeño, así que marcamos el vértice F y a la arista DF.	C	B, E, G	A, D, F
	El algoritmo continua. El vértice B, que está a una distancia de 7 de A, es el siguiente marcado. En este punto la arista DB es marcada en rojo porque sus dos extremos ya están en el árbol y por lo tanto no podrá ser utilizado.	null	C, E, G	A, D, F, B
	Aquí hay que elegir entre C, E y G. C está a 8 de distancia de B, E está a 7 de distancia de B, y G está a 11 de distancia de F. E está más cerca, entonces marcamos el vértice E y la arista EB. Otras dos aristas fueron marcadas en rojo porque ambos vértices que unen fueron agregados al árbol.	null	C, G	A, D, F, B, E
	Sólo quedan disponibles C y G. C está a 5 de distancia de E, y G a 9 de distancia de E. Se elige C, y se marca con el arco EC. El arco BC también se marca con rojo.	null	G	A, D, F, B, E, C
	G es el único vértice pendiente, y está más cerca de E que de F, así que se agrega EG al árbol. Todos los vértices están ya marcados, el árbol de expansión mínimo se muestra en verde. En este caso con un peso de 39.	null	null	A, D, F, B, E, C, G

Finalmente les dejo un link para que vean como el algoritmo de Prim resuelve el problema paso a paso: Applet de simulacion de Prim

Bibliografía:

http://www.tcs.tifr.res.in/~prahladh/teaching/2009-10/limits/lectures/lec01.pdf

http://www.lab.dit.upm.es/~lprg/material/apuntes/o/index.html

http://www.people.vcu.edu/~gasmerom/MAT131/mst.html

http://www.ics.uci.edu/~eppstein/161/960206.html

http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/kruskal/Kruskal.shtml

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

http://lear.inforg.uniovi.es/ioperativa/TutorialGrafos/minimaexp/minimaexp.htm

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

http://en.wikipedia.org/wiki/Kruskal%27s_algorithm 

http://personales.upv.es/arodrigu/grafos/Kruskal.htm

http://www.mitecnologico.com/Main/ArbolesGeneradoresMinimales

http://docencia.udea.edu.co/regionalizacion/teoriaderedes/minimos.html

http://sisbib.unmsm.edu.pe/bibvirtual/publicaciones/indata/v05_n2/algorit_evo.htm

http://dns.uls.cl/~ej/fit_2009/teo_fit_2009/Lect_2009/Fit_1998/el.htm

http://www.algorithm-code.com/wiki/Prim%27s_algorithm

http://148.202.148.5/cursos/mt260/matedisc/unidad5/tem5.7.htm