lunes, 9 de enero de 2012
3er parcial de estructuras de datos
Que es la torre de hanoi?
Se trata
Este solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo unas ciertas reglas. El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.
Descripción
El juego, en su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas:
- Sólo se puede mover un disco cada vez.
- Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
- Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.
4. Resolución
5. El problema de las Torres de Hanói es curiosísimo porque su solución es muy rápida de calcular, pero el número de pasos para resolverlo crece exponencialmente conforme aumenta el número de discos. Existen algunas versiones del problema con un número diferente de varillas. Aunque se conocen algoritmos eficientes que resuelven el problema con 3 varillas de manera óptima, no se han encontrado aún sus contrapartidas para cualquier número (N igual o superior a 3) de ellas.
6. Solución simple
7. Una forma de resolver la colocación de la torre es fundamentándose en el disco más pequeño, en este caso el de hasta arriba. El movimiento inicial de este es hacia la varilla auxiliar. El disco número dos por regla, se debe mover a la varilla número tres. Luego el disco uno se mueve a la varilla tres para que quede sobre el disco dos. A continuación se mueve el disco que sigue de la varilla uno, en este caso el disco número tres, y se coloca en la varilla dos. Finalmente el disco número uno regresa de la varilla tres a la uno (sin pasar por la dos) y así sucesivamente. Es decir, el truco está en el disco más pequeño.
Donde se emplea?
Este problema se suele plantear a menudo en ámbitos de programación, especialmente para explicar la recursividad.
Quien lo invento?
ARBOLES DE DECISIÓN
Que se utiliza en un plan de vuelo?
El plan de vuelo ( fligh plan ) es el informe donde se indicen todos los datos referentes a un vuelo.es este además de informacion. Técnica añadida por el piloto del avión, debe constar el lugar de salida, destino altitud, velocidad de crucero y todos los puntos por donde pasara la aereonave.
También se suelen incluir datos referentes a la aereonave como, carga de combustible nombre del comandante hora y fecha.
El plan de vuelo puede ser visual (VFR) o instrumental (IFR).el vuelo VFR se incluirán los puntos por donde pasara la aereonave, el vuelo IFR se deberán indicar puntos de salida y aproximadamente instrumental que ya están establecidos como estándares.
También en un plan de vuelo se especifica la altitud o nivel de vuelo.el equipo de navagacion que se cuenta a bordo de la aereonave y el tipo de transportador.
FUNCION DE BUSQUEDA
En la mayoría de los casos se soluciona mediante la definición de un conjunto de funciones. Ahora veremos una técnica para crear una función de búsqueda que sirve para los siguientes casos:
- Verificar si existe el valor buscado.
- Obtener el valor si existe y si no error.
- Obtener el valor si existe y si no notificarlo.
· Por ejemplo, tenemos una lista con parejas (clave,valor) y queremos implementar la función Busca(Clave) que retorna el valor si encuentra la clave. Además queremos utilizar la misma función para los tres casos comentados anteriormente. La base para Busca es que retorna un valor si encuentra la clave y si no, no retorna ningún valor. La implementación que se realiza se basa en la posibilidad de retornar múltiples valores, que se utilizará para retornar uno o ningún valor.
· Var l=[(1,10),(2,20),(3,30)]
· Fun Busca(clave,Lista:List)=>
· Search (e<-Lista, e[0]=:=Clave) e[1] else return void
· ValueP(Busca(clave,lista)) retorna true si encuentra la clave y false si no. De esta forma se comprueba la existencia de una clave.
· Busca(clave,lista) retorna el valor de la clave si la encuentra y si no, produce un error, ya que la función Busca no retorna ningún valor. Por ejemplo, el resultado de algunas búsquedas será:
· CoSeL> busca(2,l)
· 20
· CoSeL> busca(5,l)
· Error in command line
· [MultValueReturnError]: It returns Void when a return value needed
· Call stack:
· <Reference:00B4FA2D> Fun Busca
· <Reference:0087F4F4> Fun Start
· <Reference:00B634D4> Proc System.cmpHelpCode
· La excepción generada por la búsqueda cuando no encuentra la clave es MultValueReturnError. Se puede cambiar la excepción y el mensaje generado por otros más apropiados poniendolos como parámetros de void.
· Var l=[(1,10),(2,20),(3,30)]
· Fun Busca(clave,Lista:List)=>
· {
· Search (e<-Lista, e[0]=:=Clave) e[1]
· else return void(Exception("Clave ",Clave," no encontrada"))
· }
·
· CoSeL> busca(5,l)
· Error in command line
· [NotFoundError]: Clave 5 no encontrada
· Call stack:
· <Reference:00B50C4A> Fun Busca
· <Reference:0087F474> Fun Start
· <Reference:00B6345C> Proc System.cmpHelpCode
· v?=Busca(clave,lista) retorna true si encuentra la clave y asigna a v el valor de ésta. Si no existe la clave, retorna false y no realiza ninguna asignación.
· Esta técnica de implementación tiene la ventaja de que es genérica ya que cuando no encuentra el objeto buscado no retorna nada. Si retornara un valor especial para notificar el fallo de la búsqueda, podría pasar que se confundiera con un valor encontrado y, por la tanto, no sería un método general.
ARBOLES DE DECISION
Un árbol de decisión es un modelo de predicción utilizado en el ámbito de la inteligencia artificial. Dada una base de datos se construyen diagramas de construcciones lógicas, muy similares a los sistemas de predicción basados en reglas, que sirven para representar y categorizar una serie de condiciones que ocurren de forma sucesiva, para la resolución de un problema.
Un árbol de decisión tiene unas entradas las cuales pueden ser un objeto o una situación descrita por medio de un conjunto de atributos y a partir de esto devuelve una respuesta la cual en últimas es una decisión que es tomada a partir de las entradas. Los valores que pueden tomar las entradas y las salidas pueden ser valores discretos o continuos. Se utilizan más los valores discretos por simplicidad, cuando se utilizan valores discretos en las funciones de una aplicación se denomina clasificación y cuando se utilizan los continuos se denomina regresión.
Un árbol de decisión lleva a cabo un test a medida que este se recorre hacia las hojas para alcanzar así una decisión. El árbol de decisión suele contener nodos internos, nodos de probabilidad, nodos hojas y arcos. Un nodo interno contiene un test sobre algún valor de una de las propiedades. Un nodo de probabilidad indica que debe ocurrir un evento aleatorio de acuerdo a la naturaleza del problema, este tipo de nodos es redondo, los demás son cuadrados. Un nodo hoja representa el valor que devolverá el árbol de decisión y finalmente las ramas brindan los posibles caminos que se tienen de acuerdo a la decisión tomada.
ARBOL
Un árbol se puede definir como una estructura gerargica aplicada sobre una colección de elementos o objetos llamados nodos uno de los cuales es conocido como raíz seguido además se crea una relación o parentesco entre los nodos donde lugar o términos como padre, hijo, hermano, antecesor sucesor , ancestro .
Formalmente se define un árbol de tipo T como una estructura homogenia resultado de un elemento de tipo T. un nodo se puede representar de diferentes formas y todos ellos se consideran equivalentes . en el grafo se distingue nodos círculos, arcos, líneas con flechas.
CARACTERISTICAS Y PROPIEDADES
1.-todo árbol que no es vacio tiene un único nodo raíz.
2.- un nodo X es descendiente directo de un nodo Y es este caso es común utilizar la expresión X es hijo de Y.
3.- un nodo X es antecesor de un nodo Y, si el nodo X apunta al nodo Y, en este caso es común utilizar la expresión X, es padre de Y.
4.-se dice que todos los nodos que son descendientes directos hijos de un mismo nodo padre son hermanos.
5.- todo nodo que no tiene ramificaciones hijos se conoce con el nombre de terminal o hoja.
6.- todo nodo que no es raíz ni terminal es hoja se conoce con el nombre de interior.
7.- grado es el numero de descendientes directos de un determinado nodo.
8.-grado del árbol es el máximo grado de todos los nodos del árbol.
9.- nivel es el numero de arcos que deben ser recorridos para llegar a un determinado nodo por definición la raíz tiene nivel 1.
10.- altura árbol es el máximo numero de niveles de todos los nodos del árbol.
ARBOL
Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.
También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles.
Esto son definiciones simples. Pero las características que implican no lo son tanto.
Árbol
Definiremos varios conceptos. En relación con otros nodos:
- Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'.
- Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.
Los árboles con los que trabajaremos tienen otra característica importante: cada nodo sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto hace que estos árboles estén fuertemente jerarquizados, y es lo que en realidad les da la apariencia de árboles.
En cuanto a la posición dentro del árbol:
- Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'.
- Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.
- Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.
Otra característica que normalmente tendrán nuestros árboles es que todos los nodos contengan el mismo número de punteros, es decir, usaremos la misma estructura para todos los nodos del árbol. Esto hace que la estructura sea más sencilla, y por lo tanto también los programas para trabajar con ellos.
Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir, que pueden usarse todos, algunos o ninguno de los punteros de cada nodo.
Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol completo.
En una cosa, los árboles se parecen al resto de las estructuras que hemos visto: dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente. Es decir, un nodo cualquiera puede ser considerado como la raíz de un árbol completo.
Existen otros conceptos que definen las características del árbol, en relación a su tamaño:
- Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc.
- Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos.
- Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3.
- Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.
Los árboles de orden dos son bastante especiales, de hecho les dedicaremos varios capítulos. Estos árboles se conocen también como árboles binarios.
Frecuentemente, aunque tampoco es estrictamente necesario, para hacer más fácil moverse a través del árbol, añadiremos un puntero a cada nodo que apunte al nodo padre. De este modo podremos avanzar en dirección a la raíz, y no sólo hacia las hojas.
Es importante conservar siempre el nodo raíz ya que es el nodo a partir del cual se desarrolla el árbol, si perdemos este nodo, perderemos el acceso a todo el árbol.
Arbol es el tipo para declarar árboles de orden ORDEN.
Árbol
El movimiento a través de árboles, salvo que implementemos punteros al nodo padre, será siempre partiendo del nodo raíz hacia un nodo hoja. Cada vez que lleguemos a un nuevo nodo podremos optar por cualquiera de los nodos a los que apunta para avanzar al siguiente nodo.
En general, intentaremos que exista algún significado asociado a cada uno de los punteros dentro de cada nodo, los árboles que estamos viendo son abstractos, pero las aplicaciones no tienen por qué serlo. Un ejemplo de estructura en árbol es el sistema de directorios y ficheros de un sistema operativo. Aunque en este caso se trata de árboles con nodos de dos tipos, nodos directotio y nodos fichero, podríamos considerar que los nodos hoja son ficheros y los nodos rama son directorios.
Otro ejemplo podría ser la tabla de contenido de un libro, por ejemplo de este mismo curso, dividido en capítulos, y cada uno de ellos en subcapítulos. Aunque el libro sea algo lineal, como una lista, en el que cada capítulo sigue al anterior, también es posible acceder a cualquier punto de él a través de la tabla de contenido.
También se suelen organizar en forma de árbol los organigramas de mando en empresas o en el ejército, y los árboles genealógicos.
POST ORDEN
En este caso se trata primero el subárbol izquierdo, después el derecho y por último el nodo actual. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo izquierda, nodo derecha, nodo raiz. En el árbol de la figura el recorrido en postorden sería: 2, 5, 11, 6, 7, 4, 9, 5 y 2.
void postorden(tArbol *a)
{
if (a != NULL) {
postorden(a->hIzquiedo);
postorden(a->hDerecho);
tratar(a); //Realiza una operación en nodo
}
}
PREORDEN
En este tipo de recorrido se realiza cierta acción (quizás simplemente imprimir por pantalla el valor de la clave de ese nodo) sobre el nodo actual y posteriormente se trata el subárbol izquierdo y cuando se haya concluido, el subárbol derecho. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo raiz, nodo izquierda, nodo derecha.
En el árbol de la figura el recorrido en preorden sería: 2, 7, 2, 6, 5, 11, 5, 9 y 4.
void preorden(tArbol *a)
{
if (a != NULL) {
tratar(a); //Realiza una operación en nodo
preorden(a->hIzquierdo);
preorden(a->hDerecho);
}
}
Implementación en pseudocódigo de forma iterativa:
push(s,NULL); //insertamos en una pila (stack) el valor NULL, para asegurarnos de que esté vacía
push(s,raíz); //insertamos el nodo raíz
MIENTRAS (s <> NULL) HACER
p = pop(s); //sacamos un elemento de la pila
tratar(p); //realizamos operaciones sobre el nodo p
SI (D(p) <> NULL) //preguntamos si p tiene árbol derecho
ENTONCES push(s,D(p));
FIN-SI
SI (I(p) <> NULL) //preguntamos si p tiene árbol izquierdo
ENTONCES push(s,I(p));
FIN-SI
FIN-MIENTRAS
INORDEN
En este caso se trata primero el subárbol izquierdo, después el nodo actual y por último el subárbol derecho. En un ABB este recorrido daría los valores de clave ordenados de menor a mayor. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo izquierda,nodo raiz,nodo derecha. En el árbol de la figura el recorrido en inorden sería: 2, 7, 5, 6, 11, 2, 5, 4, 9.
Esquema de implementación:
void inorden(tArbol *a)
{
if (a != NULL) {
inorden(a->hIzquierdo);
tratar(a); //Realiza una operación en nodo
inorden(a->hDerecho);
}
}
OPERACIONES BASICAS DE LOS ARBOLES BINARIOS DE BUSQUEDA
Todo árbol vacío es un árbol binario de búsqueda.
Un árbol binario no vacío, de raíz R, es un árbol binario de búsqueda si:
• En caso de tener subárbol izquierdo, la raíz R debe ser mayor que el valor máximo
almacenado en el subárbol izquierdo, y que el subárbol izquierdo sea un árbol binario
de búsqueda.
• En caso de tener subárbol derecho, la raíz R debe ser menor que el valor mínimo
almacenado en el subárbol derecho, y que el subárbol derecho sea un árbol binario
de búsqueda.
Un árbol binario de búsqueda de tamaño 9 y profundidad 3, con raíz 8 y hojas 1, 4, 7 y 13
Para una fácil comprensión queda resumido en que es un árbol binario que cumple que el subárbol izquierdo de cualquier nodo (si no está vacío) contiene valores menores que el que contiene dicho nodo, y el subárbol derecho (si no está vacío) contiene valores mayores.
Para estas definiciones se considera que hay una relación de orden establecida entre los elementos de los nodos. Que cierta relación esté definida, o no, depende de cada lenguaje de programación. De aquí se deduce que puede haber distintos árboles binarios de búsqueda para un mismo conjunto de elementos.
La altura h en el peor de los casos siempre el mismo tamaño que el número de elementos disponibles. Y en el mejor de los casos viene dada por la expresión h = ceil(log2(c + 1)), donde ceil indica redondeo por exceso.
El interés de los árboles binarios de búsqueda (ABB) radica en que su recorrido en inorden proporciona los elementos ordenados de forma ascendente y en que la búsqueda de algún elemento suele ser muy eficiente.
Dependiendo de las necesidades del usuario que trate con una estructura de este tipo se podrá permitir la igualdad estricta en alguno, en ninguno o en ambos de los subárboles que penden de la raíz. Permitir el uso de la igualdad provoca la aparición de valores dobles y hace la búsqueda más compleja.
Un árbol binario de búsqueda no deja de ser un caso particular de árbol binario, así usando la siguiente especificación de árbol binario
Operaciones
Todas las operaciones realizadas sobre árboles binarios de búsqueda están basadas en la comparación de los elementos o clave de los mismos, por lo que es necesaria una subrutina, que puede estar predefinida en el lenguaje de programación, que los compare y pueda establecer una relación de orden entre ellos, es decir, que dados dos elementos sea capaz de reconocer cual es mayor y cual menor. Se habla de clave de un elemento porque en la mayoría de los casos el contenido de los nodos será otro tipo de estructura y es necesario que la comparación se haga sobre algún campo al que se denomina clave.
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. La búsqueda de un elemento en un ABB (Árbol Binario de Búsqueda) se puede realizar de dos formas, iterativa o recursiva.
1.- obtener el resultado de dicha clase?
Class z {
Public ( int j=3) {}
}
Y la sig sentencia
Zm(1)
M se construye correctamente y toma el valor de 1.
2.-si tenemos un puntero que apunta a un arreglo que obtenemos
Char *P
Char ar [10];
Y la sig instrucción
P=ar;
P señala la premera posición del array
P es el primer elemento del array
3.- si tenemos una clase X y una función void f (x) o realiza una llamada f(u) donde U es de tipo X
Al realizar la llamada se utiliza el constructor de copia de X
4.- que propiedades tiene un vector ?
Los elementos ocupan posiciones de memoria física consecutivas el tiempo se tarda en las inserciones y borradas de elementos depende de la posición de la inserccion o borrada.
5.-que propiedades tiene una lista?
List-style-type
List-style-image
List-style-position
6.- que niveles de ocultacion existen en C ++?
Public, printe,protected
7.-cual es la representación en memoria de los arrays C++ de 3 dimensiones?
Arrays de arrays
8.- cuantos nodos tiene un árbol de N nodos?
n-1 arcos
9.- que se necesita para construir una estructura de árbol de N nodo?
Definir un tipo de nodo y era y enlazar n objetos de tipo nodo.
10.- que es un árbol binario de búsqueda?
La búsqueda en árboles binarios es un método de búsqueda simple, dinámico y eficiente considerado como uno de los fundamentales en Ciencia de la Computación. De toda la terminología sobre árboles,tan sólo recordar que la propiedad que define un árbol binario es que cada nodo tiene a lo más un hijo a la izquierda y uno a la derecha.Para construir los algoritmos consideraremos que cada nodo contiene un registro con un valor clave a través del cual efectuaremos las búsquedas.En las implementaciones que presentaremos sólo se considerará en cada nodo del árbol un valor del tipo tElemento aunque en un caso general ese tipo estará compuesto por dos:una clave indicando el campo por el cual se realiza la ordenación y una información asociada a dicha clave o visto de otra forma,una información que puede ser compuesta en la cual existe definido un orden.
Suscribirse a:
Entradas (Atom)