domingo, 7 de noviembre de 2010

Lenguajes Script (puntos extra) AWK

esta vez hablare un poco de lenguajes script mas específicamente de awk, shell y python

AWK

AWK es un diseñado para procesar datos basados en texto, ya sean ficheros o flujos de datos. El nombre AWK deriva de los apellidos de los autores: Alfred Aho, Peter Weinberger, y Brian Kernighan. awk, cuando está escrito todo en minúsculas, hace referencia al programa de UnixPlan 9 que interpreta programas escritos en el lenguaje de programación AWK. o
AWK es ejemplo de un lenguaje de programación que usa ampliamente el tipo de datos de listas asociativas (es decir, listas indexadas por cadenas clave), y expresiones regulares.

bien en este caso realize un programa ejercicio que utiliza las propiedades basicas de AWK

en este programa lo que muestra es la cantidad de lineas de un archivo, la cantidad de palabras y caracteres asi mismo, cuenta la cantidad de vocales que hay en dicho archivo con la  funcion gsub esto podria ayudarnos si quisiesemos buscar una palabra en concreto de ntro de un archivo, la cantidad de caracteres es sencilla de calcular con el comando length.
aqui la fotografia de la ejecucion y el archivo que yo utilize 
archivo aqui






















Aqui para descargar el codigo

Shell
Se conoce con el nombre de Shell al programa que atiende a los ordenes tecleadas en el terminal y las traduce (interpreta) a instrucciones en la sintaxis interna del sistema; es decir es él interprete de comandos del sistema operativo UNIX.
En este caso con shell puede ser muy util ya sea para realizar tareas que pueden ser repetitivas, en este caso lo usare para crear un respaldo de los archivos mas importantes de mi memoria USB loscuales los tengo en una carpeta llamada proyectos adicionales.

 














en este caso primero comprueba si existe la carpeta llamada respaldo donde seran copiados los archivos, y despues copia los archivos

Aqui el archivo del programa

Python

Python es un lenguaje de programación de alto nivel cuya filosofía hace hincapié en una sintaxis muy limpia y que favorezca un código legible.
Se trata de un lenguaje de programación multiparadigma ya que soporta orientación a objetos, programación imperativa y, en menor medida, programación funcional. Es un lenguaje interpretado, usa tipado dinámico, es fuertemente tipado y es multiplataforma.

 Bueno para este caso relize un programa que genera un numero aleatorio y hay que adivinar cual es, dependiendo de la respuesta indica si es mayor, menor o igual

este es el codigo




















Esta es la ejecucion de del programa





































Aqui dejare el programa para descarga

martes, 24 de agosto de 2010

Presentacion #1 Compiladores

Que tal gente bien pues esta vez les dejo una pequeña presentación acerca de optimización de compiladores y un pequeño resumen acerca de ellos, esta presentación estaría mejor entendida unto con la que dieron mis compañeros acerca del mismo tema así que les dejare la dirección de sus respectivos blog para que la revisen.

blogs
1. Ramón Esteban
2. Jonathan de la rosa

Con esto les dejo la presentación.

Si no se llega a ver aquí les dejo el link de la pagina host.
Presentación

Este otro para descarga.
Descarga

Bibliografía
1
2
3
4

lunes, 16 de agosto de 2010

Reporte # 2 Lenguajes de programacion : JAVA

Que tal compañeros pues bueno aquí me encuentro con este nuevo tema en una nueva asignatura Lenguajes de Programación y pues como su nombre lo indica este reporte hablara acerca de uno de los lenguajes mas conocidos que es JAVA.

Bien pues empecemos primero a conocer un poco acerca de este lenguaje con una definición un poco formal.

Definición
JAVA es un lenguaje de programación orientado a objetos, el lenguaje en sí mismo toma mucha de su sintaxis de C y C++, pero tiene un modelo de objetos más simple y elimina herramientas de bajo nivel, que suelen inducir a muchos errores, como la manipulación directa de punteros o memoria.

Esto se podría decir que JAVA cuenta con una interfaz mas sencilla que C y C++.

También encontré esta otra definición acerca del mismo.

La Máquina virtual Java es un maquina virtual de proceso nativo, es decir, ejecutable en una plataforma específica, capaz de interpretar y ejecutar instrucciones expresadas en un código binario especial y por estos días necesaria para correr muchos de programas cotidianos.

Bueno a pesar de que nuestra clase se basa netamente en el sistema operativo Ubuntu incluiré una liga a un pequeño tutorial de instalación en windows (realmente no recomiendo usar windows para programar pero eso es gusto de cada quien).

Comencemos entonces con los pasos para la instalación de java así como de su compilador.

Instalación

Por defecto, en Ubuntu nos encontramos con una versión libre del JRE (Java Runtime Environment) de Java, pero lamentablemente es una versión antigua, la 1.4.2. Actualmente Java ya es de código abierto, y se encuentra en la versión 6.

También existen otras formas sencillas de instalarlo como por ejemplo usar los repositorios oficiales de Ubuntu Para ello, simplemente debemos instalar desde los repositorios los paquetes
$ sudo aptitude install sun-java6-bin
$ sudo aptitude install sun-java6-jre
$ sudo aptitude install sun-java6-jdk.

Después de aver instalado posiblemente te hayas dado cuenta que al intentar compilar un archivo Java con algún programa, aparece un error que dice: javac no fue encontrado.

Esto se debe a que después de aver agregado algún JDK en este caso JDK6 (la version defalut), se debe de configurar el path.

El path o ruta en nuestro caso servirá para referenciar a la ubicación donde nosotros tenemos instalado JAVA.

Pues bien, primero abrimos una terminal. Luego, tendremos que hacer esto

1. Establecer javac de JDK como una "alternativa" (todo en la misma linea), ya que el sistema no lo reconoce:

$ sudo update-alternatives --install "/usr/bin/javac" "javac" "/usr/lib/jvm/jdk1.6.0_XX/bin/javac"
(XX la vesion del JDK que se descargo)

2. Ahora establecemos la "nueva alternativa" como la real de javac en el sistema:

$ sudo update-alternatives --set javac /usr/lib/jvm/jdk1.6.0_XX/bin/javac


3. Para comprobar si tenemos la versión de javac 1.6.0_06, escribimos en la terminal:

$ javac -version



Después de esto tendremos bien instalado java y podremos pasar a programar.

Yo recomiendo utilizar emacs para ello pues cuenta con muchas utilidades que se podrían aprovechar, ya un compañero hablo de eso eh hizo un pequeño tutorial acerca de emacs les dejare la liga a su blog si les interesa aprender de ello antes de empezar a utilizarlo.

Tutorial Emacs

Bueno una vez en emacs podremos empezar a utilizar dicho programa y bueno utilizar algo sencillo para verificar las funciones de compilación y ejecución.

Bien en este caso utilizare un código estilo "hola mundo" para verificar dichas funciones.
---------------------------------------------------------------------------------------
public class HolaMundo {

public static void main(String[] args) {
System.out.println("Hola Mundo");
}

}
---------------------------------------------------------------------------------------

Algo muy importante que debemos recordar al momento de nombrar nuestro fichero para la compilación es que este debe de llevar el mismo nombre que la clase. de manera que si en nuestro programa lo llamamos

HolaMundo
nuestro fichero pasaría a llamarse
HolaMundo.java

Para compilar y ejecutar este código tendremos que ejecutar las siguientes sentencias:

javac HolaMundo.java (esta linea para Compilar dentro de un terminal.)
java HolaMundo (esta otra para Ejecutarlo).


Bueno con esto termino la pequeña explicación sobre java dejare las ligas a algunos tutoriales y manuales, así como las ligar de referencias de información que vieron en este blog.

Tutoriales.
1
2
Manual de Instalación en Windows

Definiciones:
Path
JAVA
Añadir aplicaciones

viernes, 16 de julio de 2010

Que tal gente esta vez venimos a hablarles acerca del algoritmo de kruskal y bien esta vez fue el algoritmo lo explicaremos paso a paso para mayor entendimiento y puedan comprender lo que hace.

aquí les dejare la liga para la descarga directa. descargar

Acerca de esto
Este es un algoritmo de los grafos, su intención es la de encontrar el camino mas corto(con menos recursos) llegando a todos los nodos, una de sus características de este algoritmo es de que al finalizar su resultado no tendrá ciclos, así que sera un árbol.


Funciona de la siguiente manera:
se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es un árbol separado
* se crea un conjunto C que contenga a todas las aristas del grafo
* mientras C es no vacío
* eliminar una arista de peso mínimo de C
* si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un solo árbol
* en caso contrario, se desecha la arista.


Aplicaciones.
Las aplicaciones mas comunes que se utilizan en este algoritmo son para ahorrar recursos, como en circuitos eléctricos, conexiones, entre otras...



Aquí un ejemplo de su aplicación
Supongamos que una compañía de teléfono va a brindar servicio a sus clientes, tómese, los nodos azules son los postes de teléfono, y los nodos naranjas, son el lugar donde se quiere dar el servicio, y la linea negra, seria el cable necesario a usarse...





Ahora hay que encontrar cual sería la menor cantidad de cable que se puede utilizar.



Aquí si quieres hay paginas donde vienen animaciones, para que entiendas mejor

Kruskal
View more documents from Jorge.


www.mincel.com/java/prim.html
http://www.cut-the-knot.org/Curriculum/Games/Mazes.shtml

martes, 13 de julio de 2010

Tarea # 3

Que tal compañeros esta vez vengo a hablar de la búsqueda por anchura esta a diferencia de la búsqueda por profundidad es que esta usa una cola en vez de una pila.

acá dejare la liga para la descarga del archivo ó podrán verlo mas abajo si tiene instalado el plug-in de adobe flash.

código para descarga.
archivo .dat que contiene los nodos descarga.
Definición
¿Que es el BFS? es un algoritmo de búsqueda por anchura que dado un nodo inicial viaja por los vértices hacia los vecinos de este, después viaja através de los vértices de sus vecinos y así sucesivamente hasta visitar cada nodo del grafo.

¿Que es el coloreo de grafos? se dice que es un caso etiquetado de grafos en el cual asignamos
unas etiquetas llamadas colores, bien pues el objetivo de esto es colorear un nodo de tal manera que se use la menor cantidad de colores posibles cumpliendo con la condición de que no debe tener el mismo color dos nodos que estén unidos entre si.
Objetivo
Bien pues a mi me toco utilizar dicho algoritmo para la coloración de un grafo con dos colores, de esta manera al aplicar el algoritmo si detectaba un ciclo no seria posible que fuese dos coloreable.

Procedimiento
Bien pues el procedimiento para resolver este problema lo realice de una manera utilizando un código que ya antes teníamos este código fue uno realizado en clase en el cual simulaba las acciones de un algoritmo de DFS, bien pues apartir de este tomando la parte del código donde
abrimos un archivo creado por nosotros donde almacenamos:
  • El numero de nodos
  • El numero de aristas
  • Las uniones de los nodos
  • El peso de las aristas
Al leer estos datos del archivo pasamos a implementarlos al BFS de tal manera que nuestro primer nodo tomaría el primer color y almacenándolo dentro de una cola después de esto pasamos a visitar a uno de los vecinos (en este caso elegí que se escogiera la arista de menor peso).

Al pasar a los vecinos a cada uno de ellos se le asignaba un color dos, y así sucesivamente a sus vecinos de nuevo el color uno y cada uno de los nodos no visitados se agregaba dentro de la cola
de manera que al final nos imprimiría el orden del recorrido (solo imprimiendo visitados) y con su respectivo color.

Si llegase a ser que mas de un nodo comparte una arista con otro del mismo color llegamos a la conclusión de que no es dos-coloreable.

Observaciones
Bueno una de las observaciones es que este código puede implementarse dentro de una detección de ciclos pues en el caso de que nuestro grafo no sea dos-coloreable indica que existe un ciclo dentro de nuestro grafo y así como para este caso sirve el decir que no es dos coloreable para una detección de ciclos diría que si existe tal.

martes, 6 de julio de 2010

Encriptación RSA

Que tal compañeros esta vez bueno me toco hacer el código de la encriptación RSA y pues bueno tengo un código que pseudo simula lo que la encartación hace (por ahora)

debido al tiempo no pude poner algunos detalles mas en el programa pero poco a poco iré cambiando el código para que quede como debería ir el bosquejo del RSA.

bueno pues presentare el código y luego explicare que hace.

-----------------------------------------------------------------------------
#include <>
#include <>
int main (int pedro,char** amanda)
{
int i;
long int n;
long int e;
long int h;
int pr1;
int pr2;
long int p[i];
long int cociente[i];
long int residuo[i];
long int h_aux;
long int q[i];
long int encrypt_op;
long int uncrypt_op;
int mensaje;
//pedimos los dos números para iniciar el proceso de encriptación

printf("introduzca 2 números primos para iniciar al encriptación\n");
printf("introduzca el primer numero primo: ");
scanf("%d",&pr1);
printf("introduzca introduzca el segundo numero primo: ");
scanf("%d",&pr2);


n = (pr1 * pr2); //se le asigna una variable extra para asignar el producto de ambos
printf("n es: %d\n",n);

h = ((pr1 - 1) * (pr2 - 1));
printf("euler es: %d\n",h);
while(1){
printf("introduce un numero entre 1 y %d que su MCD con %d sea 1:",h,h);
scanf("%d", &e);

printf("e es: %d\n",e);
if(e <> h){
printf("el numero introducido no esta en el rango inroduce otro.\n");
}else{
break;
}
}

i=0;
h_aux = h;
p[0]=0;
p[1]=1;
while(1){

cociente[i] = h / e;
residuo[i] = h - (e*cociente[i]);
h = e;
e = residuo[i];
q[i]=cociente[i];
if(i>=2){
p[i]=((p[i-2])-(p[i-1]*q[i-2])) % h_aux;

printf("el paso actual es:%d \nel cociente es %d\n",i, cociente[i]);
printf("el residuo es %d \nel inverso es %d",residuo[i], p[i]);
printf("\n");
if(residuo[i] == 1){
break;
}
i++;
}

printf("introduce el numero a convertir: ");
scanf("%d", &mensaje);
encrypt_op = (pow(mensaje,e) % n);
printf("el mensaje encriptado es %ld\n",encrypt_op);

uncrypt_op = (pow(encrypt_op,p[i]) % n);
printf("el mensaje desencriptado es: %ld\n",uncrypt_op);


}
return 8;
scanf(NULL);
}
---------------------------------------------------------------------

bien pues el programa por ahora le pide al usuario que introduzca dos números los cuales deben ser primos, despues de eso el programa le asingará a una variable n el valor del producto de estos dos

n = primo 1 * primo 2

luego se calcula un h

h = ((primo 1)-1) - ((primo 2) - 1)

despues de esto pasamos a elegir un numero primo.
el cual se encuentre entre 1 y nuestro numero h, al cual llamaremos "e" este debe ser MCD(e,h)=1.

despues pasaremos a utilizar el algoritmo extendido de euler, con el cual obtendremos un valor "d"
de tal manera manera que satisfaga la condición




acá les dejare un applet que me proporcionaron con el cual pueden obtener el inverso del numero que busquen. applet

una vez teniendo este dato podemos introducir un mensaje, el cual podemos cifrar con la forma de encriptación.

C = M^e mod n

y desencriptarlo con la formula:

M = C^d mod n

bien pues le falta todavia mucho a este programa pero por ahora creo que es la base para poder hacer el programa completo aun falta que sea una generación aleatoria de números primos al inicio y tambien de los subsecuentes "e" y "h".

pero creo que esas modificaciones seran durante los proximos dias espero les guste y me seria de gran ayuda opiniones para esas modificaciones

hasta pronto.

jueves, 1 de julio de 2010

Tipos de datos

Que tal Gente, Bueno pues esta vez vengo ha dejarles un pequeño reporte de términos sencillos de tipos de datos este reporte es el primero de otros que aremos durante este curso de verano aquí en la facultad de ingeniería mecánica eléctrica y bueno pues espero que les agrade

primero que nada pues diré que la realización de este reporte fue digamos sencilla a pesar del tiempo que teníamos pero pues pese a algunas complicaciones por parte mía se termino a tiempo

dentro de este trabajo recabé la mayor parte de información junto con datos que mis compañeros me proporcionaron.

la realización y diseño del mismo fueron por parte mía con algunos consejos de mis compañeros
y bueno creo que esta vez voy mejorando en cuanto a trabajo en equipo.

bien pues aquí les dejo la liga ha el reporte revisenlo y dejen sus comentarios acerca del mismo ya se para incluir datos que falten o para puntos de vista de ustedes mismos.

saludos.

link para ver online. enlace
link para descarga. enlace

lunes, 31 de mayo de 2010

Complejidad de funciones.

bien pues esta vez me enfoco en el problema numero 2 del primer parcial bien pues este problema decia lo siguiente:

Análisis asintótico
Encuentre una función de complejidad asintótica f(n) así que la función g(n)
definida experimentalmente por doce puntos en la siguiente tabla sea O(f(n)) (este para el martes y Ω(f(n)) para el jueves) .
Justifique esto con una gráfica y discute la calidad de la cota obtenida.

bueno primero que nada partamos sobre que nos piden entonces, si lo que nos estan pidiendo es una grafica que sea O de otra esto quiere decir que tenemos que encontrar una grafica que sea superior para f(n) esto en el caso de los martes y una cota inferior (osea Ω(f(n)).

bueno primero que nada lo que podemos hacer es ubicar la grafica que nos dan comparandola con algunas otras que nos han dado en clase antes de basealgunas de ellas y las cuales voy a usar son estas

O(1)

Orden constante

O(log n)

Orden logarítmico

O(n)

Orden lineal

O(n log n)

Orden cuasi-lineal

O(n2)

Orden cuadrático

O(n3)

Orden cúbico

O(na)

Orden polinómico

O(2n)

Orden exponencial

O(n!) ó O(nn)

Orden factorial


bien el resto del tema esta en este documento anexo debido a limitaciones que tube con la pagina.
para ver el pdf del tema haz click aqui.
para descarga aqui





jueves, 20 de mayo de 2010

Algoritmo de Shor

Que tal compañeros esta vez vengo a mostrar una pequeña introducción a un tema que me pareció interesante y trata acerca del algoritmo de shor.


¿Que es exactamente o cual es su definición?


El algoritmo de Shor es un algoritmo cuántico para descomponer en factores un número N en tiempo O((log N)3) y espacio O(log N), así nombrado por Peter Shor.

Muchas criptografías de clave pública, tales como RSA, llegarían a ser obsoletas si el algoritmo de Shor es implementado alguna vez en una computadora cuántica práctica. Un mensaje cifrado con RSA puede ser descifrado descomponiendo en factores la llave pública N, que es el producto de dos números primos.

Los algoritmos clásicos conocidos no pueden hacer esto en tiempo O((log N)k) para ningún k, así que llegan a ser rápidamente imprácticos a medida que se aumenta N. Por el contrario, el algoritmo de Shor puede romper RSA en tiempo polinómico. También se ha ampliado para atacar muchas otras criptografías públicas.

Como todos los algoritmos de computación cuántica, el algoritmo de Shor es probabilístico: da la respuesta correcta con alta probabilidad, y la probabilidad de fallo puede ser disminuida repitiendo el algoritmo.

¿Que es un computador cuántico?

La computación cuántica es un paradigma de computación distinto al de la computación clásica. Se basa en el uso de qubits en lugar de bits, y da lugar a nuevas puertas lógicas que hacen posibles nuevos algoritmos. Una misma tarea puede tener diferente complejidad en computación clásica y en computación cuántica, lo que ha dado lugar a una gran expectación, ya que algunos problemas intratables pasan a ser tratables. Mientras un computador clásico equivale a una máquina de Turing, un computador cuántico equivale a una máquina de Turing indeterminista.

El problema que intenta solucionar el algoritmo de Shor es que, dado un número entero N, intentamos encontrar otro número entero p entre 1 y N que divida N.
El algoritmo de Shor consiste en dos partes:

1. Una reducción del problema de descomponer en factores al problema de encontrar el orden, que se puede hacer en una computadora clásica.
2. Un algoritmo cuántico para solucionar el problema de encontrar el orden.

punto 1 (la parte clásica):


1. Escoja un número pseudo-aleatorio a <>
2.Compute el mcd(a, N).podemos por ejemplo usar el aglrotimo de Euclides.
#algoritmo que nos permite encontrar eficientemente el máximo común divisor.

Si el mcd(a, N) ≠ 1, entonces es un factor no trivial de N, así que terminamos.
Si no, utilice el subprograma para encontrar el período para encontrar r, el período de la función siguiente:
f(x) = a^x mod N,
es decir el número entero más pequeño r para el cual
f(x + r) = f(x).
3. Si r es impar, vaya de nuevo al paso 1.
4. Si ar/2 ≡ -1 (mod N), vaya de nuevo al paso 1.
5. Los factores de N son el mcd(ar/2 ± 1, N). Terminamos.

punto 2 subprograma para encontrar el período (parte cuántica):


1. Comience con un par de registros qubits de entrada y salida con log2N qubits cada uno, e inicialícelos a
N^{-1/2} \sum_x \left|x\right\rangle \left|0\right\rangle
donde x va de 0 a N - 1.
2. Construya f(x) como función cuántica y aplíquela al estado antedicho, para obtener
N^{-1/2} \sum_x \left|x\right\rangle \left|f(x)\right\rangle
3. Aplique la transformada de Fourier cuántica al registro de entrada. La transformada de Fourier cuántica en N puntos se define como:
U_{QFT} \left|x\right\rangle = N^{-1/2} \sum_y e^{2\pi i x y/N} \left|y\right\rangle
Lo que nos deja en el estado siguiente:
N^{-1} \sum_x \sum_y e^{2\pi i x y/N} \left|y\right\rangle \left|f(x)\right\rangle
4. Realice una medición. Obtenemos un cierto resultado y en el registro de entrada y f(x0) en el registro de salida. Puesto que f es periódica, la probabilidad de medir cierto y viene dada por

N^{-1} \left| \sum_{x:\, f(x)=f(x_0)} e^{2\pi i x y/N} \right|^2 = N^{-1} \left| \sum_{b} e^{2\pi i (x_0 + r b) y/N} \right|^2
El análisis muestra ahora que cuanto más alta es esta probabilidad, tanto más el yr/N es cercano a un número entero.

5. Convierta a y/N en una fracción irreducible, y extraiga el denominador r ', que es un candidato a r.
6. Compruebe si f(x) = f(x + r '). Si es así terminamos.
7. Si no, obtenga más candidatos a r usando valores cercanos a y, o múltiplos de r '. Si cualquier candidato cumple las condiciones, terminamos.
8. Si no, vaya de nuevo al paso 1 del subprograma.

Esto me parece algo interesante para poder empezar a investigar, por ahora solo fue la parte introductoria por la cual también en estos momentos estoy investigando; como dato les dejo algunas paginas que encontré con información acerca del tema, la mayoría de ellas en ingles pero buscare información con la cual pueda estar en español también.


Pagina con algo de contenido acerca del tema
Pagina con explicación y códigos de simulacion del mismo
Explicacion del algoritmo con datos interesantes
wikipedia: lo único que encontré por ahora en español y que se encuentra en este blog (no necesario si se lee lo de arriba)

Actualizado

aqui un pdf. con informacion del mismo en español

para verlo online haz click en este Link.

para descarga este Link.

miércoles, 19 de mayo de 2010

Proyecto # 5

Algoritmo Detección de Ciclos (Cycle Detection Algorithm)

Liebre y Tortuga (Tortoise & Hare)

Bueno compañeros hoy me toca hablar acerca de la detección de ciclos y más detalladamente acerca del algoritmo liebre tortuga Creado por Robert W. Floyd antes de entrar a este algoritmo y su explicación primero debemos saber que es la detección de ciclos.

Concepto: la detección de ciclos sirve para identificar si estos existen dentro de un grafo.

Teniendo en cuenta esto se podría deducir que nuestro algoritmo nos ayudara de alguna manera a saber si existe o no, pero ese no es lo
único que nuestro algoritmo ara y es lo que veremos a continuación.

Nuestro algoritmo toma base de una fabula en la cual una liebre y una tortuga tiene una carrera en la cual la liebre evidentemente es mas rápida que la tortuga y esta avanza primero y regresa después para burlarse de esta por su lentitud; tomando en base a esto nuestro algoritmo cambia un poco la idea y decide que la liebre regrese pero para advertir de posibles ciclos a la tortuga.

esto quiere decir que en nuestro algoritmo el papel de la liebre será la que pruebe los distintos tipos de caminos entre las opciones de una arista de manera de conseguir siempre el camino más corto esto se logra haciendo que la liebre este adelante de la tortuga.


Tal como
podemos ver en esta imagen la tortuga esta en un punto x1= 0 mientras la liebre lee el
paso siguiente e
n un punto x2 = 6 cada uno con
su respectivo valor.

Al no tener el mismo la tortuga avanza una posición y la liebre avanza dos

Podemos ver entonces que ahora la tortuga se encuentra en un estado ((x1+1) = x2) = 6 y la liebre en un estado
((x2+2)=x4) = 1 al no ser iguales los valores avanzan y repetimos la instrucción

En esta parte la tortuga se encuentra ahora en la posición((x2+1)=x3)=3 y la liebre en una posición
((x4+2)=x6)=3 al encontrarse con un mismo valor en diferentes posiciones se llega a un ciclo y es aquí donde la tortuga toma una ruta distinta en su siguiente paso no se llegase a tener












Esta sería la representación en un grafo claro este solo sería el ejemplo de que pasaría si encuentra un ciclo.















Aquí prácticamente seria repetir exactamente lo escrito arriba así que solo me limitare a decir que esto equivale al paso uno en donde se evalúa cada valor en el grafo.













En esta parte ya la tortuga ah avanzado una posición y se encuentra en 6 mientras la liebre esta en 1.



















Aquí por ultimo vemos que ambos quedaron en la misma posición en este momento el algoritmo reconoce que es un ciclo al tener la liebre y la tortuga el mismo valor por lo cual el camino resulta ineficiente para llegar a la meta indicada.

Con respecto al análisis asintótico de este algoritmo me tope con ciertas dudas dado que su complejidad en O (λ+μ) donde
λ: representa una parte de otra función ya sea f(n).
μ: está definida para todos los números naturales n y tiene valores en {-1, 0, 1} dependiendo en la factorización de n en sus factores primos. (véase este enlace para aclarar dudas)

y tomando en cuenta eso (y suponiendo que los términos estén correctos) se puede decir que la complejidad asintótica del algoritmo depende en cierta forma de la función f(n) del programa y esta a su vez seria la cual afecte a μ ya que dependerá de si f(n) es Ωf(n) pues en base a ello tomara un valor si Ωf(n) = ω(n) ó Ωf(n)>ω(n).

la complejidad computacional debería ser polinomial pues es precisamente lo que hace el algoritmo al tener dos punteros uno con el doble de velocidad que el segundo llámense "a" y "b"
"b" como primera opción siempre intentara buscar el camino más corto al punto deseado pero a su vez topara con ciclos si estos existen mientras "a" ira más lento pero llegara por la ruta más corta al evitar los caminos que se repitan recorridos por "b", y si estos no llegaran a llevar a la meta y solo se produjera un ciclo del cual no se puede salir pues el algoritmo llegaría a su fin al no llegar al punto establecido.

pseudocódigo del algoritmo
este es un pequeño pseudocódigo que encontré que muestra prácticamente lo que se dice arriba

def floyd(f, x0):
---------------------------------------------------------------------------------

# La fase principal del algoritmo,buscara una repeticion x_mu = x_2mu
# La Liebre se Mueve dos veces mas rapido que la tortuga
tortuga, liebre = f(x0), f(f(x0)) # f(x0) es el elemento ó nodo siguiente de x0.
while tortuga != liebre:
tortuga = f(tortuga)
liebre = f(f(liebre))

# encontrar la posicion de la primera repeticion de la longitud "mu"
# La tortuga y la liebre se mueven ala misma velocidad
mu = 0
tortuga, liebre = x0, tortuga
while tortuga != liebre:
tortuga = f(tortuga)
liebre = f(liebre)
mu += 1

# encontrar la longitud del cyclo mas corto empezando de x_mu
# la liebre se mueve mientras la tortuga se queda sin moverse
lam = 1
liebre = f(tortuga)
while tortuga != liebre:
tortuga = f(liebre)
lam += 1

return lam, mu

------------------------------------------------------------------------

nota: cabe recordar que los dialogos despues del simbolo "#" representan un comentario en el pseudocodigo.

hay que tener en cuenta que este código solo tiene acceso a la secuencia mediante el almacenamiento y la copia de punteros, evaluaciones de la función, y las pruebas de la igualdad, por lo que califica como un algoritmo de puntero.

Las estructuras de datos utilizadas en este algoritmo son:
listas, arreglos, punteros, funciones.

aquí incluyo un ejemplo de dicho algoritmo en un programa si desean pueden copiar el código o descargarlo directamente desde la pagina del creador en los links de la parte de abajo.
-------------------------------------------------------------------------
#include


typedef struct node_s {
void *data;
struct node_s *next;
} NODE;


int list_has_cycle(NODE *list)
{
NODE *fast=list;
while(1) {
if(!(fast=fast->next)) return 0;
if(fast==list) return 1;
if(!(fast=fast->next)) return 0;
if(fast==list) return 1;
list=list->next;
}
return 0;
}


int main()
{
NODE n1, n2, n3, n4, n5;

n1.next=&n2;
n2.next=&n3;
n3.next=&n4;
n4.next=&n5;
n5.next=NULL;

printf("Test without cycle: ");
if(list_has_cycle(&n1)) printf("cycle\n");
else printf("no cycle\n");


n5.next=&n3;

printf("Test with cycle: ");
if(list_has_cycle(&n1)) printf("cycle\n");
else printf("no cycle\n");

return 0;
-------------------------------------------------------------------
dentro del código podemos ver que si los nodos n siguen su paso hasta un estado n5 = NULL se logra llegar al estado deseado por lo tanto no hay un ciclo en el transcurso pero si cambiásemos dicha ruta por una ya escrita tal como se ve en la línea donde n5=&n3 regresamos de nueva cuenta hacia n3 donde este toma el valor de n4 y así sucesivamente es por eso que utilizamos nuestra función list_has_cycle para que en la decisión imprima si existe o no un ciclo.


Detección de ciclos (explicación en ingles)

Biografía del Autor de Dicho algoritmo
Pagina web de apoyo para mi reporte
Otra web de apoyo.
*me falto anexar algunos archivos pdf de los cuales base la investigacion que subire en estos dias para que tmb pase a revisarlos.


domingo, 25 de abril de 2010

Proyecto #4

En este proyecto fue completamente distinta la forma en la que trabajamos debido a que fuimos menos integrantes y al conocimiento que teníamos acerca del tema afortunadamente tuvimos el suficiente tiempo para corregir esos detalles

Mi papel en este proyecto fue practicamente de ayudante puesto que no soy muy bueno dirigiendo preferí el papel de acatar las ordenes que se me dieron y por mi parte buscar información que pudiese servir para el desarrollo de nuestra presentación, me encontré con unas buenas aplicaciones interactivas con las cuales se puede apreciar dicho algoritmo

Principalmente me fallo la planeacion debido a que dejamos todo hasta el final sin embargo creo que nos salio muy bien a pesar de todo, dentro de la coordinación irónicamente creo que trabajamos mejor bajo presión.

Como reflexion y para terminar creo que no debería dejar para el ultimo dicho trabajo y pues tomármela con mas calma.

Les invito a que revisen nuestra presentacion
Descarga
Vista Online

Acá les dejo el link de una buena animación para que puedan ver como funciona el algoritmo también viene para otros tipos y puedan ver las diferencias entre cada uno de ellos
Animación

Seguidores