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