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()Complejidad computacional:O(L)
{
tLista l;
l = (tLista)malloc(sizeof(tipocelda));if (l == NULL)
Error("Memoria insuficiente.");
l->siguiente = l->anterior = l;
return l;
}
Insercion de un elemento
void Insertar (tElemento x, tPosicion p, tLista l)Complejidad computacional:O(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;
}
Eliminación de un elemento
void Borrar (tPosicion *p, tLista l)Complejidad computacional:O(n)
{
tPosicion q;
if (*p == l){
Error("Posicion fin(l)");
}
q = (*p)->siguiente;
(*p)->anterior->siguiente = q;
q->anterior = (*p)->anterior;
free(*p);
(*p) = q;
}
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.
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
