viernes, 28 de mayo de 2010

Puntos Extra

Ejercicios
La profesora nos dio la oportunidad de hacer ejercicios para puntos extra, para segundas, y estos son los que hice:
Máximo común divisor: de 987654321 módulo 34567

Explicación:Se utiliza el algoritmo euclideano para encontrar el máximo común divisor de dos enteros diferentes de cero(C= A % B). Se divide el nú
mero mayor entre el número menor. Se repite la división, utilizando el residuo como divisor, hasta que el residuo se convierte en cero. El último residuo diferente de cero y 1 es el máximo común divisor de los dos enteros.
En este caso me apoye en Excel, colocando el primer numero en la celda A1 y el segundo en la B1 y con la función residuo en la celda C1 obtengo el módulo.Despues la celda A2 toma el valor de la B1 y la B2 de la C1 y copio la función en la misma columna C. Quedando terminado asi:





Dando como resultado el Máximo común divisor el: 1


Distancia de edición:

Calcular la distancia de edicion de las siguientes palabras:
Algoritmos Computacionales


Con costo 1 para insercion, eliminacion y reemplazo, (costo cero para remplazo mismo símbolo.)






Costo Final: 15 o 10?


Listas enlazadas


Expresar en pseudocódigo las operaciones y su complejidad computacional asintótica.

Creacion de una lista nueva
tLista Crear()

{

tLista l;
l = (tLista)malloc(sizeof(tipocelda));if (l == NULL)
Error("Memoria insuficiente.");
l->siguiente = l->anterior = l;
return l;
}
Complejidad computacional:O(L)

Insercion de un elemento

void Insertar (tElemento x, tPosicion p, tLista l)

{

tPosicion nuevo;
nuevo = (tPosicion)malloc(sizeof(tipocelda));
if (nuevo == NULL)
Error("Memoria insuficiente.");
nuevo->elemento = x;
nuevo->siguiente = p;
nuevo->anterior = p->anterior;
p->anterior->siguiente = nuevo;
p->anterior = nuevo;
}
Complejidad computacional:O(L)


Eliminación de un elemento

void Borrar (tPosicion *p, tLista l)

{

tPosicion q;
if (*p == l){
Error("Posicion fin(l)");
}

q = (*p)->siguiente;
(*p)->anterior->siguiente = q;
q->anterior = (*p)->anterior;
free(*p);
(*p) = q;
}
Complejidad computacional:O(n)


Bibliografía:

En este sitio explican paso a paso con animaciones la manipulacion de listas.
http://decsai.ugr.es/~jfv/ed1/tedi/cdrom/docs/ldoble.html



Coloreo de Grafos

Para colorear un grafo se siguen las sigientes condiciones:
  • Los vértices vecinos conectados por aristas entre sí, no pueden tener el mismo color.
  • Tambien se debe tomar en cuenta que el numero de colores debe ser el mínimo posible.

Ejemplo de coloreo de grafo:



Existen muchos tipos diferentes de grafos para colorear, incluso no siempre pueden ser como este, también pueden ser mapas de ciudades, países, etc.

Bibliografía:

En esta pagina encontraran informacion y software interesante para informática.

http://www.dma.fi.upm.es/gregorio/grafos/paginagrafos.html

En esta hay un software para crear grafos y colorearlos esta muy bueno.

http://www.dma.fi.upm.es/gregorio/grafos/ColorListasJuego/html/Descargas.html

domingo, 16 de mayo de 2010

Proyecto #5

Tema: Árboles de Steiner

¿Qué son los árboles de Steiner?
Son una solucion mas óptima que los árboles EMST (Euclidean Minimum Spanning Tree), de hecho se forman mediante este tipo de árboles pero con la diferencia que para lograr la maxima optimizacion se puede agregar mas vértices. Estos vértices adicionales
se denominan Vértices o Nodos de Steiner.
Mediante estos vértices se busca efectuar una minimización más óptima de los árboles de recubrimiento.

Para lograr esto se deben cumplir los suguientes criterios:

• Las aristas adyacentes concurrentes en un vérticecomún, forman un ángulo por lo menos de
120 grados
• No debe existir cruces de aristas.
• Cada punto de Steiner tiene grado tres, es decir, existen tres aristas que concurren a él.

Consideraciones:
Para un conjunto de N vértices, se tiene como máximo N-2 vértices de Steiner.

Ejemplo de árbol steiner





¿Para que se utilizan los Árboles de Steiner?

Para optimizar las redes de comunicaciones. Uno de los principales problemas en la construción de redes de comunicaciones es el diseño de una topología óptima para la mejor comunicacion entre los pares de nodos.
Tambien son utilizados en redes de transportes.

Complejidad Computacional:


La generación de Árboles de Steiner representa un tipo de problemas en el cual la respuesta es la mejor aproximación, pero el costo computacional es elevado.

En 1973 Karp demostró que el problema del árbol de Steiner es NP-Completo. Desde entonces, diferentes enfoques de métodos heurísticos han sido aplicados para obtener buenas soluciones del problema en tiempos razonables.

Se estan llevando a cabo investigaciones para diseñar e implementar en un "futuro próximo" los métodos heurísticos correspondientes a técnicas evolutivas, que permitan llegar a la optimización de un conjunto de N vértices fuertemente conexo, más allá del obtenido por los árboles EMST, permitiendo obtener inclusive la solución del Problema de Steiner Generalizado.

Autoevaluación: Los Árboles de Steiner son una muy buena aproximacion a la mejor opción, aunque es muy complejo y costoso obtenerla mediante metodos computacionales, pienso que la informacion que les dejo aquí es algo muy bueno para comprender un poco el funcionamiento básico de este tipo de árboles espero que les sea de utilidad.

Si notan algun error me lo hacen saber y pueden dejar comentarios sobre el tema. Gracias!!!

Bibliografía:

En esta pagina hay un applet que muestra el EMST

http://personal.us.es/almar/docencia/practicas/proximidad/emst.htm

http://sisbib.unmsm.edu.pe/bibvirtualdata/publicaciones/risi/n3_2005/a05.pdf

domingo, 25 de abril de 2010

Proyecto #4

Equipo: 4
Tema: Pilas

¿Qué hice yo, cómo me salió?
Yo diseñe la animación de como se acomodan las pilas, cual se elimina, y donde se puede insertar un nuevo dato etc. Me salió bien la animación mis compañeros la revisaron y les pareció buena.

En que aspectos estoy bien y en que debo mejorar:

Entendí el funcionamiento de las pilas, sus aplicaciones en la vida real, como se acomodan, cual se puede eliminar, donde insertar otra nueva etc.
No entendía el "Conteo de paréntesis" pero mis compañeros de equipo me lo explicaron y pude entenderlo.

Ayudo a los demas o me apoyo en ellos:

Todos ayudamos para poder hacer la precentación, si alguien tenia una idea la revisábamos y la aplicábamos si estaba bien, sino la mejorabamos o proponiamos otras.

¿Quien se encarga de coordinar el trabajo?

Lo hicimos en equipo, decidimos que cosas poner cuales puntos usar y como acomodarlos para que se entienda la mejor posible.

¿Que papel tomo yo?

Todos decidimos que era lo mejor para la precentación, todos fuimos una parte importante del proyecto.



Descargar presentación


Blogs de mis compañeros:
http://technolifeandmore.blogspot.com/
http://yeyohbk.wordpress.com/
http://emmanuelgs.blogspot.com/

domingo, 21 de marzo de 2010

Proyecto #3

Problema: Generacion de elementos de la serie Fibonacci


Recursión es una técnica para programar en la que se hacen llamadas de alguna función muchas veces para resolver algun problema. Siempre se cuenta con una caso base que no es recursivo.

Cuando usar la recursión:

Sirve para simplificar códigos.
Tambien para dar estilo o "elegancia"
Cuando se usan arreglos largos en los metodos.
Cuando cambia el metodo de manera impredecible.
Son mas cercanos a la descripcion matemática.
Son mas fáciles de analizar.

Cuando no usar recursión:

Cuando no se necesita repetir un proceso o una funcion, cuando es mas importante el rendimiento, ya que cuando hace muchas llamadas a una funcion consume mas memoria, al crear variables para guardar informacion.


Trabajo en Equipo

Trabajamos bien, todos dimos nuestra opinión al respecto y juntamos nuestras ideas para lograrlo.
Sabemos como crear algoritmos, sabemos un poco de como convertirlo en un programa con su codigo en "C" y creo que debemos mejorar en el análisis asintótico.

Yo contribuí con mis conocimientos en dev- C para crear un programa que genere la serie Fibonacci y analizando el algoritmo para saber si es recursivo o iterativo.

Creo que cada quien aporto algo con respecto a lo que domina.

Podemos mejorar conociendo mas temas que nos ayuden en la resolución de problemas o en la creacion de mejores algoritmos.

Presentación:

http://medel.jimdo.com/2010/03/22/proyecto-no-3/


Blogs:

http://cynthiatelles.blogspot.com/

http://karla-ias.blogspot.com/

http://medel.jimdo.com/


Bibliografía:

http://es.wikipedia.org/wiki/Sucesión_de_Fibonacci

http://computacion.cs.cinvestav.mx/~acaceres/courses/estDatosCPP/node38.html

http://ciberconta.unizar.es/leccion/fin005/700.HTM

jueves, 4 de marzo de 2010

Proyecto #2

La asignación de alumnos y maestros a grupos, horas y salones.





Primero divido el problema en partes mas pequeñas:





¿Existe una combinación de alumnos para que en todos los grupos haya el mismo numero de alumnos?


Si no es posible, buscar una combinación con una diferencia mínima de alumnos por grupo.





Después: ¿Existe una combinación de horas en la cual todos los grupos tengan la misma cantidad de horas?


Tomando en cuenta que ya habíamos llenado los grupos con la misma cantidad o mínima diferencia de alumnos.





¿Existe una combinación de salones en la que se puedan repartir la misma cantidad de horas?


Tomando en cuenta que a cada grupo ya se le asignaron sus horas.





¿Exitse una combinación de salones en la cual todos los maestros den clase en la misma cantidad de salones?


Tomando en cuenta que cada salón tiene sus horas, cada hora sus grupos y cada grupo sus alumnos.



Para solucionar este problema de la manera mas óptima necesitamos que todos los recursos con que contamos sean utilizados eficientemente y no desperdiciar unos y a otros sobrecargarlos.





Algoritmo:





1.- Revisar el total de alumnos por asignar, los maestros, la cantidad de grupos, las horas de clase y los salones disponibles que hay.


2.- Acomodar el mismo numero de alumnos por grupo, dividiendo el total de alumnos entre los grupos o si no que la diferencia sea mínima.


3.- Una vez repartidos los alumnos, se reparten las horas para los grupos, demanera que los grupos lleven la misma cantidad de horas.


4.- Darle a los salones las horas que seran utilizados.


5.- Asignar los maestros a los salones en en los que daran clase sin empalmarlos.





Este algoritmo realiza almenos 10 cosas como minimo para decidir la mejor asignación.



Este tipo de problema que es del tipo P porque si conocemos la cantidad de alumnos, maestros, grupos, salones y horas podemos encontrar la asignación más optima

jueves, 25 de febrero de 2010

Hola soy Emilio, y para el proyecto 2 elijo el problema de: "La Asignacion de alumnos y maestros a grupos/horas/salones ".

viernes, 19 de febrero de 2010

Proyecto 1_Problema 3




Libros que están en el librero:





Título del libro


Valor de “i”



0


Aeropuertos [1]


2


Escultura [2]


5


Japón [3]


10


Tornado [4]


20



Libros por acomodar ordenados de menor a mayor en cajas:




Título del libro Caja 1


Valor de “j”


Bellas Artes


3


Gatos


7


India


9


México


14


Visión


22




1.- Inicializa: Pide el valor de “j”.


2.- Compara: “j” con “i”, si j mueve a "i" y a los libros siguientes un lugar y coloca "j" antes de "i" y avanza al paso 3; si j>i, mueve "i" al libro siguiente y vuelve a comenzar el paso 2.


3.- Imprime: “i” anterior a “j”, “j”, “i” posterior a “j”; regresa “i” a i=0; mientras pide “j” siguiente y regresa al paso 2.


4.- Hecho.



Explicación:


Suponiendo que hay un librero, en el que se encuentran algunos libros y teniendo otros organizados alfabeticamente en cajas, los cuales colocaremos en el librero.


Por lo cual todos los libros tienen un número que los identifican y con estos haremos comparaciones para organizarlos.