martes, 18 de mayo de 2010

Proyecto 5

Coloreo de Grafos.

Coloreo de Grafos es la coloración de los vértices de un grafo tal que ningún vértice adyacente comparta el mismo color.

Similarmente, una arista coloración asigna colores a cada arista tal que aristas adyacentes no compartan el mismo color, y una coloración de caras de un grafo plano a la asignación de un color a cada cara o región tal que caras que compartan una frontera común tengan colores diferentes.

El primer resultado acerca de la coloración de grafos trataba exclusivamente sobre grafos planos y la coloración de mapas. Mientras intentaba colorear un mapa de Inglaterra, Francis Guthrie postulo la teoría de los 4 colores, notando que 4 colores son suficientes para colorear el mapa tal que regiones que comparten un borde común no reciban el mismo color.



Las etiquetas como rojo o azul son solamente utilizadas cuando el número de colores es pequeño, y normalmente los colores están representados por los enteros {1, 2, 3, …}.

Una coloración que usa a lo más k colores se llama k-coloración (propia). El menor número de colores necesarios para colorear un grafo G se denota número cromático . Un grafo que puede ser asignada una k-coloración (propia) es k-coloreable y es k-cromático si su número cromático es exactamente k. Un subconjunto de vértices asignados con el mismo color se llama una clase de color. Cada clase forma un conjunto independiente. Esto es, una k-coloración es lo mismo que una partición del conjunto de vértices en k conjuntos independientes, y los términos k-partito y k-coloreable tienen el mismo significado.

El polinomio cromático cuenta el número de maneras en las cuales puede ser coloreado un grafo usando no más que un número de colores dado

Un algoritmo simple para colorear gráfico es fácil de describir, pero potencialmente muy costosa.
En términos de complejidad computacional - NP-completo Lo que eso significa que no existe algoritmo conocido para colorear gráfica óptima que no es exponencial, y que, además, si hubiera un algoritmo no-exponencial para ella, no sería una solución no-exponencial de todos problemas.

Una solución general a la búsqueda de una coloración gráfica óptimo es la búsqueda exhaustiva: empezar con un nodo, dale un color, asignar colores que no sean contradictorias con sus vecinos, y así sucesivamente. Prueba con dos colores, si no se obtiene ningún resultado, a continuación, intente con tres, y así sucesivamente.



Ejemplos de coloreo de grafos:


Grafo de Petersen con 3 colores; comúnmente dibujado como un pentágono con una estrella de cinco puntas adentro:




---------





----------


Bibliografia.


http://es.wikipedia.org/wiki/Coloraci%C3%B3n_de_grafos


http://scienceblogs.com/goodmath/2007/06/graph_coloring_algorithms_1.php

http://www.google.com.mx/images?hl=es&gbv=2&tbs=isch%3A1&sa=1&q=coloreo+de+grafos&aq=f&aqi=&aql=&oq=&gs_rfai=

sábado, 8 de mayo de 2010

Problema -Puntos Extra-

Máquina de Turing

Siendo la representación binaria del número 37; ejecutaremos la Máquina de Turing, siguiendo la función de transición dada.

37: 100101





Bien, iniciemos nuestra máquina...

Vemos que la máquina empieza en un estado S.


Enseguida asigna un 0 al inicio, y avanza un espacio a la derecha.



Al pasar a la siguiente posición, se encuentra un 1, y escribe un 1, y avanza un espacio a la derecha.

Al estar un 0 en las siguientes dos posiciones, en cada una de ellas escribe un cero y avanza un espacio a la derecha.


En la siguiente posición hay un 1, escribe un 1 y avanza un espacio a la derecha.


Ahora vemos un 0, escribe 0, y avanza un espacio a la derecha.


Le sigue un 1, y al igual que las demás posiciones escribe un 1, y avanza un lugar a la derecha.


En este momento se encuentra con un espacio vacío.


Entonces la máquina escribe un cero.

Y avanza un espacio, ahora hacia la izquierda, volviendose en un estado T, y al estar en un 1, escribe 1, y avanza un espacio a la izquierda.


Al encontrar el primer cero escribe un 1, imprime SI, y termina.



Entonces nos queda el siguiente número binario: 01001110

que es el número 78.

domingo, 25 de abril de 2010

Proyecto 4

Para el Proyecto 4, mis compañeros(Klaudia Lozano, Gerard Ossio y Gustavo Chavana) y yo elegimos el tema de PILAS.

--Qué hice yo
Al igual que mis compañeros, me puse a buscar información general del tema, para así poder comprenderlo, y al ya haberlo comprendido, me puse a buscar información sobre el pseudocódigo.

--Cómo me salió
No soy muy buena con los pseudocódigos, pero me informé de cómo usalo, y así se me facilitó más el trabajo.

--En qué aspectos estoy bien y en qué me hace falta mejorar.
Me sé informar sobre la parte del tema que me toca dar, sin embargo debería mejorar la forma en la que yo expreso mis ideas, para así poder dar una clase, y que todos entiendan lo que estoy explicando.

--Ayudo a los demás o me apoyo en ellos.
Al igual que mis compañeros, me ayudaron con el pseudocódigo, yo también les ayudo sobre temas que yo tenga conocimiento, y como somos un equipo, todos nos ayudamos entre sí.

--Quién se encarga de coordinar el trabajo.
Ya hemos trabajado anteriormente en equipo, y generalmente todos somos los que ponemos de nuestra parte para coordinar todo, y que todo salga bien, pero en esta ocación, mis compañeros Gustavo y Gerardo fueron los que dieron el primer paso para empezar el proyecto.

--Qué papel tomo yo.
Una integrante del equipo, que toma las mismas responsabilidades que los demás, para así poder hacer un buen trabajo digno de presentar.

domingo, 21 de marzo de 2010

Proyecto 3: Serie Fibonacci

Qué es recursión?
En programación es una herramienta que nos sirve para llamar a una función dentro de una función.

Qué es iteración?
Es cuando tienes que repetir una acción un cierto número de veces.

Cuando usar la recursión?
Cuando hay que resolver problemas muy complejos que pueden dividirse a su vez en varios pasos y que no es posible resolver por iteración.

Para que se utiliza?
Un ejemplo de esto es para resolver problemas que tengan que ver con el factorial de un número o en juegos de lógica.

*Factorial:
http://ce.azc.uam.mx/profesores/franz/omi/recursion2.html



En esta ocación nosotros elegimos la Serie de Fibonacci que es un ejemplo claro de problemas que se pueden resolver por Iteración.

/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\

Trabajo en Equipo.

¿Como trabajaron como equipo?

Nos comunicamos vía mail, ya que no nos pusimos deacuerdo para vernos en algun lugar específico, entonces en cierta forma fué más fácil para todos, por que así podíamos buscar información por separado.


Qué fué tu contribución al trabajo?

Me enfoqué a buscar información general sobre la Serie Fibonacci.


Como comparar lo que hiciste tú, con el trabajo de los demás?

Cada uno de nosotros trató de aportar información lo más que pudo, cada quien daba su propia opinión, y mediante un debate, llegamos a juntar toda la información necesaria para la Presentacion Grupal.


Qué podrías mejorar en el futuro?

Trataría de que nos pusieramos deacuerdo con más anticipación, ya que en esta ocación no lo hicimos, pues creo que nos confiamos por que la fecha de entrega se había cambiado.


Mis compañeros de equipo:

Klaudia Lozano

Gerardo Ossio

Gustavo Chavana


Presentación Grupal. Serie Fibonacci.

Serie Fibonacci



viernes, 5 de marzo de 2010

Proyecto 2

Problema Jeep (Exploration Problem)


Descripción
Maximizar la distancia de un Jeep puede penetrar en el desierto con una cantidad dada de combustible. El jeep se le permite ir hacia adelante, descargar un poco de combustible, y luego regresar a su base con el combustible restante en el tanque. En su base, se puede repostar combustible y partir de nuevo. Cuando llega el combustible que ha guardado anteriormente, entonces se pueden utilizar para llenar parcialmente su tanque.

Problema
Hay n unidades de combustible almacenado en una base fija. El jeep se puede llevar a lo más 1 unidad de combustible en cualquier momento, y puede viajar 1 unidad de distancia en 1 unidad de combustible (el consumo de combustible del jeep se supone que es constante). En cualquier punto en un viaje del jeep puede salir de cualquier cantidad de combustible que está realizando en un vertedero de combustible, o puede recoger cualquier cantidad de combustible que quedaba en un vertedero de combustible en un viaje anterior, siempre y cuando su carga de combustible en ningún caso exceda 1 unidad.

Hay dos variantes del problema:
Explorando el desierto - El jeep debe regresar a la base al final de cada viaje.
Atravesando el desierto - El jeep tiene que volver a la base al final de cada viaje, salvo para el viaje final, cuando el jeep viaja tan lejos como pueda antes de quedarse sin combustible.

En cualquier caso el objetivo es maximizar la distancia recorrida por el jeep en su viaje final. Alternativamente, el objetivo puede ser encontrar la menor cantidad de combustible necesario para producir un viaje de final de una distancia determinada.

En el clásico problema del combustible en el jeep y en los vertederos de combustible es tratado como un continua cantidad. Más complejas variaciones en el problema han sido propuestos en los que el combustible sólo puede ser la izquierda o recogidos en cantidades discretas.


Solución

Una estrategia que aproveche al máximo la distancia recorrida en el viaje de final de la "variante de explorar el desierto" es el siguiente:

• En cada viaje se inicia desde la base con 1 unidad de combustible.
• En el primer viaje del jeep recorre una distancia de 1 / (2n) Las unidades y las hojas (n- 1) /n unidades de combustible en un vertedero de combustible. El jeep todavía tiene 1 / (2n) Unidades de combustible - sólo lo suficiente para regresar a la base.
• En cada uno de los siguientes n- 1 recoge los viajes del jeep 1 / (2n) Unidades de combustible a partir de esta primera descarga de combustible a la salida, por lo que sale de la descarga de combustible de 1 unidad de transporte de combustible. También recoge la 1 / (2n) Unidades de combustible a partir de esta primera descarga de combustible en el camino de regreso, que es justo lo suficiente combustible para regresar a la base.
• En el segundo viaje el jeep viaja a la descarga y recarga las pilas de combustible primero. A continuación, recorre una distancia de 1 / (2n- 2) unidades y las hojas (n- 2) / (n- 1) unidades de combustible en un vertedero de combustible segundo. El jeep todavía tiene 1 / (2n- 2) unidades de combustible, que es justo lo suficiente para regresar a la descarga de combustible en primer lugar. Aquí se recopila 1 / (2n) Unidades de combustible, que es justo lo suficiente combustible para regresar a la base.
• En cada uno de los siguientes n- 2 viajes del jeep recoge 1 / (2n- 2) unidades de combustible de este combustible segundo volcado a la salida, por lo que sale de la descarga de combustible de 1 unidad de transporte de combustible. También recoge la 1 / (2n- 2) unidades de combustible de la segunda descarga de combustible en el camino de regreso, que es justo lo suficiente combustible para regresar a la descarga de combustible en primer lugar.
• El jeep sigue de esta manera, de modo que en el viaje k que establece un nuevo k de combustible o volcado a una distancia de 1 / (2n- 2k+ 2) unidades de la descarga de combustible anterior y las hojas (n--k) / (n--k+ 1) unidades de combustible allí. En cada uno de los siguientes n--k los viajes que recopila 1 / (2n- 2k+ 2) unidades de combustible de la k descarga o en su salida y otro 1 / (2n- 2k+ 2) unidades de combustible en su camino de regreso.





Solución a "explorar el desierto" variante de n= 3, mostrando el contenido de combustible del jeep y los depósitos de combustible al comienzo de cada viaje y en el punto de rotación de los buques en cada viaje.






Cuando el jeep se inicia su último viaje, hay n- 1 vertederos de combustible. El más lejano contiene 1 / 2 de una unidad de combustible, el siguiente más alejado contienen 1 / 3 de una unidad de combustible, y así sucesivamente, y el basurero más cercano combustible tiene apenas 1 /n unidades de combustible a la izquierda. Junto con 1 unidad de combustible con la que se inicia desde la base, esto significa que el jeep se puede recorrer una distancia total de ida y vuelta de la de unidades en su último viaje (la máxima distancia recorrida en el desierto es la mitad de este).
Se recoge la mitad del combustible restante en cada uno de volcado a la salida, lo que llena su tanque. Después de dejar el más alejado de combustible volcado viaja a 1 / 2 de una unidad más en el desierto y luego regresa a la basura más alejado de combustible. Se acumula el combustible restante de cada descarga de combustible en el camino de regreso, que es justo lo suficiente para llegar a la siguiente o la descarga de combustible, en la etapa final, para regresar a la base.

La distancia recorrida en el último viaje es el no número de armónicos [1] , Hn. Como no están acotadas en los números armónicos, es posible superar cualquier distancia en el viaje final, como a lo largo de suficiente combustible está disponible en la base. Sin embargo, la cantidad de combustible necesario y el número de depósitos de combustible, tanto aumentar de forma exponencial con la distancia que debe recorrerse.

La "travesía del desierto" variante se pueden resolver con una estrategia similar, excepto que ya no hay ninguna obligación de recoger el combustible en el camino de regreso en el viaje final. Así que en el viaje k el jeep se establece un nuevo k de combustible o volcado a una distancia de 1 / (2n- 2k+ 1) unidades de la descarga de combustible y las hojas anteriores (2n- 2k- 1) / (2n- 2k+ 1) unidades de combustible allí. En cada uno de los próximos n--k- 1 viaje que recopila 1 / (2n- 2k+ 1) unidades de combustible de la k descarga o en su salida y otro 1 / (2n- 2k+ 1) unidades de combustible en su camino de regreso.

Ahora, cuando el jeep se inicia su último viaje, hay n- 1 vertederos de combustible. El más lejano contiene 1 / 3 de una unidad de combustible, el siguiente más lejos contener 1 / 5 de una unidad de combustible, y así sucesivamente, y el basurero más cercano de combustible acaba de 1 / (2n- 1) unidades de combustible a la izquierda. Junto con 1 unidad de combustible con la que se inicia desde la base, esto significa que el jeep se puede recorrer una distancia total de la de unidades en su viaje final. Recoge todo el combustible restante en cada uno de volcado a la salida, lo que llena su tanque. Después de dejar el más alejado de combustible volcado viaja una distancia mayor de 1 unidad.

Tenga en cuenta que lo que es posible en teoría, cruzar un desierto de cualquier tamaño dado suficiente combustible en la base. Como antes, la cantidad de combustible necesario y el número de depósitos de combustible, tanto aumentar de forma exponencial con la distancia que debe recorrerse.

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

Ln Máxima distancia Alcanzada, n combustible

Referencias

[1] http://en.wikipedia.org/wiki/Harmonic_number

http://mathworld.wolfram.com/JeepProblem.html

http://en.wikipedia.org/wiki/Jeep_problem


http://page.mi.fu-berlin.de/rote/Papers/pdf/Optimal+logistics+for+expeditions+-+the+jeep+problem+with+complete+refilling.pdf


viernes, 19 de febrero de 2010

Proyecto 1. Guía Telefónica.

Para nuestro primer proyecto, mi compañero Gustavo Chavana y yo, decidimos hacer el programa "Guía Telefónica", la cual nos premitirá buscar el número telefónico al insertar la letra inicial del apellido, después nustro programa nos dará varias opciones numeradas, que al insertar el número de la opción nos va a desplegar otra lista, la cuál contiene todos los nombres en común, y ahí se almacena en número de la persona que estamos buscando.

Aquí está parte del diagrama de flujo que utilizamos para luego hacer el programa.


Enseguida les dejo el programa que hicimos en Dev c++, e iré explicandoles brevemente lo que estamos haciendo.

En este caso buscaremos el numero telefónico de Garza de Leon Ricardo Francisco.


#include
#include

int x=0;

int main()
{
int letra;
system ("CLS");
printf("\t\t Directorio de Monterrey\n\n");


/*Aqui empezamos a correr nuestro programa, el primer paso es elegir una letra, en el ejemplo que nosotros pusimos, como recordaremos vamos a buscar el nombre de Garza Leon Ricardo Fransisco, así que al ejecutar el programa empezaremos por introducir el numero 7, que corresponde a la letra G, que es la primera letra del apellido en cuestión*/
printf("Elija una de las siguientes letras para empezar a buscar\n\n");



printf("A=1\tE=5\tI=9\tM=13\tP=17\tT=21\tX=25\nB=2\tF=6\tJ=10\tN=14\tQ=18\tU=22\tY=26\nC=3\tG=7\tK=11\tÑ=15\tR=19\tV=23\tZ=27\nD=4\tH=8\tL=12\tO=16\tS=20\tW=24\n\nopcion:");
scanf ("%d", &letra);

switch(letra)
{
case 1:
printf("\n\nUsted Selecciono la letra A para empzar a buscar, elija uno\n de los suguientes Apellidos:\n1=Avendaño\n\nopcion:");

scanf("%d", &letra);
if (x=1){
printf ("\n\nA seleccionado el apellido Avendaño, hubo una coincidencia de 5 Nombres, elija una opcion\n\n");
printf ("1=Alejandro Avendaño \n\n opcion:");
scanf ("%d", &letra);

if(x=1){
printf("\nEl numero de Alejadro Avendaño es 87674535");
}
}

case 7:
printf("\n\nUsted Selecciono la letra G para empzar a buscar, elija uno\nde los suguientes Apellidos:\n\n1=Galvan\t6=Gorrion\n2=Garcia\t7=Guitierrez\n3=Garza\n4=Guevara\n5=Guerra\n\nopcion:");


/*Al haber insertado el numero correspondiente a la letra "G", nos aparece una lista de apellidos, la cuál también está enumerada de la misma forma que con las letras, ahora tenemos que elegir uno de los apellidos, para que así nos despliegue otra lista, la cual contiene el nombre de todas las personas que coinciden en el apellido, ahora teclearemos el numero 3, el cual contiene el apellido Garza*/

scanf("%d", &letra);
if (x=3){
printf ("\n\nA seleccionado el apellido Garza, hubo una coincidencia de 22 Apellidos\ncompuestos, elija una opcion\n\n");
printf ("1=Garza Alvarado\n2=Garza Alvarez\n3=Garza Arellano\n4=Garza Barba\n6=Garza Barreda\n7=Garza Benavides\n8=Garza Blasques\n9=Garza Buentello\n10=Garza Castillo Martha\n11=Garza Cavazos\n12=Garza Casares\n13=Garza Cantu\n14=Garza Garza\n15=Garza de Leon\n16=Garza Delgado\n17=Garza Maldonado\n18=Garza Rodriguez\n19=Garza Salinas\n20=Garza Villarreal\n21=Garza Zamora\n22=Garza Zapata\n\nopcion:");
scanf ("%d", &letra);


/*Por último elegiremos de la lista enumerada, el nombre que coincida a el de la persona que estamos buscando, en este caso es el número 15 que corresponde a Garza de León, y al teclear esto nos sale una lista la cual contiene el nombre y el numero de las personas que tienen como apellido Garza de León, ahí encontraremos el que nosotros estamos buscando, que es Garza de León Ricardo Fransisco. */



if(x=15){
printf("\nHubo 12 coincidencias\n\n");
printf("Garza de Leon Eustolia\t\t83588512\nGarza de Leon Adrian\t\t83608647\nGarza de Leon Diana\t\t83492749\nGarza de Leon Hilda Gloria\t81340204\nGarza de Leon Jose Angel\t83101866\nGarza de Leon Jose Regino\t83262824\nGarza de Leon Marcelino\t\t83820750\nGarza de Leon Ramon Gerardo\t83144447\nGarza de Leon Ricardo Francisco\t83430367\nGarza de Leon Romulo\t\t83797724\nGarza de Leon Silvia\t\t83347144\nGarza de Leon Yolanda\t\t83350393");

}
getche ();
}



En nuestro segundo caso estamos buscando el teléfono de Viramontes Romo Jose Luis.

De igual forma que en el primer caso, primero vamos a introducir el numero de la letra inicial del apellido, que es el 23, correspondiente a la letra V, enseguida de la lista que nos aparece eligiremos el 10, que corresponde al apellido Viramontes, después teclearemos el numero 6, que es el que nos llevará a la lista que contiene a las personas con apellido Viramontes Romo, y de ahí obtendremos el numero de Jose Luis Viramontes Romo, el cual su teléfono es 83774291


#include
#include

int x=0;

int main()
{
int letra;
system ("CLS");
printf("\t\t Directorio de Monterrey\n\n");
printf("Elija una de las siguientes letras para empezar a buscar\n\n");
printf("A=1\tE=5\tI=9\tM=13\tP=17\tT=21\tX=25\nB=2\tF=6\tJ=10\tN=14\tQ=18\tU=22\tY=26\nC=3\tG=7\tK=11\tÑ=15\tR=19\tV=23\tZ=27\nD=4\tH=8\tL=12\tO=16\tS=20\tW=24\n\nopcion:");
scanf ("%d", &letra);

switch(letra)
{

case 23:
printf("\n\nUsted Selecciono la letra V para empezar a buscar, elija uno\nde los suguientes Apellidos:\n\n");
printf("1=Valles\n2=Vara\n3=Varela\n4=Vargas\n5=Vazquez\n6=Velasco\n7=Viera\n8=Villanueva\n10=Viramontes\n11=Vota\n\nopcion:");

scanf("%d", &letra);
if (x=10){
printf ("\n\nA seleccionado el apellido Viramontes, hubo una coincidencia de 8 Apellidos\nCompuestos, elija una opcion\n\n");
printf ("1=Viramontes Brown\n2=Viramontes Flores\n3=Viramontes Fuentes\n4=Viramontes Garcia\n5=Viramontes Gutierrez\n6=Viramontes Romo\n7=Viramontes Sierra\n8=Viramontes Velazquez\n\n opcion:");
scanf ("%d", &letra);

if(x=6){
printf("\nHubo 4 coincidencias\n");
printf ("Viramontes Romo Jesus\t\t83431255\nViramontes Romo Jose Luis\t83774291\nViramontes Romo Maria Eugenia\t83343068\nViramontes Romo Silvia\t\t83772352");
}
}


}
getche ();
}

lunes, 15 de febrero de 2010

Promedio.

Bueno, aqui les dejo un pequeño programa que hicimos en la clase de Lenguaje ANSI-C

Descripción del programa:
Al recibir como dato el promedio de un alumno, en un curso, escriba "Aprobado" en caso de que el promedio sea satisfactorio, es decir mayor o igual a 7.

#include
main(){
int x;
printf("Ingresa el promedio");
scanf("%d", &x);

if ( x >= 7){
printf("Aprobado");
printf("\n¡Felicidades!");
}

else {
printf("Reprobado");
printf("\nEchale mas ganas");
}

getch();
}


Y como podemos ver, lo fuimos modificando y pusimos la condición de que si la calificación no era igual o mayor a 7 , entonces se imprimiría "Reprobado", y un mensaje alentador "Echale mas ganas!".

jueves, 4 de febrero de 2010

Expresiones Boleanas

Definicion:

El álgebra booleana es un sistema cerrado formado por un conjunto P de dos o más elementos que pueden tomar dos valores perfectamente diferenciados ( o - 1, V - F , Abierto - Cerrado, etc.) y dos operaciones binarias suma (+), y producto (*)


Para más info --> http://www.mitecnologico.com/Main/ExpresionesBooleanas



Y aqui les dejo un ejemplo de una expresión Booleana que yo hice.





jueves, 21 de enero de 2010

2do Semestre.

Uff! ya casi 3 semanas de haber entrado a 2° semestre!
No soy fan de la estudiar, pero de verdad que ya tenia ganas de regresar a clases jeje, y aun que no me gusta estar ahi en la facu todo el dia, ahi estoy hasta los sabados :(

Lo mejor es que el primer día todos te preguntaron en que salones te tocó, con que profes, y tu siempre dijiste que no te gustó tu horario jajaja. Todas las personas que conozco eso me dijeron, que no les gustó su horario, hasta que se enteraron de cual era mi horario, ya no dijeron nada, y por si tu también eres de los que se sigue quejando de su horario.. ahí te va el mio jojo.. es M1, V5 y V4, esto es los lunes, miércoles y viernes!. Ok, ya no te puedes quejar jaja!!

En fin.. nunca había tenido un blog, y siempre me dije a mi misma "Chio no vayas a hacer un blog, no queremos que te envicies como alguna vez lo hiciste con el Fotolog y Facebook" y pues nimodo aqui estoy/estamos.
Espero que si me llego a enviciar, sirva de algo...

Y pues aqui les dejo mi blog, para cuando quieran, si tienen alguna duda comentario, etc. =)
Saludos! :D