Puntos extra

Hola profesora y compañeros de clase, aqui les muestro algunos de los problemas del ordinario.Sinceramente fueron de los problemas donde mejor me fue asi que decidi volverlos a contestar.

Arboles Binarios
Los árboles binarios constituyen un tipo particular de árboles de gran aplicación. Estos árboles se caracterizan porque no existen nodos con grado mayor que dos, es decir, un nodo tendrá como
máximo dos subárboles.
Definición: Un árbol binario es un conjunto finito de nodos que puede estar vacío o consistir
en un nodo raíz y dos árboles binarios disjuntos, llamados subárbol izquierdo y
subárbol derecho.

El problema era el siguiente:
Supongamos que los elementos siguientes están correctamente almacenados en un árbol binario
externo (llaves únicamente en las hojas) correctamente con vértices de ruteo adecuados en balance
perfecto: 45, 23, 38, 79.

a) Dibuje un posible árbol inicial (2 puntos).
b) Inserte el elemento 13 sin balancear el árbol (1 punto).
c) Elimine el elemento 38 sin balancear el árbol (1 punto).
d) Busque en el árbol por un elemento 55 y detalla cada paso de la búsqueda hasta obtener el
resultado (1 punto).
En los últimos tres incisos, identifique la complejidad computacional de la operación.

a) Lo primero que hize fue dibujar el arbol, en una rama dibuje el 23 y el 38 mientras que en la otra rama dibuje el 45 y 79.

Asi quedó el arbol

b) Despues lo que hize fue insertar el elemento 13, lo inserté debajo del elemento 23 ya que de todos los elementos, era el menor y se elimino el 23.

Insertar elementos en un árbol binario de búsqueda tiene una complejidad:


O(log n).

c) Se eliminó el elemento 38 del arbol sin balancearlo y se muestra asi:

Complejidad computacional: O(log n)

d) Se buscó un elemento 55 en el arbol, empezé desde la raiz nos vamos hacia la rama derecha, pasando por el elemento 79, por esa parte no se halló asi que nos devuelve un valor FALSE ya que ese elemento no se encontro. Aqui presento como fue la busqueda:

Recorrer los elementos del árbol en inorden tiene complejidad:

O(log n).

-------------------------------------------------------------------------------------------------Grafos

Demuestre que el grafo simple no dirigido definido por las siguientes aristas en formato (inicio,
final) es plano: (1, 2), (1, 3), (1, 4), (2, 4), (2, 6), (3, 5), (3, 6), (4, 5), (5, 6).

Calcule su diámetro y grado promedio. Luego, ejecuta paso por paso una búsqueda en profundidad (DFS) que imprime los vértices en postorden, iniciando el recorrido en el vértice con etiqueta 3 y visitando siempre primero aquel vecino no visitado que tiene la menor etiqueta.

Aqui les muestro como quedo mi grafo, como podran ver, las aristas no se intersecan, esto quiere decir que el grafo es plano.El grado es 3 porque es el numero mayor de aristas que tiene un vertice.

Aqui les muestro lo que es la busqueda, se inicia en la etiqueta 3 y va visitando el menor vertice posible para que se logre visitar todos los vertices sin pasar por el mismo.

Los vertices en postorden serian :6,5,4,2,1,3.

El diametro seria 2, porque es la mayor distancia entre dos vertices.

-------------------------------------------------------------------------------------------------
Listas enlazadas
Exprese en pseudocódigo las operaciones siguientes para listas doblemente enlazadas y analize la complejidad computacional asintótica de cada operación:
-Creación de una lista nueva
- Inserción entre dos elementos existentes
- Eliminación entre dos elementos existentes
- Inserción al inicio
- Eliminación del final


-Creacion de una lista nueva:
struct nodo {
int dato;
struct nodo *siguiente;
struct nodo *anterior;
};

Complejidad computacional: O(l) se refiere a que es lineal.

-Inserción entre dos elementos existentes:
1.Hacemos que nodo->siguiente apunte a lista->siguiente.
2.Hacemos que Lista->siguiente apunte a nodo.
3.Hacemos que nodo->anterior apunte a lista.
4.Hacemos que nodo->siguiente->anterior apunte a nodo

Complejidad computacional: O(l) se refiere a que es lineal.


-Eliminacion entre dos elementos existentes:
1.Si nodo apunta a Lista, hacemos que Lista apunte a Lista->anterior (o Lista->siguiente).
2.Hacemos que nodo->anterior->siguiente apunte a nodo->siguiente.
3.Hacemos que nodo->siguiente->anterior apunte a nodo->anterior.
4.Borramos el nodo apuntado por nodo.

Complejidad computacional: O(n) n numero de pasos


-Inserción al inicio:
Nos basamos en una lista no vacia, consideramos que lista apunta al primer elemento de la lista doblemente enlazada:
1.nodo->siguiente debe apuntar a Lista.
2.nodo->anterior apuntará a Lista->anterior.
3.Lista->anterior debe apuntar a nodo

Complejidad computacional: O(l) se refiere a que es lineal

-Eliminacion al final: 1.Si nodo apunta a Lista, hacemos que Lista apunte a Lista->anterior.
2.Hacemos que nodo->anterior->siguiente apunte a NULL
3.Borramos el nodo apuntado por nodo

Complejidad computacional: O(n) n numero de pasos.





Bibliografia: http://ldcastillo.wordpress.com/tema-2-listas-doblemente-enlazadas/

Cualquier duda u observacion favor de comentar en el blog.
Gracias.

Proyecto #5

Hola compañeros y profesora, aquí les muestro mi proyecto #5. El tema que elegí fue el de "detección de planaridad".
Este tema es bastante interesante y entretenido ya que ayuda a desarrollar la creatividad a la hora de encontrar alguna solución óptima en cuanto a los grafos, detectar si un grafo es plano o no.

-Definicion del problema
Cuando un grafo o multígrafo se puede dibujar en un plano sin que dos segmentos se corten, se dice que es plano.
Un grafo no es plano si no puede ser dibujado sobre un plano sin que sus aristas se intersequen.

Este problema es de "optimización".
La complejidad asintotica es φ(n)
Aquí les muestro un ejemplo de una pequeña actividad que una vez la profesora nos habia puesto en clases:





El dibujo nos muestra un grafo (figura del cubo) donde podemos apreciar que algunas de sus aristas se intersecan, esto quiere decir que aquel grafo no es plano.
En cambio si el grafo lo modificamos y lo analizamos desde otra perpectiva podemos ver que hay una manera de juntar todas sus aristas sin que estas se intersecan, entonces esto quiere decir que el grafo ahora si es plano.

Ahora les dejare el link de un juego para que se entretengan y comprendan un poco mejor este problema ya que esta basado en este principio.
Juego de las casas y los servicios.
Explicación del juego:


La presentación del juego es la que aparece en la imagen. El objetivo del mismo es conectar cada una de las casas de la fila superior con los tres círculos de la fila inferior si que ninguna de las líneas de conexión corte a otra.
Si representamos cada uno de los iconos (tanto las casas como los círculos) mediante puntos (vértices) y tomamos también las líneas de conexión (aristas) lo que obtenemos seria el siguiente grafo:
---------> K3,3

Llamando u1,u2,u3 a los vértices superiores y v1,v2,v3 a los inferiores y representando como ui, vj a la arista que une el vértice ui con el vértice vj obtenemos el grafo conocido como: K3,3


Partiendo de que dos aristas de un grafo sólo pueden contarse en un vértice (es decir, que si tenemos dibujados los vértices de antemano dos aristas no pueden cortarse en ningún punto nada más que en ellos).

Para intentar resolver este problema se usa el Teorema de Kuratowski:

Un grafo es plano si no contiene como subgrafo a K5(el grafo completo de 5 vértices) ni a K3,3.
Es decir, ni K5 ni K3,3 son grafos planos (ya que cada uno de ellos se contiene a sí mismo como subgrafo). O lo que es lo mismo, no pueden dibujarse en un papel con la condición de que ninguna arista corte a otra en un punto que no sea desde el principio un vértice.
En conclusión este juego por mas que intentemos encontrar una solución no se podra ya que no es un grafo plano (K3,3) .

Teorema (Formula de Euler):
"Si a y n son enteros primos relativos, entonces aφ(n) ≡ 1 (mod n)".
Sea M un mapa conexo con R regiones que represente al grafo G=(V, E), entonces:
V-E+R=2, es decir, R+V=E+2.
Sea G=(V, E) un grafo plano conexo, con V>2, entonces E3<=V-6
K5


Una subdivisión elemental de un grafo G es otro grafo, donde se sustituye una arista por
un nuevo vértice unido a los extremos de la arista suprimida por dos nuevas aristas.
En un mapa se trata de añadir un vértice sobre el interior de una arista existente.
Una subdivisión de un grafo G es el grafo obtenido efectuando un número finito (puede
ser 0) de subdivisiones elementales sucesivas.

Para K3,3
Si G es un grafo plano, conexo, con n vértices, q aristas y que
descompone al plano en r regiones (o caras), entonces

Demostración:
Por inducción sobre q
Si q=0, entonces n =1, r =1 y se cumple que n−q+r = 2
Supongamos que el resultado es cierto para todos los grafos planos
y conexos con q-1 aristas, donde q≥1.
Sea G un grafo plano y conexo con q aristas.

Si G no es árbol, entonces existe alguna arista a de un ciclo de G
G−{a} es plano, conexo con n vértices, q−1 aristas y r −1 regiones.
La hipótesis de inducción asegura entonces que:
n − (q−1)+ (r−1)= 2 , es decir, n−q+r = 2

Consecuencias
Si G es un grafo simple y planar con n vértices y q aristas
2.- Si n≥3 y G no tiene ciclos de longitud 3, entonces
q ≤ 2n−4
Ahora el borde de cada región tiene, al menos, 4 aristas y cada
arista pertenece al borde de dos regiones.
Así contando el nº de aristas, resulta que 4r ≤ 2q
Sustituyendo en la fórmula de Euler 2n−2q+2r = 4,
q ≤ 2n−4
3.- G tiene, al menos, un vértice v con grado d(v) ≤ 5
Si para cada vértice x, se tiene que d(x)≥6 entonces
2q=Σd(x) ≥ 6n, luego q≥3n

Aplicaciones:
El saber si un grafo es o no es plano puede ser de gran importancia en el diseño de circuitos integrados, de carreteras, de ferrocarriles y en general en todos los casos en que el cruce de dos aristas represente una situación incómoda (o incluso cara).


Conclusiones:
Este tema me gustó mucho en lo personal, ya que pude identificar como detectar si un grafo es plano o no. A base del juego y algunos grafos pude entender mejor este principio.
Sinceramente no fue fácil encontrar la información ya que es muy extenso este tema pero con dedicación y leyendo varias fuentes pude comprender la idea principal del tema.
Creo que me falto investigar mas ya que hay algunos aspectos cuales no logré comprender muy bien. Sobre la presentación quise poner la idea principal para que fuera concreta e invitarlos a que entraran a mi blog para que se familiarizaran mas con el problema.

Algoritmo Euclidiano (Puntos extra)

Hola profesora y compañeros, aqui les muestro un tema que me llamo la atencion para puntos extra se trata sobre el algoritmo euclidiano.

Algoritmo Euclidiano

Este algoritmo es un método para encontrar el máximo factor común de dos enteros. Primero 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 a cero es el máximo factor común de los dos enteros.

Por ejemplo, para encontrar los máximos factores comunes de 99 y 44, dividimos 44 entre 99. Esto da 2 con un residuo de 11. A continuación, se divide 11 entre 99, que da 9 con un residuo de 0. Ya que 11 es el último residuo diferente a cero, es el máximo factor común de 99 y 44.

Otro ejemplo seria el siguiente
Por ejemplo, para encontrar el máximo común divisor de 93164 y 5826 el algoritmo genera la siguiente secuencia de divisiones:

Paso Operación Significado
1 93164 dividido entre 5826 es 15 y sobran 5774
2 5826 dividido entre 5774 es 1 y sobran 5
3 5774 dividido entre 52 es 111 y sobran 2
4 52 dividido entre 2 es 26 y sobra 0

Su complejidad computacional seria O(log n) divisiones para que se calcule el maximo comun divisor de n y m donde

n>m

Su implementacion en pseudocodigo seria:

Algoritmo en forma recurrente

Funcion

mcd (a,b)

Si b=0 entonces:

El resultado es a

En otro caso:

El resultado es mcd (b, a mod b)

Algoritmo en forma iterativa

Funcion

mcd(a,b):

mientras haga lo siguiente:

El resultado es a

Cualquier duda o sugerencia favor de dejar un comentario.

Gracias