martes, 2 de noviembre de 2010

Premios a la calidad

Check out this SlideShare Presentation:

martes, 1 de junio de 2010

Puntos Extra

Árbol Binario de Busqueda

En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. Con la raíz escogida, cada vértice tendrá un único padre, y nunca más de dos hijos. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno.

Tipos de árboles binarios

  • Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.
  • Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
  • Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura).

Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.


Búsqueda:

La búsqueda consiste acceder a la raíz del árbol, si el elemento a localizar coincide con éste la búsqueda ha concluido con éxito, si el elemento es menor se busca en el subárbol izquierdo y si es mayor en el derecho. Si se alcanza un nodo hoja y el elemento no ha sido encontrado se supone que no existe en el árbol. Cabe destacar que la búsqueda en este tipo de árboles es muy eficiente, representa una función logarítmica. El maximo número de comparaciones que necesitaríamos para saber si un elemento se encuentra en un árbol binario de búsqueda estaría entre [log2(N+1)] y N, siendo N el número de nodos.


Inserción:

La inserción es similar a la búsqueda y se puede dar una solución tanto iterativa como recursiva. Si tenemos inicialmente como parámetro un árbol vacío se crea un nuevo nodo como único contenido el elemento a insertar. Si no lo está, se comprueba si el elemento dado es menor que la raíz del árbol inicial con lo que se inserta en el subárbol izquierdo y si es mayor se inserta en el subárbol derecho. De esta forma las inserciones se hacen en las hojas.


Borrado:

La operación de borrado no es tan sencilla como las de búsqueda e inserción. Existen varios casos a tener en consideración:

  • Borrar un nodo sin hijos ó nodo hoja: simplemente se borra y se establece a nulo el apuntador de su padre.

Borrar un nodo con un subárbol hijo: se borra el nodo y se asigna su subárbol hijo como subárbol de su padre.


Borrar un nodo con dos subárboles hijo: la solución está en reemplazar el valor del nodo por el de su predecesor o por el de su sucesor en inorden y posteriormente borrar este nodo. Su predecesor en inorden será el nodo más a la derecha de su subárbol izquierdo (mayor nodo del subarbol izquierdo), y su sucesor el nodo más a la izquierda de su subárbol derecho (menor nodo del subarbol derecho). En la siguiente figura se muestra cómo existe la posibilidad de realizar cualquiera de ambos reemplazos:

Recorridos:

Se puede hacer un recorrido de un árbol en profundidad o en anchura.

Los recorridos en anchura son por niveles, se realiza horizontalmente desde la raíz a todos los hijos antes de pasar a la descendencia de alguno de los hijos.

El recorrido en profundidad lleva al camino desde la raíz hacia el descendiente más lejano del primer hijo y luego continúa con el siguiente hijo. Como recorridos en profundidad tenemos inorden, preorden y postorden.

Una propiedad de los ABB es que al hacer un recorrido en profundidad inorden obtenemos los elementos ordenados de forma ascendente.

Resultado de hacer el recorrido en:

Inorden (I/R/D) = [6, 9, 13, 14, 15, 17, 20, 26, 64, 72].

Preorden (R/I/D) = [15, 9, 6, 14, 13, 20, 17, 64, 26, 72].

Postorden (I/D/R) =[6, 13, 14, 9, 17, 26, 72, 64, 20, 15].

Puntos Extra

Diagrama de Voronoi (Examen Ordinario)

Para el siguiente conjunto de puntos (x, y)
en un plano: (6,7), (3,8), (2,6), (3,1), (5,4), (2,8), (7,3), (5,7).


¿Como lo hice?
1.- Utiliza un plano carteciano en el cual coloque el conjunto de puntos (x, y).
2.- Utilize la aplicación applet proporcionada en los archivos PDF del curso para darle mayor exactitud.
Fortune's Voronoi algorithm, implemented visually

¿Qué es un diagrama de Voronoi?

Imagina que tienes un mapa sobre una ciudad con n mástiles de telefonía celular. Un teléfono móvil siempre se conecta a la más cercana del mástil, por lo que desea dividir la ciudad en zonas, donde cada zona tiene exactamente una antena de telefonía celular y cada posición dentro de dicha zona es la más cercana a la antena de telefonía celular se encuentra en el mismo zona.

El resultado de esta división se refiere a menudo como un diagrama de Voronoi y se pueden crear en O (n log n) momento por varios algoritmos. Este es también un límite inferior.

GUIA Nº6 GRAFOS Y ALGORITMOS ALEATORIOS

Como se forma un Diagrama de Voronoi.

Supongamos que, centrados en cada uno de los n puntos del plano que tenemos

como datos de partida, comienzan a crecer círculos a la misma velocidad. Cada

punto se apropia del área que ocupa el círculo centrado en él siempre que no esté

previamente ocupada por otro. Al final, cuando los radios de los círculos tienden

a infinito, ¿Qué región del plano corresponderá a cada uno de los puntos?



Puntos Extra

Problema del Examen Ordinario Puntos Extras
"Algoritmo Euclidiano (Máximo Diviaor Común)"

Calcule el Algoritmo Eulidiano el máximo divisor común de 987,654,321 y 34,567. Presente cada fase del algorit
mo e identifique el resultado. GUIA Nº6 GRAFOS Y ALGORITMOS ALEATORIOS

Método para encontrar el máximo factor común de dos enteros.

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.

Ejemplo paso a paso:
















La tabla del Algoritmo Euclidiano es:






Puntos Extra

Problema del Examen Ordinario
"Grafos"
GUIA Nº6 GRAFOS Y ALGORITMOS ALEATORIOS

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).

Luego ejecuta paso por paso una búsqueda de 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 el menor etiqueta.



El gráfo quedaria de esta manera, el cual es plano ya que ninguna de sus Aristas se cruzan o intersecan entre si.

GUIA Nº6 GRAFOS Y ALGORITMOS ALEATORIOS



El diámetro del grafo es:2

GUIA Nº6 GRAFOS Y ALGORITMOS ALEATORIOS


El grado de un vértice ,es el numero de aristas adyacentes al vértice, por lo tanto el grado de el grafo se calculara sumando el grado de cada vértice y dividiendo entre el numero de vértice.

Vértice 1.- es de grado 3 (por que tiene 3 aristas adyacentes al vertice)

Vértice 2.- es de grado 3

Vértice 3.- es de grado 3

Vértice 4.- es de grado 3

Vértice 5.- es de grado 3

Vértice 6.- es de grado 3

Primero sumamos los grados de cada vértice, que nos da un total de 18,

Después dividimos entre el numero de vértices, que en este caso son 6.

Asi que 18/6 = 3 por lo tanto el grado promedio es 3.




GUIA Nº6 GRAFOS Y ALGORITMOS ALEATORIOSComenzamos con el vértice de etiqueta tres, pasamos al de etiqueta 1 ya que es el de menor etiqueta, después al 2, de ahí sigue el 4 de ahí el 5 ya que es el único q ahí después el 6 y finalizamos.

Los vértices en postorden son: (6,5,4,2,1,3)