Etiquetas

domingo, 16 de mayo de 2010

PROYECTO 5 - Problema del Viajante

~PROBLEMA DEL VIAJANTE~
~TPS~
Éste problema consiste en encontrar un recorrido de longitud mínima para un viajante que tiene que visitar varias ciudades y volver al punto de partida, conocida la distancia entre las ciudades.

Éste problema, también conocido como el Problema del viajante de comercio, es uno de los problemas de optimización más famosos en el campo computacional; aparentemente su solución es muy sencilla, pero es desde el punto de vista práctico, desde el punto de vista teórico, las técnicas empleadas para su solucion, son solo aproximaciones, tal es el caso que muchos algoritmos clásicos no son capaces de resolver el problema, debido a todas combinaciones posibles para su solucion.
Por ello se han aplicado distintas técnicas computacionales como : heuríticas evolutivas y redes de Hopfield, solo por mencionar algunas.



*Planteamiento del problema



Sean N ciudades de un territorio, el objetivo es encontrar una ruta que, comenzando y terminando en una ciudad concreta y que pase una sola vez por una de las ciudades y minimice la distancia recorrida por el viajante.
La distancia entre cada ciudad viene dada por la matriz D: N*N, donde d[x,y], representa la distancia que hay entre la ciudad x y la ciudad y.


*Complejidad Computacional

El problema TSP, está entre los problemas de complejidad Np-Completos, esto es los problemas que no se pueden resolver en tiempo polinomial en funcion del tamaño de la entrada, en éste caso N es el numero de ciudades a visitar por el viajante.




*Pseudocódigo del algoritmo
//Problema del viajante usando heurística voraz
método viajanteVoraz(Grafo g)
Lista ciudades por visitar=g.listadeNodos()
c=ciudadesporVisitar.extraePrimera()
Lista= itinerario = {c}
mientras ciudades por visitar no esté vacía
hacer cprox= ciudad más próxima a c en ciudadesporVisitar
//elimina la más próxima de la lista a visitar
// y la añade al itinerario
ciudadesporVisitar.extrae(cprox)
itinerario.añadeAlFinal(cprox)
c=cprox //cprox pasa a ser la ciudad actual
fhacer
//vuelve al comienzo
itinerario.añadeAlFinal(itinerario.primera())
fmétodo





*Análisis Asintótico

Para encontrar la solucion mas óptima, éste algoritmo crece de forma exponencial con la entrada del problema, que en éste caso, sería el numero de nodos o vértices, que son las ciudades a visitar.
Por lo tanto, cuanto mayor sea el numero de nodos, mayor va a ser el numero de rutas posibles y por consiguiente mayor será el esfuerzo requerido todas ellas.
* Así que el análsis asintótico es N^2


*Estructuras de datos utilizadas




Para este algoritmo la estructura utilizada es el de 'GRÁFO'

Un grafo es un conjunto de objetos llamados vértices o nodos, unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias, entre elementos de un conjunto.







*EJEMPLO

~Compañia de teléfono~

Elegir una ruta que deben seguir los recolectores de dinero de cabinas públicas instaladas en una ciudad.


Cinco cabinas de teléfonos b,c,d,e,f, para las que se conocen sus coordenadas relativas a la central teléfonica 'a' desde la que reparten los recolectores y a donde deben regresar al terminar, y se supone que la distancia entre cada dos puntos viene dado por una línea recta.






Éste ejemplo lo solucioné por el método de Heurística Voraz


Consiste en ir seleccionando parejas de puntos que serán visitados de forma consecutiva:

*Se seleccionará primero aquella pareja entre los que la distancia sea minima
*Se seleccionará la siguiente pareja separada con una distancia minima, siempre y cuando ...
1. No se visite un punto dos veces o más
2. No se cierre el recorrido, antes de visitar todos los puntos



En este ejemplo, las parejas ordenadas son ...



Y los pasos a seguir son ...




Y al terminar éstos pasos, el resultado es ...






Éste recorrido no es el más óptimo, pues su longitud es de 50 unidades, es el cuarto mejor recorrido de entre los sesenta posibles y es más costoso que el óptimo en un 3.3%






*Aplicaciones




El problema tiene considerables aplicaciones prácticas, aparte de las de lógista de logística de transporte, que cualquier negocio de reparto, grande o chico, conoce. Por ejemplo en robótica, permite resolver problemas de fabricacion para minimizar el numero de desplazamientos al realizar una serie de perforaciones en una plancha o en un circuito impreso. Tambien puede ser usado en el control optimizado de semáforos.





*Presetación



Presentacion
Bibliografia1
Bibliografía2
Bibliografía3

Bibliografia4






domingo, 25 de abril de 2010

PROYECTO 4 - Bubble Sort

Ordenamiento de Burbuja (BUBBLE SORT)
para listas enlazadas


Para este proyecto elegimos el tema de Bubble sort, es decir un algoritmo de ordenamiento.

TRABAJO EN EL EQUIPO....

Entre todas unificamos el trabajo, pero en lo que colaboré mas fue en la realización de la presentación , es decir, darle formato y buscar información adicional.
Para mi gusto, lo que hice me salió bien y creo que es entendible para las demás personas.


ASPECTOS EN LOS QUE...

Estoy bien ...
Entendí el tema completamente, ya sé como funciona éste tipo de ordenamiento.

Me hace falta mejorar ...
no encuentro algo en específico en lo que pueda decir que deba mejorar , pero lo que si reconosco es que siempre se puede y debe mejorar,en lo personal, en este proyecto me gusto la contribución que hice que es la principal prioridad.


AYUDO O ME AYUDAN ?

Es imposible decidir cual de los dos, aunque la mayoría del tiempo ayudo, también he necesitado de ayuda en algo, en éste tema no tanto, pues es uno muy fácil de enteder. Además siempre me gusta saber lo que estoy haciendo y sacar adelante el tema como mejor sea posible.
Pero aveces hay algunos compañeros que se 'cuelgan' del trabajo de personas como yo, no quiero decir que mi trabajo sea el mejor ni mucho menos, sino que me gusta cumplir con lo que me toca, para mí la responsabilidad es ante todo.


COORDINACION DEL TRABAJO ...

En la coordinación del trabajo hice un buen trabajo, mi compañera Gaby y Yo empezamos con la eleccion del tema, aunque al principio fue otro, y cuando lo cambiamos, a los demas compañeros les parecio bien lo que hicimos.


Liga a la presentación

http://www.slideshare.net/agatapato/bubble-sort-algcomp

Ligas de mis compañeras

Gabriela Alemán

Dora Nelly González

domingo, 21 de marzo de 2010

PROYECTO 3 - Palíndromos

PALINDROMOS

En este proyecto ecogimos el tema sobre los palindromos

Un palindromo es una palabra, número o frase que se lee igual hacia adelante que hacia atrás, como por ejemplo, oso, reconocer, etc.

En el proyecto lo que se queria analizar es lo recursivo y lo iterativo.

RECURSIVO
La recursividad es cuando una funcion se llama a sí misma
Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva

ITERATIVO
Iteración se refiere a la acción de repetir una serie de pasos un cierto número de veces.

Es conveniente usar el recursivo cuando se requiera que un procedimiento se repita varias veces hasta que cumpla una condición dada y ejecute cierta acción o proceso.

Un ejemplo muy comun es la serie de Fibonacci y como es en nuestro caso los PALINDROMOS.



TRABAJO EN EQUIPO
Como nuestro equipo consto de 4 integrantes, optamos por repartirnos el problema en dos, es decir dos compañeros se encargaron de resolverlo en forma recursiva y mi compañera y yo lo hicimos de forma iterativa. Y así despues nos pasamos mutuamente las partes hechas y al final juntamos todo e hicimos varios ajustes a la presentacion.

Aun así pienso que si nos hubieramos juntado todos habria estado mejor el trabajo, pero desde mi punto de vista, el trabajo esta bien.

CONTRIBUCION AL TRABAJO
Lo que yo hise en este proyecto fue junto con mi compañera Gabriela, hacer la parte iterativa y tambien en la presentacion, juntando lo que cada quien hiso y dandole los ultimos detalles para poder subirla a la web.

COMPARACIÓN
Se me es dificil este punto, pues no podria dar una comparacion justa, ya que yo hise algunas cosas que otros no hicieron, pero otros hicieron cosas que yo no hice. Es decir, en algunos aspectos mis compañeros tienen mejor vision y comprension que yo y en ellos me base y viseversa, asi que creo que nos complementamos bien y lo que hicimos fue en su mayoria 'parejo'.

MEJORAR EN EL FUTURO
Creo que lo que tendria que mejorar seria organizar bien los tiempos y no dejarlo todo casi al ultimo, aunque si cumplo con la fecha y hora establecida, creo que seria mejor y con menos presion si lo hacemos con tiempo, ya sea en equipo o individual.



Estos son los blogs de mis compañeros
Gabriela Aleman
Salomon Karr
Hector Tinajero


Y esta es nuestra presentacion:



http://www.slideshare.net/danielaaguilar/palindromos

jueves, 4 de marzo de 2010

PROYECTO 2 - Optimización multicriterio de ingredientes

Optimización multicriterio de ingredientes


(multiobjective ingredient optimization)



La combinación de ingredientes mas barata, durable y ecológica para una pintura de exteriores




Para éste problema supuse el siguiente problema de decisión:


Teniendo K cantidad de combinaciones,
¿Existe una combinación de ingredientes más económica, durable y ecológica para una pintura de exteriores?


EJEMPLO
Supongamos que el Sr. Gutiérrez quiere pintar el exterior de su casa, pero ahora quiere hacer una buena compra, ya que la pintura que tiene su casa se desgasto rápidamente y fue muy cara; pero al mismo tiempo no quiere dañar el ambiente con pinturas que contengan plomo u otro componente dañino al ambiente. Así que va a ‘Home Depot’ a investigar sobre las pinturas de exteriores.
El Sr. Gutiérrez cuenta con un presupuesto $500.00 y esta dispuesto a gastar un 25% más.

Y al leer las etiquetas ve que la mayoría de las pinturas tiene como componentes pigmentos (color), resinas (protección) , aglutinantes y diluyentes.


Las variantes o criterios en este problema de optimización son
*Economico
*Durable
*Ecológico


Estas son las posibles combinaciones que yo tome en cuenta
Combinación 1
Pigmento
Resina ------------------>Daña un 10 % - Dura 5 años – Precio $350
Aglutinante
Diluyente

Combinación 2
Pigmento
Resina ----------------->Daña un 5 % - Dura 8 años – Precio $600
Aglutinante
Diluyente

Combinación 3
Pigmento
Resina ----------------> Daña un 15% - Dura 10 años – Precio $450
Aglutinante
Diluyente

Pero ahora, ¿cómo saber cual combinación es la más óptima?

Éste problema requiere una optimización de mas de un objetivo, pero habrá un conflicto entre objetivos que harán que la mejora de uno de ellos dé lugar a un empeoramiento de algún otro.

A diferencia de los problemas de optimización con un solo objetivo, será necesario decidir de alguna forma cuál es la mejor solución (o cuáles son las mejores soluciones) al problema.

En términos matemáticos, el problema de optimización multiobjetivo, puede establecerse de la siguiente forma:

Encontrar un vector x*=[x1*,x2*,...,xn*]^T

que optimice la funcio vectorial f(x)=[f1(x), f2(x), ... , fk(x)]^T

. Dentro de los métodos para calcular la combinación de ibjetivos se puede mencionar el método de la suma ponderada, en el que se optimizará el valor obtenido mediante la suma de los valores de los distintos objetivos, multiplicados cada uno por un coeficiente de peso. Estos coeficientes de peso establecerán la importancia relativa de cada objetivo.


Otro método es el de asignación de prioridades, es decir se establecen prioridades entre los distintos objetivos, teniendo en cuenta su importancia durante la optimización.¨

Y fue con éste método con el que resolví mi problema y así saque el algoritmo correspondiente

1. Inicio
2. Identificar la importancia de cada criterio
3. Jerarquizar los criterios
4. Partir del criterio considerado mas importante
5. Ir al segundo criterio considerado
6. En este caso, llegar al criterio ‘menos importante’
7. Hallar la combinación
8. Fin
En este caso, yo tomaría como criterio base, el costo de la combinación, pues en mi ejemplo la restricción en de 500 pesos, como segundo criterio tomaría la durabilidad y al ultimo el daño al ambiente.

En este ejemplo yo escogería la combinación 3, pero como el daño al ambiente es de 15% tambien podría usar la tercera combinación.
Pero ésto no quiere decir que sea la solucion mas óptima, este tipo de problema tiene multiples soluciones, por lo mismo que tiene varios criterios u objetivos.
Por último desde mi punto de vista, este problema pertenece a los de complejidad P , pues se pude solucionar en tiempo polinomico y solo depende de la cantidad de criterios que se tengan.
______________
Bibliografía
Éstas paginas me fueron de mucha ayuda

jueves, 18 de febrero de 2010

PROYECTO 1 - Problema Cuatro

Objetos para llevar a un viaje-

El cuarto y ultimo problema que decidimos hacer, es el de cómo poder elegir entre diferentes objetos de valor, cuáles llevar a un viaje, pero solo contamos con una mochila con capacidad limitada.


Éste es el algoritmo que hicimos

1.Inicio
2.Seleccionar un objeto
3.Verificar que quepa en la mochila
4.Cerciorarse que no esté muy pesado
5.Asegurar el uso del mismo, durante el viaje
6.Pensar si en verdad es necesario
7.Ponerlo en la mochila
8.Ver si cabe otro objeto
9.Fin


Después hicimos el diagrama de flujo representando el algoritmo anterior





En éste diagrama representamos la manera en que nosotras resolveriamos el problema.


Primero sería seleccionar x objeto, después preguntarnos si cabe en la mochila, si no , se selecciona otro objeto, luego se revisa si es o no muy pesado, porque si lo es, tendríamos que escoger otro objeto, ya que se supone que la mochila es para traerla en la espalda y podriamos lastimarnos o simplemente no la podríamos cargar. También tenemos que reflexionar si en verdad nos servirá en el viaje y si es verdaderamente indispensable, porque si no , no tendría caso llevar ese objeto , pudiendo llevar alguno que en verdad es importante.


Si se llega a la conclusion de que si cabe, no es muy pesado, y sí es necesario llevarlo se mete a la mochila, y si se quieren o pueden llevar mas objetos, se repite el mismo proceso las veces que sean necesarías.




EJEMPLO


El siguente video muestra, el proceso que se hizo para seleccionar varios objetos, los cuales llevar a un viaje a la playa.



video


En el anterior video se mostraron las posibles opciones del diagrama de flujo.


Aquí también dejo el mismo video pero en Youtube , para que se vea mejor


video


http://www.youtube.com/watch?v=hNpLN2TcPQ8



_________________________________________


El diagrama de flujo lo hicimos en PowerPoint


Y el video también lo hicimos en CamtasiaStudio


http://en.wikipedia.org/wiki/File:Camtasia_6.png



_____________________________


Mi compañera: Dora Nelly Gonzalez Martinez

PROYECTO 1 - Problema Tres


Ruta en un mapa-------

El tercer problema que elejimos fue el de cómo encontrar una buena ruta en un mapa para llegar a cualquier destino.

Primero no sabiamos bien como hacerlo, pero después sencillamente nos pusimos a pensar qué es lo que haríamos nosotras en una situacion así.


Primero que nada, hicimos el proceso o algoritmo del problema

1.Inicio
2.Conseguir un mapa
3.Checar si el mapa está actualizado
4.Identificar el lugar en donde te encuentras
5.Encontrar el lugar al que quieres llegar
6.Trazar dos o tres rutas, con las cuales se puede llegar
7.Elegir una de esas rutas
8.Calcular cuánto tiempo lleva llegar a ese lugar
9.Checar el presupuesto con el que se cuenta
10.Fin

*Diagrama de Flujo



Primero que nada, debemos de asegurarnos de tener un mapa adecuado, esto es , que sea de la localidad correcta y que esté actializado. En caso de no contar con ésto, simplemente se consigue uno adecuado, despues se identifica el lugar en el que nos encontramos y hacia donde queremos ir, despues trazar dos o tres rutas posibles .
Por ejemplo, si estoy en FIME y quiero ir a mi casa, primero localizo donde está FIME y despues donde está mi casa, luego trazo diferentes rutas que me lleben hasta mi casa.
Luego escoger una de esas rutas para analizar cuánto tiempo nos llevaría llegar a nuestro destino si escogemos ir por esa y si tenemos el presupuesto adecuado, dependiendo de el tipo de transporte con el que contemos.
Y si no nos convence esa ruta elegir otra y hacer lo mismo las veces que sea necesario.
______________________________
Para hacer éste diagrama, utilizamos PowerPoint
Compañera:Dora Gonzalez





PROYECTO 1 - Problema Dos

Libros en orden alfabético----

Como segundo ejemplo , elejimos el problema de acomodar cierta cantidad de libros en un librero por orden alfabético según el título.


Éste es el algoritmo que nosotras consideramos correcto


1.Inicio
2.Tomar un libro
3.Checar la letra inicial del título
4.Revisar en el librero los demás libros

5.Acomodar el libro correctamente
6.Hacer lo mismo con los otros libros que se desean acomodar
7.Fin



Éste es el diagrama de flujo



El proceso para acomodar un grupo de libros en un librero , primero es tomar un libro , el cual se desea acomodar, y checar la primera letra del título, ya que de ésta manera es como se desea acomodar.

Despues fijarse si en el librero has otros libros con esa inicial, sino los hay, se acomoda normalmente, osea que si por ejemplo el libro empieza con la letra 'D' , se acomodaría despues de 'C'.

En el caso de que si haya otros libros con esa letra, se checa la segunda letra, y si coincidieran otra vez, se checa la letra que sigue y así sucesivamente.


Si hay otros libros por ordenar, se repite el mismo ciclo las veces que sean necesarias, y si no, se acaba el proceso.







*Para hacer el diagrama de flujo, usamos WinEsquema5

*Compañera: Dora Gonzalez

PROYECTO 1 - Problema Uno

Mi compañera Dora Nelly y yo decidimos hacer cuantro problemas, éste es el primero.
Directorio Telefónico--------
Este problema consiste en como se puede buscar el número teléfonico de x persona en un directorio. Tratamos de hacerlo lo más simple que se pudiera, y de manera general; sin declarar variables ni nada , solo hicimos el proceso necesario para ubicar un número.

Primero hicimos el algoritmo
1.Inicio
2.Ir a la sección del municipio donde vive la persona
3.Localizar la primera letra del primer apellido.
4.Localizar el apellido completo
5.Buscar el segundo apellido
6.Buscar el nombre de la persona
7.Encontrar el teléfono
8.Fin

Para hacer el diagrama de flujo utilizamos 'Raptor'


y así nos quedó el diagrama




Lo que nosotros tomamos en cuenta primero es localizar
la seccion en la que se encuentra la persona que buscamos,
después ir al apartado con la letra inicial del primer apellido,
luego buscar el apellido completo,
y como hay muchas personas con ese apellido,
buscamos el segundo apellido y por ultimo el nombre; y así ya llegamos al telefono.

Por eso en el diagrama de flujo , al ultimo sumamos todas las variables para llegar al telefono , porque así es en un directorio; sumas todos los pasos que hiciste y como resultado se llega el teléfono de la persona deseada.









También hicimos dos videos en donde se buscan nuestros numeros telefónicos.
video

video
_____________________________________________
Para hacer el diagrama y los ejemplos usamos 'Raptor'
y para grabar el video usamos Camtasia Studio.
______________________________________________
Compañera: Dora Nelly González Martínez





lunes, 1 de febrero de 2010

Como convertir numeros binarios a decimales y viceversa

El sistema binario es un sistema de numeración en el que los numeros se representan utilizando 0 y 1 . Es el que se utiliza en los ordenadores, pues trabajan internamente con dos niveles de voltaje, por lo que su sistema de numeración natural es el sistema binario (encendido 1, apagado 0).




Para convertir de decimal a binario

Se divide el numero del sistema decimal entre 2, cuyo resultado entero se vuelve a dividir entre 2, y así sucesivamente. Ordenados los restos, del último al primero, éste será el número binario que buscamos.


Por ejemplo convertir el numero 131 en binario se realiza lo siguiente:

Ahora para convertir de un binario a decimal se hace lo siguiente:
1.- Tomamos el numero decimal, por ejemplo 00110100100 y lo separamos por cifras:
0 0 1 1 0 1 0 0 1 0 0

2.- A cada crifra le agregamos un multiplicador por 2 (*2):
0*2 0*2 1*2 1*2 0*2 1*2 0*2 0*2 1*2 0*2 0*2

3.- Luego de derecha a izquierda (muy importante) elevamos cada “2″ a potencias consecutivas, partiendo del cero:
0*2^10 0*2^9 1*2^8 1*2^7 0*2^6 1*2^5 0*2^4 0*2^3 1*2^2 0*2^1 0*2^0

4.- Resolvemos cada uno por separado, solo resolvemos los que tinen un “1″ ya que los que tiene “0″, sea cual sea el resultado de la potencia al multiplicar por este, el resultado sera “0″. Entonces, resolviendo solos los “1″ obtenemos los numeros:
256 128 32 4

5.- Sumamos estos valores:
256+128+32+4 = 420

6.- Para numero Binario “00110100100″, su valor como decimal es “420″
-------------------------------------------------------------------------------------
Encontre un Conversor universal para codificar texto a cualquier tipo de codificación.
Aqui tambien encontre muy buena informacion sobre los numeros binarios

Instrucciones lógicas

Un microprocesador dispone de una unidad aritmética-lógica que le permite realizar una serie de operaciones, tanto aritméticas, como lógicas. Las aritméticas incluyen la suma y resta con o sin acarreo, incremento y decremento de un registro, comparaciones, ajuste decimal, complemento y negación. Las lógicas incluyen las operaciones que se realizan con los operadores "AND", "OR" y "XOR".


Se puede observar que para la operación AND, si los dos operandos son 1, el resultado será 1, en cualquier otra situación será 0.La operación OR establece el resultado a 1 si cualquiera de los dos operandos es 1, de lo contrario el resultado será 0.La instrucción XOR coloca en 0 el resultado si los operandos son iguales, de lo contrario establece 1. Finalmente, la instrucción NOT cambia de estado todos los bits del operando, los unos por ceros y los ceros por unos.La principal aplicación de estas instrucciones es el enmascaramiento de información. La operación AND nos permite poner a cero cualquier bit de un dato; la operación OR nos permite poner a uno cualquier bit de un dato y la operación XOR permite borrar el contenido de algún registro o localidad de memoria, así como para negar algún bit.

Diagramas de Flujo

Un diagrama de flujo es la representación de un algoritmo o una serie de pasos a seguir para poder solucionar un problema.


Un ejemplo es el siguiente que hice:
Muestra un problema
con el internet
y plantea una solución.
heey! soloo estoy checando como funcionaa esto!