Asignacion Implicita

Capítulo 12

¿Cuándo ocurre una asignación implícita?

Cuando se declara un objeto y se le inicializan con los valores almacenados en otro objeto de la misma clase por medio de un método constructor.

Si se tiene la siguiente declaración de objetos de la clase Ejemplo: 

Ejemplo Objeto1(Objeto2); o Ejemplo Objeto1=Objeto2;

Se puede observar que ocurre una asignación en forma implícita del Objeto2 al Objeto1. Cuando se invoca una función libre o un método y se le envía un objeto como argumento (por valor) se genera una copia local del argumento que se recibe, se dice que el parámetro formal de la función se le asigna en forma implícita, el valor del argumento de la llamada. Cuando una función genera como salida un objeto, se genera otro pero temporal en el que se regresa el resultado de la función o método.

Constructor Copy Constructor

Un caso similar al de la asignación explicita  ocurre con los constructores de objetos que poseen atributos dinámicos. Es necesario definir un constructor especial (Copy Constructor) cuaya labor será inicializar el nuevo objeto, asignándole el contenido del objeto (de la misma clase) que recibe como parámetro.

¿Cómo funcione el Copy Constructor?

El concepto, y la forma en que trabaja, es básicamente igual a la del operador de asignación. La diferencia esta en que, al ser un método constructor, se aplica directamente sobre el objeto en creación, sin generar ninguna salida.

¿Qué implicaciones a nivel de memoria existen al utilizar una función que regresa una referencia?

Cuando se usa una referencia en el tipo de resultado de la función, el compilador no genera una réplica del objeto por regresar como resultado de la función.

Apuntador this

Cada vez que un método se ejecuta, en forma implícita existe una referencia (apuntador) al objeto sobre el que se aplica dicho método. La referencia se llama this y es un apuntador que almacena la dirección del objeto sobre el que se aplica el método. Este apuntador lo define internamente el compilador y, generalmente, se maneja en forma implícita.

class Ejemplo

{ private:

   Int atributo;

  public:

    Void Escribe() {cout << atributo; }

}:

 ¿Qué es una referencia?

Una referencia es un alias de una variable u objeto. Ya se han utilizado referencias al definir parámetros por referencia en una función. Estos parámetros, en forma conceptual, se vuelven un alias de las variables enviadas como argumento durante la ejecución de la función correspondiente.

El concepto de referencia puede ser utilizado para indicar que una función regresara como resultado una referencia a una variable u objeto. La sintaxis para indicar que la función regresara una referencia, es colocar al final del tipo de dato de la función un &.

Árbol Heap

¿Ques es un arbol heap?
basicamente, un heap es un arbol binario casi completo. Se le considera casi completo ya que se lleno en todos sus niveles,exepto, problamente, el ultimo que se va completando izquierda a derecha. la diferencia entre el arbol binario y heap es que en el segundo cada nodo tiene un valor menor o igual(o bien mayor o igual) que el valot asociado cada io de us hijos, lo que se conoce como condicio del heap.


¿Como diseñar el TDA que corresponde al arbol heap?


en el  diseño del TDA para un heap se debe considerar que los elemntos que se almacenaron deben poseer la propiedad de ordenamiento, es decir, tener una relacion de mayor que y menor que.


Elemento: los elementos de un arbol heap son nodos. cada uno contiene un datos(simple o estructura tipoinfo) unico en el arbol.
Estructura: un arbol heap posee una estructura jerarquica(a expecion del arbol vacio). cada nodo contine un elemento de un conjunto ordenado valores; los nodos forman un arbol binario completo, de tal formaque cada padre contiene un elemento de mayor prioridad que sus dos hijos(la prioridad se establece con relacion a los valores almacenado, es decir, a menor valor, mayor prioridad, o a  mayor, menor prioridad). La relacion de la prioridad se puede establecer como mayor o mayor-igual.



En un montículo de prioridad, el mayor elemento (o el menor, dependiendo de la relación de orden escogida) está siempre en el nodo raíz. Por esta razón, los montículos son útiles para implementar colas de prioridad. Una ventaja que poseen los montículos es que, por ser árboles completos, se pueden implementar usando arreglos, lo cual simplifica su codificación y libera al programador del uso de punteros.


¿Como genera un arbol heap a partir de un arreglo de elemento?

Esta operación parte de un elemento y lo inserta en un montículo aplicando su criterio de ordenación.Si suponemos que el monticulo está estructurado de forma que la raíz es mayor que sus hijos, comparamos el elemento a insertar (incluido en la primera posición libre) con su padre.Si el hijo es menor que el padre,entonces el elemento es insertado correctamente, si ocurre lo contrario sustituimos el hijo por el padre.

¿Y si la nueva raíz sigue siendo más grande que su nuevo padre?. Volvemos a hacer otra vez dicho paso hasta que el montículo quede totalmente ordenado. En la imagen adjunta vemos el ejemplo de cómo realmente se inserta un elemento en un montículo. Aplicamos la condición de que cada padre sea mayor que sus hijos, y siguiendo dicha regla el elemento a insertar es el 12. Es mayor que su padre, siguiendo el método de ordenación, sustituimos el elemento por su padre que es 9 y así quedaría el montículo ordenado.

Ahora veremos la implementación en varios lenguajes de programación del algoritmo de inserción de un elemento en un montículo.

¿Como se utilza  una estructura Heap en una cola priorizada?


Si se considera que cada uno de los elementos en un heao tiene asociada una prioridad que depende de su valor(a menor valor, mayor prioridad), entoeces el elemento de mayor prioridad siempre estará en la raíz del árbol y los elementos que le siguen en estas caracteristicas estarán cerca de el.


Cuando se desee insertar un nuevo elemento en la cola priorizada, lo mas sencillo sera agregarlo como la ultima hoja del árbol, es decir, en la primera posición es libre del ultimo nivel.

Apuntadores y Memoria Dinámica

Que es un apuntador?

Un apuntadora se define como un tipo de dato capaz de almacenar una dirección de memoria. se considera como referencia indirecta a un elemento.

Los apuntadores pueden ser un tipo de dato especial dentro del lenguaje de programación en cuyo caso, guardaran direcciones de memoria real; o bine, el programador puede simular el funcionamiento de un apuntador, por ejemplo, cuando una variable de tipo entero guarda la posición (subindice) de un dato en un arreglo.

Que es la memoria Dinámica?

Muchos lenguajes de programación permiten manejar dos tipos de almacenamiento de datos en la memoria principal: el almacenamiento estático (automático) y el almacenamiento dinámico.

La memoria estática es la que se maneja tradicionalmente. Sus principales características son:

• 
  
• Se define explicitamente al declrar una variable, ya sea global o local.
• El compilador genera automáticamente el espacio de memoeria.
• Se mantiene fija durante toda la vida de la variable (independientemente de que se utilice o no).

La memoria dinámica permite crear y destruir espacios de memoria, según indicaciones explicitas del programador durante la ejecución del programa. Sus principales características son:

• Utiliza una parte de la memoria principal denominada heap.
• Apoya el uso eficiente de la memoria durante la ejecución.
• Requiere apuntadores que almacenan direcciones de memoria real, dado que estas se asignan dinamicamente.

Representación de un estructura de Datos

Que es la representación de un estructura de datos?

Basiamente, puede entenderse como el punto de conexion entre la especificacion logica de un TDA (Tipo de Dato Abstracto) y su implementacion en un lenguaje de programacion particular. Dentro del proceso de abstraccion de datos, la representacion de un estructura corresponde al inciio del segundo nivel de abstraccion, es decir, el nivel fisico. Esta etapa construye un esquema de como se almacenaran los elementos de la estructura de datos en la memoria, de tal forma que se logre su optimo aprovechamiento.

Que tipos de representaciones existen para una estructura de datos?

Independientemente de las facilidades de implementacion que ofrezcan los lenguajes de programación, una estructura de datos (TDA) puede representarse de dos formas.

por posiciones (almacenamiento contiguo).

por ligas (almacenamiento disperso)

Como funciona la representación de una estructura de datos por posiciones?

En este tipo de representación, el lugar físico donde se almacena un elemento, determina automáticamente su posición relativa en la estructura de datos. Básicamente, se puede pensar en ella como un espacio de almacenamiento contiguo donde cada lugar sirve para almacenar un elemento, de tal forma que si un elemento esta almacenado en el lugar K, tendra la k-esima posición dentro de la estructura y, obviamente, el elemento K + 1 estará ubicado exactamente después del K y se almacenara en el lugar K + 1 del espacio de almacenamiento. esta representación en el próximo gráfico.

Como funciona la representación de una estructura de datos por ligas?

En este tipo de representación la ubicación fisica de un elemento no determina la posición relativa que tiene dentro de la estructura de datos. El almacenamiento en este tipo de representación se realiza en forma dispersa, es decir, dos elementos contiguos en la estructura de datos no necesariamente deben estar almacenados físicamente en posiciones contiguas dentro del espacio de almacenamiento, como se muestra en la siguiente figura.

Conjuntos


el conjunto es una estructura fundamental en las matemáticas  que se emplea para agrupar conjuntos. Los objetos de un conjunto se denominan elemento o miembro del conjunto. Estos elementos se toman de un conjunto universal U, que contiene todos los posibles elementos del conjunto. El numero de elementos contenidos en un conjunto S se conoce como el cardinal de S, denotado por |1|. Por ejemplo, el conjunto de números primos positivos menores que 20 puede expresarse como
                                                                                                          S={2, 3, 5, 7, 11, 13, 17 ,19}
Otra forma de representar un conjunto es utilizar notación de constructor de conjunto, tiene la forma
                                                                                                        S={x|x es un numero primo positivo<20}
Usamos esta notación, un elemento se dice que es miembro del conjunto S si tiene una de las propiedades asociadas con x. De este modo, otra forma de representar el conjunto de números primos positivos menores que es 20.


La pertenencia a conjunto se denota por a ∈ A que establece  que a es miembro del conjunto A. El cojunto espcial que no tiene elemento se le denomina conjunto vacio y se denota ∅. se dice que  es un subconjunto de B, escrito como A ⊆ B, que nos dice que cada elemento de A es elemento de B. si Ay B son conjuntos, entonces la union de ellos, se denota  A∪B, es aquellos elementos que esta A o en B, o en ambos. L interseccion de A y B, se denota por  A∩B, es el conjunto que contiene aquellos elementos  que  estan en A y en B. la diferencia A y B, denota por A~B, es el conjunto que contiene aquellos  que estan en A pero no en B, 


 si nos referimos a a una coleccion de n elementos de esta forma como una n-tuppla ordenada.Contretamente, uno n-tupla ordenadas. las 2-tuplas se conoce como pares ordenados.


El producto cartesiano de dos conjuntos A y B, denotado por A*B, es el conjunto de todos los pares ordenado (a,b) tales a∈A y b ∈B


Numeración


Las siguientes reglas básicas de numeración subyacen toda la combinatoria:


REGLA DE LA SUMA. el numero de formas de escoger único elemento de dos conjunto disjuntos viene dado por la suma por la suma de los cardinales de los conjuntos.


REGLA DEL PRODUCTO. el numero de forma de escoger un elemento de un conjunto y segundo elemento de otros conjuntos viene dado por el producto de los cardinales de los conjuntos

En combinatoria, la regla del producto es una regla de recuento básica. (véase regla de la suma). Enunciada de manera simple, es la idea de que si algo puede hacerse de a formas y otra cosa puede hacerse de b formas, entonces hay a · b formas de hacer ambas cosas. Así, elegir un elemento de {A, B, C} y otro de {X, Y} es elegir un elemento de {AX, AY, BX, BY, CX, CY}. En este ejemplo la regla dice: multiplicando 3 por 2 se obtiene 6.

Los conjuntos {A, B, C} y {X, Y} en este ejemplo son conjuntos disjuntos, pero eso no es necesario. El número de formas de elegir un miembro de {A, B, C}, y después elegir otro, o sea, elegir un par ordenado de elementos elegidos de {A, B, C}, es 3 × 3 = 9.

En la teoría de conjuntos, este principio de multiplicación se toma a veces como la definición del producto de cardinales. Así,

donde X es el producto cartesiano. Estos conjuntos no tienen por qué ser finitos, ni tampoco es necesario que haya un número finito de factores en el producto (véase número cardinal)

Un ejemplo clásico de esta regla en computación, es la ejecución de dos ciclos for anidados.

Teoría de probabilidad elemental

La teoría nos permite calcular la probabilidad de sucesos concretos si asumimos  que estos sucesos están  gobernados por un conjunto de axiomas apropiado. Primero definimos el espacio de probabilidad, que es el conjunto U cuyos elementos se denominan sucesos elementales. Especificar distribucion de probabilidad Pr() que asigne una probabilidad a cada uno de estos sucesos específicos x⊆U se denota por Pr(x). Para nuestros propósitos, la distribución de probabilidad mas importante es la distribución uniforma discreta. EN esta distribución cualquier suceso elemental x∈ U es equiprobabilidad (i.e., Pr(x)= 1/|U|)

SI algún suceso esta compuesto de sucesos elementales independientes (i.e. la probabilidad de un suceso elemental no depende de si algún otro suceso se ha producido), entonces la probabilidad del suceso viene dada por  el producto de los suceso elementales que incluye. La variable aleatoria  es una función definida sobre los sucesos de un espacio de probabilidad.


GRAFOS

Grafo

Un grafo es una pareja de conjuntos G = (V,A), donde V es el conjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de pares de la forma (u,v) tal que , tal que . Para simplificar, notaremos la arista (a,b) como ab.

En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un dibujo más claro.

Muchas redes de uso cotidiano pueden ser modeladas con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o la red de drenaje de una ciudad

Grafos simples 

Un grafo es simple si a lo sumo sólo 1 arista une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.

Un grafo que no es simple se denomina GRAFO COMPLEJO.. Un grafo simple está formado por dos conjuntos:

• Un conjunto V de puntos llamados vértices o nodos.

• Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados.

De una manera más informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, Grafos conexos [editar]

Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.

• No dirigidos: son aquellos en los cuales los lados no están orientados (No son flechas). Cada lado se representa entre paréntesis, separando sus vértices por comas, y teniendo en cuenta (Vi,Vj)=(Vj,Vi).

• Dirigidos: son aquellos en los cuales los lados están orientados (flechas). Cada lado se representa entre ángulos, separando sus vértices por comas y teniendo en cuenta <Vi ,Vj>!=<Vj ,Vi>. En grafos dirigidos, para cada lado <A,B>, A, el cual es el vértice origen, se conoce como la cola del lado y B, el cual es el vértice destino, se conoce como cabeza del lado.

Que a su vez se subdivide 

• Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular.

Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2-regular y el tercero no es regular

• Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto

Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es

• Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota .

• Un grafo bipartito regular: se denota donde m, n es el grado de cada conjunto disjunto de vértices.

• Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.

• Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.

ARBOLES

Un Árbol Binario es un conjunto de finito de Elementos, de nombre Nodos de forma que:

El Árbol Binario es Vació si no tiene ningún elemento en el.

El Árbol Binario contiene un Nodo Raíz y los dos que parten de él, llamados Nodo Izquierdo y Nodo Derecho.

Los Árboles tiene 3 Recorridos Diferentes los cuales son:

Pre-Orden

In-Orden

Post-Orden

Pre-Orden

Definición:

El Recorrido “Pre-Orden” lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en la Raíz, después viaje a través del Nodo Izquierdo y después a través del Nodo Derecho.

Detalle:

Temp toma el Valor de la Raíz y compara si el Árbol tiene algún Elemento, de otra manera Desplegara “Árbol Vació…” y terminara el método. Si el Árbol tiene elementos dentro de él, lo recorrerá y viajara a través de los Arreglos Izq y Der para determinar que valor meter en la Pila y en Temp para de esta manera imprimir el siguiente Elemento correspondiente.

Arboles de Busqueda

Capitulo 9

¿Por qué es importante el balanceo en un árbol de búsqueda?

La manera en que los elementos estén distribuidos en un árbol de búsqueda determinara su altura y, en consecuencia, la cantidad de comparaciones a realizar al buscar un elemento. Lo ideal sería que el árbol tuviera sus elementos distribuidos en forma equilibrada o balanceada, consiguiendo así la mayor eficiencia que ofrece la búsqueda binaria.

¿Cuál es el número máximo de comparaciones que se realizan en el peor caso de búsqueda en un ABB?

La cantidad máxima de comparaciones al realizar una búsqueda en un ABB está determinada por la altura del árbol.Si un BB degenera en una lista, se tiene un árbol cuya altura es igual a la cantidad de nodos en el árbol.

¿Qué es un árbol balanceado?

Se considera que un árbol esta balanceado cuando todos sus niveles, excepto el ultimo, están integrados a la máxima capacidad de nodos.

¿Qué es un árbol AVL?

Un árbol AVL es un árbol binario de búsqueda que trata de mantenerse lo más balanceado posible, conforme se realizan operaciones de inserción y eliminación. Fueron propuestos en 1962 por los matemáticos rusos Adelson-Velskii y Landis.

En estos se debe cumplir el hecho de que para cualquier nodo del árbol, la diferencia entre las alturas de sus subárboles no exceda una unidad.

Busqueda de Informacion

Capitulo 7

¿Por qué es importante la búsqueda de información?

Uno de los propósitos de la computadora es que sirva de medio para el almacenamiento de grandes volúmenes de información, lo que implica la existencia de mecanismos para accesar eficientemente a esta última.

¿Cómo realizar eficientemente una búsqueda?

Un requisito importante para que el proceso de búsqueda se realice en forma eficiente es que la información este ordenada, por lo que se plantea una representación y un método de acceso para que la información se almacene ordenadamente y se facilite la búsqueda.

Para ordenar la información es necesario realizar el ordenamiento según uno o varios de los campos que conforman cada registro de información. Este campo se llama Llave.

¿Qué opciones de representación en memoria existen para una estructura de datos para la búsqueda de información?

Si se desea utilizar una estructura temporal y limitada, para obtener accesos rápidos, se deberá pensar en la memoria principal. Si se desea utilizar una estructura permanente e ilimitada para almacenar grandes volúmenes de información, se deberá pensar en la memoria secundaria.

En memoria estática se puede utilizar un arreglo que guarde la información en forma ordenada. Esta representación se conoce con el nombre de tabla.

En memoria dinámica se puede utilizar una lista encadenada que guarde ordenadamente la información. Esta representación se llama lista ordenada.

¿Cómo se puede implementar el proceso de búsqueda en una estructura lineal?

Búsqueda secuencial: es el algoritmo más obvio y el que tiene una implantación intuitiva. Consiste en comparar a partir de del primer elemento de la estructura, secuencialmente hasta que el elemento buscado se encuentra, o un elemento mayor al buscado.

Búsqueda binaria: consiste en dividir sucesivamente la estructura en mitades, descartando del proceso de búsqueda la mitad en que no se puede encontrar el elemento que se busca. El proceso parte la estructura en mitades cada vez más pequeñas, lo que asegura que se encuentre el elemento.