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

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