miércoles, 12 de mayo de 2010

Proyecto #5 - Isomorfismo

Dos grafos G1 y G2 son isomorfos si existe una función biyectiva f entre los vértices de G1 y G2, y una función biyectiva g entre lados de G1 y G2 tales que un lado e es incidente a v y w en G1 si solo si el lado g(e) es incidente a los vértices f (v) y f (w) en G2. Al par de funciones f y g se le denomina isomorfismo.

Ejemplo:





Un isomorfismo para los grafos anteriores G1 y G2 esta definido por:
f (a) = A
f (b) = B
f (c) = C
f (d) = D
f (e) = E


Esto es ya que en G1 “a” esta conectada a “e” y “b”, en G2 “A” esta conectada a “E” y “B”, en G1, “e” se conecta a “a” y “d” y en G2, “E” se conecta a “A” y “D”, en G1 “d” se conecta a “e” y “c”, en G2 “D” se conecta a “E” y “C”, en G1 “c” se conecta a “d” y “b”, en G2, “C” se conecta a “D” y “B” y en G1 “b” se conecta a “c” y “a”, y en G2 “C” también se conecta a “C” y “A”.


El problema del isomorfismo de grafos presenta una curiosidad en teoría de complejidad computacional al ser uno de los pocos problemas pertenecientes a NP de los que se desconoce si es resoluble en tiempo polinómico o si es NP-completo.

En complejidad computacional, el Problema de isomorfismo de subgrafos, también a veces llamado Problema de matching de subgrafos, es un problema de decisión NP-completo, que formalmente, se define de la siguiente manera:

Isomorfismo-de-subgrafos(G1, G2)
Entrada: Dos grafos G1 y G2.
Pregunta: Es G1 isomorfo a un subgrafo de G2?

La NP-completitud del problema se demuestra mediante la reducción de este problema al Problema de la clique. Si el Problema de isomorfismo de subgrafos fuese polinomial, podría utilizarse para resolver el Problema de la clique, también en tiempo polinomial. Sea n el número de aristas de G, se puede ejecutar el problema de isomorfismo de subgrafos n-2 veces (siendo G1 una clique de tamaño 3 a n, y G2 siendo G) para encontrar el clique más grande en G.

Este problema es una generalización del posiblemente más sencillo Problema de isomorfismo de grafos, en el sentido que si este último es NP-completo, entonces la jerarquía polinomial colapsa, así que se supone que no debería ser así.

Otro ejemplo de Isomorfismo seria el siguiente:



Isomorfismo entre G y H:

f(a)=1

f(b)=6

f(c)=8

f(d)=3

f(g)=5

f(h)=2

f(i)=4

f(j)=7


lunes, 26 de abril de 2010

Proyecto 4

Hola, en este proyecto 4, escogimos el tema de "Colas" y mis compañeros de equipo son
Perla, Abraham y Blanca.

Bueno, en este proyecto me dedique a buscar informacion con mis compañeros, dando algunas ideas y ejemplos para el proyecto. Mis compañeras Blanca y Perla fueron las encargadas de coordinar al equipo, ya que dieron mas ideas, aportaciones y fueron las que realizaron algunas animaciones. En lo personal creo que necesito mejorar un poco mas en algunos aspectos como los pseudocodigos ya que eso es lo que se me dificulta mas.

Los blogs de mis compañeros:

Perla: http://adrianaa17.blogspot.com/

Blanca: http://www.blankardz22.blogspot.com/

Abraham: http://abrahamfime.wordpress.com/

jueves, 4 de marzo de 2010

Proyecto 2

Problema de las ocho reinas


El problema consiste en colocar 8 reinas en un tablero de ajedrez (8×8) de manera tal que ninguna de ellas amenace (pueda comerse) a ninguna de las demás. Una reina amenaza a los cuadrados de la misma columna, fila y de las mismas diagonales.

Es lógico que cada reina debe ir en una fila distinta. Por tanto, en un array se guarda la posición de cada reina en la columna que se encuentre. Ejemplo: si en la tercera fila hay una reina situada en la quinta columna, entonces la tercera posición del array guardará un 5. A este array se le llamará col.
Hace falta otro array que determine si hay puesta una reina en la fila j-ésima. A este array se le llamará fila.
Por último se utilizan dos arrays más para determinar las diagonales libres, y se llamarán diagb y diagc.

Para poner una reina se utiliza esta instrucción:
col[i] = j ; fila[j] = diagb[i+j] = diagc[7+i-j] = FALSE;

Para quitar una reina esta otra:
fila[j] = diagb[i+j] = diagc[7+i-j] = TRUE;

Se considera válida la posición para este caso:
if (fila[j] && diagb[i+j] && diagc[7+i-j]) entonces proceder ...

Aquí esta el código completo en C. Se han utilizado tipos enumerados para representar los valores booleanos.

#include 
 
enum bool {FALSE, TRUE};
typedef enum bool boolean;
 
void ensayar(int i, boolean *q, int col[], boolean fila[], boolean diagb[], boolean diagc[]);
 
int main(void)
{
  int i;
  boolean q;
 
  int col[8];
  boolean fila[8],diagb[15], diagc[15];
 
  for (i = 0; i <>
  for (i = 0; i <>
 
  ensayar(0,&q,col,fila,diagb,diagc);
  if (q) {
    printf("\nSolucion:");
    for (i = 0; i <>
  } else printf("\nNo hay solucion");
 
  return 0;
}
 
void ensayar(int i, boolean *q, int col[], boolean fila[], boolean diagb[], boolean diagc[])
{
  int j;
 
  j = 0;
  *q = FALSE;
  do {
    if (fila[j] && diagb[i+j] && diagc[7+i-j]) {
      col[i] = j; fila[j] = diagb[i+j] = diagc[7+i-j] = FALSE;
      if (i <>
        ensayar(i+1,q,col,fila,diagb,diagc);
        if (!*q)
          fila[j] = diagb[i+j] = diagc[7+i-j] = TRUE;
      } else *q = TRUE; /* encuentra la solucion */
    }
    j++;
  } while (!*q && j <>
}
 

Algoritmo del problema

Procedimiento

reinas(k, col, diag45, diag135)

//sol 1...k es k-prometedor//

//col={soli - i+1 | 1≤ i ≤ k}//


//diag45={soli - i +1 | 1≤ i ≤ k}//

//diag135={soli + i -1 | 1 ≤ i ≤ k}//

si k = 8 entonces // un vector 8 – prometedor es una solucion//

escribir sol

si no // explorar las extensiones (k+1) –prometedoras de sol//

para j← 1 hasta 8 hacer

si j no pertenece a coly j – k no pertenece a diag45y j +

k no pertenece a diag135 entonces

solk+1 ← j // sol1...k+1 es (k+1)-prometedor//

reinas (k+1, col U {j}, diag45 U {j-k}, diag135 U {j+k})


El algoritmo comprueba primero si k = 8, si esto es cierto resulta que tenemos ante nosotros un vector 8-prometedor,

lo cual indica que cumple todas las restricciones originando una solución.

Si k es distinto de 8, el algoritmo explora las extensiones

(k + 1)-prometedoras, para ello realiza un bucle, el cual va de 1 a 8, debido al número de reinas.

Este es un problema de satisfacción de restricciones o CSP, estos problemas

son importantes ya que pueden ser usados para modelar problemas combinatorios,

tales como programación de horarios e inventarios, inteligencia artificial, procesamiento de imágenes

y visión computarizada.

Los CSP son problemas NP-completos, por lo que no pueden existir

solvers completos y eficientes para CSP arbitrarios.


Aqui esta una imagen de una solucion..




martes, 16 de febrero de 2010

Proyecto I

Este proyecto es sobre la presentacion de un algoritmo para un problema que elegimos
el problema que yo elegi es el de buscar un numero telefornico en una guia telefonica.
El software que elegi para hacer el problema es el Raptor y lo hize en forma de diagrama de flujo.

Aqui esta su procedimiento...

Primero puse un output indicando que es la guia telefonica..

Despues puse otro output con las 5 opciones que indican las personas que estan en la guia telefonica asignandoles un numero a cada una..



Despues puse un input con la frase "elige un contacto" y una variable "x"..



Despues puse un selection y en el rombo puse x=1 ya que si en el input anterior pongo
un 1 se ira a la opcion "yes" y me dira el numero de ese contacto, si en el input anterior
pongo otro numero diferente de 1 se ira a la opcion "no", la cual me llevara a otro selection donde en el rombo esta un x=2, si el numero que habia puesto es 2 se ira a "yes", la cual me dira el numero telefonico de la persona 2, y si el numero que habia puesto tampoco es 2 se ira a "no", que me volvera a llevar a otro selection ahora con un x=3 en el rombo, que al igual si el numero que habia puesto es 3 me llevara a "yes" con el numero telefonico de la persona 3, si no es 3 el numero que habia puesto se ira a "no", que me volvera a llevar a otro selection con x=4 en el rombo, si el numero es igual
a 4 ira a "yes" y me dira el telefono de la persona, de lo contrario ira a "no" mandandome a un ultimo selection con x=5 en el rombo si el numero era 5 ira a "yes" y me dara el telefono, si no es 5 me pondra el mensaje "este contacto no existe", porque ya no hay mas contactos.



Aqui esta el diagrama de flujo completo..



Este es otro ejemplo del problema anterior


Tambien puse otros dos ejemplos de diagramas de diferentes problemas.

Este es sobre el menu de un restaurant..

Este es sobre cosas necesarias para sobrevivir en un desierto..


El blog de mi compañero es: http://alejandrocarrizalesgarcia.blogspot.com/

sábado, 6 de febrero de 2010

Ejercicio

En la clase pasada hicimos un ejercicio como este..
(ix13)%41=j, donde i seria un valor que se nos asignaria a cada uno, en mi caso era el 11, ese valor se multiplicaria por 13 y luego por el modulo de 41 y nos daria un valor "j" que despues lo convertiriamos a binario.
En la multiplicaion del ix13 me dio 143 y ese valor lo dividi entre 41 y el residuo me dio 20.
Convirtiendo ese numero a binario me salio a 10100.

Despues pusismos una tabla como esta (no esta muy bien hecha porque la hice con paint)..



Donde al principio se ponia el simbolo del triangulo y despues el numero binario,
si la letra S esta abajo del simbolo de triangulo se movia un lugar hacia la derecha, si la letra quedaba abajo de un 1 o un 0 tambien se movia un lugar hacia la derecha, cuando se terminaba el numero en el primer espacio la letra S se convertia en q y se movia un lugar hacia la izquierda si la letra q quedaba en un 0 se hacia "alto" y el 0 se hacia 1.
Despues con el nuevo numero binario "10101" debia dar a un valor de uno mas arriba que el anterior que daba 20, por lo tanto el valor 10101 es igual a 21.

Sistema Binario

Internamente, la máquina computadora representa los valores numéricos mediante grupos de bits. agrupados en bytes. Por ejemplo, el número 3 se representa mediante un byte que tiene "activos" los bits primero y segundo (contando desde la derecha); 00000011. Esta sería la forma de representación del número 3 en un sistema numérico de base 2, también conocido como BINARIO. El sistema que utilizamos normalmente es un sistema DECIMAL o de base 10. En un sistema DECIMAL, contamos desde el 0 hasta el 9 antes de añadir un nuevo dígito. El número 22 en un sistema decimal significa que tenemos dos conjuntos de 10s y 2 conjuntos de 1s.

En un sistema BINARIO sólo pueden haber dos valores para cada dígito: ya sea un 0=DESACTIVADO ó un 1=ACTIVADO. Para representar el número 22 en notación BINARIA lo haríamos como 00010110, notación que se explica según la siguiente tabla:

Posición del BIT: 7 6 5 4 3 2 1 0
Valor Binario: 0 0 0 1 0 1 1 0
Valor Decimal: 128 64 32 16 8 4 2 1
Valores a Sumar: 0 0 0 16 0 4 2 0
Valor Resultante: 16 + 4 + 2=2

Mas informacion:
http://personales.unican.es/togoresr/lisp/BINARIO.htm

Diagrama de Flujo

Un diagrama de flujo es una forma de representar gráficamente los detalles algorítmicos de un proceso multifactorial es decir dar soluciones a problemas que se pueden resolver en una manera que a veces no es sencilla o simplemente si no hay solucion con problema se debe usar una sencilla y sin problemas.

Aqui esta un ejemplo.


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