lunes, 31 de mayo de 2010

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.










































































































6 comentarios:

  1. Como puntos de ruteo podrias poner los siguientes en el arbol original!!!

    40

    30 60

    Espero lo tomes encuenta

    ResponderEliminar
  2. Como puntos de ruteo podrias poner los siguientes en el arbol original!!!

    40

    30 60

    Espero lo tomes encuenta

    ResponderEliminar
  3. Maldicion, me ganaron los puntos de ruteo, pero ya pueden ser los que tu quieras siempre esten en orden, los mayores a la derecha, uno que este en medio como abuelo, y los menores a la izquierda, siempre y cuando sea uno mas grande que el de la izquierda pero mas chico que el de la derecha.

    ResponderEliminar
  4. ¿En este caso podríamos utilizar la inserción de un padre postizo?, segun recuerdo en las asesorias de la Dra. Elisa podemos utilizar ese método también

    como lo mencionaba mi compañero hector tinajero, el numero de la derecha tiene que ser mayor al de la izquierda.

    Una duda, en el problema 5 ¿que significa que sea de grado 3?

    Gracias

    ResponderEliminar
  5. Muy buena la explicacion y respondiendo a erik creo que el grado 3 significa los vertices adyacentes al principal

    ResponderEliminar
  6. Solo para agregar un poco mas de informacion cuando se refieren al grado de un nodo hablan de el número de hijos de dicho nodo.
    El grado de un árbol es el mayor grado de los nodos que contiene.
    El nivel de un nodo se asigna en función al criterio siguiente:
    La raiz tiene nivel 1.
    Si un nodo tiene nivel N, sus hijos tendrán nivel N+l.
    El nº de niveles de un árbol es igual a la altura de su raíz, o a 0, si el árbol es vacío.

    ResponderEliminar